Surrogate Assisted Evolutionary Algorithm for Multi-Objective Optimization
Evolutionary algorithms (EAs) are population based approaches that start with an initial population of candidate solutions and evolve them over a number of generations to finally arrive at a set of desired solutions. Such population based algorithms are particularly attractive for multi-objective optimization (MOO) problems as they can result in a set of non-dominated solutions in a single run. However, they are known to require evaluations of a large number of candidate solutions during the process that often becomes prohibitive for problems involving computationally expensive analyses. Use of multiple processors and cheaper approximations (surrogates or metamodels) in lieu of the actual analyses are attractive means to contain the computational time within affordable limits. A major problem in using surrogates within an evolutionary algorithm lies with its representation accuracy; the problem is far more acute for multi-objective problems where both the proximity to the Pareto front and the diversity of the solutions along the non-dominated front are required. In this chapter, a surrogate assisted evolutionary algorithm (SAEA) for multi-objective optimization is presented.
A Radial Basis Function (RBF) network is used as a surrogate model. The algorithm performs actual evaluations of objectives and constraints for all the members of the initial population and periodically evaluates all the members of the population after every S generations. An external archive of the unique solutions evaluated using actual analysis is maintained to train the RBF model which is then used in lieu of the actual analysis for the next S generations. In order to ensure the prediction accuracy of the RBF surrogate model, a candidate solution is only approximated if at least one candidate solution in the archive exists in the vicinity (based on a user defined distance threshold) and the accuracy of the surrogate is within an user defined limit. Five multi-objective test problems are presented in this study and a comparison with Nondominated Sorting Genetic Algorithm II (NSGA-II) [Deb et al. (2002a)] is included to highlight the benefits offered by the approach. SAEA algorithm consistently reported better nondominated solutions for all the test cases for the same number of actual evaluations of candidate solutions.