| Revue: | Computación y sistemas |
| Base de datos: | |
| Número de sistema: | 000560610 |
| ISSN: | 1405-5546 |
| Autores: | Aguilar Canepa, José1 Menchaca Méndez, Rolando1 Menchaca Méndez, Ricardo1 García, Jesús2 |
| Instituciones: | 1Instituto Politécnico Nacional, Centro de Investigación en Computación, México 2Consejo Nacional de Ciencia y Tecnología, México 3Instituto Nacional de Astrofísica Óptica y Electrónica, Coordinación de Ciencias Computacionales, México |
| Año: | 2021 |
| Periodo: | Jul-Sep |
| Volumen: | 25 |
| Número: | 3 |
| Paginación: | 465-481 |
| País: | México |
| Idioma: | Inglés |
| Resumen en inglés | 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. |
| Keyword: | Genetic algorithms, Dynamic programming, Graph coloring |
| Texte intégral: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
