An efficient eigenvector-based crossover for differential evolution: Simplifying with rank-one updates

Tae Jong Choi; Tae Jong Choi

doi:10.3934/math.2025162

AIMS Mathematics

2025, Volume 10, Issue 2: 3500-3522. doi: 10.3934/math.2025162

Previous Article Next Article

Research article Special Issues

An efficient eigenvector-based crossover for differential evolution: Simplifying with rank-one updates

Tae Jong Choi ^,

Graduate School of Data Science, Chonnam National University, Gwangju 61186, Republic of Korea

Received: 02 January 2025 Revised: 25 January 2025 Accepted: 06 February 2025 Published: 24 February 2025
MSC : 68T01, 68W50

We propose a new approach to enhancing the efficiency of the differential evolution (DE) algorithm, specifically targeting rotational invariance. The performance of the DE algorithm can be hampered by the crossover's dependency on the coordinate system, particularly in optimization problems involving strongly correlated variables. Previous attempts to achieve rotational invariance in the DE algorithm have involved estimating the covariance matrix using the population's distribution information and executing the crossover operation in an eigen coordinate system. However, these methods are computationally intensive. Our approach exclusively employs the rank-one update method, estimating the covariance matrix using the means of the current and previous generations' populations. This lightweight technique reduces the computational costs from $O(Np \cdot D^{2})$ to $O(D^{2})$ (where $ Np $ is the population size and $ D $ is the dimension) operations, yet still preserves the critical rotational invariance property. Experiments conducted on 57 benchmark functions demonstrated that our method finds quicker and more accurate solutions than previous methods. This represents a substantial improvement in achieving rotational invariance in the DE algorithm.
- artificial intelligence,
- evolutionary algorithms,
- evolutionary computation,
- differential evolution,
- eigenvector-based crossover
Citation: Tae Jong Choi. An efficient eigenvector-based crossover for differential evolution: Simplifying with rank-one updates[J]. AIMS Mathematics, 2025, 10(2): 3500-3522. doi: 10.3934/math.2025162

Related Papers:

Abstract

We propose a new approach to enhancing the efficiency of the differential evolution (DE) algorithm, specifically targeting rotational invariance. The performance of the DE algorithm can be hampered by the crossover's dependency on the coordinate system, particularly in optimization problems involving strongly correlated variables. Previous attempts to achieve rotational invariance in the DE algorithm have involved estimating the covariance matrix using the population's distribution information and executing the crossover operation in an eigen coordinate system. However, these methods are computationally intensive. Our approach exclusively employs the rank-one update method, estimating the covariance matrix using the means of the current and previous generations' populations. This lightweight technique reduces the computational costs from $O(Np \cdot D^{2})$ to $O(D^{2})$ (where $ Np $ is the population size and $ D $ is the dimension) operations, yet still preserves the critical rotational invariance property. Experiments conducted on 57 benchmark functions demonstrated that our method finds quicker and more accurate solutions than previous methods. This represents a substantial improvement in achieving rotational invariance in the DE algorithm.

References

