Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics

TIAN Ye; ZHANG Xingyi; HE Cheng; TAN Kay Chen; JIN Yaochu

doi:10.23919/cje.2022.00.100

Volume 32 Issue 1

Jan. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(1): 111-129

TIAN Ye, ZHANG Xingyi, HE Cheng, TAN Kay Chen, JIN Yaochu. Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics[J]. Chinese Journal of Electronics, 2023, 32(1): 111-129. doi: 10.23919/cje.2022.00.100

Citation:

TIAN Ye, ZHANG Xingyi, HE Cheng, TAN Kay Chen, JIN Yaochu. Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics[J]. Chinese Journal of Electronics, 2023, 32(1): 111-129. doi: 10.23919/cje.2022.00.100

Citation:

PDF( 3707 KB)

Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics

doi: 10.23919/cje.2022.00.100

1.
Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Institutes of Physical Science and Information Technology, Anhui University, Hefei 230601, China
2.
School of Artificial Intelligence, Anhui University, Hefei 230601, China
3.
School of Electrical and Electronic Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
4.
Department of Computing, The Hong Kong Polytechnic University, Hong Kong SAR, China
5.
Faculty of Technology, Bielefeld University, Bielefeld 33619, Germany

Funds: This work was supported in part by the National Key R&D Program of China (2018AAA0100100), the National Natural Science Foundation of China (61876162, 61906001, 61903178, 62136008, U20A20306, U21A20512), and an Alexander von Humboldt Professorship for Artificial Intelligence funded by the Federal Ministry of Education and Research, Germany

More Information

Author Bio:
Ye TIAN was born in Anhui Province in 1991. He received the B.S., M.S., and Ph.D. degrees from Anhui University, Hefei, China, in 2012, 2015, and 2018, respectively. He is currently an Associate Professor with the Institutes of Physical Science and Information Technology, Anhui University, Hefei, China. His current research interests include evolutionary computation and its applications. (Email: field910921@gmail.com)

Xingyi ZHANG (corresponding author) was born in Anhui Province in 1982. He received the B.S. degree from Fuyang Normal College, Fuyang, China, in 2003, and the M.S. and Ph.D. degrees from Huazhong University of Science and Technology, Wuhan, China, in 2006 and 2009, respectively. He is currently a Professor with the School of Artificial Intelligence, Anhui University, Hefei, China. His current research interests include unconventional models and algorithms of computation, evolutionary multi-objective optimization, and logistic scheduling. (Email: xyzhanghust@gmail.com)

Cheng HE was born in Hubei Province in 1989. He received the B.E. degree from the Wuhan University of Science and Technology, Wuhan, China, in 2012, and the Ph.D. degree from the Huazhong University of Science and Technology, Wuhan, China, in 2018. He is currently an Associate Professor with the School of Electrical and Electronic Engineering, Huazhong University of Science and Technology, Wuhan, China. His current research interests include model-based evolutionary algorithms, multiobjective optimization, large-scale optimization, deep learning, and their applications. (Email: chenghehust@gmail.com)

Kay Chen TAN received the B.E. (First Class Hons.) and Ph.D. degrees from the University of Glasgow, Glasgow, UK, in 1994 and 1997, respectively. He is currently a Chair Professor of the Department of Computing at the Hong Kong Polytechnic University, Hong Kong SAR, China. (Email: kctan@polyu.edu.hk)

Yaochu JIN was born in 1966. He received the B.S., M.S., and Ph.D. degrees from Zhejiang University, Hangzhou, China, in 1988, 1991, and 1996, respectively, and the Dr.-Ing. degree from Ruhr University Bochum, Germany, in 2001. He is currently an Alexander von Humboldt Professor for artificial intelligence, Chair of Nature Inspired Computing and Engineering, Faculty of Technology, Bielefeld University, Germany. He is also a Distinguished Chair, Professor in computational intelligence, Department of Computer Science, University of Surrey, Guildford, UK. (Email: yaochu.jin@uni-bielefeld.de)
Received Date: 2022-04-23
Accepted Date: 2022-07-13

Available Online: 2022-07-22

Publish Date: 2023-01-05

Abstract

Abstract

A large number of metaheuristics have been proposed and shown high performance in solving complex optimization problems. While most variation operators in existing metaheuristics are empirically designed, new operators are automatically designed in this work, which are expected to be search space independent and thus exhibit robust performance on different problems. This work first investigates the influence of translation invariance, scale invariance, and rotation invariance on the search behavior and performance of some representative operators. This work then deduces the generic form of translation, scale, and rotation invariant operators, and proposes a principled approach for the automated design of operators, which searches for high-performance operators based on the deduced generic form. The experimental results demonstrate that the operators generated by the proposed approach outperform state-of-the-art ones on a variety of problems with complex landscapes and up to 1000 decision variables.
- Metaheuristics,
- Evolutionary computation,
- Swarm intelligence,
- Variation operator,
- Transformation invariance,
- Automated design

FullText(HTML)

References(44)

References

