Genetic and hybrid algorithms for graph coloring. (English) Zbl 0851.90095

Fleurent, Charles; Ferland, Jacques A.

Ann. Oper. Res. 63, 437-461 (1996).

Summary: 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.

MSC:

90C27	Combinatorial optimization
90C35	Programming involving graphs or networks
68T05	Learning and adaptive systems in artificial intelligence

Keywords:

genetic algorithms; graph coloring

Software:

Tabu search

References:

[1]	R. Battiti and G. Tecchiolli, Parallel biased search for combinatorial optimization: Genetic algorithms and tabu, Microproc. Microsyst. 16(1992)351–367.
[2]	R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA J. Comp. 6(1994)126–140. · Zbl 0807.90094
[3]	T. Starkweather, S. McDaniel, K. Mathias, D. Whitley and C. Whitley, A comparison of genetic sequencing operators,Proc. 4th Int. Conf. on Genetic Algorithms, ed. R.K. Belew and L.B. Booker (Morgan Kaufmann, San Mateo, CA, 1991) pp. 69–76.
[4]	D. Brelaz, New methods to color vertices of a graph, Commun. ACM 22(1979)251–256. · Zbl 0394.05022
[5]	B. Carter and K. Park, How good are genetic algorithms at finding large cliques: An experimental study, Technical Report BU-CS-93-015, Boston University (1994).
[6]	M. Chams, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs, Euro. J. Oper. Res. 32(1987)260–266. · Zbl 0626.90067
[7]	L. Davis,Handbook of Genetic Algorithms (Van Nostrand Reinhold, New York, 1991).
[8]	F. Dammeyer and S. Voss, Dynamic tabu list management using the reverse elimination method, Ann. Oper. Res. 41(1993)31–46. · Zbl 0775.90290
[9]	DIMACS, Discrete Mathematics and Theoretical Computer Science anonymous ftp site at dimacs.rutgers.edu.
[10]	L.J. Eshelman, The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 265–283.
[11]	C. Fleurent and J.A. Ferland, Genetic hybrids for the quadratic assignment problem, DIMACS Series, Discr. Math. Theor. Comp. Sci. 16(1994)173–187 · Zbl 0817.90056
[12]	B.R. Fox and M.B. McMahon, Genetic operators for sequencing problems, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 284–300.
[13]	C, Friden, A. Hertz and D. de Werra, STABULUS: A technique for finding stable sets in large graphs with tabu search, Computing 42(1989)35–44. · Zbl 0685.68056
[14]	M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[15]	F. Glover, Heuristics for integer programming using surrogate constraints, Dec. Sci. 8(1977)156–166.
[16]	F. Glover, Genetic algorithms and scatter search: Unsuspected potentials, Technical Report, University of Colorado at Boulder (1993).
[17]	F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 13(1986)533–549. · Zbl 0615.90083
[18]	F. Glover, Tabu search for nonlinear and parametric optimization (with links to genetic algorithms), to appear in Discr. Appl. Math. · Zbl 0799.90109
[19]	F. Glover and M. Laguna, Tabu search, in:Modern Heuristic Techniques for Combinatorial Problems, ed. C.R. Reeves (Blackwell Scientific, Oxford, 1993) pp. 70–141.
[20]	D.E. Goldberg,Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, 1989). · Zbl 0721.68056
[21]	J.J. Grefenstette, Incorporating problem specific knowledge into genetic algorithms, in:Genetic Algorithms and Simulated Annealing (Morgan Kaufmann, 1987) pp. 42–60.
[22]	A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 39(1987)345–351. · Zbl 0626.68051
[23]	J.H. Holland,Adaptation in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, 1975). · Zbl 0317.68006
[24]	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, Oper. Res. 39(1991)378–406. · Zbl 0739.90055
[25]	A. Johri and D.W. Matula, Probabilistic bounds and heuristic algorithms for coloring large random graphs, Technical Report, Southern Methodist University, Dallas, TX (1982).
[26]	P. L’Écuyer, Efficient and portable combined random number generators, Commun. ACM 31(1988)742–774.
[27]	F. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bureau of Standards 84(1979)489–505. · Zbl 0437.68021
[28]	S. Lin, Computer solutions of the traveling salesman problem, Bell. Syst. Tech. J. 44(1965)2245–2269. · Zbl 0136.14705
[29]	S. Lin and B.W. Kernighan, An effective heuristic for the traveling salesman problem, Oper. Res. 21(1973)498–516. · Zbl 0256.90038
[30]	C. Morgenstern, Distributed coloration neighborhood search, presented at the15th Int. Symp. on Mathematical Programming, Ann Arbor (1994).
[31]	H. Muhlenbein, M. Gorges-Schleuter and O. Kramer, Evolution algorithms in combinatorial optimization, Parallel Comp. 7(1988)65–88. · Zbl 0646.65054
[32]	H. Muhlenbein, Evolution in time and space – the parallel genetic algorithm, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 316–335.
[33]	J.D. Schaffer, L.J. Eshelman and D. Offutt, Spurious correlations and premature convergence in genetic algorithms, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 102–112.
[34]	G. Syswerda, Uniform crossover in genetic algorithms,Proc. 3rd Int. Conf. on Genetic Algorithms (Morgan Kaufmann, 1989) pp. 2–9.
[35]	G. Syswerda, A study of reproduction in generational and steady-state genetic algorithms, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 94–101.
[36]	E. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Comp. 17(1991)443–455.
[37]	E. Taillard, Recherches itératives dirigées parallèles, Ph.D. Thesis, École Polytechnique Fédérale de Lausanne (1993).
[38]	E. Taillard, Comparison of iteratives searches for the quadratic assignment problem, Technical Report ORWP94/04, DMA, École Polytechnique Fédérale de Lausanne (1994).
[39]	D.E. Tate and A.E. Smith, A genetic approach to the quadratic assignment problem, Comp. Oper. Res. 22(1995)73–83. · Zbl 0812.90099
[40]	D. Welsh,Codes and Cryptography (Oxford University Press, New York, 1988). · Zbl 0678.94003
[41]	D. Whitley, T. Starkweather and D. Shaner, The traveling salesman and sequence scheduling: Quality solutions using genetic edge recombination, in:Handbook of Genetic Algorithms (Van Nostrand Reinhold, New York, 1991) pp. 350–372.