TY - JOUR
T1 - A structure-driven genetic algorithm for graph coloring
AU - Aguilar-Canepa, Jose
AU - Menchaca-Mendez, Rolando
AU - Menchaca-Mendez, Ricardo
AU - García, Jesus
N1 - Publisher Copyright:
© 2021 Instituto Politecnico Nacional. All rights reserved.
PY - 2021
Y1 - 2021
N2 - Genetic algorithms are well-known numerical optimizers used for a wide array of applications. However, their performance when applied to combinatorial optimization problems is often lackluster. This paper introduces a new Genetic Algorithm (GA) for the graph coloring problem that is competitive, on standard benchmarks, with state-of-the-art heuristics. In particular, we propose a crossover operator that combines two individuals based on random cuts (A, B) of the input graph with small cut-sets. The idea is to combine individuals by merging parts that interact as little as possible so that one individual's goodness does not interfere with the other individual's goodness. Also, we use a selection operator that picks individuals based on the individuals' fitness restricted to the nodes in one of the sets in the partition rather than based on the individuals' total fitness. Finally, we embed local search within the genetic operators applied to both the individuals' sub-solutions chosen to be combined and the individual that results after applying the crossover operato.
AB - Genetic algorithms are well-known numerical optimizers used for a wide array of applications. However, their performance when applied to combinatorial optimization problems is often lackluster. This paper introduces a new Genetic Algorithm (GA) for the graph coloring problem that is competitive, on standard benchmarks, with state-of-the-art heuristics. In particular, we propose a crossover operator that combines two individuals based on random cuts (A, B) of the input graph with small cut-sets. The idea is to combine individuals by merging parts that interact as little as possible so that one individual's goodness does not interfere with the other individual's goodness. Also, we use a selection operator that picks individuals based on the individuals' fitness restricted to the nodes in one of the sets in the partition rather than based on the individuals' total fitness. Finally, we embed local search within the genetic operators applied to both the individuals' sub-solutions chosen to be combined and the individual that results after applying the crossover operato.
KW - Dynamic programming
KW - Genetic algorithms
KW - Graph coloring
UR - http://www.scopus.com/inward/record.url?scp=85118763691&partnerID=8YFLogxK
U2 - 10.13053/CyS-25-3-3901
DO - 10.13053/CyS-25-3-3901
M3 - Artículo
AN - SCOPUS:85118763691
SN - 1405-5546
VL - 25
SP - 465
EP - 481
JO - Computacion y Sistemas
JF - Computacion y Sistemas
IS - 3
ER -