ارائه یک الگوریتم چندجمعیتی مبتنی بر ازدحام ذرات برای حل مسائل بهینه‌سازی پویا

نویسندگان

1 دانشکده مهندسی برق - واحد یاسوج - دانشگاه آزاد اسلامی - یاسوج

2 باشگاه پژوهشگران و نخبگان - واحد یاسوج - دانشگاه آزاد اسلامی - یاسوج

3 دانشکده ریاضی - واحد یاسوج - دانشگاه آزاد اسلامی - یاسوج

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

5 باشگاه پژوهشگران و نخبگان - واحد نورآباد ممسنی - دانشگاه آزاد اسلامی - فارس

چکیده

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

کلیدواژه‌ها

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

Introducing a Multi Population Algorithm based on PSO for Solving Dynamic Optimization Problems

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

  • S. Nejatian 1 2
  • V. Rezaie 3 2
  • H. Parvin 4 5
1 Department of Electrical Engineering, Yasooj Branch, Islamic Azad University, Yasooj, Iran|Young Researchers and Elite Clubs, Yasooj Branch, Islamic Azad University, Yasooj, Iran
2 Department of Electrical Engineering, Yasooj Branch, Islamic Azad University, Yasooj, Iran|Young Researchers and Elite Clubs, Yasooj Branch, Islamic Azad University, Yasooj, Iran
3 Department of Mathematic, Yasooj Branch, Islamic Azad University, Yasooj, Iran|Young Researchers and Elite Clubs, Yasooj Branch, Islamic Azad University, Yasooj, Iran
4 Department of Computer Engineering, Noorabad Mamasani Branch, Islamic Azad University, Noorabad Mamasani, Fars, Iran|Young Researchers and Elite Clubs, Noorabad Mamasani Branch, Islamic Azad University, Noorabad Mamasani, Fars, Iran
5 Department of Computer Engineering, Noorabad Mamasani Branch, Islamic Azad University, Noorabad Mamasani, Fars, Iran|Young Researchers and Elite Clubs, Noorabad Mamasani Branch, Islamic Azad University, Noorabad Mamasani, Fars, Iran
چکیده [English]

Many real-world problems are dynamic, requiring an optimization algorithm which is able to continuously track the changing optima over time. Typical examples include recognition of the moving objects in changing background; constructing financial trading models in various changing market conditions; data mining in continuously updating databases; scheduling problems with dynamic available resources; vehicle routing in traffic networks of dynamic traffic flow, etc. which requires the optimization algorithms to be able to find and track the changing optima efficiently over time. Among various algorithms for dynamic optimization, particle swarm optimization algorithms (PSOs) are attracting more and more attentions in recent years. We have proposed three algorithms based on PSO for dynamic environments. The proposed algorithms are the multi-swarm algorithms. In the traditional research it is shown that the multi swarm algorithms are suitable for creating diversity in the environments. In this paper, we propose an adaptive strategy for dynamic envirounments. The adaptive strategy increases convergence speed of the algorithm. The proposed algorithm uses several suitable operators for increasing the efficiency of the algorithm. One of the operators in the proposed algorithm is the trajectory control operator.  The proposed algorithm has the best results rather than the state-of-the-art.

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

  • particle swarm optimization
  • dynamic optimization problems
  • moving peaks benchmark
  • offline error
  • multi swarm

مراجع

