An Improved particle swarm optimization based on lévy flight and simulated annealing for high dimensional optimization problem

(1) Samar Bashath Mail (Department of Computer Science, International Islamic University Malaysia, Malaysia)
(2) * Amelia Ritahani Ismail Mail (Department of Computer Science, International Islamic University Malaysia, Malaysia)
(3) Ali A Alwan Mail (Department of Computer Science, International Islamic University Malaysia, Malaysia)
(4) Amir Aatieff Amir Hussin Mail (Department of Computer Science, International Islamic University Malaysia, Malaysia)
*corresponding author

Abstract


Particle swarm optimization (PSO) is a simple metaheuristic method to implement with robust performance. PSO is regarded as one of the numerous researchers' most well-studied algorithms. However, two of its most fundamental problems remain unresolved. PSO converges onto the local optimum for high-dimensional optimization problems, and it has slow convergence speeds. This paper introduces a new variant of a particle swarm optimization algorithm utilizing Lévy flight-McCulloch, and fast simulated annealing (PSOLFS). The proposed algorithm uses two strategies to address high-dimensional problems: hybrid PSO to define the global search area and fast simulated annealing to refine the visited search region. In this paper, PSOLFS is designed based on a balance between exploration and exploitation. We evaluated the algorithm on 16 benchmark functions for 500 and 1,000 dimension experiments. On 500 dimensions, the algorithm obtains the optimal value on 14 out of 16 functions. On 1,000 dimensions, the algorithm obtains the optimal value on eight benchmark functions and is close to optimal on four others. We also compared PSOLFS with another five PSO variants regarding convergence accuracy and speed. The results demonstrated higher accuracy and faster convergence speed than other PSO variants. Moreover, the results of the Wilcoxon test show a significant difference between PSOLFS and the other PSO variants. Our experiments' findings show that the proposed method enhances the standard PSO by avoiding the local optimum and improving the convergence speed.

Keywords


Particle Swarm Optimization; Levy Flight Optimization; Simulated Annealing; High Dimensions

   

DOI

https://doi.org/10.26555/ijain.v8i1.818
      

Article metrics

Abstract views : 136 | PDF views : 42

   

Cite

   

Full Text

Download

References


[1] A. F. J. Levi and S. Haas, Eds., “Global optimization algorithms,” in Optimal Device Design, Cambridge: Cambridge University Press, 2008, pp. 262–276. doi: 10.1017/CBO9780511691881.010

[2] S. Mahdavi, M. E. Shiri, and S. Rahnamayan, “Metaheuristics in large-scale global continues optimization: A survey,” Inf. Sci. (Ny)., vol. 295, pp. 407–428, Feb. 2015, doi: 10.1016/j.ins.2014.10.042.

[3] E. K. Nyarko, R. Cupec, and D. Filko, “A comparison of several heuristic algorithms for solving high dimensional optimization problems,” Int. J. Electr. Comput. Eng. Syst., vol. 5, no. 1., pp. 1–8, 2014. Available at: Google Scholar.

[4] N. Quirante and J. A. Caballero, “Large scale optimization of a sour water stripping plant using surrogate models,” Comput. Chem. Eng., vol. 92, pp. 143–162, Sep. 2016, doi: 10.1016/j.compchemeng.2016.04.039.

[5] H. Wei, X. Du, L. Yang, and Y. Yang, “Entransy dissipation based optimization of a large-scale dry cooling system,” Appl. Therm. Eng., vol. 125, pp. 254–265, Oct. 2017, doi: 10.1016/j.applthermaleng.2017.06.117.

[6] Y. Zhao, Y. Yuan, F. Nie, and Q. Wang, “Spectral clustering based on iterative optimization for large-scale and high-dimensional data,” Neurocomputing, vol. 318, pp. 227–235, Nov. 2018, doi: 10.1016/j.neucom.2018.08.059.

[7] L. Sun, L. Lin, H. Li, and M. Gen, “Large scale flexible scheduling optimization by a distributed evolutionary algorithm,” Comput. Ind. Eng., vol. 128, pp. 894–904, Feb. 2019, doi: 10.1016/j.cie.2018.09.025.

