An Improved Particle Swarm Optimization Algorithm using Gaussian Mixture Model in Dynamic Environment

Document Type : Original Article

Authors

Departyment of Computer Engineering, Faculty of Engineering and Science, Shahrekord Branch, Islamic Azad University, Shahrekord, Iran

Abstract

Many problems in the real world due to the local and global optimization change over time are a matter of dynamic optimization. Therefore, optimization algorithms despite global optimization and tracking of environments changed over time are needed in these environments. We are faced with two problems in designing the particle swarm optimization algorithm for dynamic environments to find the best solution in a short time and follow the solution after the environmental changes: Outdated memory and loss of population diversity in search area. The problem of loss of population diversity is one of the biggest challenges in dynamic environments because diversifying a convergent population to find dynamic optimization and then turning it into a new optimization greatly reduces the efficiency of the algorithm. Given the challenges presented in this paper, a hybrid particle swarm optimization algorithm based on a Gaussian mixture model is proposed. In the proposed method, the change of each particle is based on the result of the best particles in its cluster. The results of the Moving Peak Benchmark experiments show a better performance of the proposed algorithm than other algorithms.

Keywords


[1]      J. K. Kazemi, A. Rezvanian and M. R. A. Meybodi, “CDEPSO: a bi-population hybrid approach for dynamic optimization     problems,” Applied Intelligence, vol.40, no. 4, pp. 682-694, 2014.
[2]      I. Zahid, W. Shahzad and M. Faiza, “A diverse clustering particle   swarm optimizer for dynamic environment: To locate and track multiple optima,” In: Proceedings of 10th IEEE Conference on InIndustrial Electronics and Applications (ICIEA), pp. 1755-1760, 2015.
[3]      A. Sharifi, K. Kazemi, M. J. Mahdaviani and M. R. Meybodi, “A novel hybrid adaptive collaborative approach based on particle swarm optimization and local search for dynamic optimization problems,” Applied Soft Computing, vol. 32, pp. 432-448, 2015.
[4]      S. Sadeghi, H. Parvin and F. Rad, “Particle swarm optimization algorithm for dynamic environments,” In: Proceedings of Mexican International Conference on Artificial Intelligence, pp. 260-269, 2015.
[5]      B. Frohlich, M. Enzweiler and U. Franke, “Will this car change the lane?-Turn signal recognition in the frequency domain,” In IEEE Intelligent Vehicles Symposium Proceedings, pp. 37-42, 2014.
[6]      A. Kaveh, Particle swarm optimization, Book chapter of Advances in Metaheuristic Algorithms for Optimal Design of Structures, Springer International Publishing, pp. 11-43, 2017.
[7]      B. Xue, M. Zhang and W. N. Browne, “Multi-objective particle swarm optimisation (PSO) for feature selection,” In: Proceedings of GECCO, pp. 81–88, New York, NY, USA, 2012.
[8]      E. Vellasques, R.Sabourin and E. Granger, “Gaussian mixture modeling for dynamic particle swarm optimization of recurrent problems,” In: Proceedings of GECCO, pp. 73–80, New York, NY, 2012.
[9]      سعید اباذری، امید مرادی، «بهبود میرایی نوسانات سیستم قدرت با به‌کارگیری UPFC و تنظیم پارامترهای کنترل‌کننده بر اساس یک الگوریتم جدید PSO»، مجله مهندسی برق دانشگاه تبریز، دوره 46، شماره 1، صفحه 1-11، 2016.
[10]      X. Hu and R. C. Eberhart, “Adaptive particle swarm optimization: detection and response to dynamic systems,” In: Proceedings of Congress on Evolutionary Computation, vol. 2, pp. 1666–1670, 2002.
[11]      الهام شکرانی‌پور، امیرمسعود افتخاری‌مقدم، «ACPSO: یک الگوریتم جدید بهینه‌سازی گروه ذرات تعاونی با قابلیت به روزرسانی تطبیقی پارامترها»، مجله مهندسی برق دانشگاه تبریز، دوره 40، شماره 2، صفحه 21-36، 2010.
[12]      Y. Shengxiang, “Genetic algorithms with memory-and elitism-based immigrants in dynamics,” Evolutionary Computation, vol. 16, no. 3, pp. 385-416, 2008.
[13]      T. M. Blackwell and P. J. Bentley, “Don't push me! Collision-avoiding swarms,” In: Proceedings of Congress on Evolutionary Computation, vol. 2, pp. 1691-1696, 2002.
[14]      T. M. Blackwell and P. J. Bentley, “Dynamic search with charged swarms,” In: Proceedings ofthe fourth Annual Conference on Genetic and Evolutionary Computation, pp. 19-26. Morgan Kaufmann Publishers Inc., 2002.
[15]      S. Janson and M. Middendorf, “A hierarchical particle swarm optimizer for noisy and dynamic environments,” Genetic Programming and Evolvable Machines, vol. 7, no. 4, pp. 329-354, 2006.
[16]      H. Wang, D. Wang and S. Yang, “Triggered memory-based swarm optimization in dynamic environments,” Applications of Evolutionary Computing, pp. 637-646, 2007.
[17]      T. Blackwell and J. Branke, “Multi- swarms, exclusion, and anti-convergence in dynamic environments,” IEEE Transactions on Evolutionary Computation, vol. 10, no. 4 pp. 459-472, 2006.
[18]      T. Blackwell, J. Branke and X. Li, “Particle swarms for dynamic optimization problems,” Book Chapter of Swarm Intelligence. Springer Berlin Heidelberg, pp. 193-217, 2008.
[19]      M. Kamosi, A. B. Hashemi and M. R. Meybodi, “A new particle swarm optimization algorithm for dynamic environments,” In: Proceedings of International Conference on Swarm, Evolutionary and Memetic Computing, pp. 129-138, 2010.
[20]      D. Yazdani, B. Nasiri, A. Sepas-Moghaddam and M. R.Meybodi, “A novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization,” Applied Soft Computing, vol.13, no. 4, pp. 2144-2158, 2013.
[21]      A. Hashemi and M. R. Meybodi, “Cellular PSO: A PSO for dynamic environments,” In: Proceedings of International Symposium on Intelligence Computation and Applications, pp. 422-433, 2009.
[22]      C. Li and S. Yang, “Fast multi-swarm optimization for dynamic optimization problems,” In: Proceedings of Fourth International Conference on Natural Computation, vol. 7, pp. 624-628, 2008.
[23]      L. Liu, S. Yang and D. Wang, “Particle swarm optimization with composite particles in dynamic environments,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, pp. 1634-1648, 2010.
[24]      U. Halder, S. Das and D. Maity, “A cluster-based differential evolution algorithm with external archive for optimization in dynamic environments,” IEEE Transactions on Cybernetics, vol. 43, no. 3, pp. 881–897, 2013.
[25]      T. T. Nguyen, S. Yang and J. Branke, “Evolutionary dynamic optimization. A survey of the state of the art,” Swarm and Evolutionary Computation, vol. 6, pp. 1-24, 2012.
  [26]      سجاد هواسی، محمدرضا میبدی، سمانه رحیمی، «یک الگوریتم ترکیبی جدید مبتنی‌بر بهینه‌سازی دسته‌جمعی و الگوریتم فرهنگی برای محیط‌های پویا»، دومینکنفرانس ملی مهندسی نرم‌افزار لاهیجان، دانشگاه آزاد اسلامی واحد لاهیجان، ۱۳۹1.
