A partition-based convergence framework for population-based optimization algorithms. (English) Zbl 07838292
Summary: Population-based optimization algorithms, such as genetic algorithm and particle swarm optimization, have become a class of important algorithms for solving global optimization problems. However, there is an issue that the global convergence is often absent for most of them. This paper proposes a partition-based convergence framework for population-based optimization algorithms to solve this troubling problem. In this framework, regular partitions and evolutions of populations are implemented alternatively. Specifically, the initial population is generated from a regular partition on the search space; after several generations of evolution of the population, the evolution result is returned to join in the regular partition again, and a new population is generated. Repeat such progress until some stop condition is satisfied. Global convergence is guaranteed for the framework. Then this convergence framework is applied to particle swarm optimization, differential evolution, and genetic algorithm. The modified algorithms are globally convergent and perform better than the original version.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
population-based optimization; partition-based optimization; global optimization; global convergenceReferences:
| [1] | Sundaram, R. K., A first course in optimization theory (1996), Cambridge University Press · Zbl 0885.90106 |
| [2] | Liu, B.; Wang, L.; Liu, Y.; Wang, S., A unified framework for population-based metaheuristics, Ann. Oper. Res., 186, 1, 231-262 (2011) · Zbl 1225.90163 |
| [3] | Rudolph, G., Convergence analysis of canonical genetic algorithms, IEEE Trans. Neural Networks, 5, 1, 96-101 (1994) |
| [4] | Li, Q.; Shang, M., BALFA: A brain storm optimization-based adaptive latent factor analysis model, Inf. Sci., 578, 913-929 (2021), ISSN 0020-0255 |
| [5] | D. Hu, X. Qiu, Y. Liu, X. Zhou, Probabilistic convergence analysis of the stochastic particle swarm optimization model without the stagnation assumption, Inf. Sci. 547 (2021) 996-1007, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2020.08.072. · Zbl 1475.68478 |
| [6] | Solis, F. J.; Wets, R. J.-B., Minimization by random search techniques, Math. Oper. Res., 6, 1, 19-30 (1981) · Zbl 0502.90070 |
| [7] | Leung, K.-S.; Duan, Q.-H.; Xu, Z.-B.; Wong, C., A new model of simulated evolutionary computation-convergence analysis and specifications, IEEE Trans. Evol. Comput., 5, 1, 3-16 (2001) |
| [8] | Liu, Q., Order-2 stability analysis of particle swarm optimization, Evol. Comput., 23, 2, 187-216 (2015) |
| [9] | Liu, Q.; Zeng, J., Global optimization by multilevel partition, J. Global Optim., 61, 1, 47-69 (2015) · Zbl 1312.90062 |
| [10] | Bunel, R.; Mudigonda, P.; Turkaslan, I.; Torr, P.; Lu, J.; Kohli, P., Branch and bound for piecewise linear neural network verification, J. Mach. Learn. Res., 21 (2020), URL:http://jmlr.org/papers/v21/19-468.html · Zbl 1498.68153 |
| [11] | Jones, D. R.; Perttunen, C. D.; Stuckman, B. E., Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181 (1993) · Zbl 0796.49032 |
| [12] | J. Kennedy, R. Eberhart, Particle swarm optimization, in: Proceedings of ICNN’95-international conference on neural networks, vol. 4, IEEE, 1942-1948, 1995. |
| [13] | Storn, R.; Price, K., Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11, 4, 341-359 (1997) · Zbl 0888.90135 |
| [14] | Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT Press (1992) |
| [15] | A. Hedar, Hedar test set, Website,http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm, 2014. |
| [16] | Price, K.; Awad, N.; Ali, M.; Suganthan, P., Problem definitions and evaluation criteria for the 100-digit challenge special session and competition on single objective numerical optimization, 1-20 (2018), Nanyang Technological University, (Technical Report) |
| [17] | A. Colorni, M. Dorigo, V. Maniezzo, et al., Distributed optimization by ant colonies, in: Proceedings of the first European conference on artificial life, vol. 142, Paris, France, 134-142, 1991. |
| [18] | M. Dowlatshahi, V. Derhami, H. Nezamabadi-Pour, Fuzzy particle swarm optimization with nearest-better neighborhood for multimodal optimization, Iran. J. Fuzzy Syst. 17(4) (2020) 7-24. doi:10.22111/ijfs.2020.5403. · Zbl 1458.90644 |
| [19] | Uymaz, S. A.; Tezel, G.; Yel, E., Artificial algae algorithm (AAA) for nonlinear global optimization, Appl. Soft Comput., 31, 153-171 (2015) |
| [20] | Yang, X.-S., Nature-inspired metaheuristic algorithms (2010), Luniver Press |
| [21] | C. Wang, C. Chen, Z. Lun, Z. Ye, Q. Liu, A General Framework for Intelligent Optimization Algorithms Based on Multilevel Evolutions, Adv. Swarm Intell. (2022) 1-14. https://doi.org/10.1007/978-3-031-09677-8_2. |
| [22] | Liu, Q.; Yan, Y., Global optimization: new approaches based on recursive deep and swarm searches (2021), Tsinghua University Press |
| [23] | Passino, K., Biomimicry of bacterial foraging for distributed optimization and control, IEEE Control Syst. Mag., 22, 3, 52-67 (2002) |
| [24] | D. Karaboga, et al., An idea based on honey bee swarm for numerical optimization, Tech. Rep., Technical report-tr06, Erciyes university, engineering faculty, computer, 2005. |
| [25] | Y. Tan, Y. Zhu, Fireworks Algorithm for Optimization, in: Y. Tan, Y. Shi, K.C. Tan (Eds.), Advances in Swarm Intelligence, First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part I, vol. 6145 of Lecture Notes in Computer Science, Springer, 355-364, 2010. DOI: 10.1007/978-3-642-13495-1_44. |
| [26] | Y. Shi, Brain Storm Optimization Algorithm, in: Y. Tan, Y. Shi, Y. Chai, G. Wang (Eds.), Advances in Swarm Intelligence - Second International Conference, ICSI 2011, Chongqing, China, June 12-15, 2011, Proceedings, Part I, vol. 6728 of Lecture Notes in Computer Science, Springer, 303-309, 2011. DOI: 10.1007/978-3-642-21515-5_36. |
| [27] | Hashemi, A.; Joodaki, M.; Joodaki, N. Z.; Dowlatshahi, M. B., Ant Colony Optimization equipped with an ensemble of heuristics through Multi-Criteria Decision Making: A case study in ensemble feature selection, Appl. Soft Comput., 124, Article 109046 pp. (2022) |
| [28] | Paniri, M.; Dowlatshahi, M. B.; Nezamabadi-pour, H., Ant-TD: Ant colony optimization plus temporal difference reinforcement learning for multi-label feature selection, Swarm Evol. Comput., 64, Article 100892 pp. (2021) |
| [29] | Bayati, H.; Dowlatshahi, M. B.; Hashemi, A., MSSL: A memetic-based sparse subspace learning algorithm for multi-label classification, Int. J. Mach. Learn. Cybern., 13, 11, 3607-3624 (2022) |
| [30] | M. Paniri, M.B. Dowlatshahi, H. Nezamabadi-pour, MLACO: A multi-label feature selection algorithm based on ant colony optimization, Knowl.-Based Syst. 192 (2020) 105285, ISSN 0950-7051. https://doi.org/10.1016/j.knosys.2019.105285. |
| [31] | Dowlatshahi, M. B.; Nezamabadi-pour, H., GGSA: A Grouping Gravitational Search Algorithm for data clustering, Eng. Appl. Artif. Intell., 36, 114-121 (2014) |
| [32] | J.C. Figueroa-Garca, R. Neruda, G. HernandezCPrez, A genetic algorithm for multivariate missing data imputation, Inf. Sci. 619 (2023) 947-967, ISSN 0020-0255. https://doi.org/10.1016/j.ins.2022.11.037. · Zbl 07834444 |
| [33] | Altabeeb, A. M.; Mohsen, A. M.; Abualigah, L.; Ghallab, A., Solving capacitated vehicle routing problem using cooperative firefly algorithm, Appl. Soft Comput., 108, Article 107403 pp. (2021) |
| [34] | Bansal, J. C.; Gopal, A.; Nagar, A. K., Analysing convergence, consistency, and trajectory of artificial bee colony algorithm, IEEE Access, 6, 73593-73602 (2018) |
| [35] | Bhandari, D.; Murthy, C.; Pal, S. K., Genetic algorithm with elitist model and its convergence, Int. J. Pattern Recogn. Artif. Intell., 10, 06, 731-747 (1996) |
| [36] | Hu, Z.; Xiong, S.; Su, Q.; Fang, Z., Finite Markov chain analysis of classical differential evolution algorithm, J. Comput. Appl. Math., 268, 121-134 (2014) · Zbl 1293.65013 |
| [37] | Xu, G.; Yu, G., Reprint of: On convergence analysis of particle swarm optimization algorithm, J. Comput. Appl. Math., 340, 709-717 (2018) · Zbl 1432.90164 |
| [38] | Stutzle, T.; Dorigo, M., A short convergence proof for a class of ant colony optimization algorithms, IEEE Trans. Evol. Comput., 6, 4, 358-365 (2002) |
| [39] | Gutjahr, W. J., ACO algorithms with guaranteed convergence to the optimal solution, Inf. Process. Lett., 82, 3, 145-153 (2002) · Zbl 1013.68092 |
| [40] | Liu, Q., Linear scaling and the DIRECT algorithm, J. Global Optim., 56, 3, 1233-1245 (2013) · Zbl 1272.90060 |
| [41] | Yan, Y.; Zhou, Q.; Cheng, S.; Liu, Q.; Li, Y., Bilevel-search particle swarm optimization for computationally expensive optimization problems, Soft. Comput., 25, 22, 14357-14374 (2021) |
| [42] | Finkel, D.; Kelley, C. T., Convergence analysis of the DIRECT algorithm (2004), North Carolina State University. Center for Research in Scientific Computation, Tech. Rep |
| [43] | Moré, J. J.; Wild, S. M., Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 1, 172-191 (2009) · Zbl 1187.90319 |
| [44] | Liu, Q.; Gehrlein, W. V.; Wang, L.; Yan, Y.; Cao, Y.; Chen, W.; Li, Y., Paradoxes in Numerical Comparison of Optimization Algorithms, IEEE Trans. Evol. Comput., 24, 4, 777-791 (2020) |
| [45] | Yan, Y.; Liu, Q.; Yun, Li, Paradox-free analysis for comparing the performance of optimization algorithms, IEEE Trans. Evol. Comput., 1 (2022) |
| [46] | Liu, Q.; Zeng, J.; Yang, G., MrDIRECT: a multilevel robust DIRECT algorithm for global optimization problems, J. Global Optim., 62, 2, 205-227 (2015) · Zbl 1326.90065 |
| [47] | De Jong, K. A., An analysis of the behavior of a class of genetic adaptive systems (1975), University of Michigan |
| [48] | Y.-F. Ge, Z.-H. Zhan, J. Cao, H. Wang, Y. Zhang, K.-K. Lai, J. Zhang, DSGA: A Distributed Segment-Based Genetic Algorithm for Multi-Objective Outsourced Database Partitioning, Inf. Sci. 612 (2022) 864-886, ISSN 0020-0255. https://doi.org/10.1016/j.ins.2022.09.003. |
| [49] | Liu, Y.; Guo, C.; Weng, Y., Online time-optimal trajectory planning for robotic manipulators using adaptive elite genetic algorithm with singularity avoidance, IEEE Access, 7, 146301-146308 (2019) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
