Simulation-based crossover for the firefighter problem

Krzysztof Michalak

Abstract

The 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
Author Krzysztof Michalak (MISaF / IBI / DIT)
Krzysztof Michalak,,
- Department of Information Technologies
Pages601-608
Publication size in sheets0.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
URL 10.1145/3071178.3071335
Languageen angielski
Score (nominal)20
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back