Simulation-based crossover for the firefighter problem
AbstractThe Firefighter Problem (FFP) is a combinatorial optimization problem in which the goal is to find the best way of protecting nodes in a graph from spreading fire or other threat given limited resources. Because of high computational complexity the FFP is often solved using metaheuristic methods such as evolutionary algorithms (EAs). The problem that arises is that many crossover operators used in EAs were developed with problems such as the TSP or the flowshop problem in mind and are therefore not optimized towards the FFP. In this paper a new crossover operator SimX is proposed that determines how to combine information from parent specimens using a simulation of fire spreading and some problem-specific heuristics. The proposed crossover operator was compared to a set often permutation-based crossover operators in experiments performed using a multipopulation algorithm with operator autoadaptation. In the experiments it was observed that the proposed simulation-based crossover operator produced good offspring more often than the other operators
|Publication size in sheets||0.5|
|Book||Bosman Peter (eds.): Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'17 Companion), 2017, Association for Computing Machinery, ISBN 978-1-4503-4920-8, 1422 p., DOI:10.1145/3067695.3084380|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.