[1] R.I. Lung, D. Dumitrescu, “A Collaborative Model for Tracking Optima in Dynamic Environments”. In: IEEE Congress on Evolutionary Computation, pp.564–567, 2007.
[2] F.B. Ozsoydan and A. Baykasoglu, "A multi-population firefly algorithm for dynamic optimization problems", Evolving and Adaptive Intelligent Systems (EAIS), IEEE International Conference. Pp 1-7. DOI: 10.1109/EAIS.2015.7368777, 2015.
[3] X. Hu, R.C. Eberhart, “Adaptive particle swarm optimization: detection and response to dynamic systems”. In: IEEE Congress on Evolutionary Computation, Honolulu, HI, USA, vol. 2, pp. 1666–1670, 2002.
[4] S. Sadeghi, H. Parvin and F. Rad, "Particle Swarm Optimization for Dynamic Environments", Springer International Publishing, 14th Mexican International Conference on Artificial intelligence, MICAI 2015, PP 260-269, October 2015.
[5] H. Wang, D.  Wang, and S. Yang, , "A Memetic Algorithm With Adaptive Hill Climbing Strategy For Dynamic Optimization Problems," Soft Computing - A Fusion of Foundations, Methodologies and Applications - Special Issue on Emerging Trends in Soft Computing - Memetic Algorithms, Vol. 13, pp. 763-780, 2009.
[6] A. Rezvanian, M. R.  Meybodi, , "Tracking Extrema In Dynamic Environments Using A Learning Automata-Based Immune Algorithm," Grid and Distributed Computing, Control and Automation, Vol. 121, pp. 216-225, 2010.
[7] T.T. Nguyen, "Solving dynamic optimization problems by combining Evolutionary Algorithms with KD-Tree",Soft Computing and Pttern Recogonition (SoCPaR), International Conference, pp. 247-252, 2013.
[8] Y. Xin, T. Ke, and Y.  Xin, , "Immigrant Schemes For Evolutionary Algorithms In Dynamic Environments: Adapting The Replacement Rate," Science in China Series F - Information Sciences, Vol. II, pp. 543-552, 2011.
[9] هوشمند، محکمی، خدابخشیان، "روشی جدید در جایابی بهینه خازنها و ژنراتورهای توزیع شده در شبکه‌های توزیع با استفاده از الگوریتم جستجوی باکتریای جهت داده شده با pso". مجله مهندسی برق دانشگاه تبریز. جلد 39. شماره 2. 1389.
[10] محمدپور و پروین، "الگوریتم ژنتیک آشوب‌گونه مبتنی بر حافظه و خوشه‌بندی برای حل مسائل بهینه‌سازی پویا". مجله مهندسی برق دانشگاه تبریز، جلد 64 ، شماره 3، پائیز 1395.
[11] M. Kamosi, A.B. Hashemi, M.R. Meybodi, “A New Particle Swarm Optimization Algorithm for Dynamic Environments”. SEMCCO. pp. 129-138, 2010.
[12] I. Rezazadeh, M. R.  Meybodi, and A. Naebi, "Adaptive Particle Swarm Optimization Algorithm For Dynamic Environments," ICSI'11 Proceedings of the Second international conference on Advances in swarm intelligence, vol. I, pp. 120-129, 2011.
[13] J. Kennedy, R.C. Eberhart, “Particle Swarm Optimization”, Proceedings of IEEE International Conference on Neural Networks”, Piscataway, NJ, pp. 1942-1948, 1995.
[14] T. Blackwell and J. Branke, “Multi-Swarms, Exclusion, and Anti-Convergence in Dynamic Environments,” IEEE Transactions on Evolutionary Computation 10, 459–472, 2006.
[15] T. Blackwell, J. Branke and X. Li, “Particle swarms for  dynamic optimization problems,” Swarm Intelligence. Springer Berlin Heidelberg, 193-217, 2008.
[16] S. Yang and C. Li, “Fast Multi-Swarm Optimization for Dynamic Optimization Problems,” Proc, Int’l Conf.  Natural Computation, vol. 7, no. 3, pp. 624-628, 2008.
[17] B. Hashemi and M. R.  Meybodi, “Cellular PSO: A PSO for Dynamic Environments”, in Advances in Computation and ntelligence, Lecture Notes in Computer Science, vol. 5821, pp. 422-433, 2009.
[18] C. Li, S. Yang and M. Yang, “An Adaptive Multi-Swarm Optimizer for Dynamic Optimization Problems”, in Evolutionary Computation, vol. 22 no. 4, pp. 559–594, 2014.
[19] P. Novoa-Hernández, C. Cruz Corona, D. A. Pelta, “Efficient multi-swarm PSO algorithms for dynamic environments”, Memetic Comp, vol. 3, pp.163–174, 2011.
[20] D.Yazdani, B. Nasiri, A.Sepas-Moghaddam, Meybodi, M.R., "A Novel Multi-Swarm Algorithm For Optimization In Dynamic Environments Based On Particle Swarm Optimization," Applied Soft Computing, Vol.13, pp. 2144- 2158, 2013.
[21] N . Krasnogor and j. Smith . “A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design Issues,” IEEE Trans. Evolutionary Computation, vol. 9, no. 5, pp. 474-488, 2005.
[22] J. Branke, “Evolutionary Optimization in Dynamic Environment”. Kluwer, 2002.
[23] J. K. Kordestani, A. Rezvanian, and M. R. Meybodi, "CDEPSO: a bi-population hybrid approach for dynamic optimization problems," Applied intelligence, vol. 40, pp. 682-694, 2014.
[24] N. Baktash and M. R. Meybodi, "A New Hybrid Model of PSO and ABC Algorithms for Optimization in Dynamic Environment," Int’l Journal of Computing Theory Engineering, vol. 4, pp. 362-364, 2012.
[25] S. Yang and C. Li, “A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments,” IEEE Trans.Vol 16, no. 4, Aug 2012.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار