Volume 14, Issue 2 (9-2017)                   JSDP 2017, 14(2): 75-96 | Back to browse issues page


XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

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
Abstract:   (5380 Views)

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.
Results show that the proposed algorithm can effectively solve GCP and have comparable outcome with the recent studies in this field. The proposed method outperforms other algorithms on very large graphs (Wap graphs). 
 

Full-Text [PDF 6922 kb]   (2070 Downloads)    
Type of Study: Research | Subject: Paper
Received: 2015/07/7 | Accepted: 2017/03/5 | Published: 2017/10/21 | ePublished: 2017/10/21

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

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2015 All Rights Reserved | Signal and Data Processing