[1]	M. R. Alam, K. S. Lee, M. Rahman, and Y. F. Zhang, “Process planning optimization for the manufacture of injection moulds using a genetic algorithm,” International Journal of Computer Integrated Manufacturing, vol.16, no.3, pp.181–191, 2003. doi: 10.1080/0951192021000025742
[2]	J. Y. Potvin and S. Bengio, “The vehicle routing problem with time windows part Ⅱ: Genetic search,” INFORMS Journal on Computing, vol.8, no.2, pp.165–172, 1996. doi: 10.1287/ijoc.8.2.165
[3]	Y. Tian, X. Su, Y. Su, and X. Zhang, “EMODMI: A multi-objective optimization based method to identify disease modules,” IEEE Transactions on Emerging Topics in Computational Intelligence, vol.5, no.4, pp.570–582, 2021. doi: 10.1109/TETCI.2020.3014923
[4]	K. J. Oh, T. Y. Kim, and S. Min, “Using genetic algorithm to support portfolio optimization for index fund management,” Expert Systems with Applications, vol.28, pp.371–379, 2005. doi: 10.1016/j.eswa.2004.10.014
[5]	H. Robbins and S. Monro, “A stochastic approximation method,” The Annals of Mathematical Statistics, vol.22, no.3, pp.400–407, 1951. doi: 10.1214/aoms/1177729586
[6]	J. H. Holland, Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, USA, 1992.
[7]	R. Storn and K. Price, “Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol.11, no.4, pp.341–359, 1997. doi: 10.1023/A:1008202821328
[8]	N. Hansen and A. Ostermeier, “Completely derandomized self-adaptation in evolution strategies,” Evolutionary Computation, vol.9, no.2, pp.159–195, 2001. doi: 10.1162/106365601750190398
[9]	X. Yao, Y. Liu, and G. Lin, “Evolutionary programming made faster,” IEEE Transactions on Evolutionary Computation, vol.3, no.2, pp.82–102, 1999. doi: 10.1109/4235.771163
[10]	R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proceedings of the 6th International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp.39–43, 1995.
[11]	K. Socha and M. Dorigo, “Ant colony optimization for continuous domains,” European Journal of Operational Research, vol.185, no.3, pp.1155–1173, 2008. doi: 10.1016/j.ejor.2006.06.046
[12]	D. Karaboga, “An idea based on honey bee swarm for numerical optimization,” Technical Report, TR06, Erciyes University, 2005.
[13]	J. Galletly, “Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms,” Kybernetes, vol.27, no.8, pp.979–980, 1998. doi: 10.1108/k.1998.27.8.979.4
[14]	T. Okabe, Y. Jin, and B. Sendhoff, “Theoretical comparisons of search dynamics of genetic algorithms and evolution strategies,” in Proceedings of the 2005 IEEE Congress on Evolutionary Computation, Edinburgh, UK, pp. 382–389, 2005.
[15]	S. Li, Y. Li, and Y. Lin, Intelligent Optimization Algorithms and Emergent Computation, Tsinghua University Press, Beijing, China, 2019.
[16]	A. E. Eiben and C. A. Schippers, “On evolutionary exploration and exploitation,” Fundamenta Informaticae, vol.35, pp.1–16, 1998. doi: 10.3233/FI-1998-35123401
[17]	Y. Su, N. Guo, Y. Tian, and X. Zhang, “A non-revisiting genetic algorithm based on a novel binary space partition tree,” Information Sciences, vol.512, pp.661–674, 2020. doi: 10.1016/j.ins.2019.10.016
[18]	H. Li and Q. Zhang, “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-Ⅱ,” IEEE Transactions on Evolutionary Computation, vol.13, no.2, pp.284–302, 2009. doi: 10.1109/TEVC.2008.925798
[19]	T. Rodemann, “Industrial portfolio management for many-objective optimization algorithms,” in Proceedings of the 2018 IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil, pp.1-8, 2018.
[20]	C. A. Coello Coello and M. S. Lechuga, “MOPSO: A proposal for multiple objective particle swarm optimization,” in Proceedings of the 2002 IEEE Congress on Evolutionary Computation, Honolulu, HI, USA, pp.1051–1056, 2002.
[21]	M. Jebalia, A. Auger, and N. Hansen, “Log-linear convergence and divergence of the scale-invariant (1+1)-ES in noisy environments,” Algorithmica, vol.59, no.3, pp.425–460, 2011. doi: 10.1007/s00453-010-9403-3
[22]	F. Caraffini and F. Neri, “A study on rotation invariance in differential evolution,” Swarm and Evolutionary Computation, vol.50, article no.100436, 2019. doi: 10.1016/j.swevo.2018.08.013
[23]	G. Karafotias, M. Hoogendoorn, and A. E. Eiben, “Parameter control in evolutionary algorithms: Trends and challenges,” IEEE Transactions on Evolutionary Computation, vol.19, no.2, pp.167–187, 2015. doi: 10.1109/TEVC.2014.2308294
[24]	C. Huang, Y. Li, and X. Yao, “A survey of automatic parameter tuning methods for metaheuristics,” IEEE Transactions on Evolutionary Computation, vol.24, no.2, pp.201–216, 2020. doi: 10.1109/TEVC.2019.2921598
[25]	P. Kerschke and H. Trautmann, “Automated algorithm selection on continuous black-box problems by combining exploratory landscape analysis and machine learning,” Evolutionary Computation, vol.27, no.1, pp.99–127, 2019. doi: 10.1162/evco_a_00236
[26]	Y. Tian, S. Peng, X. Zhang, et al., “A recommender system for metaheuristic algorithms for continuous optimization based on deep recurrent neural networks,” IEEE Transactions on Artificial Intelligence, vol.1, no.1, pp.5–18, 2020. doi: 10.1109/TAI.2020.3022339
[27]	K. Li, A. Fialho, S. Kwong, and Q. Zhang, “Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol.18, no.1, pp.114–130, 2014. doi: 10.1109/TEVC.2013.2239648
[28]	L. C. Bezerra, M. López-Ibánez, and T. Stützle, “Automatic component-wise design of multiobjective evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol.20, no.3, pp.403–417, 2016. doi: 10.1109/TEVC.2015.2474158
[29]	L. P. M. Birattari, T. Stützle, and K. Varrentrapp, “A racing algorithm for configuring metaheuristics,” in Proceedings of the 2002 Conference on Genetic and Evolutionary Computation, New York, NY, USA, pp. 11–18, 2002.
[30]	F. Rosenblatt, “The perceptron: a probabilistic model for information storage and organization in the brain,” Psychological Review, vol.65, no.6, pp.386–408, 1958. doi: 10.1037/h0042519
[31]	A. Fialho, M. Schoenauer, and M. Sebag, “Toward comparison-based adaptive operator selection,” in Proceedings of the 2010 Conference on Genetic and Evolutionary Computation, Portland, USA, pp.767–774, 2002.
[32]	K. Deb and R. B. Agrawal, “Simulated binary crossover for continuous search space,” Complex Systems, vol.9, no.4, pp.115–148, 1995.
[33]	C. Igel, N. Hansen, and S. Roth, “Covariance matrix adaptation for multi-objective optimization,” Evolutionary Computation, vol.15, no.1, pp.1–28, 2007. doi: 10.1162/evco.2007.15.1.1
[34]	N. Hansen, R. Ros, N. Mauny, et al., “Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems,” Applied Soft Computing, vol.11, no.8, pp.5755–5769, 2011. doi: 10.1016/j.asoc.2011.03.001
[35]	K. A. Hoffmann and S. T. Chiang, Computational Fluid Dynamics Volume I, Engineering Education System, Wichita, USA, 2000.
[36]	L. Pan, W. Xu, L. Li, C. He, and R. Cheng, “Adaptive simulated binary crossover for rotated multi-objective optimization,” Swarm and Evolutionary Computation, vol.60, article no.100759, 2021. doi: 10.1016/j.swevo.2020.100759
[37]	R. Cheng and Y. Jin, “A competitive swarm optimizer for large scale optimization,” IEEE Transactions on Cybernetics, vol.45, no.2, pp.191–204, 2015. doi: 10.1109/TCYB.2014.2322602
[38]	R. Tanabe and A. Fukunaga, “Success-history based parameter adaptation for differential evolution,” in Proceedings of the 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, 2013.
[39]	K. M. Sallam, S. M. Elsayed, R. K. Chakrabortty, and M. J. Ryan, “Improved multi-operator differential evolution algorithm for solving unconstrained problems,” in Proceedings of the 2020 IEEE Congress on Evolutionary Computation, Glasgow, UK, 2020.
[40]	K. Deb and M. Goyal, “A combined genetic adaptive search (GeneAS) for engineering design,” Computer Science and Informatics, vol.26, no.4, pp.30–45, 1996.
[41]	J. Derrac, S. Garcia, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms,” Swarm and Evolutionary Computation, vol.1, no.1, pp.3–18, 2011. doi: 10.1016/j.swevo.2011.02.002
[42]	X. Li, K. Tang, M. N. Omidvar, Z. Yang, and K. Qin, “Benchmark functions for the CEC’2013 special session and competition on large-scale global optimization,” Gene, vol.7, no.33, 2013.
[43]	J. Sun, X. Liu, T. Bäck, and Z. Xu, “Learning adaptive differential evolution algorithm from optimization experiences by policy gradient,” IEEE Transactions on Evolutionary Computation, vol.25, no.4, pp.666–680, 2021. doi: 10.1109/TEVC.2021.3060811
[44]	H. A. A. Nomer, A. W. Mohamed, and A. H. Yousef, “GSK-RL: Adaptive gaining-sharing knowledge algorithm using reinforcement learning,” in Proceedings of the 3rd Novel Intelligent and Leading Emerging Sciences Conference, Giza, Egypt, pp.169–174, 2021.