An Overview of the Concepts, Classifications, and Methods of Population Initialization in Metaheuristic Algorithms
Subject Areas : Software Architecture
Mohammad Hassanzadeh
1
,
farshid keynia
2
1 - Department of Computer and Information Technology, Islamic Azad University, Kerman Branch, Kerman, IRAN
2 - Department of Energy, Institute of Science and High Technology and Environmental Sciences, Graduate University of Advanced Technology, Kerman, Iran;
Keywords: metaheuristic algorithms, Optimization Algorithms, Classification, Clustering,
Abstract :
Metaheuristic algorithms are typically population-based random search techniques. The general framework of a metaheuristic algorithm consisting of its main parts. The sections of a metaheuristic algorithm include setting algorithm parameters, population initialization, global search section, local search section, and checking the stopping conditions in a metaheuristic algorithm. In the parameters setting section, the user can monitor the performance of the metaheuristic algorithm and improve its performance according to the problem under consideration. In this study, an overview of the concepts, classifications, and different methods of population initialization in metaheuristic algorithms discussed in recent literature will be provided. Population initialization is a basic and common step between all metaheuristic algorithms. Therefore, in this study, an attempt has been made that the performance, methods, mechanisms, and categories of population initialization in metaheuristic algorithms. Also, the relationship between population initialization and other important parameters in performance and efficiency of metaheuristic algorithms such as search space size, population size, the maximum number of iteration, etc., which are mentioned and considered in the literature, are collected and presented in a regular format.
[1] Q. Li, S.-Y. Liu, and X.-S. Yang, 2020. Influence of initialization on the performance of metaheuristic optimizers, Applied Soft Computing, vol. 91, pp. 106193. https://doi.org/10.1016/j.asoc.2020.106193.
[2] B. Kazimipour, X. Li, and A. K. Qin, 2014, July in 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 2404-2411). IEEE. https://doi.org/10.1109/CEC.2014.6900624.
[3] H. Deng, L. Peng, H. Zhang, B. Yang, and Z. Chen, 2019. Ranking-based biased learning swarm optimizer for large-scale optimization, Information Sciences, vol. 493, pp. 120-137. https://doi.org/10.1016/j.ins.2019.04.037.
[4] Z. Lin, A. Matta, and S. Du, 2021. A Budget Allocation Strategy Minimizing the Sample Set Quantile for Initial Experimental Design, IISE Transactions, vol. 53, no. 1, pp. 39-57. https://doi.org/10.1080/24725854.2020.1748771.
[5] V. de Albuquerque Torreão, and R. Vimieiro, 2018, October in 2018 7th Brazilian Conference on Intelligent Systems (BRACIS) (pp. 25-30). IEEE. https://doi.org/10.1109/BRACIS.2018.00013.
[6] K. Łapa, K. Cpałka, and Y. Hayashi, 2017, June in International Conference on Artificial Intelligence and Soft Computing (pp. 380-393). Springer, Cham. https://doi.org/10.1007/978-3-319-59063-9_34.
[7] N. Henderson, M. de Sá Rêgo, J. Imbiriba, M. de Sá Rêgo, and W. F. Sacco, 2018. Testing the topographical global initialization strategy in the framework of an unconstrained optimization method, Optimization Letters, vol. 12, no. 4, pp. 727-741. https://doi.org/10.1007/s11590-017-1137-6.
[8] Vlašić, M. Ðurasević, and D. Jakobović, 2019. Improving genetic algorithm performance by population initialisation with dispatching rules, Computers & Industrial Engineering, vol. 137, pp. 106030. https://doi.org/10.1016/j.cie.2019.106030.
[9] K. Łapa, K. Cpałka, A. Przybył, and K. Grzanek, 2018, June in International Conference on Artificial Intelligence and Soft Computing (pp. 449-461). Springer. https://doi.org/10.1007/978-3-319-91253-0_42.
[10] M. Richards, and D. Ventura, 2004, July in IEEE Int. Joint. Conf. Neural (pp. 2309-2312). IEEE. https://doi.org/10.1109/IJCNN.2004.1380986.
[11] B. Kazimipour, X. Li, and A. K. Qin, 2014, July in 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 2585-2592). IEEE. https://doi.org/10.1109/CEC.2014.6900618.
[12] W. Zhao, L. Wang, and Z. Zhang, 2019. Supply-demand-based Optimization: a Novel Economics-inspired Algorithm for Global Optimization., IEEE Access, vol. 7, pp. 73182-73206. https://doi.org/10.1109/ACCESS.2019.2918753.
[13] A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja, and H. Chen, 2019. Harris hawks optimization: Algorithm and applications., Future Generation Computer Systems, vol. 97, pp. 849-872. https://doi.org/10.1016/j.future.2019.02.028.
[14] H. Bouchekara, 2020. Most Valuable Player Algorithm: a novel optimization algorithm inspired from sport., Operational Research, vol. 20, no. 1, pp. 139–195. https://doi.org/10.1007/s12351-017-0320-y.
[15] Aljarah, M. Mafarja, A. A. Heidari, H. Faris, and S. Mirjalili, 2020. Multi-verse optimizer: theory, literature review, and application in data clustering, Nature-Inspired Optimizers, pp. 123-141: Springer, Cham. https://doi.org/10.1007/978-3-030-12127-3_8.
[16] K. Zervoudakis, and S. Tsafarakis, 2020. A mayfly optimization algorithm, Computers & Industrial Engineering, pp. 106559. https://doi.org/10.1016/j.cie.2020.106559.
[17] Y. Xue, W. Jia, and A. X. Liu, 2019, June in 2019 IEEE Congress on Evolutionary Computation (CEC) (pp. 1572-1579). IEEE. https://doi.org/10.1109/CEC.2019.8790156.
[18] E. Keedwell, M. Brevilliers, L. Idoumghar, J. Lepagnot, and H. Rakhshani, 2018, October in 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (pp. 751-756). IEEE. https://doi.org/10.1109/SMC.2018.00136.
[19] A. Yahya, A. Osman, and M. S. El-Bashir, 2017. Rocchio algorithm-based particle initialization mechanism for effective PSO classification of high dimensional data, Swarm and evolutionary computation, vol. 34, pp. 18-32. https://doi.org/10.1016/j.swevo.2016.11.005.
[20] N. Dong, C.-H. Wu, W.-H. Ip, Z.-Q. Chen, C.-Y. Chan, and K.-L. Yung, 2012. An opposition-based chaotic GA/PSO hybrid algorithm and its application in circle detection, Computers & Mathematics with Applications, vol. 64, no. 6, pp. 1886-1902. https://doi.org/10.1016/j.camwa.2012.03.040.
[21] R. Poli, J. Kennedy, and T. Blackwell, 2007. Particle swarm optimization., Swarm intelligence, vol. 1, no. 1, pp. 33-57. https://doi.org/10.1007/s11721-007-0002-0.
[22] X.-S. Yang, and S. Deb, 2009, December Cuckoo search via Lévy flights., in 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), Coimbatore, India (pp. 210-214). https://doi.org/10.1109/NABIC.2009.5393690.
[23] H. Gandomi, X.-S. Yang, and A. H. Alavi, 2013. Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems., Engineering with computers, vol. 29, no. 1, pp. 17-35. https://doi.org/10.1007/s00366-011-0241-y.
[24] R. Storn, and K. Price, 1997. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces., Journal of global optimization, vol. 11, no. 4, pp. 341-359. https://doi.org/10.1023/A:1008202821328.
[25] S. Mirjalili, S. M. Mirjalili, and A. Lewis, 2014. Grey wolf optimizer., Advances in engineering software, vol. 69, pp. 46-61. https://doi.org/10.1016/j.advengsoft.2013.12.007.
[26] Z.-j. Teng, J.-l. Lv, and L.-w. Guo, 2019. An improved hybrid grey wolf optimization algorithm., Soft computing, vol. 23, no. 15, pp. 6617-6631. https://doi.org/10.1007/s00500-018-3310-y.
[27] P. Bratley, and B. L. Fox, 1988. Algorithm 659: Implementing Sobol's quasirandom sequence generator, ACM Transactions on Mathematical Software (TOMS), vol. 14, no. 1, pp. 88-100. https://doi.org/10.1145/42288.214372.
[28] W. F. Sacco, and A. C. Rios-Coelho, 2019. On Initial Populations of Differential Evolution for Practical Optimization Problems, Computational Intelligence, Optimization and Inverse Problems with Applications in Engineering, pp. 53-62: Springer, Cham. https://doi.org/10.1007/978-3-319-96433-1_3.
[29] M. Mitchell, 1995. Genetic algorithms: An overview., Complexity, vol. 1, no. 1, pp. 31-39. https://doi.org/10.1002/cplx.6130010108.
[30] Arauzo-Azofra, J. M. Benitez, and J. L. Castro, 2004,December in Proceedings of the fifth international conference on Recent Advances in Soft Computing (pp. 104-109).
[31] D. Karaboga, and B. Basturk, 2008. On the performance of artificial bee colony (ABC) algorithm., Applied soft computing, vol. 8, no. 1, pp. 687-697. https://doi.org/10.1016/j.asoc.2007.05.007.
[32] P. J. Gaidhane, and M. J. Nigam, 2018. A hybrid grey wolf optimizer and artificial bee colony algorithm for enhancing the performance of complex systems., Journal of computational science, vol. 27, pp. 284-302. https://doi.org/10.1016/j.jocs.2018.06.008.
[33] D. Simon, 2008. Biogeography-based optimization., IEEE transactions on evolutionary computation, vol. 12, no. 6, pp. 702-713. https://doi.org/10.1109/TEVC.2008.919004.
[34] X. Zhang, Q. Kang, J. Cheng, and X. Wang, 2018. A novel hybrid algorithm based on biogeography-based optimization and grey wolf optimizer., Applied Soft Computing, vol. 67, pp. 197-214. https://doi.org/10.1016/j.asoc.2018.02.049.
[35] S. Kazemzadeh Azad, 2018. Seeding the initial population with feasible solutions in metaheuristic optimization of steel trusses, Engineering Optimization, vol. 50, no. 1, pp. 89-105. https://doi.org/10.1080/0305215X.2017.1284833.
[36] E. Segredo, B. Paechter, C. Segura, and C. I. González-Vila, 2018. On the comparison of initialisation strategies in differential evolution for large scale optimisation, Optimization Letters, vol. 12, no. 1, pp. 221-234. https://doi.org/10.1007/s11590-017-1107-z.
[37] L. Skanderova, and A. Řehoř, 2014. Comparison of pseudorandom numbers generators and chaotic numbers generators used in differential evolution, Nostradamus 2014: Prediction, Modeling and Analysis of Complex Systems, pp. 111-121: Springer, Cham. https://doi.org/10.1007/978-3-319-07401-6_11.
[38] B. Kazimipour, X. Li, and A. K. Qin, 2013, June in 2013 IEEE Congress on Evolutionary Computation (pp. 2750-2757). IEEE. https://doi.org/10.1109/CEC.2013.6557902.
[39] B. Kazimipour, X. Li, and A. K. Qin, 2014, December in Asia-Pacific Conference on Simulated Evolution and Learning (pp. 479-490). Springer, Cham. https://doi.org/10.1007/978-3-319-13563-2_41.
[40] J. H. Halton, 1960. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numerische Mathematik, vol. 2, no. 1, pp. 84-90. https://doi.org/10.1007/BF01386213.
[41] H. Sloan, I. Sloan, and S. Joe, 1994, Lattice methods for multiple integration: Oxford University Press.
[42] L. Rajashekharan, and C. S. Velayutham, 2016. Is differential evolution sensitive to pseudo random number generator quality?–an investigation, Intelligent Systems Technologies and Applications, pp. 305-313: Springer, Cham. https://doi.org/10.1007/978-3-319-23036-8_26.
[43] H. Gandomi, and A. H. Alavi, December 2012. Krill herd: a new bio-inspired optimization algorithm., Communications in nonlinear science and numerical simulation, vol. 17, no. 12, pp. 4831-4845. https://doi.org/10.1016/j.cnsns.2012.05.010.
[44] T. Bradley, J. du Toit, R. Tong, M. Giles, and P. Woodhams, 2011. Parallelization techniques for random number generators, GPU Computing Gems Emerald Edition, pp. 231-246: Elsevier. https://doi.org/10.1016/B978-0-12-384988-5.00016-4.
[45] Y.-W. Leung, and Y. Wang, 2001. An orthogonal genetic algorithm with quantization for global numerical optimization, IEEE Transactions on Evolutionary computation, vol. 5, no. 1, pp. 41-53. https://doi.org/10.1109/4235.910464.
[46] S. Otto, and J. P. Denier, 2005, An introduction to programming and numerical methods in MATLAB.: Springer Science & Business Media. https://doi.org/10.1007/1-84628-133-4.
[47] J. R, 2019. A Hybrid Data Clustering Algorithm Using Modified Krill Herd Algorithm and K-MEANS, Journal of Advances in Computer Engineering and Technology, vol. 5, no. 2, pp. 93-106.
[48] N. Damya, and F. Soleimanian Gharehchopogh, 2020. An Improved Bat Algorithm based on Whale Optimization Algorithm for Data Clustering, Journal of Advances in Computer Engineering and Technology, pp. -.
[49] F. Soleimanian Gharehchopogh, and S. Haggi, 2020. An Optimization K-Modes Clustering Algorithm with Elephant Herding Optimization Algorithm for Crime Clustering, Journal of Advances in Computer Engineering and Technology, vol. 6, no. 2, pp. 79-90.
[50] H. Zheng, Y. Zheng, and P. Li, 2013, May in 2013 IEEE International Symposium on Industrial Electronics (pp. 1-5). IEEE. https://doi.org/10.1109/ISIE.2013.6563726.
[51] L. Peng, Y. Wang, and G. Dai, 2010, December in 2010 3rd International Symposium on Parallel Architectures, Algorithms and Programming (pp. 239-246). IEEE. https://doi.org/10.1109/PAAP.2010.61.
[52] R. Wang, L. Ma, T. Zhang, S. Cheng, and Y. Shi, 2019, June in 2019 IEEE Congress on Evolutionary Computation (CEC) (pp. 262-270). IEEE. https://doi.org/10.1109/CEC.2019.8790307.
[53] S. Mahdavi, S. Rahnamayan, and K. Deb, 2018. Opposition based learning: A literature review, Swarm and evolutionary computation, vol. 39, pp. 1-23. https://doi.org/10.1016/j.swevo.2017.09.010.
[54] Q. Xu, L. Wang, N. Wang, X. Hei, and L. Zhao, 2014. A review of opposition-based learning from 2005 to 2012, Engineering Applications of Artificial Intelligence, vol. 29, pp. 1-12. https://doi.org/https://doi.org/10.1016/j.engappai.2013.12.004.
[55] D. Bajer, G. Martinović, and J. Brest, 2016. A population initialization method for evolutionary algorithms based on clustering and Cauchy deviates, Expert Systems with Applications, vol. 60, pp. 294-310. https://doi.org/10.1016/j.eswa.2016.05.009.
[56] M. Ergezer, and D. Simon, 2014. Mathematical and experimental analyses of oppositional algorithms, IEEE transactions on cybernetics, vol. 44, no. 11, pp. 2178-2189. https://doi.org/10.1109/TCYB.2014.2303117.
[57] J. MacQueen, 1967, June in Proceedings of the fifth Berkeley symposium on mathematical statistics and probability (pp. 281-297). Oakland, CA, USA.
[58] Q. Du, V. Faber, and M. Gunzburger, 1999. Centroidal Voronoi tessellations: Applications and algorithms, SIAM review, vol. 41, no. 4, pp. 637-676. https://doi.org/10.1137/S0036144599352836.
[59] S. Lloyd, 1982. Least squares quantization in PCM, IEEE transactions on information theory, vol. 28, no. 2, pp. 129-137. https://doi.org/10.1109/TIT.1982.1056489.
[60] F. Barenghi. CHAOS WITH MATLAB, Matlab tutorial, last accessed on January 17 , 2020; http://www.mas.ncl.ac.uk/~ncfb/mat3.pdf.
[61] S. Wessing, 2019. Proper initialization is crucial for the Nelder–Mead simplex search, Optimization Letters, vol. 13, no. 4, pp. 847-856. https://doi.org/10.1007/s11590-018-1284-4.
[62] E. Segredo, E. Lalla-Ruiz, E. Hart, and S. Voß, 2020. A similarity-based neighbourhood search for enhancing the balance exploration–exploitation of differential evolution, Computers & Operations Research, vol. 117, pp. 104871. https://doi.org/10.1016/j.cor.2019.104871.