[8] D. E. Mazzuco et al., “A concept for simulation-based optimization in Vehicle Routing Problems,” IFAC-PapersOnLine, vol. 51, no. 11, pp. 1720–1725, 2018, doi: 10.1016/j.ifacol.2018.08.208.

[9] A. Singh and N. Dulal, “A Survey on Metaheuristics for Solving Large Scale Optimization Problems,” Int. J. Comput. Appl., vol. 170, no. 5, pp. 1–7, Jul. 2017, doi: 10.5120/ijca2017914839.

[10] X. Lai and Y. Zhou, “An adaptive parallel particle swarm optimization for numerical optimization problems,” Neural Comput. Appl., vol. 31, no. 10, pp. 6449–6467, Oct. 2019, doi: 10.1007/s00521-018-3454-9.

[11] B. Goertzel, “The Embodied Communication Prior: A characterization of general intelligence in the context of Embodied social interaction,” in 2009 8th IEEE International Conference on Cognitive Informatics, 2009, pp. 38–43, doi: 10.1109/COGINF.2009.5250687.

[12] W. Guo, C. Si, Y. Xue, Y. Mao, L. Wang, and Q. Wu, “A Grouping Particle Swarm Optimizer with Personal-Best-Position Guidance for Large Scale Optimization,” IEEE/ACM Trans. Comput. Biol. Bioinforma., vol. 15, no. 6, pp. 1904–1915, Nov. 2018, doi: 10.1109/TCBB.2017.2701367.

[13] S. Chen, J. Montgomery, and A. Bolufé-Röhler, “Measuring the curse of dimensionality and its effects on particle swarm optimization and differential evolution,” Appl. Intell., vol. 42, no. 3, pp. 514–526, Apr. 2015, doi: 10.1007/s10489-014-0613-2.

[14] X.-S. Yang, “Swarm intelligence based algorithms: a critical analysis,” Evol. Intell., vol. 7, no. 1, pp. 17–28, Apr. 2014, doi: 10.1007/s12065-013-0102-2.

[15] J. Wen, H. Ma, and X. Zhang, “Optimization of the occlusion strategy in visual tracking,” Tsinghua Sci. Technol., vol. 21, no. 2, pp. 221–230, Apr. 2016, doi: 10.1109/TST.2016.7442504.

[16] R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization,” Swarm Intell., vol. 1, no. 1, pp. 33–57, Oct. 2007, doi: 10.1007/s11721-007-0002-0.

[17] M. Juneja and S. K. Nagar, “Particle swarm optimization algorithm and its parameters: A review,” in 2016 International Conference on Control, Computing, Communication and Materials (ICCCCM), 2016, pp. 1–5, doi: 10.1109/ICCCCM.2016.7918233.

[18] F. Zhu, D. Chen, and F. Zou, “A novel hybrid dynamic fireworks algorithm with particle swarm optimization,” Soft Comput., vol. 25, no. 3, pp. 2371–2398, Feb. 2021, doi: 10.1007/s00500-020-05308-6.

[19] D. Wang, D. Tan, and L. Liu, “Particle swarm optimization algorithm: an overview,” Soft Comput., vol. 22, no. 2, pp. 387–408, Jan. 2018, doi: 10.1007/s00500-016-2474-6.

[20] M. N. Ab Wahab, S. Nefti-Meziani, and A. Atyabi, “A Comprehensive Review of Swarm Optimization Algorithms,” PLoS One, vol. 10, no. 5, p. e0122827, May 2015, doi: 10.1371/journal.pone.0122827.

[21] J. Ding, Q. Wang, Q. Zhang, Q. Ye, and Y. Ma, “A Hybrid Particle Swarm Optimization-Cuckoo Search Algorithm and Its Engineering Applications,” Math. Probl. Eng., vol. 2019, pp. 1–12, Mar. 2019, doi: 10.1155/2019/5213759.

[22] Y. Ning, Z. Peng, Y. Dai, D. Bi, and J. Wang, “Enhanced particle swarm optimization with multi-swarm and multi-velocity for optimizing high-dimensional problems,” Appl. Intell., vol. 49, no. 2, pp. 335–351, Feb. 2019, doi: 10.1007/s10489-018-1258-3.

[23] A. F. Ali and M. A. Tawhid, “A hybrid particle swarm optimization and genetic algorithm with population partitioning for large scale optimization problems,” Ain Shams Eng. J., vol. 8, no. 2, pp. 191–206, Jun. 2017, doi: 10.1016/j.asej.2016.07.008.

