الگوریتم ژنتیکِ آگاه از بهترین عضو با کاربرد در رنگ آمیزي و بعدمتریک گراف
محورهای موضوعی : عمومى
محمود امین طوسی
1
*
,
هاشم عزتی
2
1 - دانشکده ریاضی و علوم کامپیوتر، دانشگاه حکیم سبزواري، سبزوار
2 - دانشکده ریاضی و علوم کامپیوتر، دانشگاه حکیم سبزواري، سبزوار
کلید واژه: لگوریتم ژنتیک, الگوریتم هاي فراابتکاري, بعدمتریک گراف, رنگ آمیزي گراف,
چکیده مقاله :
الگوریتم ژنتیک از معروف ترین روش هاي حل مسائل بهینه سازي ترکیبیاتی است که کاربردهاي متعددي در حوزه هاي گوناگونی الگوریتم ژنتیک از معروف‌ترین روش‌های حل مسائل بهینه‌سازی ترکیبیاتی است که کاربردهای متعددی در حوزه‌های گوناگونی همچون برق، کامپیوتر و ریاضی داشته و دارد. نسل بعد در این الگوریتم با انتخاب اعضای جمعیت بر اساس میزان برازندگی آنها صورت می‌پذیرد. ارتباط اعضا از طریق عملگر ترکیب می‌باشد و برخی از بهترین اعضا مستقیماً به نسل بعد منتقل می‌شوند. به صورت معمول اعضای ضعیف جمعیت نیز امکان مشارکت در ایجاد نسل بعد را دارند و حذف نمی‌شوند. در این مقاله، عملگرهای تولید فرزند، از بهترین عضو نسل جاری آگاه هستند و تنها فرزندانی به خوبیِ بهترین عضو، تولید شده و در نسل بعد قرار می‌گیرند. شیوه‌ی پیشنهادی در دو کاربرد رنگ‌آمیزی و بعدمتریک گراف با روش معمول الگوریتم ژنتیک مورد مقایسه قرار گرفته و برتری آن در حالت متوسط هم از نظر کیفیت و هم سرعت اجرا نسبت به الگوریتم ژنتیک مرسوم، نشان داده شده است.
Genetic algorithm is one of the most famous methods for solving Combinatorial Optimization Problems. It had various applications in different field of studies such as Electronics, Computer Science and Mathematics and still has. In this algorithm, the population members which contribute for producing the next generation are selected according to their fitness values. The combination of the members is through Crossover Operator; And in some versions a few of the best members migrate to the next generation directly. Normally, the weak members of population may participate to the next generation. In this study, the combination operators are aware of the best member of generation; Only those child which are as good as the best member, are allowed to form the next generation. The proposed method is applied on graph coloring and finding metric-dimension of graph problems. The results are compared with the common genetic algorithm. Experimental results shows the superior performance of the proposed method in comparison to common genetic algorithm.
[1] D. Beasley, D. R. Bull, and R. R. Martin, “An overview of genetic algorithms: Part 1, fundamentals,” University Computing, vol.15, no.2, pp.58– 69, 1993.
[2 [م. امین طوسی و ه . صدوقی یزدي، “کلاسه بندي فازي بهینه دانشجویان با استفاده از یک تابع فازي در حل مسئله برنامه ریزي ژنتیکی دروس هفتگی دانشگاه،” در نهمین کنفرانس سالانه انجمن کامپیوتر ایران، (تهران، ایران)، صفحات 352-345 ،دانشگاه صنعتی شریف، اسفند 1382.
[3] M. Amintoosi, H. SadoghiYazdi, M.Fathy, and R. Monsefi, “Using pattern matching for tiling and
packing problems,” European Journal of Operational Research, vol.183, pp.950–960, 2007. [4 [ر. منصفی و م. امین طوسی، “جورچینی قطعات راست گوشه با استفاده از شبکه هاي عصبی و الگوریتم ژنتیک،” در پنجمین کنفرانس سالانه انجمن کامپیوتر ایران، (تهران، ایران)، صفحات 304-298 ،دانشگاه شهید بهشتی، بهمن 1378. 153 محمود امین طوسی و ... دو فصلنامه فناوري اطلاعات و ارتباطات ایران، سال دوازدهم، شماره هاي43 و44 ،بهار و تابستان99
[5] J. Kratica, “Improving performances of the genetic algorithm by caching,” Computers and Artificial Intelligence, vol.18, 01 1999.
[6] Z. Xin and X. Chunbo, “New genetic algorithm improved and its applications,” in 2011 International Conference on Electronics, Communications and Control (ICECC), pp.926–928, Sept 2011.
[7] A. Shrestha and A. Mahmood, “Improving genetic algorithm with fine-tuned crossover and scaled architecture,” Journal of Mathematics, vol.2016, p.10, Article ID 4015845 2016.
[8] R. Tanese, “Distributed genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, (San Francisco, CA, USA), pp.434–439, Morgan Kaufmann Publishers Inc., 1989.
[9] T. C. Belding, “The distributed genetic algorithm revisited,” in Proceedings of the 6th International Conference on Genetic Algorithms, (San Francisco, CA, USA), pp.114–121, Morgan Kaufmann Publishers Inc., 1995.
[10] D. Whitley, S. Rana, and R. B. Heckendorn, “The island model genetic algorithm: On separability, population size and convergence,” Journal of Computing and Information Technology, vol.7, pp.33–47, 1998.
[11] S. H. Ling and F. H. Leung, “An improved genetic algorithm with average-bound crossover and wavelet mutation operations,” Soft Comput., vol.11, pp.7–31, Jan. 2007.
[12] R.-L. Wang and K. Okazaki, “An improved genetic algorithm with conditional genetic operators and its application to set-covering problem,” Soft Comput., vol.11, pp.687–694, Feb. 2007.
[13] H. Mühlenbein and D. Schlierkamp-Voosen, “Predictive models for the breeder genetic algorithm
i. continuous parameter optimization,” Evol. Comput., vol.1, pp.25–49, Mar. 1993. [14] I. Ono, H. Kita, and S. Kobayashi, “Advances in
evolutionary computing,” chap. A Real-coded Genetic Algorithm Using the Unimodal Normal Distribution Crossover, pp.213–237, New York, NY, USA: Springer-Verlag New York, Inc., 2003.
[15] https://en.wikipedia.org/wiki/Graph-coloring, 2016.
[16] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd ed. , 2009.
[17] J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, “Computing the metric dimension of graphs by genetic algorithms,” Computational Optimization and Applications, vol.44, pp.343–361, 01 2009.
[18] J. Bensmail, F. Mc Inerney, and N. Nisse, “Metric Dimension: from Graphs to Oriented Graphs,” in LAGOS 2019 - 10th Latin & American Algorithms, Graphs and Optimization Symposium, vol.346 of Electronic Notes in Theoretical Computer Science, (Belo Horizonte, Brazil), pp.111–123, June 2019.
[19] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood, “On the metric dimension of cartesian products of graphs,” SIAM Journal on Discrete Mathematics, vol.21, no.2, pp.423–441, 2007.
[20] S. Farooq, Rashid; Akhter, “Metric dimension of fullerene graphs,” GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, vol.Vol 7, No 1 (2019): Electronic Journal of Graph Theory and Applications, 2019.
[21] Z. Shao, S. M. Sheikholeslami, P. Wu, and J.-B. Liu, “The Metric Dimension of Some Generalized Petersen Graphs,” Discrete Dynamics in Nature and Society, vol.2018, pp.1–10, August 2018.
[22] A. Ahmad, M. Bača, and S. Sultan, “Computing the metric dimension of kayak paddles graph and cycles with chord,” Proyecciones (Antofagasta, On line), vol.39, pp.287–300, Apr. 2020.
[23] F. Harary, J. P. Hayes, and H.-J. Wu, “A survey of the theory of hypercube graphs,” Computers & Mathematics with Applications, vol.15, no.4, pp.277 – 289, 1988.
[24 [هـ. عزتی و م. امین طوسی، “محاسبه بعد متریک گراف با الگوریتم شبیه سازي تبریدي،” در سومین سمینار کنترل
و بهینه سازي، (دانشگاه حکیم سبزواري)، صفحات 42-39،1398