Crossover Operator using Knowledge Transfer for the Firefighter Problem

Krzysztof Michalak

Abstract

This paper concerns the Firefighter Problem (FFP) which is a graph-based problem in which solutions can be represented as permutations. A new crossover operator is proposed that uses a machine learning model to decide how to combine two parent solutions of the FFP into an offspring. The operator works on two parent permutations andthe machine learning model provides information which parent to select the next permutation element from, when constructing a new solution. Training data is collected during a training run in which transpositions are applied to solutions found by an evolutionary algorithm for a small problem instance. The machine learning model is trained to classify pairs of graph vertices into two classes corresponding to which vertex should be placed earlier in the permutation. In the experiments the machine learning model was trained on a set of FFP instances with 1000 vertices. Subsequently, the proposed operator was used for solving FFP instances with up to 10000 vertices. The experiments, in which the proposed operator was compared against a set of other crossover operators, shown that the proposed operator is able to effectively use knowledge gathered when solving smaller instances for solving larger instances of the same problem
Author Krzysztof Michalak (MISaF / IBI / DIT)
Krzysztof Michalak,,
- Department of Information Technologies
Pages305-316
Publication size in sheets0.55
Book Yin Hujun, Camacho David, Novais Paulo, Tallon-Ballesteros Antonio J. (eds.): Intelligent Data Engineering and Automated Learning – IDEAL 2018. 19th International Conference , Lecture Notes in Computer Science, vol. 11314, 2018, Springer International Publishing, ISBN 9783030034924, [9783030034931 ], 865 p., DOI:10.1007/978-3-030-03493-1
Keywords in EnglishKnowledge-based optimization, Graph problems, REDS graphs
DOIDOI:10.1007/978-3-030-03493-1_33
Languageen angielski
File
Michalak_Crossover_Operator_ Using_ Knowledge_Transfer 2018.pdf 1,56 MB
Score (nominal)20
Score sourceconferenceList
Publication indicators Scopus Citations = 0
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