[24] F. Javidrad and M. Nazari, “A new hybrid particle swarm and simulated annealing stochastic optimization method,” Appl. Soft Comput., vol. 60, pp. 634–654, Nov. 2017, doi: 10.1016/j.asoc.2017.07.023.

[25] S. Bashath and A. R. Ismail, “Improved Particle Swarm Optimization By Fast Simulated Annealing Algorithm,” in 2019 International Conference of Artificial Intelligence and Information Technology (ICAIIT), 2019, pp. 297–301, doi: 10.1109/ICAIIT.2019.8834515.

[26] R. Jensi and G. W. Jiji, “An enhanced particle swarm optimization with levy flight for global optimization,” Appl. Soft Comput., vol. 43, pp. 248–261, Jun. 2016, doi: 10.1016/j.asoc.2016.02.018.

[27] D. Sedighizadeh, E. Masehian, M. Sedighizadeh, and H. Akbaripour, “GEPSO: A new generalized particle swarm optimization algorithm,” Math. Comput. Simul., vol. 179, pp. 194–212, Jan. 2021, doi: 10.1016/j.matcom.2020.08.013.

[28] Z. Li, W. Wang, Y. Yan, and Z. Li, “PS–ABC: A hybrid algorithm based on particle swarm and artificial bee colony for high-dimensional optimization problems,” Expert Syst. Appl., vol. 42, no. 22, pp. 8881–8895, Dec. 2015, doi: 10.1016/j.eswa.2015.07.043.

[29] H. Zhang, J. Sun, T. Liu, K. Zhang, and Q. Zhang, “Balancing exploration and exploitation in multiobjective evolutionary optimization,” Inf. Sci. (Ny)., vol. 497, pp. 129–148, Sep. 2019, doi: 10.1016/j.ins.2019.05.046.

[30] M. R. Bonyadi and Z. Michalewicz, “Particle Swarm Optimization for Single Objective Continuous Space Problems: A Review,” Evol. Comput., vol. 25, no. 1, pp. 1–54, Mar. 2017, doi: 10.1162/EVCO_r_00180.

[31] S. S. Dash, S. K. Nayak, and D. Mishra, “ABC Versus PSO: A Comparative Study and Analysis on Optimization Aptitude,” 2021, pp. 527–544. doi: 10.1007/978-981-16-0695-3_50

[32] H.-K. Jung, J. T. Kim, T. Sahama, and C.-H. Yang, Eds., Future Information Communication Technology and Applications, vol. 235. Dordrecht: Springer Netherlands, 2013. doi: 10.1007/978-94-007-6516-0

[33] A. R. Ismail, N. A. Aziz, A. M. Ralib, N. Z. Abidin, and S. S. Bashath, “A particle swarm optimization levy flight algorithm for imputation of missing creatinine dataset,” Int. J. Adv. Intell. Informatics, vol. 7, no. 2, p. 225, Jul. 2021, doi: 10.26555/ijain.v7i2.677.

[34] X.-S. Yang and Suash Deb, “Cuckoo Search via Lévy flights,” in 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 2009, pp. 210–214, doi: 10.1109/NABIC.2009.5393690.

[35] M. Abdel-Basset, A.-N. Hessin, and L. Abdel-Fatah, “A comprehensive study of cuckoo-inspired algorithms,” Neural Comput. Appl., vol. 29, no. 2, pp. 345–361, Jan. 2018, doi: 10.1007/s00521-016-2464-8.

[36] M. Leccardi, “Comparison of three algorithms for Levy noise generation,” in Proceedings of fifth EUROMECH nonlinear dynamics conference, 2005, pp. 1–14. Available at: Google Scholar.

[37] X.-S. Yang and S. Deb, “Cuckoo search: recent advances and applications,” Neural Comput. Appl., vol. 24, no. 1, pp. 169–174, Jan. 2014, doi: 10.1007/s00521-013-1367-1.

[38] S. Chakraborty et al., “Modified cuckoo search algorithm in microscopic image segmentation of hippocampus,” Microsc. Res. Tech., vol. 80, no. 10, pp. 1051–1072, Oct. 2017, doi: 10.1002/jemt.22900.