[27]      J. Kennedy, “Stereotyping: Improving particle swarm performance with cluster analysis,” In: Proceeding of Congress Evolutionary Computation, pp. 1507-1512, 2000.
[28]      R. Brits, A. P. Engelbrecht and F. Van den Bergh, “Solving systems of unconstrained equations using particle swarm optimization,” In: Proceeding of IEEE International Conference on Systems, Man, and Cybernetics, vol. 3, pp. 102-107, 2002.
[29]      A. W. Moore, Clustering with gaussian mixtures, School of Computer Science, Carnegie Mellon University, 2001.
[30]      D. Reynolds, “Gaussian mixture models,” Encyclopedia of biometrics, pp. 827-832, 2015.
[31]      N. Shental, A. Bar-Hillel, T. Hertz and D. Weinshall, “Computing gaussian mixture models with EM using equivalence constraints,” In: Proceedings of Advances in neural information processing systems, pp. 465-472, 2004.
[32]      A. P. Dempster, N. M. Laird and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” Journal of the Royal Statistical Society, Series B (Methodological), vol. 39, no. 1, pp. 1–38, 1977.
[33]      C. Li, S. Yang and M. Yang, “An adaptive multi-swarm optimizer for dynamic optimization problems,” Evolutionary computation, vol. 22, no. 4, pp. 559-594, 2014.
[34]      C. Li, T. T. Nguyen, M. Yang, S. Yang and S. Zeng, “Multi-population methods in unconstrained continuous dynamic environments: the challenges,” Information Sciences, vol. 296, pp. 95-118, 2015.
[35]      J. Branke, The moving peaks benchmark, 1999, URL.www.aifb.uni-karlsruhe.de/~jbr/MovPeaks/movpeaks.  
[36]      B. Nasiri, M. R. Meybodi and M. M. Ebadzadeh, “History - driven particle swarm optimization in dynamic and uncertain environments,” Neurocomputing, vol. 172, pp. 356-370, 2016.
[37]      M. Kamosi, A. B. Hashemi and M. R. Meybodi, “A hibernating multi-swarm optimization algorithm for dynamic environments,” In: Proceedings of Second World Congress on Nature and Biologically Inspired Computing (NaBIC), pp. 363-369, 2010.
[38]      I. Rezazadeh, M. R.  Meybodi and A. Naebi, “Adaptive particle swarm optimization algorithm for dynamic environments,” Advances in Swarm Intelligence, pp.120–129, 2011.
[39]      B. Nasiri and M. R. Meybodi, “Speciation based firefly algorithm for optimization in dynamic environments,” International Journal of Artificial Intelligence, vol. 8, no. S12, pp. 118-132, 2012.
[40]      R. I. Lung and D. Dumitrescu, “Acollaborative model for tracking optimain dynamic environments,” In: Proceedings of the IEEE Congresson Evolutionary Computation, pp.564–567, 2007.
[41]      V. Noroozi, A. B. Hashemi and M. R. Meybodi, “CellularDE: a cellular based differential evolution for dynamic optimization problems,” In: Proceedings of International Conference on Adaptive and Natural Computing Algorithms, Springer, Berlin, Heidelberg, pp. 340-349, 2011.‌
[42]      M. C. Du Plessis and A. P. Engelbrecht, “Differential evolution for dynamic environments with unknown numbers of optima,” Journal of Global Optimization, pp. 1-27, 2013.
[43]      S. Kundu, D. Basu and S. S. Chaudhuri, “Multipopulation-based differential evolution with speciation-based response to dynamic environments,” In: Proceedings ofInternational Conference on Swarm, Evolutionary, and Memetic Computing, pp. 222-235, 2013.
[44]      R. Mukherjee, G. R. Patra, R. Kundu and S. Das, “Cluster-based differential evolution with crowding archive for niching in dynamic environments,” Information Sciences, vol. 267, pp. 58-82, 2014.
[45]      N. Baktash and M. R. Meybodi, “A new hybrid model of PSO and ABC algorithms for optimization in dynamic environment,” International Journal of Computer Theory and Engineering, vol. 4, no. 3, p. 362, ‌2012.
[46]      D. Yazdani, B. Nasiri, R. Azizi, A. Sepas-Moghaddam and M. R. Meybodi, “Optimization in dynamic environments utilizing a novel method based on particle swarm optimization,” International Journal of Artificial Intelligence, vol. 11, no. A13, pp. 170-192, 2013.
[47]      D. Yazdani, B. Nasiri, A. Sepas-Moghaddam, M. R. Meybodi and M. M. Akbarzadeh-Totonchi, “mNAFSA: a novel approach for optimization in dynamic environments with global changes,” Swarm and Evolutionary Computation, vol. 18, pp. 38-53, 2014.
  [48]      طیبه طاهری، بابک نصیری، محمدرضا میبدی، «یک الگوریتم ترکیبی برای بهینه‌سازی در محیط پویا با استفاده از الگوریتم جستجوی هارمونی و الگوریتم گروه ذرات»، پنجمین کنفرانس ملی مهندسی برق و الکترونیک ایران، دانشگاه آزاد اسلامی واحد گناباد، 1392.
[49]      J. J. Verbeek, N. Vlassis and B. Kröse, “Efficient greedy learning of Gaussian mixture models,” Neural computation, vol. 15, no. 2, pp. 469-485, 2003.‌
[50]      N. Iqbal, A. Zerguine and N. Al-Dhahir, “Decision feedback equalization using particle swarm optimization,” Signal Processing, vol. 108, pp. 1-12, 2015.