دوره 14، شماره 2 - ( 6-1396 )                   جلد 14 شماره 2 صفحات 75-96 | برگشت به فهرست نسخه ها


XML English Abstract Print


دکتری - استادیار دانشگاه صنعتی (نوشیروانی) بابل
چکیده:   (813 مشاهده)

تخصیص مقدار رنگی را به هر یک از گره‌های گراف، به‌گونه‌ای که هیچ دو گره مجاوری دارای رنگ یکسانی نباشد و کمترین مقدار رنگی استفاده شود، مسئله رنگ‌آمیزی گراف گویند. این مسئله به‌عنوان یکی از مسائل NP-hard شناخته می‌شود که کاربردهای مختلفی در زمینه تخصیص پهنای باند، اختصاص حافظه به برنامه‌ها و همچنین، طراحی مدارهای مجتمع دارد. در مقاله حاضر، از الگوریتم ژنتیک و پدیده آَشوب برای حل این مسئله استفاده شده است. در روش پیشنهادی حاضر، عمل‌گر ترکیب چند‌نقطه‌ای مکاشفه‌ای به نام CMHn معرفی شده است. این عمل‌گر، با انتخاب چند نقطه برش در والدین و معتبر‌کردن یکی از زیر بخش‌های والدین (دومین زیربخش هر والد می‌تواند معتبر یا غیر معتبر باشد) آنها را با هم، با استفاده از روشی ابتکاری ترکیب می‌کند. برای اینکه بتوان از بهینه محلی فرار کرد و همچنین، برای یافتن فضای جستجوی جدید، از عمل‌گر جهش استفاده می‌شود. در این مقاله، عمل‌گر جهش آشوبی هوشمند معرفی شده است که با استفاده از فرمولی گره‌هایی را که برای جهش مناسب‌ترند، انتخاب و بر روی آنها جهش را اعمال می‌کند. همچنین، نیمی از جمعیت اولیه با استفاده از روش ابتکاری و نیمی از آن با روش تصادفی تولید شده است. به‌منظور ارزیابی الگوریتم پیشنهادی از نمونه گراف‌های DIMACS و Queen استفاده شده است. نتایج به‌دست‌آمده نشان می‌دهد که روش پیشنهادی در بیش‌تر گراف‌ها، به‌خصوص گراف‌های بسیار بزرگ (wap) و گراف‌های Queen جواب بهتری نسبت به تحقیقات مشابه ارائه می‌دهد.

متن کامل [PDF 6922 kb]   (304 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات پردازش داده‌های رقمی
دریافت: ۱۳۹۴/۴/۱۶ | پذیرش: ۱۳۹۵/۱۲/۱۵ | انتشار: ۱۳۹۶/۷/۲۹ | انتشار الکترونیک: ۱۳۹۶/۷/۲۹

فهرست منابع
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.