بهبود الگوریتم های بهینه سازی اجتماع ذرات و تکامل تفاضلی با استفاده از نظریه چانه زنی نش
محورهای موضوعی : هوش مصنوعی
مرضیه دادور
1
,
حمید رضا نویدی
2
*
,
حمید حاج سید جوادی
3
,
میترا میرزارضایی
4
1 - گروه مهندسی کامپیوتر، واحد علوم و تحقیقات، دانشگاه آزاد اسلامی، تهران، ایران
2 - گروه ریاضیات و علوم کامپیوتر، دانشگاه شاهد، تهران، ایران
3 - گروه ریاضیات و علوم کامپیوتر، دانشگاه شاهد، تهران، ایران
4 - گروه مهندسی کامپیوتر، واحد علوم و تحقیقات، دانشگاه آزاد اسلامی، تهران، ایران
کلید واژه: بهینه سازی ازدحام ذرات (PSO), تکامل تفاضلی (DE), تئوری بازی همکارانه , نظریه چانه زنی نش .,
چکیده مقاله :
این مقاله، رویکرد جدیدی را به منظور حل مسائل بهینهسازی ارائه میکند، که دو الگوریتم شناخته شده‌ی بهینهسازی ازدحام ذرات (Particle Swarm Optimization) و تکامل تفاضلی (Differential Evolution) با هم همکاری می‌نماید. در رویکرد پیشنهادی برای حفظ تعادل بین توانایی اکتشاف و استخراج با جلوگیری از سکون جمعیت، اجتناب از بهینه محلی و بهبود در الگوریتمهای PSO و DE از مدل ائتلافی یا همکاری در تئوری بازی‌ها استفاده می‌شود. در واقع الگوریتمهای PSO و DE به عنوان دو بازیکن در فضای جستجو هستند، که با استفاده نظریه چانه زنینش (Nash bargaining theory) در هر مرحله با هم بازی همکارانه (Cooperative game) انجام داده تا بهترین راهحل را در فضای جستجو بدست آورند. مطابق با ساختارCEC2005، بیست و پنج تابع معیار (Benchmark functions) برای ارزیابی کارایی الگوریتم پیشنهادی مورد استفاده قرار می‌گیرند. روش پیشنهادی با دو الگوریتم کلاسیک PSO وDE و الگوریتمهای ترکیبی که اخیرا پیشنهاد شده است مقایسه می‌شود. نتایج نشان می‌دهد، رویکرد ارائه شده در مقایسه با الگوریتمهای کلاسیک و سایر مدل های ترکیبی عملکرد بهتری دارد.
This article proposes a new approach in solving optimization (issues) problems in which two known optimization algorithm of particle swarm algorithm (PSO) and differential evolution (DE) a cooperate. The proposed approach uses a coalition or cooperation model in the game theory to improve the DE and PSO algorithms. This is done in an attempt to keep a balance between the exploration and exploitation capabilities by preventing population stagnation and avoiding the local optimum. The DE and PSO algorithms are two players in the state space, which play cooperative games together using the Nash bargaining theory to find the best solution. To evaluate the performance of the proposed algorithm, 25 benchmark functions are used in terms of the CEC2005 structure. The proposed algorithm is then compared with the classical DE and PSO algorithms and the hybrid algorithms recently proposed. The results indicated that the proposed hybrid algorithm outperformed the classical algorithms and other hybrid models.
محیط بازی یک فضای رقابتی را در بین الگوریتم ها ایجاد می کند و باعث می شود توانایی جستجوی الگوریتم ها تا حد زیادی افزایش پیدا کند.
سود حاصل از چانه زنی نش با توجه به خاصیت بهینه پرتو بودن بهترین جوابی هست که برای هر دو الگوریتم بدست می آید.
تبادل سود حاصل از بازی در بین الگوریتم ها باعث اکتشاف نواحی جدید در فضای جستجو و افزایش تنوع و اجتناب از بهینه محلی می شود.
شرط قضیه چانه زنی نش به حفظ تعادل در بین توانایی اکتشاف و استخراج در روش پیشنهادی کمک می کند.
[1] J. P. B. Mapetu, Z. Chen and L. Kong, "Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing," Applied Intelligence, vol. 49, pp. 3308-3330, 2019, doi: 10.1007/s10489-019-01448-x.
[2] Q.-V. Pham, S. Mirjalili, N. Kumar, M. Alazab and W.-J. Hwang, "Whale optimization algorithm with applications to resource allocation in wireless networks," IEEE Transactions on Vehicular Technology, vol. 69, pp. 4285-4297, 2020, doi: 10.1109/TVT.2020.2973294.
[3] M. Dadvar, H. Navidi, H. H. S. Javadi and M. Mirzarezaee, "A cooperative approach for combining particle swarm optimization and differential evolution algorithms to solve single-objective optimization problems," Applied Intelligence, vol. 52, no. 4, pp. 4089-4108, 2022, doi:10.1007/s10489-021-02605-x.
[4] X. Meng, Y. Liu, X. Gao and H. Zhang, "A new bio-inspired algorithm: chicken swarm optimization," in International conference in swarm intelligence, pp. 86-94, 2014, doi: 10.1007/978-3-319-11857-4_10
[5] S. Mirjalili, "SCA: a sine cosine algorithm for solving optimization problems," Knowledge-based systems, vol. 96, pp. 120-133, 2016, doi: 10.1016/j.knosys.2015.12.022.
[6] S. Mirjalili, S. M. Mirjalili and A. Lewis, "Grey wolf optimizer," Advances in engineering software, vol. 69, pp. 46-61, 2014, doi: 10.1016/j.advengsoft.2013.12.007.
[7] W.-T. Pan, "A new fruit fly optimization algorithm: taking the financial distress model as an example," Knowledge-Based Systems, vol. 26, pp. 69-74, 2012, doi: 10.1016/j.knosys.2011.07.001.
[8] S.-C. Chu, P.-W. Tsai and J.-S. Pan, "Cat swarm optimization", in Pacific Rim international conference on artificial intelligence, 2006, pp. 854-858, doi: 10.1007/978-3-540-36668-3_94.
[9] X.-B. Meng, X. Z. Gao, L. Lu, Y. Liu and H. Zhang, "A new bio-inspired optimisation algorithm: Bird Swarm Algorithm," Journal of Experimental & Theoretical Artificial Intelligence, vol. 28, no. 4, pp. 673-687, 2016, doi.org/10.1080/0952813X.2015.1042530.
[10] X.-S. Yang, "A new metaheuristic bat-inspired algorithm," in Nature inspired cooperative strategies for optimization (NICSO 2010), ed: Springer, 2010, pp. 65-74, doi: 10.1007/978-3-642-12538-6_6.
[11] R. Storn and K. Price, "Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces," Journal of global optimization, vol. 11, no. 4, pp. 341-359, 1997, 10.1023/A:1008202821328.
[12] A. Askarzadeh, "A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm," Computers & Structures, vol. 169, pp. 1-12, 2016, doi: 10.1016/j.compstruc.2016.03.001.
[13] R. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995, pp. 39-43, doi: 10.1109/MHS.1995.494215.
[14] X. Yu, J. Cao, H. Shan, L. Zhu and J. Guo, "An adaptive hybrid algorithm based on particle swarm optimization and differential evolution for global optimization," The Scientific World Journal, vol. 2014, 2014, no. 6, doi: 10.1155/2014/215472.
[15] B. Mao, Z. Xie, Y. Wang, H. Handroos and H. Wu, "A hybrid strategy of differential evolution and modified particle swarm optimization for numerical solution of a parallel manipulator," Mathematical Problems in Engineering, vol. 2018, no. 1, 2018, doi: 10.1155/2018/9815469.
[16] Q. Abbas, J. Ahmad and H. Jabeen, "OPSODE: opposition based particle swarm optimization instilled with differential evolution," International journal of advanced and applied sciences, vol. 4, no. 7, pp. 50-58, 2017, doi: 10.21833/ijaas.2017.07.008.
[17] K. Price, R. M. Storn and J. A. Lampinen, "Differential evolution: a practical approach to global optimization," Springer Science & Business Media, 2006.
[18] R. Thangaraj, M. Pant, A. Abraham and P. Bouvry, "Particle swarm optimization: hybridization perspectives and experimental illustrations," Applied Mathematics and Computation, vol. 217, no. 12, pp. 5208-5226, 2011, doi: 10.1016/j.amc.2010.12.053.
[19] C. Huang, X. Zhou, X. Ran, J. Wang, H. Chen and W. Deng, "Adaptive cylinder vector particle swarm optimization with differential evolution for UAV path planning," Eng. Appl. Artif. Intell., vol. 121, p. 105942, 2023, doi: 10.1016/j.engappai.2023.105942.
[20] Q. Gao, H. Sun and Z. Wang, "DP-EPSO: Differential privacy protection algorithm based on differential evolution and particle swarm optimization," Optics Laser Technology, vol. 173, p. 110541, 2024, doi: 10.1016/j.optlastec.2023.110541.
[21] S. Wang, Y. Li and H. Yang, "Self-adaptive mutation differential evolution algorithm based on particle swarm optimization," Applied Soft Computing, vol. 81, p. 105496, 2019, doi: 10.1016/j.asoc.2019.105496.
[22] D. Fan and J. Lee, "A Hybrid Mechanism of Particle Swarm Optimization and Differential Evolution Algorithms based on Spark," KSII Transactions on Internet and Information Systems (TIIS), vol. 13, no. 12, pp. 5972-5989, 2019, doi: 10.3837/tiis.2019.12.010.
[23] H. Liu, X.-W. Zhang and L.-P. Tu, "A modified particle swarm optimization using adaptive strategy," Expert Systems with Applications, vol. 152, p. 113353, 2020, doi: 10.1016/j.eswa.2020.113353.
[24] H. Wang, L. Zuo, J. Liu, W. Yi and B. Niu, "Ensemble particle swarm optimization and differential evolution with alternative mutation method," Natural Computing, vol. 19, pp. 699-712, 2020, doi: 10.1007/s11047-018-9712-z.
[25] A. Lin, D. Liu, Z. Li, H. M. Hasanien and Y. Shi, "Heterogeneous differential evolution particle swarm optimization with local search," Complex & Intelligent Systems, vol. 9, no. 6, pp. 6905-6925, 2023, doi: 10.1007/s40747-023-01082-8.
[26] B. Tang, K. Xiang and M. Pang, "An integrated particle swarm optimization approach hybridizing a new self-adaptive particle swarm optimization with a modified differential evolution," Neural Computing and Applications, vol. 32, no. 7, pp. 4849-4883, 2020, doi: 10.1007/s00521-018-3878-2.
[27] T. M. Dao, M. Q. Tran, L. T. Duong, D. Do, N. Nguyen and D. Vo, "Temperature Dependent Optimal Power Flow Using Combined Particle Swarm Optimization and Differential Evolution Method," GMSARN International Journal, vol. 18, pp. 84-105, 2024.
[28] S.-Y. Du and Z.-G. Liu, "Hybridizing Particle Swarm Optimization with JADE for continuous optimization," Multimedia Tools and Applications, vol. 79, pp. 4619-4636, 2020, doi: 10.1007/s11042-019-08142-7.
[29] Y. Shi and R. C. Eberhart, "Empirical study of particle swarm optimization," Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Washington, DC, USA, 1999, pp. 1945-1950 Vol. 3, doi: 10.1109/CEC.1999.785511.
[30] Z. -H. Zhan, J. Zhang, Y. Li and H. S. -H. Chung, "Adaptive Particle Swarm Optimization," in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 39, no. 6, pp. 1362-1381, Dec. 2009, doi: 10.1109/TSMCB.2009.2015956.
[31] GH. Abdoli, “Game theory and its applications (incomplete information, evolutionary and cooperative games)”, 2007, The organization for researching and composing university textbooks in the humanities.
[32] R. B. Myerson, "Game theory", Harvard university press, 2013.
[33] P. N. Suganthan et al., "Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization," KanGAL report, vol. 2005005, p. 2005, 2005.