查看文章

The firefighter problem (FFP) is a combinatorial problem requiring the allocation of ‘firefighters’ to nodes in a graph in order to protect the nodes from fire (or other threat) spreading along the edges. In the original formulation the problem is deterministic: fire spreads from burning nodes to adjacent, unprotected nodes with certainty.

In this paper a nondeterministic version of the FFP is introduced where fire spreads to unprotected nodes with a probability (lower than 1) per time step. To account for the stochastic nature of the problem the simheuristic approach is used in which a metaheuristic algorithm uses simulation to evaluate candidate solutions. Also, it is assumed that the optimization has to be performed in a limited amount of time available for computations in each time step.

In this paper online and offline optimization using a multipopulation evolutionary algorithm is performed and the …