Genetic and hybrid algorithms for graph coloring |
| |
Authors: | Charles Fleurent Jacques A Ferland |
| |
Institution: | (1) Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, 2900 Édouard-Montpetit, C.P. 6128 Succ. A, H3C 3J7 Montréal, Québec, Canada |
| |
Abstract: | Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|