Skip to main content

Advertisement

Log in

A hierarchical parallel genetic approach for the graph coloring problem

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Graph Coloring Problems (GCPs) are constraint optimization problems with various applications including time tabling and frequency allocation. The GCP consists in finding the minimum number of colors for coloring the graph vertices such that adjacent vertices have distinct colors. We propose a hierarchical approach based on Parallel Genetic Algorithms (PGAs) to solve the GCP. We call this new approach Hierarchical PGAs (HPGAs). In addition, we have developed a new operator designed to improve PGAs when solving constraint optimization problems in general and GCPs in particular. We call this new operator Genetic Modification (GM). Using the properties of variables and their relations, GM generates good individuals at each iteration and inserts them into the PGA population in the hope of reaching the optimal solution sooner. In the case of the GCP, the GM operator is based on a novel Variable Ordering Algorithm (VOA) that we propose. Together with the new crossover and the estimator of the initial solution we have developed, GM allows our solving approach to converge towards the optimal solution sooner than the well known methods for solving the GCP, even for hard instances. This was indeed clearly demonstrated by the experiments we conducted on the GCP instances taken from the well known DIMACS website.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Algorithm 5
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Algorithm 6
Algorithm 7
Algorithm 8
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

Notes

  1. http://mat.gsia.cmu.edu/COLOR03/.

