An Evolutionary Algorithm Assisted by an Ensemble of Pareto-Optimal Surrogate Models

AI summary

Overview

Research area: Evolutionary computation / surrogate-assisted evolutionary algorithms (SAEAs) for computationally expensive single-objective optimization (cs.NE).

Technical level: Advanced. The paper assumes familiarity with differential evolution, NSGA-II, multi-objective optimization, radial basis function networks, and infill criteria such as the lower confidence bound.

Scope (one sentence): The paper proposes EPOS, an evolutionary algorithm that automatically builds an ensemble of radial basis function network surrogates by solving a bi-objective problem of approximation error versus model complexity, then uses that ensemble to prescreen candidate solutions under a tight budget of function evaluations.

What This Paper Is About

Many real-world design problems, such as vehicle aerodynamics, cost hours or dollars per single evaluation, so optimizers can afford only a few hundred function evaluations. Surrogate-assisted evolutionary algorithms cope with this by training machine-learning models on already-evaluated solutions and using them to screen which new candidate solutions deserve a costly evaluation. The problem EPOS targets is that existing ensemble SAEAs pick their ensemble members from a small, hand-defined menu of model types or settings, and they select members using prediction accuracy alone, which gives little control over how smooth or ragged the approximated fitness landscape is and makes the ensemble fragile. EPOS instead treats surrogate construction itself as a bi-objective optimization problem (minimize approximation error, minimize model complexity) so that the ensemble is populated automatically with a diverse, controlled spread of models.

Key Contributions

1. First explicit bi-objective formulation of surrogate adaptation in SAEAs. The authors state that this is the first work to minimize approximation error and model complexity simultaneously in the automatic design of ensemble surrogate models for SAEAs. They distinguish this from evolutionary neural architecture search, which considers a similar objective pair but for a different purpose (fitting networks to devices of varying scales).

2. Pareto-optimal surrogate models as a route to robust ensembles. Rather than choosing ensemble elements from a predefined list, EPOS uses NSGA-II to evolve the structure of radial basis function networks (RBFNs), tuning two quantities that govern landscape smoothness: the number of hidden layer nodes n and the spread parameter σ. This yields a much larger pool of candidate surrogates than prior work, reported as 110 surrogate models per generation, equal to the NSGA-II population size times the number of generations plus the number of initial solutions.

3. A low-cost emulated uncertainty for the infill criterion. Instead of probabilistic modeling as in Kriging, EPOS computes uncertainty as the standard deviation across the outputs of the Pareto-optimal ensemble members, then applies a lower confidence bound (LCB) rule to prescreen offspring.

4. Empirical validation and released code. The authors report statistical superiority over state-of-the-art SAEAs on the CEC 2020 bound-constrained single-objective benchmark suite and on real-world problem sets under an expensive optimization scenario. Source code is available at https://github.com/haranychan/EPOS.

Main Findings

• Ensemble benefit illustrated on a one-dimensional Rastrigin problem. Figure 1 shows two surrogate models built from the same training data by EPOS: a smooth model (orange) and an accurate model (blue). Their average (green) combines a global-shape-correcting tendency with a locally accurate tendency, and the disagreement between the lines provides an uncertainty band. Under LCB, the solution at the lowest edge of that band is selected, which the authors argue steers search toward the global optimum.

• Model complexity is a usable proxy for landscape smoothness. Because n and σ determine how smooth the RBFN's approximation is, solving the error-versus-complexity multi-objective problem gives explicit, flexible control over smoothness, which the paper argues existing ensembles only control indirectly through a handful of manually chosen model or kernel types.

• Large, automatically generated ensemble instead of a small manual menu. Table I contrasts EPOS's 110 surrogate models with earlier adaptive, ensemble, and adaptive-ensemble SAEAs, whose numbers of "variation seeds" range from 2 to 11 (for example, SUMO with 7 model types, RBFBS with 11 spread-parameter values, aRBF-NFO with 5 RBF types, ESAMA with 2, GS-SOMA with 3, ASMEA with 5, HESNFO with 5, DSP-SAEA with 4). PS-SAEA constructs 2,000 RBFNs but only once at the beginning, for offline problems.

• Statistical superiority reported on benchmark and real-world suites. The abstract and introduction state that EPOS was statistically superior to state-of-the-art SAEAs on the CEC 2020 bound-constrained single-objective benchmark suite and on real-world problems. The specific numerical results, error values, rankings, and significance values are not included in the provided content.

• Ablation-style verification of design choices. Section VI is described as comparing EPOS against its own variants, and Section S-VII of the supplementary material compares the prescreening strategy against an iterative search strategy. The outcomes of those comparisons are not reported in the provided content.

• Prescreening chosen over iterative search to preserve diversity. EPOS prescreens offspring generated by differential evolution and evaluates only the single offspring with the smallest LCB, a choice the authors justify as maintaining the diversity of evaluated solutions used to build future surrogate models.

Methodology in Plain English

EPOS runs in a loop with three stages per generation.

