افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین خودکار سلولی یک بعدی
محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسی
کلید واژه: Genetic Algorithm, Optimization, الگوریتم ژنتیک, بهینه سازی, ماشین خودکار سلولی یک بعدی, Keywords:One dimensional Cellular Automata,
چکیده مقاله :
چکیده: الگوریتم ژنتیک در حل بسیاری از مسائل بهینه سازی الگوریتم قدرتمندی است که کارایی آن به میزان زیادی تحت تأثیر انتخاب صحیح پارامترها و عملگرهای آن نظیر تعداد کروموزوم جمعیت، نوع عملگر تقاطع، جهش و... قرار دارد. تا کنون روشهای مختلفی به منظور افزایش کارایی الگوریتم ژنتیک پیشنهاد شده است. در این مقاله برای اولین بار از یک روش محاسبه برازندگی جدید مبتنی بر ماشین خودکار سلولی(CA (به منظور افزایش کارایی الگوریتم ژنتیک (GA (استفاده شده است. الگوریتم ترکیبی پیشنهادی در نهایت به منظور تعیین مینیمم 5 تابع شناخته شده در زمینۀ بهینهسازی با 5 و 10 متغیر مورد استفاده قرار گرفت. نتایج نشان داد که الگوریتم ترکیبی GA-CA در مقایسه با الگوریتم ژنتیک استاندارد از دقت بیشتری در پیدا کردن بهترین مینیمم توابع مورد بهینه سازی برخوردار است. همچنین الگوریتم ترکیبی GA-CA به لحاظ زمان رسیدن به بهترین مینیمم گلوبال ( زمان همگرایی) در حدود 5 برابر کمتر از الگوریتم ژنتیک استاندارد می باشد.
Abstract: Genetic Algorithm is a powerful algorithm for solving optimization problems. Its performance is affected by appropriate selection of its parameters and operators such as size of population, type of crossover, mutation, etc. Different methods have been suggested to enhance the performance of standard Genetic Algorithm (sGA). In this paper, we propose a new method based on one dimensional Cellular Automata (1D CA) to enhance the performance of sGA. The proposed hybrid CA-GA algorithm then has been used to find the minimum of five well-known test functions (with 5 and 10 dimension). Results showed that the hybrid CA-GA algorithm has a greater accuracy compared with sGA in finding the best minimum of test function. Also, the convergence speed of hybrid CA-GA algorithm to the exact global minimum is clearly more than sGA.
1. Katsaras, Vlasis K. Koumousis and Christos P. “A Saw-Tooth Genetic Algorithm Combining the Effects of Variable Population Size and Reinitialization to Enhance Performance”. 1, s.l. : IEEE, FEBRUARY 2006, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, Vol. 10. doi:10.1109/TEVC.2005.860765. 2. Liu, Juan Cai, Zixing Liu, Jianqin. Hefei, “Premature Convergence in Genetic Algorithm :Analysis and Prevention Based on Chaos Operator.” P.R. China : Proceedings ofthe 3rd World Congress on Intelligent Control and Automation, 2000 , June 28-July 2. pp. 495–499. doi:10.1109/WCICA.2000.860016. 3. Ondrej Hrstkaa, Anna Kucerovab,. “Improvements of real coded genetic algorithms based on differential operators preventing premature convergence.” s.l. : Advances in Engineering Software, 2004, Vol. 35, pp. 237–246. doi:10.1016/S0965-9978(03)00113-3. 4. J. Andrea, P. Siarryb,T. Dognona. “An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization.” s.l. : Advances in Engineering Software, 2001, Vol. 32, pp. 49-60. doi:10.1016/S0965-9978(00)00070-3. 5. Abu Bakar Md Sultan, Ramlan Mahmud, Muhammad Nasir Sulaiman. “Reducing Premature Convergence Problem through Numbers Structuring in Genetic Algorithm.” 4, s.l. : IJCSNS International Journal of Computer Science and Network Security, April 2007, Vol. 7. doi:10.1.1.130.5783. 6. Riccardo Caponetto, Member, IEEE, Luigi Fortuna, Stefano Fazzino, and Maria Gabriella Xibilia. “Chaotic Sequences to Improve the Performance of Evolutionary Algorithms.” 3, s.l. : IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, JUNE 2003, Vol. 7, pp. 289-304. doi: 10.1109/TEVC.2003.810069. 7. Wu, J. Cao Q. H. “A CELLULAR AUTOMATA BASED GENETIC ALGORITHM AND ITS APPLICATION IN MECHANICAL DESIGN OPTIMISATIONY.” s.l. : UKACC International Conference on CONTROL, 1998, September. pp. 1-4. doi: 10.1049/cp:19980467. 8. Yufa Xu “A Hybrid Optimization Method Based on Cellular Automata and Its aplication in SoftSensing Modeling.” 1, 2, Guochu Chen1, and Jinshou Yu2. Haikou, Hainan, China : ICNC '07 Proceedings of the Third International Conference on Natural Computation, 2007 , August. doi:10.1109/ICNC.2007.53. 9. Ilachinski, Andrew, “Cellular Automata, A discrete universe.” s.l.: World Scientific Publishing, 2001. p. 71. ISBN 981-02-4623-4. ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 108 10. Neumann, John von. “The general and logical theory of automata.” Los Alamos : John Wiley & Sons, New York, 1951. pp. 1-31. 11. wolfram, Stephen. “Statistical mechanics of cellular automata.” 2, July 1983, Reviews of Modern Physics, Vol. 55. doi:10.1103/RevModPhys.55.601. 12. Kesslcr, D.A., H.Lavine and W.N.Reynolds. “Coupled-map lattice model for crystal growth.” 1990, Phys. Rev, Vol. 42. doi:10.1103/PhysRevA.42.6125. 13. M. Chahoud1, D. Fehly, H. -H. Wehmann, and A. Schlachetzki. “Cellular-automata -based simulation of anisotropic crystal growth.” 4, December 2000, Journal of Crystal Growth, Vol. 220, pp. 471-479 . doi:10.1016/S0022-0248(00)00902-7. 14. Ch. Mizasa, G.Ch. Sirakoulisa, V. Mardirisa, I. Karafyllidisa, N. Glykosb and R. Sandaltzopoulos. “Reconstruction of DNA sequences using genetic algorithms and cellular automata: Towards mutation prediction?” 1, April 2008, Biosystems, Vol. 92, pp. 61-68 . doi: 10.1016/j.biosystems.2007.12.002. 15. G. Ch. Sirakoulisa, I. Karafyllidis , b, Ch. Mizasa, V. Mardirisa, A. Thanailakisb and Ph. Tsalidesb. “A cellular automaton model for the study of DNA sequence evolution.” 5, September 2003, Computers in Biology and Medicine , Vol. 33, pp. 439-453. doi:10.1016/S0010- 4825(03)00017-9 I. 16. Langton, Christopher. “Studying Artificial Life With Cellular Automata.” 1-3, s.l. : 22, OctoberNovember 1986, Physica D: Nonlinear Phenomena, pp. 120-149. doi:10.1016/0167- 2789(86)90237-X. 17. L. Hernández Encinasa, S. Hoya Whiteb, A. Martín del Reyc, and G. Rodríguez ánchezd. “Modelling forest fire spread using hexagonal cellular Automata.” 6, June 23, 2007, Applied Mathematical Modelling, Vol. 31, pp. 1213-1227. doi:10.1016/j.apm.2006.04.001. 18. Ying Zhenga, Bin Jia, a, Xin-Gang Lia and Nuo Zhua. “Evacuation dynamics with fire spreading based on cellular automaton.” 18-19, September 15, 2011, Physica A: Statistical Mechanics and its Applications , Vol. 390, pp. 3147-3156 . doi:10.1016/j.physa.2011.04.011. 19. Acedoa, L. “A cellular automaton model for collective neural dynamics.” 5-6, September 2009, Mathematical and Computer Modelling, Vol. 50, pp. 717-725. doi:10.1016/j.mcm.2008.12.018. 20. Lev Naumova, Alfons Hoekstraa, and Peter Sloot. “Cellular automata models of tumour natural shrinkage.” 12, June 15 , 2011, Physica A: Statistical Mechanics and its Applications, Vol. 390, pp. 2283-2290 . doi:10.1016/j.physa.2011.02.006. 21. P. Gerlee, a, and A.R.A. Andersona. “An evolutionary hybrid cellular automaton model of solid tumour growth.” 4, June 21 , 2007, Journal of Theoretical Biology, Vol. 246, pp. 583-603 . doi:10.1016/j.jtbi.2007.01.027. 22. P. Gerlee, a, and A.R.A. Andersona. “A hybrid cellular automaton model of clonal evolution in cancer: The emergence of the glycolytic phenotype.” 4, February 21, 2008, Journal of Theoretical Biology , Vol. 250, pp. 705-722 . doi:10.1016/j.jtbi.2007.10.038. 23. Zykov V., Mytilinaios E., Adams B., Lipson H. “Self-reproducing machines.” 7038, 2005, Nature , Vol. 435, pp. 163-164. doi:10.1038/435163a. 24. JH, Holland. “Adaptation in natural and artificial systems.” Internal report. Ann Arbor,MI : University of Michigan, 1975. 25. P.M. Mateo, I. Alberto. “A mutation operator based on a Pareto ranking for multi-objective evolutionary algorithms.” s.l. : J Heuristics, 14 January 2011. DOI 10.1007/s10732-011-9156-4
_||_