[39] H. Soneji and R. C. Sanghvi, “Towards the improvement of Cuckoo search algorithm,” in 2012 World Congress on Information and Communication Technologies, 2012, pp. 878–883, doi: 10.1109/WICT.2012.6409199.

[40] L. Ingber, “Very fast simulated re-annealing,” Math. Comput. Model., vol. 12, no. 8, pp. 967–973, 1989, doi: 10.1016/0895-7177(89)90202-1.

[41] A. M. Zain, H. Haron, and S. Sharif, “Simulated annealing to estimate the optimal cutting conditions for minimizing surface roughness in end milling Ti-6Al-4V,” Mach. Sci. Technol., vol. 14, no. 1, pp. 43–62, Feb. 2010, doi: 10.1080/10910340903586558.

[42] S. N. Kadry and A. El Hami, “A New Hybrid Simulated Annealing Algorithm for Large Scale Global Optimization,” Int. J. Manuf. Mater. Mech. Eng., vol. 5, no. 3, pp. 24–36, Jul. 2015, doi: 10.4018/IJMMME.2015070102.

[43] A. Peng, “Particle Swarm Optimization Algorithm Based on Chaotic Theory and Adaptive Inertia Weight,” J. Nanoelectron. Optoelectron., vol. 12, no. 4, pp. 404–408, Apr. 2017, doi: 10.1166/jno.2017.2033.

[44] S. N. Chegini, A. Bagheri, and F. Najafi, “PSOSCALF: A new hybrid PSO based on Sine Cosine Algorithm and Levy flight for solving optimization problems,” Appl. Soft Comput., vol. 73, pp. 697–726, Dec. 2018, doi: 10.1016/j.asoc.2018.09.019.

[45] X. Shen, Z. Chi, J. Yang, C. Chen, and Z. Chi, “Particle Swarm Optimization with Dynamic Adaptive Inertia Weight,” in 2010 International Conference on Challenges in Environmental Science and Computer Engineering, 2010, pp. 287–290, doi: 10.1109/CESCE.2010.16.

[46] R. K. Huda and H. Banka, “New efficient initialization and updating mechanisms in PSO for feature selection and classification,” Neural Comput. Appl., vol. 32, no. 8, pp. 3283–3294, Apr. 2020, doi: 10.1007/s00521-019-04395-3.

[47] H. Wang, W. Wang, and Z. Wu, “Particle swarm optimization with adaptive mutation for multimodal optimization,” Appl. Math. Comput., vol. 221, pp. 296–305, Sep. 2013, doi: 10.1016/j.amc.2013.06.074.

[48] T. Nishio, J. Kushida, A. Hara, and T. Takahama, “Adaptive particle swarm optimization with multi-dimensional mutation,” in 2015 IEEE 8th International Workshop on Computational Intelligence and Applications (IWCIA), 2015, pp. 131–136, doi: 10.1109/IWCIA.2015.7449476.

[49] E. H. Houssein, M. R. Saad, F. A. Hashim, H. Shaban, and M. Hassaballah, “Lévy flight distribution: A new metaheuristic algorithm for solving engineering optimization problems,” Eng. Appl. Artif. Intell., vol. 94, p. 103731, Sep. 2020, doi: 10.1016/j.engappai.2020.103731.

[50] H. Haklı and H. Uğuz, “A novel particle swarm optimization algorithm with Levy flight,” Appl. Soft Comput., vol. 23, pp. 333–345, Oct. 2014, doi: 10.1016/j.asoc.2014.06.034.

[51] L. Yi, “Study on an Improved PSO Algorithm and its Application for Solving Function Problem,” Int. J. Smart Home, vol. 10, no. 3, pp. 51–62, Mar. 2016, doi: 10.14257/ijsh.2016.10.3.06.

[52] “Autonomous Groups Particle Swarm Optimization Algorithm Based On Exponential Decreasing Inertia Weight,” Rev. Tec. La Fac. Ing. Univ. Del Zulia, vol. 39, no. 7, Nov. 2016, doi: 10.21311/001.39.7.36.

[53] W. Wang, J.-M. Wu, and J.-H. Liu, “A Particle Swarm Optimization Based on Chaotic Neighborhood Search to Avoid Premature Convergence,” in 2009 Third International Conference on Genetic and Evolutionary Computing, 2009, pp. 633–636, doi: 10.1109/WGEC.2009.168.

