| Revista: | 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, Ciudad de México. México 2Instituto Nacional de Astrofísica Óptica y Electrónica, Coordinación de Ciencias Computacionales, Tonantzintla, Puebla. México |
| Año: | 2021 |
| Periodo: | Jul-Sep |
| Volumen: | 25 |
| Número: | 3 |
| Paginación: | 465-481 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| 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. |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Inteligencia artificial |
| Keyword: | Genetic algorithms, Dynamic programming, Graph coloring, Artificial intelligence |
| Texto completo: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
