Voronoi-based Efficient Surrogate-assisted Evolutionary Algorithm for Very Expensive Problems
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.
Code (1)
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Surrogate-assisted performance prediction for data-driven knowledge discovery algorithms: application to evolutionary modeling of clinical pathways
The paper proposes and investigates an approach for surrogate-assisted performance prediction of data-driven knowledge discovery algorithms. The approach is based on the identification of surrogate models for prediction …
ClusteringFeature ImportancePredictionCombining Lipschitz and RBF Surrogate Models for High-dimensional Computationally Expensive Problems
Standard evolutionary optimization algorithms assume that the evaluation of the objective and constraint functions is straightforward and computationally cheap. However, in many real-world optimization problems, these ev…
Evolutionary AlgorithmsTowards an Evolvable Cancer Treatment Simulator
The use of high-fidelity computational simulations promises to enable high-throughput hypothesis testing and optimisation of cancer therapies. However, increasing realism comes at the cost of increasing computational req…
Evolutionary AlgorithmsTwo-sample testingExploring the effectiveness of surrogate-assisted evolutionary algorithms on the batch processing problem
Real-world optimisation problems typically have objective functions which cannot be expressed analytically. These optimisation problems are evaluated through expensive physical experiments or simulations. Cheap approxima…
Evolutionary AlgorithmsSurrogate-Assisted Partial Order-based Evolutionary Optimisation
In this paper, we propose a novel approach (SAPEO) to support the survival selection process in multi-objective evolutionary algorithms with surrogate models - it dynamically chooses individuals to evaluate exactly based…
Evolutionary Algorithms