[54] M. Chen, T. Wang, J. Feng, Y.-Y. Tang, and L.-X. Zhao, “A Hybrid Particle Swarm Optimization Improved by Mutative Scale Chaos Algorithm,” in 2012 Fourth International Conference on Computational and Information Sciences, 2012, pp. 321–324, doi: 10.1109/ICCIS.2012.19.

[55] Z. Du, S. Li, Y. Sun, and N. Li, “Adaptive particle swarm optimization algorithm based on levy flights mechanism,” in 2017 Chinese Automation Congress (CAC), 2017, pp. 479–484, doi: 10.1109/CAC.2017.8242815.

[56] Z. Lin and Q. Zhang, “An effective hybrid particle swarm optimization with Gaussian mutation,” J. Algorithm. Comput. Technol., vol. 11, no. 3, pp. 271–280, Sep. 2017, doi: 10.1177/1748301817710923.

[57] H. Shi et al., “Oscillatory Particle Swarm Optimizer,” Appl. Soft Comput., vol. 73, pp. 316–327, Dec. 2018, doi: 10.1016/j.asoc.2018.08.037.

[58] D. Li, W. Guo, A. Lerch, Y. Li, L. Wang, and Q. Wu, “An adaptive particle swarm optimizer with decoupled exploration and exploitation for large scale optimization,” Swarm Evol. Comput., vol. 60, p. 100789, Feb. 2021, doi: 10.1016/j.swevo.2020.100789.

[59] M. S. Kıran and M. Gündüz, “A recombination-based hybridization of particle swarm optimization and artificial bee colony algorithm for continuous optimization problems,” Appl. Soft Comput., vol. 13, no. 4, pp. 2188–2203, Apr. 2013, doi: 10.1016/j.asoc.2012.12.007.

[60] L. Idoumghar, M. Melkemi, R. Schott, and M. I. Aouad, “Hybrid PSO-SA Type Algorithms for Multimodal Function Optimization and Reducing Energy Consumption in Embedded Systems,” Appl. Comput. Intell. Soft Comput., vol. 2011, pp. 1–12, 2011, doi: 10.1155/2011/138078.

[61] M. Basu, P. Deb, and G. Garai, “Hybrid of particle swarm optimization and simulated annealing for multidimensional function optimization,” Int. J. Inf. Technol., vol. 20, no. 1, pp. 112–120, 2014. Available at: Google Scholar.

[62] Qian Wang, Pei-hong Wang, and Zhi-gang Su, “A hybrid search strategy based particle swarm optimization algorithm,” in 2013 IEEE 8th Conference on Industrial Electronics and Applications (ICIEA), 2013, pp. 301–306, doi: 10.1109/ICIEA.2013.6566384.

[63] W. Phuchan, B. Kruatrachue, and K. Siriboon, “Hybrid multi-swarm with Harmony Search algorithm,” in 2017 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), 2017, pp. 541–544, doi: 10.1109/ECTICon.2017.8096294.

[64] F. Wang, H. Zhang, K. Li, Z. Lin, J. Yang, and X.-L. Shen, “A hybrid particle swarm optimization algorithm using adaptive learning strategy,” Inf. Sci. (Ny)., vol. 436–437, pp. 162–177, Apr. 2018, doi: 10.1016/j.ins.2018.01.027.

[65] Q. Cui et al., “Globally-optimal prediction-based adaptive mutation particle swarm optimization,” Inf. Sci. (Ny)., vol. 418–419, pp. 186–217, Dec. 2017, doi: 10.1016/j.ins.2017.07.038.

[66] M. Gholamian and M. R. Meybodi, “Enhanced comprehensive learning cooperative particle swarm optimization with fuzzy inertia weight (ECLCFPSO-IW),” in 2015 AI & Robotics (IRANOPEN), 2015, pp. 1–7, doi: 10.1109/RIOS.2015.7270730.




Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571  (print) | 2548-3161 (online)
Organized by Informatics Department - Universitas Ahmad Dahlan, and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: ijain@uad.ac.id (paper handling issues)
    info@ijain.org, andri.pranolo.id@ieee.org (publication issues)

View IJAIN Stats

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0