Crossover Meta-Operator Based on Operator Sequences for the Firefighter Problem

The Firefighter Problem is a graph-based optimization problem in which a threat called ‘fire’ has to be prevented from spreading on a graph by protecting graph vertices. Solutions to this problem are permutations, which are used to determine the order in which vertices of the graph are to be protected. In this paper, a crossover meta-operator Seq-X is proposed which works by applying various crossover operators available for the permutation-based representation. The quality of solutions generated by sequences of different crossover operators is analyzed during a preliminary run of the optimization algorithm on small problem instances and this information is used by Seq-X to decide which operator to select when the crossover operation has to be performed. The experiments described in this paper show that information collected when optimizing solutions for problem instances based on graphs with 1000 vertices can effectively be used for graphs with up to 10000 vertices.