查看文章

One of the approaches to combinatorial optimization is to use global search methods, such as evolutionary algorithms combined with local search procedures. Local search can be very effective in improving the quality of solutions, however, searching large neighbourhoods can be computationally expensive. In this paper a new local search method is described that is dedicated to the Firefighter Problem (FFP). The Firefighter Problem concerns protecting nodes of a graph in order to stop a threat that is spreading in the graph. Because the resources used for protection are limited, the goal is to find the best order in which the nodes are protected and thus the FFP is a combinatorial optimization problem. One of the key elements in the design of a local search method is the definition of the neighbourhoods of solutions from which the local search starts. The method proposed in this paper (ED-LS) aims at lowering the …