Abstract
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 PspPsp (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 results are compared to various heuristics that determine how to place firefighters. Given the time-constrained nature of the problem we also investigate for how long to simulate the spread of fire when evaluating solutions produced by an evolutionary algorithm. Results generally indicate that the evolutionary algorithm proposed is effective for Psp≥0.7Psp≥0.7, whereas for lower probabilities the heuristics are competitive suggesting that more work on hybrids is warranted.
In this paper a nondeterministic version of the FFP is introduced where fire spreads to unprotected nodes with a probability PspPsp (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 results are compared to various heuristics that determine how to place firefighters. Given the time-constrained nature of the problem we also investigate for how long to simulate the spread of fire when evaluating solutions produced by an evolutionary algorithm. Results generally indicate that the evolutionary algorithm proposed is effective for Psp≥0.7Psp≥0.7, whereas for lower probabilities the heuristics are competitive suggesting that more work on hybrids is warranted.
Original language | English |
---|---|
Title of host publication | Applications of Evolutionary Computation |
Subtitle of host publication | 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 - April 1, 2016, Proceedings, Part II |
Editors | Giovanni Squillero, Paolo Burelli |
Publisher | Springer |
Pages | 248-265 |
Volume | LNCS 9598 |
ISBN (Electronic) | 9783319311531 |
ISBN (Print) | 9783319311524 |
DOIs | |
Publication status | Published - 2 Apr 2016 |
Event | Evolutionary Algorithms and Meta-heuristics in Stochastic and Dynamic Environments (EVOSTOC 2016) - Porto, Portugal Duration: 30 Mar 2016 → 1 Apr 2016 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 9598 |
ISSN (Electronic) | 0302-9743 |
Conference
Conference | Evolutionary Algorithms and Meta-heuristics in Stochastic and Dynamic Environments (EVOSTOC 2016) |
---|---|
Country/Territory | Portugal |
City | Porto |
Period | 30/03/16 → 1/04/16 |