Inertia weight control strategies for particle swarm optimization
Tóm tắt
Particle swarm optimization (PSO) is a population-based, stochastic optimization technique inspired by the social dynamics of birds. The PSO algorithm is rather sensitive to the control parameters, and thus, there has been a significant amount of research effort devoted to the dynamic adaptation of these parameters. The focus of the adaptive approaches has largely revolved around adapting the inertia weight as it exhibits the clearest relationship with the exploration/exploitation balance of the PSO algorithm. However, despite the significant amount of research efforts, many inertia weight control strategies have not been thoroughly examined analytically nor empirically. Thus, there are a plethora of choices when selecting an inertia weight control strategy, but no study has been comprehensive enough to definitively guide the selection. This paper addresses these issues by first providing an overview of 18 inertia weight control strategies. Secondly, conditions required for the strategies to exhibit convergent behaviour are derived. Finally, the inertia weight control strategies are empirically examined on a suite of 60 benchmark problems. Results of the empirical investigation show that none of the examined strategies, with the exception of a randomly selected inertia weight, even perform on par with a constant inertia weight.
Tài liệu tham khảo
Bansal, J. C., Singh, P. K., Saraswat, M., Vermam A., Jadon, S. S., & Abraham, A. (2011). Inertia weight strategies in particle swarm. In Proceedings of the third world congress on nature and biologically inspired computing (pp. 633–640). IEEE.
Beielstein, T., Parsopoulos, K. E., & Vrahatis, M. N. (2002). Tuning PSO parameters through sensitivity analysis. Technical report. Universitat Dortmund.
Bonyadi, M. R., & Michalewicz, Z. (2016). Particle swarm optimization for single objective continuous space problems: A review. Evolutionary Computation. doi:10.1162/EVCO_r_00180.
Carlisle, A., & Dozier, G. (2001). An off-the-shelf PSO. In Proceedings of the workshop on particle swarm optimization (pp. 1–6). Indianapolis.
Chatterjee, A., & Siarry, P. (2006). Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization. Computers & Operations Research, 33(3), 859–871.
Chauhan, P., Deep, K., & Pant, M. (2013). Novel inertia weight strategies for particle swarm optimization. Memetic Computing, 5(3), 229–251.
Chen, G., Min, Z., Jia, J., & Xinbo, H. (2006). Natural exponential inertia weight strategy in particle swarm optimization. In Proceedings of the 6th world congress on intelligent control and automation (Vol. 1, pp. 3672–3675).
Chen, H. H., Li, G. Q., & Liao, H. L. (2009). A self-adaptive improved particle swarm optimization algorithm and its application in available transfer capability calculation. In Proceedings of the fifth international conference on natural computation (Vol. 3, pp. 200–205).
Cleghorn, C. W., & Engelbrecht, A. P. (2014a). Particle swarm convergence: An empirical investigation. In Proceedings of the 2014 IEEE congress on evolutionary computation (pp. 2524–2530).
Cleghorn, C. W., & Engelbrecht, A. P. (2014b). Particle swarm convergence: Standardized analysis and topological influence. In M. Dorigo, M. Birattari, S. Garnier, H. Hamann, M. de Oca, C. Solnon, & T. Sttzle (Eds.), Swarm intelligence (Vol. 8667, pp. 134–145). Lecture Notes in Computer Science. Springer International Publishing.
Cleghorn, C. W., & Engelbrecht, A. P. (2015). Particle swarm variants: Standardized convergence analysis. Swarm Intelligence, 9(2–3), 177–203.
de Oca, M., Pena, J., Stutzle, T., Pinciroli, C., & Dorigo, M. (2009). Heterogeneous particle swarm optimizers. In Proceedings of the 2009 IEEE congress on evolutionary computation (pp. 698–705).
Deep, K., Chauhan, P., & Pant, M. (2011). A new fine grained inertia weight particle swarm optimization. In Proceedings of the 2011 world congress on information and communication technologies (pp. 424–429). IEEE.
Eberhart, R., & Shi, Y. (2000). Comparing inertia weights and constriction factors in particle swarm optimization. In Proceedings of the 2000 IEEE congress on evolutionary computation (Vol. 1, pp. 84–88). IEEE.
Eberhart, R. C., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings of the sixth international symposium on micro machine and human science (Vol. 1, pp. 39–43). New York, NY.
Eberhart, R. C., & Shi, Y. (2001). Tracking and optimizing dynamic systems with particle swarms. In Proceedings of the 2001 IEEE congress on evolutionary computation (Vol. 1, pp. 94–100). IEEE.
Engelbrecht, A. P. (2012). Particle swarm optimization: Velocity initialization. In Proceedings of the 2012 IEEE congress on evolutionary computation (pp. 1–8).
Engelbrecht, A. P. (2013a). Particle swarm optimization: Global best or local best? In Proceedings of the 2013 BRICS congress on computational intelligence and 11th Brazilian congress on computational intelligence (pp. 124–135). IEEE.
Engelbrecht, A. P. (2013b). Roaming behavior of unconstrained particles. In Proceedings of the 2013 BRICS congress on computational intelligence and 11th Brazilian congress on computational intelligence (pp. 104–111).
Fan, S. K. S., & Chiu, Y. Y. (2007). A decreasing inertia weight particle swarm optimizer. Engineering Optimization, 39(2), 203–228.
Feng, Y., Teng, G. F., Wang, A. X., & Yao, Y. M. (2007). Chaotic inertia weight in particle swarm optimization. In Proceedings of the second international conference on innovative computing. Information and control (pp. 475–479). IEEE.
Gao, Y. L., An, X. H., & Liu, J. M. (2008). A particle swarm optimization algorithm with logarithm decreasing inertia weight and chaos mutation. In Proceedings of the 2008 international conference on computational intelligence and security (pp. 61–65). IEEE.
Garden, R. W., & Engelbrecht, A. P. (2014). Analysis and classification of optimisation benchmark functions and benchmark suites. In Proceedings of the 2014 IEEE congress on evolutionary computation (Vol. 1, pp. 1641–1649).
Harrison, K. R., Engelbrecht, A. P., & Ombuki-Berman, B. M. (2016). The sad state of self-adaptive particle swarm optimizers. In Proceedings of the 2016 IEEE congress on evolutionary computation (pp. 431–439). IEEE.
Hu, J. Z., Xu, J., Wang, J. Q., & Xu, T. (2009). Research on particle swarm optimization with dynamic inertia weight. In Proceedings of the 2009 international conference on management and service science (Vol. 3, pp. 1–4).
Jiao, B., Lian, Z., & Gu, X. (2008). A dynamic inertia weight particle swarm optimization algorithm. Chaos, Solitons and Fractals, 37(3), 698–705.
Kennedy, J., & Eberhart, R. C. (1995). Particle swarm optimization. In Proceedings of the 1995 IEEE international joint conference on neural networks (Vol. IV, pp 1942–1948).
Kentzoglanakis, K., & Poole, M. (2009). Particle swarm optimization with an oscillating inertia weight. In Proceedings of the 11th annual conference on genetic and evolutionary computation (pp. 1749–1750). ACM.
Lei, K., Qiu, Y., & He, Y. (2006). A new adaptive well-chosen inertia weight strategy to automatically harmonize global and local search ability in particle swarm optimization. In Proceedings of the 1st international symposium on systems and control in aerospace and astronautics (pp. 977–980). IEEE.
Leonard, B. J., & Engelbrecht, A. P. (2013). On the optimality of particle swarm parameters in dynamic environments. In Proceedings of the 2013 IEEE congress on evolutionary computation (pp. 1564–1569). doi:10.1109/CEC.2013.6557748.
Li, C., Yang, S., & Nguyen, T. T. (2012). A self-learning particle swarm optimizer for global optimization problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 42(3), 627–646.
Li, Z., & Tan, G. (2008). A self-adaptive mutation-particle swarm optimization algorithm. In Proceedings of the fourth international conference on natural computation (Vol. 1, pp. 30–34). IEEE.
Liu, B., Wang, L., Jin, Y. H., Tang, F., & Huang, D. X. (2005). Improved particle swarm optimization combined with chaos. Chaos, Solitons & Fractals, 25(5), 1261–1271.
Liu, Q., Wei, W., Yuan, H., Zhan, Z. H., & Li, Y. (2016). Topology selection for particle swarm optimization. Information Sciences, 363(2015), 154–173. doi:10.1016/j.ins.2016.04.050.
Lynn, N., & Suganthan, P. N. (2015). Heterogeneous comprehensive learning particle swarm optimization with enhanced exploration and exploitation. Swarm and Evolutionary Computation, 24, 11–24.
Mascia, F., Pellegrini, P., Stützle, T., & Birattari, M. (2014). An analysis of parameter adaptation in reactive tabu search. International Transactions in Operational Research, 21(1), 127–152.
Nepomuceno, F. V., & Engelbrecht, A. P. (2013). A self-adaptive heterogeneous PSO for real-parameter optimization. In Proceedings of the 2013 IEEE congress on evolutionary computation (pp. 361–368). IEEE.
Nickabadi, A., Ebadzadeh, M. M., & Safabakhsh, R. (2011). A novel particle swarm optimization algorithm with adaptive inertia weight. Applied Soft Computing, 11(4), 3658–3670.
Pandey, B. B., Debbarma, S., & Bhardwaj, P. (2015). Particle swarm optimization with varying inertia weight for solving nonlinear optimization problem. In Proceedings of the 2015 international conference on electrical, electronics, signals, communication and optimization (pp. 1–5). IEEE.
Panigrahi, B. K., Ravikumar Pandi, V., & Das, S. (2008). Adaptive particle swarm optimization approach for static and dynamic economic load dispatch. Energy Conversion and Management, 49(6), 1407–1415.
Pellegrini, P., Stützle, T., & Birattari, M. (2012). A critical analysis of parameter adaptation in ant colony optimization. Swarm Intelligence, 6(1), 23–48.
Poli, R. (2009). Mean and variance of the sampling distribution of particle swarm optimizers during stagnation. IEEE Transactions on Evolutionary Computation, 13(4), 712–721.
Poli, R., & Broomhead, D. (2007). Exact analysis of the sampling distribution for the canonical particle swarm optimiser and its convergence during stagnation. In Proceedings of the 9th annual conference on genetic and evolutionary computation (pp. 134–141). New York, NY: ACM.
Salomon, R. (1996). Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. BioSystems, 39(3), 263–278.
Shi, Y., & Eberhart, R. (1998). A modified particle swarm optimizer. In Proceedings of the 1998 IEEE international conference on evolutionary computation, (pp. 69–73).
Shi, Y., & Eberhart, R. C. (1999). Empirical study of particle swarm optimization. In Proceedings of the 1999 IEEE congress on evolutionary computation (Vol. 3, pp. 1945–1950). IEEE.
Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K., Chen, Y., & Auger, A., et al. (2005). Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization. Technical report. Nanyang Technological University.
Taherkhani, M., & Safabakhsh, R. (2016). A novel stability-based adaptive inertia weight for particle swarm optimization. Applied Soft Computing, 38(4), 281–295.
Tanweer, M. R., Suresh, S., & Sundararajan, N. (2015). Self regulating particle swarm optimization algorithm. Information Sciences, 294, 182–202.
Trelea, I. C. (2003). The particle swarm optimization algorithm: Convergence analysis and parameter selection. Information Processing Letters, 85(6), 317–325.
Van Den Bergh, F., & Engelbrecht, A. P. (2006). A study of particle swarm optimization particle trajectories. Information Sciences, 176(8), 937–971.
Van Zyl, E., & Engelbrecht, A. (2014). Comparison of self-adaptive particle swarm optimizers. In Proceedings of the 2014 IEEE symposium on swarm intelligence (pp. 48–56).
Wang, Y., Li, B., Weise, T., Wang, J., Yuan, B., & Tian, Q. (2011). Self-adaptive learning based particle swarm optimization. Information Sciences, 181(20), 4515–4538.
Xu, G. (2013). An adaptive parameter tuning of particle swarm optimization algorithm. Applied Mathematics and Computation, 219(9), 4560–4569.
Yang, C., Gao, W., Liu, N., & Song, C. (2015). Low-discrepancy sequence initialized particle swarm optimization algorithm with high-order nonlinear time-varying inertia weight. Applied Soft Computing, 29, 386–394.