A Structure-Driven Genetic Algorithm for Graph Coloring

Authors

  • José Carlos Aguilar-Canepa Centro de Investigación en Computación
  • Rolando Menchaca-Mendez Centro de Investigación en Computación
  • Ricardo Menchaca-Mendez Centro de Investigación en Computación
  • Jesus García Instituto Nacional de Astrofísica, Óptica y Electrónica, Coordinación de Ciencias Computacionales

DOI:

https://doi.org/10.13053/cys-25-3-3901

Keywords:

Genetic algorithms, dynamic programming, graph coloring

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 operator.

Author Biography

José Carlos Aguilar-Canepa, Centro de Investigación en Computación

Ph. D. student at Network and Data Science Lab

Downloads

Published

2021-08-18

Issue

Vol. 25 No. 3 (2021): 25(3) 2021

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.