ED-LS – A heuristic local search for the multiobjective Firefighter Problem

Krzysztof Michalak

Abstract

One of the approaches to combinatorial optimization is to use global search methods, such as evolutionary algorithms combined with local search procedures. Local search can be very effective in improving the quality of solutions, however, searching large neighbourhoods can be computationally expensive. In this paper a new local search method is described that is dedicated to the Firefighter Problem (FFP). The Firefighter Problem concerns protecting nodes of a graph in order to stop a threat that is spreading in the graph. Because the resources used for protection are limited, the goal is to find the best order in which the nodes are protected and thus the FFP is a combinatorial optimization problem. One of the key elements in the design of a local search method is the definition of the neighbourhoods of solutions from which the local search starts. The method proposed in this paper (ED-LS) aims at lowering the computational cost of the local search by reducing, based on certain heuristics, the size of these neighbourhoods. In this paper the ED-LS is compared to an optimization without the local search, a local search using non-reduced neighbourhoods and a method that reduces the neighbourhood by checking only some randomly selected neighbours. The results show that the ED-LS improves the performance of the algorithm with respect to no local search at all and to the local search using non-reduced neighbourhoods, supporting the view that reducing the size of the neighbourhood is beneficial. Also, the ED-LS produces better results than when the size of the neighbourhood is reduced randomly, which means that the proposed heuristics are indeed selecting promising neighbours effectively. In the last part of the experiments the ED-LS is further improved to obtain faster improvement of solutions at the beginning of the optimization run
Author Krzysztof Michalak (MISaF / IBI / DIT)
Krzysztof Michalak,,
- Department of Information Technologies
Journal seriesApplied Soft Computing, ISSN 1568-4946, (A 40 pkt)
Issue year2017
Vol59
Pages389-404
Publication size in sheets0.75
Keywords in Englishgraph-based optimization; multiobjective optimization; combinatorial problems
ASJC Classification1712 Software
DOIDOI:10.1016/j.asoc.2017.05.049
URL http://dx.doi.org/10.1016/j.asoc.2017.05.049
Languageen angielski
File
Michalak_ED-LS_ A_ heuristic_ local2017.pdf 1,66 MB
Score (nominal)40
ScoreMinisterial score = 40.0, 20-08-2019, ArticleFromJournal
Publication indicators Scopus Citations = 4; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 2.037; WoS Impact Factor: 2017 = 3.907 (2) - 2017=4.004 (5)
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