Skip to main content
SpringerLink
Log in

Genetic and hybrid algorithms for graph coloring

  • Genetic Algorithms
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Battiti and G. Tecchiolli, Parallel biased search for combinatorial optimization: Genetic algorithms and tabu, Microproc. Microsyst. 16(1992)351–367.

    Article  Google Scholar 

  2. R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA J. Comp. 6(1994)126–140.

    Google Scholar 

  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.

    Google Scholar 

  4. D. Brelaz, New methods to color vertices of a graph, Commun. ACM 22(1979)251–256.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  7. L. Davis,Handbook of Genetic Algorithms (Van Nostrand Reinhold, New York, 1991).

    Google Scholar 

  8. F. Dammeyer and S. Voss, Dynamic tabu list management using the reverse elimination method, Ann. Oper. Res. 41(1993)31–46.

    Article  Google Scholar 

  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.

    Google Scholar 

  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

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  14. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

    Google Scholar 

  15. F. Glover, Heuristics for integer programming using surrogate constraints, Dec. Sci. 8(1977)156–166.

    Google Scholar 

  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.

    Article  Google Scholar 

  18. F. Glover, Tabu search for nonlinear and parametric optimization (with links to genetic algorithms), to appear in Discr. Appl. Math.

  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.

    Google Scholar 

  20. D.E. Goldberg,Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, 1989).

  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.

    Google Scholar 

  23. J.H. Holland,Adaptation in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, 1975).

    Google Scholar 

  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.

    Google Scholar 

  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).

    Google Scholar 

  26. P. L'Écuyer, Efficient and portable combined random number generators, Commun. ACM 31(1988)742–774.

    Article  Google Scholar 

  27. F. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bureau of Standards 84(1979)489–505.

    Google Scholar 

  28. S. Lin, Computer solutions of the traveling salesman problem, Bell. Syst. Tech. J. 44(1965)2245–2269.

    Google Scholar 

  29. S. Lin and B.W. Kernighan, An effective heuristic for the traveling salesman problem, Oper. Res. 21(1973)498–516.

    Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  36. E. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Comp. 17(1991)443–455.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  40. D. Welsh,Codes and Cryptography (Oxford University Press, New York, 1988).

    Google Scholar 

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  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

    Charles Fleurent & Jacques A. Ferland

Authors
  1. Charles Fleurent
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jacques A. Ferland
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fleurent, C., Ferland, J.A. Genetic and hybrid algorithms for graph coloring. Ann Oper Res 63, 437–461 (1996). https://doi.org/10.1007/BF02125407

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02125407

Keywords

Search

Navigation