Hybrid Evolutionary Algorithms for Graph Coloring
Tóm tắt
A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement.
Tài liệu tham khảo
D. Br´elaz, "New methods to color vertices of a graph," Communications of ACM, vol. 22, pp. 251–256, 1979.
G.J. Chaitin, "Register Allocation and Spilling via Graph Coloring," in Proc. of ACM SIGPLAN 82 Symposium on Compiler Construction, New York, 1982, pp. 98–105.
M. Chams, A. Hertz, and D. de Werra, "Some experiments with simulated annealing for coloring graphs," European Journal of Operational Research, vol. 32, pp. 260–266, 1987.
D. Costa, A. Hertz, and O. Dubuis, "Embedding of a sequential procedure within an evolutionary algorithm for coloring problems in graphs," Journal of Heuristics, vol. 1, no. 1, pp. 105–128, 1995.
L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold: New York, 1991.
R. Dorne and J.K. Hao, "Tabu search for graph coloring, T-coloring and set T-colorings," in Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I.H. Osman and C. Roucairol (Eds.), Kluwer Academic Publishers, 1999, Chapter 6, pp. 77–92.
R. Dorne and J.K. Hao, "A new genetic local search algorithm for graph coloring," Lecture Notes in Computer Science 1498, Springer-Verlag, 1998, pp. 745–754.
E. Falkenauer, "A hybrid grouping genetic algorithm for bin packing," Journal of Heuristics, vol. 2, no. 1, pp. 5–30, 1996.
C. Fleurent and J.A. Ferland, "Object-Oriented Implementation of Heuristic Search Methods for Graph Coloring, Maximum Clique, and Satisfiability," in Proceedings of the 2nd DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, D.S. Johnson and M.A. Trick (Eds.), American Mathematical Society, vol. 26, 1996, pp. 619–652.
B. Freisleben and P. Merz, "New genetic local search operators for the travelling salesman problem," Lecture Notes in Computer Science 1141, Springer-Verlag, 1996, pp. 890–899.
A. Gamst, "Some lower bounds for a class of frequency assignment problems," IEEE Transactions on Vehicular Technology, vol. 35, no. 1, pp. 8–14, 1986.
M.R. Garey and D.S. Johnson, Computer and Intractability, Freeman: San Francisco, 1979.
F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.
D.E. Goldberg, Genetic Algorithms in Search; Optimization and Machine Learning, Addison-Wesley, 1989.
J.J. Greffenstette, "Incorporating problem specific knowledge into a genetic algorithm," in Genetic Algorithms and Simulated Annealing, L. Davis (Ed.), Morgan Kauffmann Publishers, 1987, pp. 42–60.
A. Hertz and D. de Werra, "Using tabu search techniques for graph coloring," Computing, vol. 39, pp. 345–351, 1987.
J.H. Holland, Adaptation and Artificial Systems, University of Michigan Press: Ann Arbor, 1975.
D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon, "Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning," Operations Research, vol. 39, no. 3, pp. 378–406, 1991.
D.S. Johnson and M.A. Trick (Eds.), in Proceedings of the 2nd DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, American Mathematical Society, 1996.
F.T. Leighton, "A graph coloring algorithm for large scheduling problems," Journal of Research of the National Bureau Standard, vol. 84, pp. 489–505, 1979.
P. Merz and B. Freisleben, "A Genetic Local Search Approach to the Quadratic Assignment Problem," in Proc. of the 7th International Conference of Genetic Algorithms, Morgan Kauffman Publishers, 1997, pp. 465–472.
C. Morgenstern, "Distributed Coloration Neighborhood Search," in Proceedings of the 2nd DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, D.S. Johnson and M.A. Trick (Eds.), American Mathematical Society, vol. 26, 1996, pp. 335–358.
H. M¨uehlenbein, M. Gorges-Schleuter, and O. Kr¨amer, "Evolution algorithms in combinatorial optimization," Parallel Computing, vol. 7, pp. 65–88, 1988.
P.M. Pardalos, T. Mavridou, and J. Xue, "The graph coloring problem: A bibliographic survey," in Handbook of Combinatorial Optimization, D.-Z. Du and P. Pardalos (Eds.), Kluwer Academic Publishers, vol. 2, 1998, pp. 331–395.