[1]	R. D. Al-Dabbagh, F. Neri, N. Idris, M. S. Baba, Algorithmic design issues in adaptive differential evolution schemes: Review and taxonomy, Swarm Evol. Comput., 43 (2018), 284–311. https://doi.org/10.1016/j.swevo.2018.03.008 doi: 10.1016/j.swevo.2018.03.008
[2]	N. Awad, M. Ali, J. Liang, B. Qu, P. Suganthan, Problem definitions and evaluation criteria for the cec 2017 special session and competition on single objective bound constrained real-parameter numerical optimization, in Technical report, Nanyang Technological University, Singapore, 2016, 1–34.
[3]	F. Caraffini, F. Neri, A study on rotation invariance in differential evolution, Swarm Evol. Comput., 50 (2019), 100436. https://doi.org/10.1016/j.swevo.2018.08.013 doi: 10.1016/j.swevo.2018.08.013
[4]	T. J. Choi, A rotationally invariant stochastic opposition-based learning using a beta distribution in differential evolution, Expert Syst. Appl., 231 (2023), 120658. https://doi.org/10.1016/j.eswa.2023.120658 doi: 10.1016/j.eswa.2023.120658
[5]	T. J. Choi, C. W. Ahn, Artificial life based on boids model and evolutionary chaotic neural networks for creating artworks, Swarm Evol. Comput., 47 (2019), 80–88. https://doi.org/10.1016/j.swevo.2017.09.003 doi: 10.1016/j.swevo.2017.09.003
[6]	T. J. Choi, C. W. Ahn, An improved lshade-rsp algorithm with the cauchy perturbation: ilshade-rsp, Knowl.-Based Syst., 215 (2021), 106628. https://doi.org/10.1016/j.knosys.2020.106628 doi: 10.1016/j.knosys.2020.106628
[7]	T. J. Choi, J. H. Lee, H. Y. Youn, C. W. Ahn, Adaptive differential evolution with elite opposition-based learning and its application to training artificial neural networks, Fund. Inform., 164 (2019), 227–242. https://doi.org/10.3233/FI-2019-1764 doi: 10.3233/FI-2019-1764
[8]	T. J. Choi, J. Togelius, Y. G. Cheong, Advanced cauchy mutation for differential evolution in numerical optimization, IEEE Access, 8 (2020), 8720–8734. https://doi.org/10.1109/ACCESS.2020.2964222 doi: 10.1109/ACCESS.2020.2964222
[9]	T. J. Choi, J. Togelius, Y. G. Cheong, A fast and efficient stochastic opposition-based learning for differential evolution in numerical optimization, Swarm Evol. Comput., 60 (2021), 100768. https://doi.org/10.1016/j.swevo.2020.100768 doi: 10.1016/j.swevo.2020.100768
[10]	M. Dai, X. Feng, H. Yu, W. Guo, An opposition-based differential evolution clustering algorithm for emotional preference and migratory behavior optimization, Knowl.-Based Syst., 259 (2023), 110073. https://doi.org/10.1016/j.knosys.2022.110073 doi: 10.1016/j.knosys.2022.110073
[11]	S. Das, S. S. Mullick, P. N. Suganthan, Recent advances in differential evolution–-An updated survey, Swarm Evol. Comput., 27 (2016), 1–30. https://doi.org/10.1016/j.swevo.2016.01.004 doi: 10.1016/j.swevo.2016.01.004
[12]	S. Das, P. N. Suganthan, Differential evolution: A survey of the state-of-the-art, IEEE T. Evolut. Comput., 15 (2010), 4–31. https://doi.org/10.1109/TEVC.2010.2059031 doi: 10.1109/TEVC.2010.2059031
[13]	M. Friedman, The use of ranks to avoid the assumption of normality implicit in the analysis of variance, J. Am. Stat. Assoc., 32 (1937), 675–701. https://doi.org/10.1080/01621459.1937.10503522 doi: 10.1080/01621459.1937.10503522
[14]	M. Friedman, A comparison of alternative tests of significance for the problem of m rankings, Ann. Math. Stat., 11 (1940), 86–92. https://doi.org/10.1214/aoms/1177731944 doi: 10.1214/aoms/1177731944
[15]	W. Gao, Q. Dang, M. Gong, An adaptive framework to select the coordinate systems for evolutionary algorithms, Appl. Soft Comput., 129 (2022), 109585. https://doi.org/10.1016/j.asoc.2022.109585 doi: 10.1016/j.asoc.2022.109585
[16]	S. M. Guo, C. C. Yang, Enhancing differential evolution utilizing eigenvector-based crossover operator, IEEE T. Evol. Comput., 19 (2014), 31–49. https://doi.org/10.1109/TEVC.2013.2297160 doi: 10.1109/TEVC.2013.2297160
[17]	S. Gupta, W. Shu, Y. Zhang, R. Su, Differential evolution-driven traffic light scheduling for vehicle-pedestrian mixed-flow networks, Knowl.-Based Syst., 274 (2023), 110636. https://doi.org/10.1016/j.knosys.2023.110636 doi: 10.1016/j.knosys.2023.110636
[18]	S. Gupta, R. Su, Multiple individual guided differential evolution with time varying and feedback information-based control parameters, Knowl.-Based Syst., 259 (2023), 110091. https://doi.org/10.1016/j.knosys.2022.110091 doi: 10.1016/j.knosys.2022.110091
[19]	Y. Han, H. Peng, C. Mei, L. Cao, C. Deng, H. Wang, et al., Multi-strategy multi-objective differential evolutionary algorithm with reinforcement learning, Knowl.-Based Syst., 277 (2023), 110801. https://doi.org/10.1016/j.knosys.2023.110801 doi: 10.1016/j.knosys.2023.110801
[20]	N. Hansen, The cma evolution strategy: A comparing review, Towards a new evolutionary computation: Advances in the estimation of distribution algorithms, Springer, Berlin, Heidelberg, 2006, 75–102. https://doi.org/10.1007/3-540-32494-1_4
[21]	N, Hansen, The cma evolution strategy: A tutorial, arXiv preprint, arXiv: 1604.00772, 2016.
[22]	N. Hansen, S. Kern, Evaluating the cma evolution strategy on multimodal test functions, in International conference on parallel problem solving from nature, Springer, 2004,282–291.
[23]	N. Hansen, S. D. Müller, P. Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es), Evol. Comput., 11 (2003), 1–18. https://doi.org/10.1162/106365603321828970 doi: 10.1162/106365603321828970
[24]	N. Hansen, A. Ostermeier, Completely derandomized self-adaptation in evolution strategies, Evol. Comput., 9 (2001), 159–195. https://doi.org/10.1162/106365601750190398 doi: 10.1162/106365601750190398
[25]	N. Hansen-INRIA, Variable metrics in evolutionary computation, 2009.
[26]	Y. Hochberg, A sharper bonferroni procedure for multiple tests of significance, Biometrika, 75 (1988), 800–802. https://doi.org/10.1093/biomet/75.4.800 doi: 10.1093/biomet/75.4.800
[27]	J. J. Liang, B. Qu, P. N. Suganthan, A. G. Hernández-Díaz, Problem definitions and evaluation criteria for the cec 2013 special session on real-parameter optimization, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang Technological University, Singapore, Technical Report, 201212 (2013), 281–295.
[28]	Z. Z. Liu, Y. Wang, S. Yang, K. Tang, An adaptive framework to tune the coordinate systems in nature-inspired optimization algorithms, IEEE T. Cybernetics, 49 (2018), 1403–1416. https://doi.org/10.1109/TCYB.2018.2802912 doi: 10.1109/TCYB.2018.2802912
[29]	K. D. Lu, Z. G. Wu, Constrained-differential-evolution-based stealthy sparse cyber-attack and countermeasure in an ac smart grid, IEEE T. Ind. Inform., 18 (2021), 5275–5285. https://doi.org/10.1109/TII.2021.3129487 doi: 10.1109/TII.2021.3129487
[30]	K. D. Lu, Z. G. Wu, T. Huang, Differential evolution-based three stage dynamic cyber-attack of cyber-physical power systems, IEEE-ASME T. Mech., 28 (2022), 1137–1148. https://doi.org/10.1109/TMECH.2022.3214314 doi: 10.1109/TMECH.2022.3214314
[31]	H. B. Mann, D. R. Whitney, On a test of whether one of two random variables is stochastically larger than the other, Ann. Math. Stat., 1947, 50–60. https://doi.org/10.1214/aoms/1177730491 doi: 10.1214/aoms/1177730491
[32]	R. R. Mostafa, A. M. Khedr, Z. A. Aghbari, I. Afyouni, I. Kamel, N. Ahmed, An adaptive hybrid mutated differential evolution feature selection method for low and high-dimensional medical datasets, Knowl.-Based Syst., 283 (2024), 111218. https://doi.org/10.1016/j.knosys.2023.111218 doi: 10.1016/j.knosys.2023.111218
[33]	F. Neri, V. Tirronen, Recent advances in differential evolution: A survey and experimental analysis, Artif. Intell. Rev., 33 (2010), 61–106. https://doi.org/10.1007/s10462-009-9137-2 doi: 10.1007/s10462-009-9137-2
[34]	B. Mirza, M. Pant, H. Zaheer, L. Garcia-Hernandez, A. Abraham, Differential evolution: A review of more than two decades of research, Eng. Appl. Artif. Intel., 90 (2020), 103479. https://doi.org/10.1016/j.engappai.2020.103479 doi: 10.1016/j.engappai.2020.103479
[35]	K. V. Price, Differential evolution vs. the functions of the 2/sup nd/iceo, in Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC'97), IEEE, 1997,153–157.
[36]	X. Song, Y. Zhang, W. Zhang, C. He, Y. Hu, J. Wang, et al., Evolutionary computation for feature selection in classification: A comprehensive survey of solutions, applications and challenges, Swarm Evol. Comput., 90 (2024), 101661. https://doi.org/10.1016/j.swevo.2024.101661 doi: 10.1016/j.swevo.2024.101661
[37]	V. Stanovov, S. Akhmedova, E. Semenkin, Nl-SHADE-RSP algorithm with adaptive archive and selective pressure for CEC 2021 Numerical Optimization, in 2021 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2021,809–816. https://doi.org/10.1109/CEC45853.2021.9504959
[38]	V. Stanovov, S. Akhmedova, E. Semenkin, Nl-SHADE-LBC algorithm with linear parameter adaptation bias change for CEC 2022 Numerical Optimization, in 2022 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2022, 01–08. https://doi.org/10.1109/CEC55065.2022.9870295
[39]	R. Storn, On the usage of differential evolution for function optimization, in Proceedings of north american fuzzy information processing, IEEE, 1996,519–523. https://doi.org/10.1109/NAFIPS.1996.534789
[40]	R. Storn, K. Price, Minimizing the real functions of the icec'96 contest by differential evolution, in Proceedings of IEEE international conference on evolutionary computation, IEEE, 1996,842–844. https://doi.org/10.1109/ICEC.1996.542711
[41]	R. M. Storn, K. Price, Differential evolution–-A simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11 (1997), 341–359. https://doi.org/10.1023/A:1008202821328 doi: 10.1023/A:1008202821328
[42]	A. M. Sutton, M. Lunacek, L. D. Whitley, Differential evolution and non-separability: Using selective pressure to focus search, in Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007, 1428–1435.
[43]	Y. Wang, H. X. Li, T. Huang, L. Li, Differential evolution based on covariance matrix learning and bimodal distribution parameter setting, Appl. Soft Comput., 18 (2014), 232–247. https://doi.org/10.1016/j.asoc.2014.01.038 doi: 10.1016/j.asoc.2014.01.038
[44]	Y. Wang, Z. Z. Liu, J. Li, H. X. Li, G. G. Yen, Utilizing cumulative population distribution information in differential evolution, Appl. Soft Comput., 48 (2016), 329–346. https://doi.org/10.1016/j.asoc.2016.07.012 doi: 10.1016/j.asoc.2016.07.012
[45]	Y. Zhang, D. W. Gong, X. Z. Gao, T. Tian, X. Y. Sun, Binary differential evolution with self-learning for multi-objective feature selection, Inform. Sciences, 507 (2020), 67–85. https://doi.org/10.1016/j.ins.2019.08.040 doi: 10.1016/j.ins.2019.08.040
[46]	X. Zhong, P. Cheng, Z. You, An improved differential evolution algorithm based on basis vector type and its application in fringe projection 3D imaging, Knowl.-Based Syst., 268 (2023), 110470. https://doi.org/10.1016/j.knosys.2023.110470 doi: 10.1016/j.knosys.2023.110470

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)