الگوریتم ژنتیک بهبود یافته مبتنی بر راهکار خودسازماندهی بحرانی و حافظه گوسی برای حل مسائل بهینه‌سازی پویا

نویسندگان

1 دانشگاه فنی و حرفه‌ای کهگیلویه و بویراحمدـ یاسوج- ایران

2 دانشگاه علم و صنعت ایران

3 دانشکده مهندسی کامپیوتر- دانشگاه آزاد اسلامی-فارس-نورآباد ممسنی- ایران

4 دانشکده مهندسی کامپیوتر، دانشگاه یاسوج، ایران

چکیده

از آن­جایی­که اجزای پویا، همراه با محدویت­های غیرخطی و اهداف متعدد، یکی از خصوصیت­هایی است که به­طور مکرر در مسائل دنیای واقعی ظاهر می­شود و چون زمان زیادی است که محاسبات تکاملی وارد حوزه کاربردهای صنعتی شده است (به­خصوص به­علت توانایی آن­ها در مواجهه با محیط­های چندهدفه و غیرخطی) انتظار می­رود که هرچه زودتر توجه به این زمینه در جامعه علمی رشد پیدا کند.امروزه استفاده از الگوریتم­های تکاملی که بر اساس رفتارهای زیستی طبیعی به­وجود آمده­اند برای حل این مسائل از اهمیت ویژه­ای برخوردار هستند. از جمله این الگوریتم­ها می­توان به الگوریتم ژنتیک اشاره نمود. هدف این مقاله و ادعای اصلی آن، امکان طراحی پروتکل­های الهام گرفته از طبیعت در الگوریتم ژنتیک است که روی بهینه­سازی در محیط­های پویا موثر باشد، در حالی­که پیچیدگی الگوریتم را حفظ کند و تغییرات در فضای مسئله به­صورت دوره­ای رخ دهد. در این مقاله، یک الگوریتم ژنتیک بهبودیافته (خودسازمانده بحرانی) مبتنی بر حافظه برای حل مسائل­بهینه­سازی پویا ارائه شده است. در الگوریتم ارائه­شده، از یک عملگر جهش خودسازمانده که مبتنی بر مدل تپه شنی است، استفاده شده است. عملگر جهش خودسازمانده یک عملگر جهش هست که می­تواند نرخ­های جهش خودتنظیم­شونده را با یک توزیع ویژه بر مبنای مدل تپه شنی انجام دهد که این برای بهینه­سازی پویا مناسب است. اگر تغییرات به­صورت دوره­ای رخ دهند، به­طور معمول استفاده از اطلاعات گذشته اجازه می­دهد الگوریتم به­سرعت بعد از تغییر محیط به سازگاری در شرایط محیطی جدید برسد. ایده مورد نظر در این زمینه، استفاده از یک حافظه می­باشد. یکی از چالش­های اساسی در به­کارگیری حافظه، تنوع می­باشد. برای افزایش سطح تنوع از یک حافظه تخمبن تراکم با خوشه­بندی گاوسی استفاده شده است. همچنین از راهکاری برای جایگزینی و بازیابی در حافظه استفاده شده است. در طرح پیشنهادی ابتدا جهش خودسازمانده بحرانی جدید، با سایر الگوریتم­های ژنتیک ارائه شده توسط سایر محققین ترکیب شده ونتایج حاصل شده نشان می­دهد که این روش توانسته به­کرات سایر الگوریتم­های ژنتیک را برای محیط­های پویا بهبود بخشد. در نهایت روش پیشنهادی این مقاله که ترکیب خودسازماندهی بحرانی جدید با حافظه تخمین تراکم گوسی است ارائه شده است. نتایج این روش با سایر روش­های مشابه که با راهکار جهش خودسازمانده جدید نتایجشان بهبود داده شده است، مقایسه خواهد شد. نتایج حاصل بر روی مسائل محک مختلف باعنوان توابع تله پویا، آزمایش شده است. نشان داده شده که روش پیشنهادی، حتی از روش­های رقیب که با روش جهش خودسازمانده جدید، بهبود یافته­اند نتایج مناسب­تری را تولید کرده است. معیار ارزیابی در این مقاله معیار کارآیی برون­خطی می­باشد. نتایج آزمایش­ها نشان می­دهند که روش پیشنهادی موثر هست چراکه با روش­های دیگر در پارامترهایی از محیط­های پویا مقایسه گردیده که آن­ها بهترین کارایی را دارا هستند.