Stage 1 — Adapting the surrogates. The best N_data solutions found so far are pulled from an archive of everything evaluated, split into training and test sets at a ratio of (1 − δ) to δ, and handed to NSGA-II. NSGA-II searches over two values that define an RBFN: the number of hidden layer nodes n and the spread parameter σ. Each candidate RBFN is scored on two objectives, the RMSE on the test set and the model complexity, taken as n itself. The search range for n is half the training-set size up to the training-set size; the range for σ runs from the smallest to the largest pairwise distance among training points. Center points of the RBF nodes are not evolved; they are set to k-means cluster centers to avoid nodes piling up in one place. The Pareto set from the final generation is kept as the pool of surrogate models. The paper notes that n is treated as a real value during NSGA-II but rounded to the nearest integer when evaluated.

Stage 2 — Generating offspring. The top N archived solutions form the differential evolution population, and offspring are produced using the best/1 mutation strategy with binomial crossover. The authors chose best/1 because expensive optimization benefits from exploitation-oriented operators.

Stage 3 — Prescreening. All surrogate models in the Pareto set are averaged to give a mean prediction, and their spread is measured as an unbiased estimate of the standard deviation. The LCB of each offspring is the mean prediction minus α times that standard deviation, where α is a hyperparameter. The offspring with the smallest LCB is evaluated on the true objective function and added to the archive. EpOS initializes its population with Latin Hypercube Sampling. Complexity analysis (Supplementary Section S-II) reportedly shows EPOS is more expensive than plain SAEAs, with the NSGA-II population size N_M and generation limit ω_max governing how it compares to adaptive and ensemble SAEAs.

Why This Matters

Impact on research. The paper reframes surrogate model selection in SAEAs from "pick the most accurate model" to "pick a Pareto front of models trading accuracy against complexity." That gives a principled, tunable handle on the smoothness of approximated fitness landscapes, a property the authors argue is central to ensemble performance but has previously been controlled only indirectly. It also positions a deliberately simple model class, the RBFN, as competitive against increasingly complex surrogates such as XGBoost and ELDR, because the automated multi-objective search supplies the flexibility that manual configuration would otherwise require.

Real-world applications (the paper cites expensive optimization examples; EPOS's own real-world test problems are not named in the provided content):

• Vehicle aerodynamic design optimization, where the paper notes that evaluating the rear of a car model can take one hour of numerical simulation per design.
• Neural architecture search, listed among representative expensive optimization problems.
• General engineering design under budget limits, where function evaluations are restricted to a few hundreds due to computational or financial resources.
• Distributed-data expensive optimization settings, which the related work covers through CESAEA and CCoEA-ASAA, though EPOS itself is presented for centralized online expensive optimization.

Industry relevance. The release of source code at https://github.com/haranychan/EPOS lowers the barrier to adopting the method in industrial design loops where each simulation is costly and the evaluation budget is fixed in advance. Automated surrogate configuration is attractive precisely where expert time for tuning model hyperparameters is scarce.

Future Directions

• Extending the bi-objective surrogate adaptation to multi-objective optimization problems; the paper scopes itself to single-objective problems and cites multi-objective SAEAs such as DA-PSL, TEA, DISK, XGBEA, SIDSAEA, and SMEA-PF as the parallel literature.
• Extending to expensive multi-task optimization, a direction represented in the related work by (θ_l, θ_u)-PMTO.
• Reducing the computational overhead of the NSGA-II-driven surrogate search, given the paper's own finding that EPOS has larger time complexity than plain SAEAs, with the overhead depending on N_M and ω_max.
• Establishing theoretical guarantees for the emulated uncertainty. The paper states that, unlike Kriging, convergence of the disagreement-based uncertainty is not theoretically guaranteed as the sample size grows, and relies on empirical evidence from the Deep Ensemble literature instead.
• Applying EPOS to offline expensive optimization, where all data are given up front and no further objective evaluations are possible, as PS-SAEA does.

Target Audience

Researchers and graduate students working on surrogate-assisted evolutionary computation, expensive optimization, and ensemble machine learning for optimization. Practitioners in simulation-driven design who work under fixed evaluation budgets may also benefit, but they should expect to engage with multi-objective optimization concepts, RBFN structure, and infill criteria to follow the mechanism in detail.

Authors’ abstract

An ensemble of surrogate models helps improve the prediction quality and robustness of surrogate models, and in turn, the search performance of surrogate-assisted evolutionary algorithms (SAEAs). Although different degrees of smoothness of the approximated fitness landscapes need to be carefully designed for an effective ensemble, little attention has been paid to the explicit tuning of the degree of smoothness derived by surrogate models. This study proposes an adaptive ensemble SAEA, which automatically constructs plausible ensemble models by optimizing their parameter settings. Unlike existing adaptive/ensemble SAEAs, which consider prediction accuracy alone, the proposed algorithm optimizes the structure of radial basis function networks (RBFNs) by solving bi-objective minimization problems of approximation error and model complexity, resulting in robust ensemble models of accurate surrogate models with different degrees of smoothness of the approximated fitness landscapes. As a result, the over/under-fittings are reduced. Additionally, an infill criterion is designed so that surrogate models with different degrees of smoothness can contribute to the solution prescreening. The experimental results demonstrated the statistical superiority of our algorithm over state-of-the-art SAEAs on a single-objective benchmark and real-world problem sets under an expensive optimization scenario. The source code of the proposed algorithm is available at https://github.com/haranychan/EPOS