Solving the parameterless firefighter problem using multiobjective evolutionary algorithms
Krzysztof Michalak · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2019
The Firefighter Problem (FFP) is a graph-based optimization problem that is an abstraction of real-life problems such as epidemics control, economic crises prevention, etc. In the FFP spreading of fire is simulated on a graph in discrete time steps. In the original formulation of the problem a fixed number of graph nodes Nf can be defended in each time step. In this paper the problem is reformulated, and three different solution representations are studied. In one of the representations (N+P), the Nf parameter is a decision variable and in the other two (P using permutations and T using integer vectors) it is determined when the solution is decoded. Because higher Nf values mean more resources used for defense it is desirable to minimize this value, but on the other hand we want to minimize the number of graph nodes consumed by fire. Therefore the Parameterless FFP is tackled using two well-known multiobjective evolutionary algorithms: the MOEA/D and the NSGA-II as a multiobjective optimization problem with two and three objectives. The results presented in the paper show that for the Parameterless FFP the best solution representation is N+P.