کلیدواژه‌ها


عنوان مقاله [English]

Improved Genetic Algorithm Based on Critical Self-Organization and Gaussian Memory for Solving Dynamic Optimization Problems

نویسندگان [English]

  • majid mohammadpour 1
  • Behrooz Minaei 2
  • Hamid Parvin 3
  • Kyvan Rahimizadeh 4
چکیده [English]

Dynamic components, nonlinear limitation, and multi-objectives are characteristics that we face in the real world. Nowadays, using transmutation algorithms based on biological behaviors is spread e.g. Genetic algorithm. This study tried to design optimization protocol, inspired by Genetic algorithm. Such algorithm tries to keep its complexity and variation in question scope will happen periodically. In other words, this study proposes an optimized Genetic algorithm to solve dynamic optimization problems.
A new self-mutate operator based on the sandhill model was used in this algorithm. a self-mutate operator is a new mutate operator which can predict self-regulated mutation rates based on the sandhill distribution model. This model can match the new cope condition If variations happen periodically. Switching to a new situation is based on memory. One of the issues of using memory is diversity. a density prediction memory with gaussian clusters was used to increase memory diversity. The new method showed better results compare to the other genetic algorithms. Results were compared with the other self-mutate methods. Also, results were tested with on different functions such as royal road, one max, and deceptive. The phase results were much better than the opponent methods. Since the parameters of the proposed method will not increase in comparison with other algorithms, It can be used in real-world applications.
 

