Sustainable Performance Improvement of Surrogate-Assisted Evolutionary Algorithms Using Tabu Search
摘要
Surrogate-assisted evolutionary algorithms (SAEAs) are a representative approach for expensive optimization problems, as solutions for expensive function evaluations (FEs) are prescreened or iteratively improved with the surrogate model of objective functions. These days, SAEAs are often designed to enhance convergence speed by utilizing previously evaluated solutions with good function values. Although this convergence-first design enables SAEAs to find relatively better solutions quickly at the beginning of the search, SAEAs tend to select quite similar solutions to each other for expensive FEs in the middle to the end of the search, resulting in the waste of expensive FEs. Accordingly, this work first incorporates a principle of tabu search into existing SAEAs as well as observes the behavior of the existing SAEAs and their extension. Tabu search extended for continuous optimization prevents to evaluation of similar solutions to previously evaluated ones. This promotes a variety of solution choices in SAEAs and realizes a sustainable performance improvement toward the end of the search. In the experiments held in this work, some SAEAs that have different search strategies and machine learning models for surrogate models are selected, and their extended versions incorporating tabu search are tested in a suite of single-objective continuous optimization benchmarks under an expensive scenario.