Voronoi-based Efficient Surrogate-assisted Evolutionary Algorithm for Very Expensive Problems

Tong, Hao; Huang, Changwu; Liu, Jialin; Yao, Xin

10.1109/CEC.2019.8789910

2019

978-1-7281-2154-3

2019 IEEE Congress on Evolutionary Computation, CEC 2019

1996-2003

10-13 June 2019

Wellington, New zealand

345 E 47TH ST, NEW YORK, NY 10017 USA

Institute of Electrical and Electronics Engineers Inc.

Very expensive problems are very common in practical system that one fitness evaluation costs several hours or even days. Surrogate assisted evolutionary algorithms (SAEAs) have been widely used to solve this crucial problem in the past decades. However, most studied SAEAs focus on solving problems with a budget of at least ten times of the dimension of problems which is unacceptable in many very expensive real-world problems. In this paper, we employ Voronoi diagram to boost the performance of SAEAs and propose a novel framework named Voronoi-based efficient surrogate assisted evolutionary algorithm (VESAEA) for very expensive problems, in which the optimization budget, in terms of fitness evaluations, is only 5 times of the problem's dimension. In the proposed framework, the Voronoi diagram divides the whole search space into several subspace and then the local search is operated in some potentially better subspace. Additionally, in order to trade off the exploration and exploitation, the framework involves a global search stage developed by combining leave-one-out cross-validation and radial basis function surrogate model. A performance selector is designed to switch the search dynamically and automatically between the global and local search stages. The empirical results on a variety of benchmark problems demonstrate that the proposed framework significantly outperforms several state-of-art algorithms with extremely limited fitness evaluations. Besides, the efficacy of Voronoi-diagram is furtherly analyzed, and the results show its potential to optimize very expensive problems.
© 2019 IEEE.

Voronoi diagram surrogate expensive problems evolutionary algorithms

第一

英语

EI ; CPCI-S

Program for University Key Laboratory of Guangdong Province[2017KSYS008]

Engineering ; Mathematical & Computational Biology

Engineering, Electrical & Electronic ; Mathematical & Computational Biology

WOS:000502087102002

20193507373958

Budget control ; Computational geometry ; Economic and social effects ; Graphic methods ; Health ; Local search (optimization) ; Radial basis function networks ; Statistical methods

Medicine and Pharmacology:461.6 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Optimization Techniques:921.5 ; Mathematical Statistics:922.2 ; Social Sciences:971

EV Compendex

Shenzhen Key Laboratory of Computational Intelligence, University Key Laboratory of Evolving Intelligent Systems of Guangdong Province, Southern University of Science and Technology, Shenzhen; 518055, China

Tong, Hao,Huang, Changwu,Liu, Jialin,et al. Voronoi-based Efficient Surrogate-assisted Evolutionary Algorithm for Very Expensive Problems[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:Institute of Electrical and Electronics Engineers Inc.,2019:1996-2003.