Genetic Algorithm for Graph Coloring: Exploration of Galinier and Hao's Algorithm |
| |
| Authors: | Celia A. Glass Adam Prügel-Bennett |
| |
| Affiliation: | (1) Faculty of Actuarial Science and Statistics, Cass Business School, London, EC1Y 8TZ, UK;(2) Department of Electronics and Computer Science, University of Southampton, Southampton, SO17 1BJ, UK |
| |
| Abstract: | This paper examines the best current algorithm for solving the Chromatic Number Problem, due to Galinier and Hao (Journal of Combinatorial Optimization, vol. 3, no. 4, pp. 379–397, 1999). The algorithm combines a Genetic Algorithm with Tabu Search. We show that the algorithm remains powerful even if the Tabu Search component is eliminated, and explore the reasons for its success where other Genetic Algorithms have failed. In addition we propose a generalized algorithm for the Frequency Assignment Problem. |
| |
| Keywords: | graph theory: chromatic number problem frequency assignment problem heuristics: local search genetic algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