References

  1. Ayvaz D, Topcuoglu HR, Gürgen FS (2012) Performance evaluation of evolutionary heuristics in dynamic environments. Appl Intell 37(1):130–144

    Article  Google Scholar 

  2. Brélaz D (1979) New methods to color the vertices of a graph. Commun ACM 22:251–256

    Article  MATH  Google Scholar 

  3. Briggs P, Cooper KD, Torczon L (1994) Improvements to graph coloring register allocation. ACM Trans Program Lang Syst 16(3):428–455

    Article  Google Scholar 

  4. Cantu-Paz E (2000) Efficient and accurate parallel genetic algorithms. Kluwer Academic, Norwell

    MATH  Google Scholar 

  5. Caramia M, Dell’Olmo P (2001) Iterative coloring extension of a maximum clique. Nav Res Logist 48(6):518–550

    Article  MathSciNet  MATH  Google Scholar 

  6. Chaitin G (2004) Register allocation and spilling via graph coloring. SIGPLAN Not 39(4):66–74

    Article  MathSciNet  Google Scholar 

  7. Costa D, Hertz A, Dubuis O (1995) Embedding of a sequential algorithm within an evolutionary algorithm for coloring problems in graphs. J Heuristics 1:105–128

    Article  MATH  Google Scholar 

  8. Coudert O (1997) Exact coloring of real-life graphs is easy. In: 34th design automation conference, pp 121–126

    Chapter  Google Scholar 

  9. Cui J, Fogarty TC, Gammack JG (1993) Searching databases using parallel genetic algorithms on a transputer computing surface. Future Gener Comput Syst 9(1):33–40

    Article  Google Scholar 

  10. Cutello V, Nicosia G, Pavone M (2003) A hybrid immune algorithm with information gain for the graph coloring problem. In: Proceedings of the 2003 international conference on genetic and evolutionary computation: Part I (GECCO’03). Springer, Berlin, pp 171–182

    Chapter  Google Scholar 

  11. da Silva FJM, Perez JMS, Pulido JAG, Rodriguez MAV (2010) AlineaGA—a genetic algorithm with local search optimization for multiple sequence alignment. Appl Intell 32:164–172

    Article  Google Scholar 

  12. Fister I, Mernik M, Filipic̆ B (2012) Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm. Comput Optim Appl. doi:10.1007/s10589-012-9496-5

    MATH  Google Scholar 

  13. Galinier P, Hao JK (1999) Hybrid evolutionary algorithms for graph coloring. J Comb Optim 3(4):379–397

    Article  MathSciNet  MATH  Google Scholar 

  14. Galinier P, Hertz A, Zufferey N (2008) An adaptive memory algorithm for the k-coloring problem. Discrete Appl Math 156(2):267–279

    Article  MathSciNet  MATH  Google Scholar 

  15. Garey MR, Johnson DS (1990) Computers and intractability; A guide to the theory of NP-completeness. Freeman, New York

    Google Scholar 

  16. Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading

    MATH  Google Scholar 

  17. Kang MH, Choi HR, Kim HS, Park BJ (2012) Development of a maritime transportation planning support system for car carriers based on genetic algorithm. Appl Intell 36(3):585–604

    Article  Google Scholar 

  18. Kirovski D, Potknojak M (1997) Exact coloring of many real-life graphs is difficult, but heuristic coloring is almost always effective. Technical report

  19. Klotz W (2002) Graph coloring algorithms. In: Mathematics Report, pp 1–9. Technical University Clausthal

  20. Leighton F (1997) A graph coloring algorithm for large scheduling algorithms. J Res Natl Bur Stand 84:489–506

    Article  MathSciNet  Google Scholar 

  21. Leighton FT (1979) A graph coloring algorithm for large scheduling problems. J Res Natl Bur Stand 84(6):489–506

    Article  MathSciNet  MATH  Google Scholar 

  22. Li J, Burke EK, Qu R (2010) A pattern recognition based intelligent search method and two assignment problem case studies. Appl Intell. doi:10.1007/s10489-010-0270-z

  23. Lim D, Ong YS, Jin Y, Sendhoff B, Lee BS (2007) Efficient hierarchical parallel genetic algorithms using grid computing. Future Gener Comput Syst 23(4):658–670

    Article  Google Scholar 

  24. Liu Z, Liu A, Wang C, Niu Z (2004) Evolving neural network using real coded genetic algorithm (ga) for multispectral image classification. Future Gener Comput Syst 20(7):1119–1129

    Article  Google Scholar 

  25. Mabrouk BB, Hasni H, Mahjoub Z (2009) On a parallel genetic-tabu search based algorithm for solving the graph colouring proble. Eur J Oper Res 197(3):1192–1201

    Article  MATH  Google Scholar 

  26. Malaguti E, Toth P (2010) A survey on vertex coloring problems. Int Trans Oper Res 17(1):1–34

    Article  MathSciNet  MATH  Google Scholar 

  27. Mansour N, Isahakian V, Ghalayini I (2011) Scatter search technique for exam timetabling. Appl Intell 34(2):299–310

    Article  Google Scholar 

  28. Marx D (2004) Graph coloring with local and global constraints. PhD thesis, Budapest University of Technology and Economics

  29. Mehrotra A, Trick MA (1995) A column generation approach for graph coloring. INFORMS J Comput 8:344–354

    Article  Google Scholar 

  30. Miguel I, Shen Q (2000) Dynamic flexible constraint satisfaction. Appl Intell 13(3):231–245

    Article  Google Scholar 

  31. Mouhoub M, Sukpan A (2012) Conditional and composite temporal CSPs. Appl Intell 36(1):90–107

    Article  Google Scholar 

  32. Riihijarvi J, Petrova M, Mahonen P (2005) Frequency allocation for wlans using graph colouring techniques. In: Proceedings of the second annual conference on wireless on-demand network systems and services. IEEE Comput Soc, Los Alamitos, pp 216–222

    Chapter  Google Scholar 

  33. Sabar NR, Ayob M, Qu R, Kendall G (2011)A graph coloring constructive hyper-heuristic for examination timetabling problems. Appl Intell. doi:10.1007/s10489-011-0309-9

  34. Sena GA, Megherbi D, Isern G (2001) Implementation of a parallel genetic algorithm on a cluster of workstations: traveling salesman problem, a case study. Future Gener Comput Syst 17(4):477–488

    Article  MATH  Google Scholar 

  35. Shi K, Li L (2012) High performance genetic algorithm based text clustering using parts of speech and outlier elimination. Appl Intell. doi:10.1007/s10489-012-0382-8

    Google Scholar 

  36. Svenson P, Nordahl MG (1999) Relaxation in graph coloring and satisfiability problems. Phys Rev E 59(4):3983–3999

    Article  Google Scholar 

  37. Welsh D, Powell M (1967) An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput J 10:85

    Article  MATH  Google Scholar 

  38. Xing H, Qu R (2012) A compact genetic algorithm for the network coding based resource minimization problem. Appl Intell 36:809–823

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Malek Mouhoub.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Abbasian, R., Mouhoub, M. A hierarchical parallel genetic approach for the graph coloring problem. Appl Intell 39, 510–528 (2013). https://doi.org/10.1007/s10489-013-0429-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-013-0429-5

Keywords

Navigation