Adaptive surrogate-assisted evolution

Abstract

Evolutionary Algorithms (EAs) used in complex optimization domains usually need to perform a large number of fitness function evaluations in order to find near-optimal solutions. In real world application domains such as engineering design problems, such evaluations can be extremely computationally expensive. It is therefore common to estimate or approximate the fitness. A popular method is to construct a so-called surrogate or meta-model, which can simulate the behavior of the original fitness function, but can be evaluated much faster. An up-to-date survey of fitness approximation applied to EA is presented in this dissertation. The main focuses are the methods of fitness approximation, the working styles of the fitness approximation, and management of the fitness approximation during the optimization process. Working with fitness approximations creates a problem in that it is difficult to determine which approximate model is appropriate for each domain and how often the model should be used. Even for one domain the answer is not usually fixed, but varies within the different stages of the optimization process. To solve this problem, an adaptive fitness approximation GA (ASAGA) is presented. ASAGA adaptively chooses the appropriate model type by adjusting the model complexity and the frequency of model usage according to time elapsed and model accuracy. ASAGA also introduces a stochastic penalty function method to handle constraints. Experiments show that ASAGA performs better than or comparable to several state-of-art surrogate-assisted EAs in benchmark domains and engineering design domains. Statistical analysis suggests that ASAGA outperforms a fixed surrogate-assisted GA in constrained function domains with statistical significance.