کلیدواژه‌ها [English]

  • optimization
  • Genetic algorithm
  • dynamic environment
  • memory
  • Clustering
  • density estimation
  • crossover
  • mutation
  • self-organizing
  1. [1] John, J. Grefenstette and Ramsey. Connie, L., "An approach to anytime learning". In International Conference on Machine Learning, pages 189–195, 1992. [2] Branke, J. Kaußler, T. Schmidt, C. and Schmeck, H., "A multi population approach to dynamic optimization problems". In Adaptive Computing in Design and Manufacturing, pages 299–308, 2000. [3] Branke, J. "Evolutionary Optimization in Dynamic Environment". Kluwer, 2002. [4] Darwin, C. on the Origins of Species by means of natural selection, or the preservation of favoured race in the struggle for life. LONDON: JOHN MURRAY (1STEDITION), 1859. [5] Jin, Y., and Branke, J. "Evolutionary Optimization In Uncertain environments: A Survey", IEEE Transactions On Evolutionary Computation, Vol. 9(3), 303-317, 2005. [6] Whitley, d. Genitor: A Different Genetic Algorithm. In Proceedings of the Rocky Mountain Conference on Artificial Intelligence, 118-130, 1988. [7] Cobb, H.G. An Investigation Into The Use Of Hyper-mutation As An Adaptive Operator In Genetic Algorithms Having Continuous, Time dependent Nonstationary Environments, Technical Report Aic-90- 001, 1990, Naval Research Laboratory, Washington, USA. [8] Grefenstette, J.J. (1999). Evolvability in Dynamic Fitness Landscapes: A Genetic Algorithm Approach. In Proceedings of the 1999 IEEE Congress on Evolutionary Computation (Cec’1999), Vol. 3, IEEE Press, 2031-2038. [9] Bak, p., and sneppen, k. (2003). Punctuated equilibrium and criticality in a simple model of evolution. Physical review of letters, vol. 71(24), 4083-4086. [10] Stephens, C.R., Olmedo, I.G., Vargas, J.M., and Waelbroeck. H. (1998). Selfadaptation in Evolving Systems. Artificial life, vol. 4(2), 183-201. [11] Goldberg, D.E., and Smith, R.E. (1987). Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy. In J.J. Grefenstette (Ed.): Proceedings Of The 2nd International Conference On Genetic Algorithm, L. Erlbaum Associates, Hillsdale, Nj, USA, 59-68. [12] Uyar, A.S., and Harmanci, A.E. (2005). A New Population Based Adaptive Domination Change Mechanism For Diploid Genetic Algorithms In 237dynamic Environments. Journal Of Soft Computing, Vol. 9(11), 803–815. [13] Ryan, C. (1997). Diploidy without Dominance. In J.T. Alander (Ed.), Proceedings of the 3rd Nordic Workshop on Genetic Algorithms and Their Applications, 63-70. [14] Lewis, J., Hart, E., and Ritchie, G. (1998). A Comparison of Dominance Mechanisms and Simple Mutation on Non Stationary Problems. In A.E. Eiben, T. Bäck, M. Schoenauer, H.-P. Schwefel (Eds.), Proceedings Of 5th International Conference On Parallel Problem Solving From Nature (PPSN-V), Lecture Notes In Computer Science, Vol. 1498, Springer-Verlag, London, UK, 139-148. [15] Dasgupta, D., and Mcgregor, D.R. (1992). Nonstationary Function Optimization Using the Structured Genetic Algorithm. In R. Manner R And B. Manderick (Eds.), Proceedings Of The 2nd International Conference on Parallel Problem Solving From Nature (Ppsn-Ii), Elsevier Science, New York, 145-154. [16] Klinkmeijer, L.Z., De Jong, E., and Wiering, M. (2006). A Serial Population Genetic Algorithm for Dynamic Optimization Problems. In Y. Saeys, E. Tsiporkova, B. De Baets And Y..Van De Peer (Eds.), Proceedings of the Annual Machine Learning Conference of Belgium and the Netherlands, 41-48. [17] Hollstein, R.B. (1971). Artificial Genetic Adaptation in Computer Control Systems. Doctoral Thesis. University of Michigan. [18] Ramsey, C.L., and Grefenstette, J.J. (1993). Case-Based Initialization of Genetic Algorithms. In S. Forrest (Ed.), Proceedings of the 5th International Conference Genetic Algorithms (Icga’1993), Morgan Kaufmann, San Francisco, 84–91. [19] Trojanowski, K., and Michalewicz, Z. (2000). Evolutionary Optimization in Non-Stationary Environments. Journal of Computer Science and Technology, Vol. 1(2), 93-124. [20] مجید محمدپور و حمید پروین."الگوریتم ژنتیک آشوب‌گونه مبتنی بر حافظه و خوشه‌بندی برای حل مسائل بهینه‌سازی پویا". مجله مهندسی برق دانشگاه تبریز. جلد 46. شماره 3. پاییز 1396. [21] مجید محمدپور، بهروز مینایی بیدگلی و حمید پروین."ارائه یک الگوریتم فرااکتشافی جدید مبتنی بر رفتار پرنده تیهو برای حل مسائل بهینه‌سازی پویا". مجله محاسبات نرم دانشگاه کاشان، پذیرفته شده در 1399/7/4. [22] Mohammadpour M, Parvin H, Sina M (2018) Chaotic genetic algorithm based on explicit memory with a new strategy for updating and retrieval of memory in dynamic environments. J AI Data Min 6:191–205 (in press). [23] M. Mohammadpour, H. Parvin. “Genetic Algorithm Based on Explicit Memory for Solving Dynamic Problems”. In Journal of Advances in Computer Research Sari Branch Islamic Azad University, vol. 7, no. 2, pp. 53-68, 2016. [24] H. Parvin., S. Nejatian., M. Mohammadpour, “Explicit memory based ABC with a clustering strategy for updating and retrieval of memory in dynamic environments”. In Applied Intelligence Springer Nature, 2018. doi: 10.1007/s10489-018-1197-z. [25] Ursem. R. K. (2000). Multinational Ga Optimization Techniques in Dynamic Environments. In Proceedings of the 2000 Genetic and Evolutionary Computation Conference (Gecco’2000), Morgan Kaufmann, San Francisco, 19-26. [26] Park, T., and Ryu, K.R. (2007a). A Dual Population Genetic Algorithm with Evolving Diversity. In Proceedings of the 2007 IEEE Congress on Evolutionary Computation (Cec’2007), IEEE Press, 3516-3522. [27] Park, T., Choe, R., And Ryu, K.R. (2007b). Adjusting Population Distance for the Dual-Population Genetic Algorithm. In Proceedings of The Australian Conference On Artificial Intelligence (Ai’2007), Lecture Notes On Computer Science, Vol. 4830, Springer Verlag, Berlin171-180. [28] Park, T., Choe, R., And Ryu, K.R. (2008). Dual Population Genetic Algorithm for Nonstationary Optimization. In In Proceedings of the 2008 234 Genetic and Evolutionary Computation Conference (Gecco’2008), Acm, New York, Ny, 1025-1032. [29] Yang, S. (2004). Constructing Test Environments For Genetic Algorithms Based On Problem Difficulty. In Proceedings of the 2004 IEEE Congress On Evolutionary Computation, Vol. 2, IEEE Press, 2004, 1262 1269.238. [30] Martello, S., and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, New York. [31] جواد سلیمی سرتختی، سلمان گلی بیدگلی، "ارائۀ یک الگوریتم ترکیبی با استفاده از الگوریتم کرم شب‌تاب، الگوریتم ژنتیک و جست‌وجوی محلی"، مجله محاسبات نرم دانشگاه کاشان، جلد ۸، شماره ۱ )بهار و تابستان 1398(، صفحه 14-28. [32] R. Agarwal, D. Schuurmans, and M. Norouzi. (2020), “An optimistic perspective on offline reinforcement learning”, In International Conference on Machine Learning. [33] S. Cabi, S. G. Colmenarejo, A. Novikov, K. Konyushkova, S. Reed, R. Jeong, K. Zołna, Y. Aytar, D. Budden, M. Vecerik, O. Sushkov, D. Barker, J. Scholz, M. D. andx Nando de Freitas, and Z. Wang, (2019), Scaling datadriven robotics with reward sketching and batch reinforcement learning. arXiv preprint:1909.12200. [34] P. S. Castro, S. Moitra, C. Gelada, S. Kumar, and M. G. Bellemare. Dopamine: A Research Framework for Deep Reinforcement Learning. 2018. URL http://arxiv.org/abs/1812.06110. [35] Bäck, T. (1996). Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York. [36] Goldberg, D.E. (2002). The Design of Innovation Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, Ma, 2002. [37] Baluja, S. (1994). Population-Based Incremental Learning: A Method For Integrating Genetic Search Based Function Optimization and Competitive Learning, Technical Report CMU-Cs 94-163, Carnegie Mellon University, USA. [38] Harik, G.R., Lobo, F., and Sastry, K. (2006). Linkage Learning Via Probabilistic Modeling in the Ecga. In M. Pelikan, K. Sastry, E. Cantú-Paz (Eds.), Scalable Optimization Via Probabilistic Modeling: From Algorithms To Applications, Springer-Verlag New York Inc., Secaucus Inc., Nj, Usa,39-61. [39] Bak, P., Tang, C., and Wiesenfeld, K. (1987). Self Organized Criticality: An Explanation Of 1/F Noise. Physical Review of Letters, Vol. 59(4), 381-384. [40] Bak, P., and Sneppen, K. (2003). Punctuated Equilibrium and Criticality in a Simple Model of Evolution. Physical Review of Letters, Vol. 71(24), 4083-4086. [41] Fernandes, C.M. (2009). Pherographia: Drawing By Ants. Leonardo–Journal of the International Society for the Arts, Sciences and Technology, Mit Press, In Press. [42] Fernandes CM, Merelo JJ, Ramos V, Rosa AC (2008) A selforganized criticality mutation operator for dynamic optimization problems. In: Proceedings of the 2008 genetic and evolutionary computation conference. ACM, New York, pp 937–944. [43] Fernandes CM, Laredo JLJ, Rosa AC, Merelo JJ (2013). The sandpile mutation Genetic Algorithm: an investigation on the working mechanisms of a diversity-oriented and self-organized mutation operator for non-stationary functions. Applied Intelligence 39: 279–306. [44] Tinós R, Yang S (2007) A self-organizing RIGA for dynamic optimization problems. Genet Program Evol Mach 8:255–286. [45] Yang S (2008) Genetic algorithms with memory- and elitismbased immigrants in dynamic environments. Evol Comput 6(3):385–416. [46] Fernandes CM, Merelo JJ, Rosa AC (2011). A comparative study on the performance of dissortative mating and immigrants’ strategies for evolutionary dynamic optimization. Inf Sci 181(20):4428–4459. [47] Martello, S., and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, New York. [48] B. Jana, S. Mitra, and S. Acharyya, (2019), “Repository and mutation based particle swarm optimization (rmpso): a new PSO variant applied to reconstruction of gene regulatory network,” Applied Soft Computing, vol. 74, pp. 330–355. [49] G. Pampar`a and A. P. Engelbrecht, “Self-adaptive quantum particle swarm optimization for dynamic environments,” International Series in Operations Research and Management Science, vol. 272, pp. 163–175, 2018. [50] I. Dzalbs and T. Kalganova, (2020), "Accelerating supply chains with Ant Colony Optimization across range of hardware solutions," no. arXiv:2001.08102. [51] حمید‌رضا محمدی، علی اخوان، مقایسه عملکرد الگوریتم‌های HSA،ICA و PSO به‌منظور حذف انتخابی هارمونیک‌ها در اینورتر چندسطحی آبشاری با وجود منابع DC متغیر، نشریه علمی-ترویجی محاسبات نرم، شماره ششم، پاییز و زمستان 93، صفحۀ 20-30. [52] H. Parvin, B. Minaei, S. Ghatei, (2014), “A New Particle Swarm Optimization for Dynamic Environments,” Part of the Lecture Notes in Computer Science book series (LNCS, volume 6694), Computational Intelligence in Security for Information Systems pp 293-300. [53] A. Hashemi and M. Meybodi, (2009), "Cellular PSO: A PSO for Dynamic Environments," Advances in Computation and Intelligence, p. 422–433. [54] H. Assimi, O. Harper, Y. Xie, A. Neumann, F. Neumann, (2020), “Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives,” 24th European Conference on Artificial Intelligence - ECAI 2020 Santiago de Compostela, Spain [55] V. Roostapour, A. Neumann, and F. Neumann, (2018), “On the performance of baseline evolutionary algorithms on the dynamic knapsack problem”, in Parallel Problem Solving from Nature, PPSN XV 2018, Lecture Notes in Computer Science, pp. 158–169. Springer. [56] Y. Xie, O. Harper, H. Assimi, A. Neumann, and F. Neumann, (2019), “Evolutionary algorithms for the chance-constrained knapsack problem”, in Proceedings of the Genetic and Evolutionary Computatio Conference, GECCO 2019, pp. 338–346. [57] Z. ZHAO, F. Gu, Y.m. Cheung, (2020), “Co-operative Prediction Strategy for Solving Dynamic Multi-Objective Optimization Problems,” Published in: 2020 IEEE Congress on Evolutionary Computation (CEC), DOI: 10.1109/CEC48606.2020.9185721. [58] W. Hu, M. Jiang, X. Gao, K.-c. Tan and Y.-m. Cheung, (2019), "Solving dynamic multi-objective optimization problems using incremental support vector machine", 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 2794-2799.