A structure-driven genetic algorithm for graph coloring

Jose Aguilar-Canepa, Rolando Menchaca-Mendez, Ricardo Menchaca-Mendez, Jesus García

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)465-481
Número de páginas17
PublicaciónComputacion y Sistemas
Volumen25
N.º3
DOI
EstadoPublicada - 2021

Huella

Profundice en los temas de investigación de 'A structure-driven genetic algorithm for graph coloring'. En conjunto forman una huella única.

Citar esto