A structure-driven genetic algorithm for graph coloring

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

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)465-481
Number of pages17
JournalComputacion y Sistemas
Volume25
Issue number3
DOIs
StatePublished - 2021

Keywords

  • Dynamic programming
  • Genetic algorithms
  • Graph coloring

Fingerprint

Dive into the research topics of 'A structure-driven genetic algorithm for graph coloring'. Together they form a unique fingerprint.

Cite this