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

نویسندگان

1 پردیس فنی و مهندسی - گروه مهندسی کامپیوتر - دانشگاه یزد

2 دانشکده فنی و مهندسی - گروه مهندسی برق - دانشگاه شهید باهنر کرمان

چکیده

الگوریتم جمعیت ذراتِ اطلاع‌دهنده‌ی محلی، یک روش ساده و مؤثر است که اخیراً برای حل مسائل بهینه‌سازی چندمُدی ارائه شده است. این الگوریتم دارای یک ضعف اساسی است: برای محاسبه سرعت یک ذره، "شایستگی" و " فاصله‌ی" ذرات همسایه‌ی آن ذره را در نظر نمی‌گیرد، درصورتیکه در نظر گرفتن این دو پارامتر در محاسبه سرعت می‌تواند به الگوریتم برای ایجاد یک تعادل مناسب بین همگرایی و تنوع راه‌حل‌ها کمک زیادی کند. در این مقاله، یک نسخه جدید از این الگوریتم با نام "الگوریتم جمعیت ذراتِ اطلاع‌دهنده‌ی محلی گرانشی" ارائه شده است، که در آن هر ذره موقعیت خود را با استفاده از قوانین گرانش و حرکت به سمت بهترین موقعیت همسایگان محلی‌اش تنظیم می‌کند. در الگوریتم پیشنهادی، هر چه همسایه‌ی محلی یک ذره دارای کیفیت بیشتری باشد یا دارای فاصله‌ی کمتری با ذره باشد، جرم گرانشی بیشتری به آن همسایه تعلق می‌گیرد و در نتیجه آن همسایه مجاز به اعمال نیروی گرانشی بیشتری به آن ذره می‌شود. برای بررسی کارایی الگوریتم پیشنهادی، یک ارزیابی تجربی روی چندین تابع محک استاندارد صورت گرفته است. نتایج این آزمایشات نشان می‌دهد که الگوریتم پیشنهادی می‌تواند نتایج بهتری نسبت به الگوریتم جمعیت ذراتِ اطلاع‌دهنده‌ی محلی و سایر الگوریتم‌های بهینه‌ساز چندمُدی به دست آورد.

کلیدواژه‌ها


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

Gravitational Locally Informed Particle Swarm Algorithm for solving Multimodal Optimization Problems

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

  • M. B. Dowlatshahi 1
  • V. Derhami 1
  • H. Nezamabadi-pour 2
1 Faculty of Engineering, Computer Engineering Department, Yazd University, Yazd, Iran
2 Department of Electrical Engineering, Shahid Bahonar University of Kerman, Kerman, Iran
چکیده [English]

Locally Informed Particle Swarm (LIPS) is a simple and effective method for solving multimodal optimization problems. Despite the good performance of LIPS’s velocity updating rule, the quality (fitness) of this local neighbors is not considered in calculating the velocity. Considering the quality of neighbors to update the particle velocity can reinforce the search power of LIPS. In this paper, a new version of LIPS with Gravitational velocity updating rule (GLIPS) is proposed. In GLIPS each particle successively adjusts its position towards the best positions of its local neighbors using laws of gravity and motion. In proposed GLIPS, local neighbors with a higher quality get a greater gravitational mass and therefore are allowed to apply the higher gravity force to other particles to attract them. In this case, the particles near good solutions try to attract the other particles which are exploring the search space. We perform a detailed empirical evaluation on the several commonly used multimodal benchmark functions. Our results demonstrate that the new velocity updating rule for LIPS can obtain better results for multimodal function optimization.

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

  • particle swarm optimization
  • Gravitational Search Algorithm
  • Velocity updating rule
  • Multimodal optimization
[1] J. Nocedal and S. Wright, Numerical optimization, Springer Science & Business Media, 2006.
[2] J.J. Liang, B.Y. Qu, P.N. Suganthan and Q. Chen, “Problem definitions and evaluation criteria for the CEC 2015 competition on learning-based real-parameter single objective optimization.” Technical Report201411A, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore, 2014.
[3] B.Y. Qu, J.J. Liang, Z.Y. Wang, Q. Chen and P.N. Suganthan, “Novel benchmark functions for continuous multimodal optimization with comparative results,” Swarm and Evolutionary Computation, vol. 26, pp. 23-34, 2016.
[4] E.G. Talbi, Metaheuristics: from design to implementation, John Wiley & Sons, 2009.
[5] K. Miettinen, P. Neittanmaki, M.M. Makela and J. Periaux, Evolutionary algorithms in engineering and computer science, John Wiley and Sons, Ltd, New York, 1999.
[6] J. Kennedy, R.C. Eberhart and Y. Shi, Swarm intelligence. Morgan Kaufmann, 2001.
[7] R.C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” In Proceedings of the sixth international symposium on micro machine and human science, 1995.
[8] عباسیان و نظام آبادی پور، «الگوریتم جستجوی گرانشی چندهدفه مبتنی بر مرتب‌سازی جبهه‌های مغلوب‌نشده»، مجله مهندسی برق، دوره 41، شماره 1، صفحات 80-68، دانشگاه تبریز، 1390.
[9] شکرانی‌پور و افتخاری‌مقدم، «ACPSO: یک الگوریتم جدید بهینه‌سازی گروه ذرات تعاونی با قابلیت به‌روزرسانی تطبیقی پارامترها»، مجله مهندسی برق، دوره 40، شماره 2، صفحات 36-21، دانشگاه تبریز، 1389.
[10] M. Dorigo, Optimization, learning and natural algorithms, Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
[11] B.Y. Qu, P.N. Suganthan and S. Das, “A distance-based locally informed particle swarm model for multimodal optimization,” IEEE Transactions on Evolutionary Computation, vol. 17(3), pp. 387-402, 2013.
[12] R. Brits, A.P. Engelbrecht and F. Van den Bergh, “A niching particle swarm optimizer,” In Proceedings of the 4th Asia-Pacific conference on simulated evolution and learning. Singapore: Orchid Country Club, 2002.
[13] E. Özcan and M. Yılmaz, “Particle swarms for multimodal optimization,” In International Conference on Adaptive and Natural Computing Algorithms (pp. 366-375). Springer Berlin Heidelberg, 2007.
[14] A. Passaro and A. Starita, “Particle swarm optimization for multimodal functions: a clustering approach,” Journal of Artificial Evolution and Applications, vol. 2008, 2008.
[15] X. Li, “Niching without niching parameters: particle swarm optimization using a ring topology,” IEEE Transactions on Evolutionary Computation, vol. 14(1), pp. 150-169, 2010.
[16] X. Li, “Adaptively choosing neighborhood bests using species in a particle swarm optimizer for multimodal function optimization,” in Proc. Genet. Evol. Computat. Conf., vol. 3102, pp. 105–116, 2004.
[17] X. Li, “A multimodal particle swarm optimizer based on fitness Euclidean-distance ration,” in Proc. Genet. Evol. Computat. Conf., pp. 78–85, 2007.
[18] X. Li, “Efficient differential evolution using speciation for multimodal function optimization,” in Proc. Conf. Genet. Evol. Computat., pp. 873–880, 2005.
[19] R. Thomsen, “Multimodal optimization using crowding-based differential evolution,” in Proc. IEEE Congr. Evol. Computat, pp.  1382–1389, 2004.