BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks

Sadati Tileboni S A, Jazayeriy H, Valinataj M. Genetic Algorithm with Intelligence Chaotic Algorithm and Heuristic Multi-Point Crossover for Graph Coloring Problem. JSDP. 2017; 14 (2) :75-96

URL: http://jsdp.rcisp.ac.ir/article-1-392-en.html

URL: http://jsdp.rcisp.ac.ir/article-1-392-en.html

**Graph coloring is a way of coloring the vertices of a graph such that no two adjacent ****vertices**** have the same color. Graph coloring problem (GCP) is about finding the smallest number of colors needed to color a given graph. The smallest number of colors needed to color a graph G, is called its chromatic number. GCP is a well-known NP-hard problems and, therefore, heuristic algorithms are usually used to solve it. GCP has many applications such as: bandwidth allocation, register allocation, VLSI design, scheduling, Sudoku, map coloring and so on. **

**We try genetic algorithm (GA) and chaos theory to solve GCP. We proposed a heuristic algorithm called CMHn to implement multi-point crossover operation in GA. To generate initial population, a fast greedy algorithm is used. In this algorithm, the degree of each node and the number colors in its neighbor is used to assign a color to each node. Mutation operation in GA is used to explore the search space and scape from the local optima. In this study, a chaotic mutation operation is presented to select some vertices and change their color. The crossover and mutation parameters in the proposed algorithm is tuned based on some experiment.**

**To evaluate the proposed algorithm, some experiment is conducted on DIMACS**** data set. Among DIMACS sample graphs, DSJ, Queen, Le450, Wap are well-known challenging samples for graph coloring. The proposed algorithm is executed 10 times on each sample and the best, worst and mean results are reported.**

Type of Study: Research |
Subject:
Paper

Received: 2015/07/7 | Accepted: 2017/03/5 | Published: 2017/10/21 | ePublished: 2017/10/21

Received: 2015/07/7 | Accepted: 2017/03/5 | Published: 2017/10/21 | ePublished: 2017/10/21

1. [1] R. M. Karp, "Reducibility among combinat-orial problems," in Complexity of computer computations, ed: Springer, 1972, pp. 85-103.

2. [2] F. T. Leighton, "A graph coloring algorithm for large scheduling problems," Journal of research of the national bureau of standar-ds, vol. 84, pp. 489-506, 1979. [DOI:10.6028/jres.084.024]

3. [3] N. R. Sabar, M. Ayob, R. Qu, and G. Kenda-ll, "A graph coloring constructive hyper-heuristic for examination timetabling problems," Applied Intelligence, vol. 37, pp. 1-11, 2012. [DOI:10.1007/s10489-011-0309-9]

4. [4] J. Riihijarvi, M. Petrova, and P. Mahonen, "Frequency allocation for WLANs using graph colouring techniques," in Wireless On-demand Network Systems and Services, 2005. WONS 2005. Second Annual Confere-nce on, 2005, pp. 216-222.

5. [5] G. Chaitin, "Register allocation and spilling via graph coloring," Acm Sigplan Notices, vol. 39, pp. 66-74, 2004. [DOI:10.1145/989393.989403]

6. [6] D. Brélaz, "New methods to color the vertic-es of a graph," Communications of the ACM, vol. 22, pp. 251-256, 1979. [DOI:10.1145/359094.359101]

7. [7] J. C. Culberson and F. Luo, "Exploring the k-colorable landscape with iterated greedy," Cliques, coloring, and satisfiability: second DIMACS implementation challenge, vol. 26, pp. 245-284, 1996.

8. [8] C. Avanthay, A. Hertz, and N. Zufferey, "A variable neighborhood search for graph coloring," European Journal of Operational Research, vol. 151, pp. 379-388, 2003. [DOI:10.1016/S0377-2217(02)00832-9]

9. [9] D. C. Porumbel, J.-K. Hao, and P. Kuntz, "A search space "cartography" for guiding graph coloring heuristics," Computers & Operations Research, vol. 37, pp. 769-778, 2010. [DOI:10.1016/j.cor.2009.06.024]

10. [10] M. Chams, A. Hertz, and D. De Werra, "Some experiments with simulated anneal-ing for coloring graphs," European Journal of Operational Research, vol. 32, pp. 260-266, 1987. [DOI:10.1016/S0377-2217(87)80148-0]

11. [11] 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, pp. 378-406, 1991. [DOI:10.1287/opre.39.3.378]

12. [12] Y. Wang, C. Zhang, and Z. Liu, "A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems," Automatica, vol. 48, pp. 1227-1236, 2012. [DOI:10.1016/j.automatica.2012.03.024]

13. [13] P. Galinier, A. Hertz, and N. Zufferey, "An adaptive memory algorithm for the k-color-ing problem," Discrete Applied Mathema-tics, vol. 156, pp. 267-279, 2008. [DOI:10.1016/j.dam.2006.07.017]

14. [14] J.-P. Hamiez and J.-K. Hao, "Scatter search for graph coloring," in Internation-al Conference on Artificial Evolution (Evolu-tion Artificielle), 2001, pp. 168-179.

15. [15] E. Malaguti, M. Monaci, and P. Toth, "A metaheuristic approach for the vertex color-ing problem," INFORMS Journal on Computing, vol. 20, pp. 302-316, 2008. [DOI:10.1287/ijoc.1070.0245]

16. [16] E. Malaguti, M. Monaci, and P. Toth, "An exact approach for the vertex coloring probl-em," Discrete Optimization, vol. 8, pp. 174-190, 2011. [DOI:10.1016/j.disopt.2010.07.005]

17. [17] I. Blöchliger and N. Zufferey, "A graph coloring heuristic using partial solutions and a reactive tabu scheme," Computers & Operations Research, vol. 35, pp. 960-975, 2008. [DOI:10.1016/j.cor.2006.05.014]

18. [18] T. Park and K. R. Ryu, "A dual-population genetic algorithm for adaptive diversity control," IEEE transactions on evolutionary computation, vol. 14, pp. 865-884,2010. [DOI:10.1109/TEVC.2010.2043362]

19. [19] Y. Tan, G. Tan, and X. Wu, "Hybrid real-coded genetic algorithm with chaotic local search for global optimization," JOURNAL OF INFORMATION &COMPUTATIONAL SCIENCE, vol. 8, pp. 3171-3179, 2011.

20. [20] M. Last and S. Eyal, "A fuzzy-based lifetime extension of genetic algorithms," Fuzzy sets and systems, vol. 149, pp. 131-147, 2005. [DOI:10.1016/j.fss.2004.07.011]

21. [21] C. A. Glass and A. Prügel-Bennett, "Genetic algorithm for graph coloring: exploration of Galinier and Hao's algorithm," Journal of Combinatorial Optimization, vol. 7, pp. 229-236, 2003. [DOI:10.1023/A:1027312403532]

22. [22] D. C. Porumbel, J.-K. Hao, and P. Kuntz, "An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring," Comput-ers & Operations Research, vol. 37, pp. 1822-1832, 2010. [DOI:10.1016/j.cor.2010.01.015]

23. [23] f. hoseinkhani and b. nasersharif, "Two Fea-tuer Transformation Methods Based on Genetic Algorithm for Reducing Support Vector Machine Classification Error," Signal and Data Processing, vol. 12, pp. 23-39, 2015.

24. [24] S. Garcia, M. Saad, and O. Akhrif, "Nonlin-ear tuning of aircraft controllers using genetic global optimization: A new periodic mutation operator," Canadian Journal of Electrical and Computer Engineering, vol. 31, pp. 149-158, 2006. [DOI:10.1109/CJECE.2006.259210]

25. [25] M. Rocha and J. Neves, "Preventing prema-ture convergence to local optima in genetic algorithms via random offspring generation," in International Conference on Industrial, Engineering and Other Applica-tions of Applied Intelligent Systems, 1999, pp. 127-136.

26. [26] Q. Lü, G. Shen, and R. Yu, "A chaotic approach to maintain the population diver-sity of genetic algorithm in network train-ing," Computational Biology and Che-mistry, vol. 27, pp. 363-371, 2003. [DOI:10.1016/S1476-9271(02)00083-X]

27. [27] G. Sadeghi Bajestani, A. Monzavi, and S. M. R. Hashemi Golpaygani, "Precisely chaotic models survey with Qualitative Bifurcation Diagram," Signal and Data Processing, vol. 13, pp. 17-34, 2016. [DOI:10.18869/acadpub.jsdp.13.3.17]

28. [28] E. N. Lorenz, "Deterministic nonperiodic flow," Journal of the atmospheric sciences, vol. 20, pp. 130-141, 1963.
https://doi.org/10.1175/1520-0469(1963)020<0130:DNF>2.0.CO;2 [DOI:10.1175/1520-0469(1963)0202.0.CO;2]

29. [29] J. Determan and J. A. Foster, "Using chaos in genetic algorithms," in Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, 1999, pp. 2094-2101.

30. [30] M.-Y. Cheng and K.-Y. Huang, "Genetic algorithm-based chaos clustering approach for nonlinear optimization," Journal of Marine Science and Technology, vol. 18, pp. 435-441, 2010.

31. [31] C.-T. Cheng, W.-C. Wang, D.-M. Xu, and K. Chau, "Optimizing hydropower reservoir operation using hybrid genetic algorithm and chaos," Water Resources Management, vol. 22, pp. 895-909, 2008. [DOI:10.1007/s11269-007-9200-1]

32. [32] E. Salari and K. Eshghi, "An ACO algorithm for graph coloring problem," in Computa-tional Intelligence Methods and Applicatio-ns, 2005 ICSC Congress on, 2005, p. 5 pp.

33. [33] I. Méndez-Díaz and P. Zabala, "A cutting plane algorithm for graph coloring," Discr-ete Applied Mathematics, vol. 156, pp. 159-179, 2008. [DOI:10.1016/j.dam.2006.07.010]

34. [34 P. San Segundo, "A new DSATUR-based algorithm for exact vertex coloring," Comp-uters & Operations Research, vol. 39, pp. 1724-1733, 2012. [DOI:10.1016/j.cor.2011.10.008]

35. [35] S. M. Douiri and S. Elbernoussi, "An Effec-tive Ant Colony Optimization Algor-ithm for the Minimum Sum Coloring Problem," in International Conference on Computational Collective Intelligence, 2013, pp. 346-355.

36. [36] Y. Jin, J.-K. Hao, and J.-P. Hamiez, "A memetic algorithm for the minimum sum coloring problem," Computers & Operations Research, vol. 43, pp. 318-327, 2014. [DOI:10.1016/j.cor.2013.09.019]

37. [37] S. Mahmoudi and S. Lotfi, "Modified cuck-oo optimization algorithm (MCOA) to solve graph coloring problem," Applied soft computing, vol. 33, pp. 48-64, 2015. [DOI:10.1016/j.asoc.2015.04.020]

38. [38] S. M. Douiri and S. Elbernoussi, "Solving the graph coloring problem via hybrid gene-tic algorithms," Journal of King Saud University-Engineering Sciences, vol. 27, pp. 114-118, 2015. [DOI:10.1016/j.jksues.2013.04.001]

39. [39] R. Marappan and G. Sethumadhavan, "Solu-tion to graph coloring problem using divide and conquer based genetic method," in Information Communication and Embedd-ed Systems (ICICES), 2016 Internat-ional Con-ference on, 2016, pp. 1-5.

40. [40] B. Ray, A. J. Pal, D. Bhattacharyya, and T. Kim, "An efficient ga with multipoint guided mutation for graph coloring problems," International Journal of Signal Processing, Image Processing and Pattern Recognition, vol. 3, pp. 51-58, 2010.

41. [41] S. Bakhtar, H. Jazayeriy, and M. Valinataj, "A multi-start path-relinking algorithm for the flexible job-shop scheduling problem," in Information and Knowledge Technology (IKT), 2015 7th Conference on, 2015, pp. 1-6.

Send email to the article author