Contour-Assisted Evolutionary Computation: Estimating Peaks From the Contour Lines of Evaluated Solutions
Authors: Jun Zhang, Tong Qian, Hua Ding, Zhi-Hui Zhan, Wei-Jie Yu, Jian-Yu Li
Organizations: Hanyang University ERICA, Republic of Korea · Nankai University, Tianjin, China · Zhejiang Normal University · Chaoyang University of Technology, Taiwan · Sun Yat-sen University, Guangzhou, China
Evolutionary algorithms (EAs) evaluate many candidate solutions but use them mainly to rank individuals. This paper treats the evaluated solutions as the spot heights of a topographic survey and draws the contour lines they imply. The contour map decomposes the evaluated region into peaks: in two dimensions a contour tree with persistence separates significant peaks from interpolation ripples, and in more dimensions hill climbing on the interpolated surface locates the peaks and ray-cast level sets describe them. A memory of the explored peaks directs the search to new ones. The data-supported contours of each peak are extrapolated to zero size by an area law, exact for quadratic peaks and second-order accurate for smooth ones, that estimates a peak's location, height and shape before it is sampled. A contour-assisted EA (CA-EA) inserts contour steps with local search and peak memory into a genetic algorithm (GA), differential evolution or particle swarm optimization. A contour-assisted surrogate-assisted EA (CA-SAEA), for expensive problems, spends each evaluation on surrogate-screened offspring or on sampling around a peak, entered at the maximum of the interpolated surface. On 2-D benchmarks, CA-EA reduces the evaluations a plain GA needs by factors of 12 to 112; controls attribute its gain over classical memetic search to restarting local search on distinct peaks. On the CEC 2015 expensive suite in 10 and 30 dimensions, CA-SAEA has the second-best average rank, behind DYCORS and ahead of lq-CMA-ES and the competition winner MVMO, although in 30 dimensions MVMO wins significantly on 9 functions and loses on 6; there the map beats sampling around the best point on 5 of 15 functions and loses on 3. Entering the peaks at their extrapolated locations brought no gain at these budgets, although, with enough samples, it improves the estimated heights on most two-dimensional functions.
Figures & tables
Fig. 1: One contour step on the Peaks function after four generations of a GA. (a) The 150 evaluated points and the contour map reconstructed from them (blue) over the true contours (grey). (b) Data-supported closed contours of the significant peaks. (c) Areas enclosed by the nested contours of the main peak versus the contour level, and the fitted area law; the zero of the fitted curve is the estimated peak height (8.113; true height 8.106; best evaluated value 8.073). (d) Centroids of the nested contours, colored by level, extrapolate to the estimated peak (star). A Nelder–Mead search started there (orange) reaches the global maximum to 10−14 in 86 evaluations.
Fig. 2: Contour-assisted evolutionary computation: the solutions evaluated so far are turned into a contour map, whose peaks are estimated and then exploited by CA-EA (mid-run acceleration of an EA) or CA-SAEA (expensive optimization).
band [0.20,0.60]
band [0.50,0.90]
band [0.70,0.95]
Peak shape
ΔhT2
Δhlin
Δx
ΔhT2
Δhlin
Δx
ΔhT2
Δhlin
Δx
quadratic
-0.04
0.00
2.3e-16
+0.01
0.00
1.7e-16
0.00
0.00
5.6e-17
Gaussian
+20.03
-16.58
2.0e-16
+0.64
-2.31
5.6e-17
+0.09
-0.67
1.1e-16
skewed Gaussian
+19.97
-16.61
2.9e-3
+0.64
-2.31
1.8e-4
+0.08
-0.67
5.6e-5
cone
-2.09
-26.81
2.3e-16
-1.77
-8.31
0
-1.08
-4.25
2.8e-16
Peaks (main peak)
+26.30
-13.60
6.4e-3
+0.40
-1.92
3.1e-4
+0.06
-0.56
8.2e-5
TABLE I: Contour extrapolation on exact peaks ( d=2 ): relative height error Δh in % of f∗−cbase for the second-order (T2) and linear (lin) area models, and location error Δx (T2, normalized units), for bands at the given fractions of the way from the base contour to the peak
Func.
GA
GA+ LS(best)
GA+ LS(topo)
GA+ LS(surf.)
CA-GA (iso)
CA-GA
Peaks
4073 (0.43)
155
155
153
152
152
Himmelblau
3031 (0.53)
148
148
148
146
147
SixHumpCamel
1670 (0.80)
146
146
145
144
145
Branin
2253 (0.67)
147
147
147
147
147
Rosenbrock
18665 (0.10)
176
176
168
180
167
GaussPeaks
7889 (0.23)
952 (0.73)
552 (0.93)
450 (0.93)
407 (0.97)
422 (0.93)
TABLE II: 2D suite (budget 2000, 30 runs): ERT to a relative error of 10−6 , with the success rate in parentheses when it is below 1; the best ERT of each row and panel is in bold. Upper panel: the GA, its four controls and CA-GA; lower panel: DE, PSO and the references. LS per run: mean number of local searches per run
Func.
CA-SAEA
DYCORS
lq-CMA-ES
IPOP-CMA-ES
MVMO
CA-DE
CA-GA
GA ( NP=20 )
DE ( NP=20 )
F1
1.66e4 (1.09e4)
7.72e4 (2.74e4) +
3.44e3 (8.23e3) -
8.07e7 (1.41e8) +
193 (577) -
4.60e4 (1.65e5) -
5.59e6 (2.43e7) -
4.76e8 (2.93e8) +
5.19e8 (2.89e8) +
F2
3.78e4 (1.53e4)
3.03e4 (9.70e3) ≈
1.47e3 (2.92e3) -
4.88e4 (2.09e4) ≈
0.0168 (1.86e-3) -
3.77e4 (1.49e4) ≈
4.24e4 (1.56e4) ≈
4.41e4 (1.85e4) ≈
2.74e4 (1.27e4) -
F3
5.41 (1.72)
5.03 (1.89) ≈
5.93 (2.37) ≈
7.19 (1.46) +
9.40 (1.03) +
7.79 (2.27) +
8.80 (2.16) +
8.27 (1.63) +
8.40 (1.28) +
F4
473 (211)
581 (183) ≈
1.95e3 (302) +
1.95e3 (259) +
465 (236) ≈
973 (386) +
1.06e3 (243) +
521 (131) ≈
1.88e3 (152) +
F5
2.48 (0.878)
1.71 (0.530) -
3.21 (0.428) +
3.02 (0.613) +
1.13 (0.576) -
2.06 (1.03) ≈
1.83 (1.00) -
2.24 (0.542) ≈
2.72 (0.825) ≈
F6
0.460 (0.182)
0.493 (0.121) ≈
0.380 (0.0953) ≈
0.746 (0.185) +
0.326 (0.257) -
0.546 (0.162) ≈
0.602 (0.170) +
1.07 (0.446) +
1.07 (0.367) +
TABLE III: CEC 2015 expensive suite, D=10 , 500 evaluations, 20 runs: mean (standard deviation) of the error. + , - and ≈ indicate that CA-SAEA is significantly better, significantly worse or not significantly different (Wilcoxon rank-sum test, α=0.05 ); the best mean of each row is in bold
Func.
CA-SAEA
DYCORS
lq-CMA-ES
IPOP-CMA-ES
MVMO
GA ( NP=20 )
DE ( NP=20 )
F1
4.10e3 (2.69e3)
3.02e5 (4.05e5) +
1.96e3 (3.27e3) -
2.13e8 (1.14e8) +
2.09e3 (4.84e3) -
2.12e9 (6.06e8) +
5.58e9 (2.19e9) +
F2
1.17e5 (2.02e4)
1.24e5 (1.89e4) ≈
1.10e4 (3.29e4) -
1.67e5 (2.08e4) +
6.93e-3 (3.16e-4) -
1.43e5 (3.44e4) ≈
8.65e4 (1.68e4) -
F3
23.4 (3.08)
25.1 (2.62) +
21.5 (2.79) ≈
20.1 (4.84) ≈
37.9 (3.75) +
35.0 (3.16) +
30.1 (4.81) +
F4
2.98e3 (777)
1.19e3 (419) -
8.02e3 (259) +
8.15e3 (334) +
1.43e3 (560) -
1.85e3 (435) -
7.30e3 (352) +
F5
3.35 (0.716)
1.43 (0.383) -
4.78 (0.577) +
4.33 (0.553) +
1.68 (0.492) -
2.03 (0.607) -
3.98 (0.440) +
F6
0.766 (0.147)
0.653 (0.130) -
0.622 (0.101) ≈
0.806 (0.189) ≈
0.520 (0.129) -
0.615 (0.136) -
1.45 (0.935) ≈
TABLE IV: CEC 2015 expensive suite, D=30 , 1500 evaluations: mean (standard deviation) of the error over 20 runs for CA-SAEA and DYCORS and 10 runs for IPOP-CMA-ES, GA and DE (lq-CMA-ES: 10 runs on F1 and F2 and 5 runs on F3–F15; MVMO: the 20 runs released by the organizers). Marks and bold face as in Table III
D=10 , 500 evaluations
D=30 , 1500 evaluations
Func.
CA-SAEA
MVMO
TunedCMAES
CMAS-ES_QR
iSRPSO
humanCog
CA-SAEA
MVMO
TunedCMAES
CMAS-ES_QR
iSRPSO
humanCog
F1
1.66e4
193
1.17e6
4.43e6
7.40e6
3.27e9
4.10e3
2.09e3
1.52e6
8.50e5
7.19e8
4.74e10
F2
3.78e4
0.0168
4.78e4
2.58e4
3.19e4
7.80e4
1.17e5
6.93e-3
1.44e5
9.17e4
7.67e4
1.13e5
F3
5.41
9.40
7.62
2.79
6.60
11.2
23.4
37.9
24.3
11.5
25.7
41.3
F4
473
465
1.34e3
1.73e3
925
2.09e3
2.98e3
1.43e3
6.11e3
6.68e3
5.41e3
7.99e3
F5
2.48
1.13
2.77
3.20
2.46
2.82
3.35
1.68
3.13
4.55
4.24
4.39
TABLE V: Mean error after 50D evaluations: CA-SAEA and the entries of the CEC 2015 expensive competition (MVMO: raw results released by the organizers; other entries: published mean errors [ 21 ] ). The best mean of each row and dimension is in bold; the last row counts the functions on which CA-SAEA has the lower mean
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
Kei Nishihara, Yaochu Jin, Masaya Nakata
Organization for the Promotion of Education, Yokohama National University, Yokohama 2408501, Japan · School of Engineering, Westlake University, Hangzhou 310030, China · Faculty of Engineering, Yokohama National University, Yokohama 2408501, Japan
This paper proposes RCMAES, a novel variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for CEC benchmark optimization. RCMAES integrates a dimension-dependent nonlinear population-size reduction strategy with an adaptive restart mechanism within a pure CMA-ES framework. RCMAES is evaluated on three benchmark suites (CEC2017, CEC2020, and CEC2022) and compared with state-of-the-art DE algorithms as well as its closely related counterpart, BIPOP-aCMAES. Experimental results show that RCMAES achieves competitive and robust performance across all benchmarks.
Khoirul Faiq Muzakka, Sören Möller, Martin Finsterbusch
Institute of Energy Materials and Devices (IMD-2), Forschungszentrum Jülich GmbH, Germany
The Strength Pareto Evolutionary Algorithm 2 (SPEA2) is a popular and prominent evolutionary algorithm for solving multi-objective optimisation problems. Despite its popularity, theoretical analyses of SPEA2 have only appeared recently. Moreover, these analyses focus exclusively on how SPEA2 handles non-dominated solutions and disregard the algorithmic components responsible for handling dominated solutions. We conduct a first runtime analysis of SPEA2 for which these components are analysed. We prove that, unlike other prominent algorithms, including NSGA-II, NSGA-III and SMS-EMOA under the same setting of constant population size and duplicate elimination, SPEA2 is unable to cover the Pareto front of the OneTrapZeroTrap benchmark efficiently. Our results indicate that using k-th nearest-neighbour distance in the fitness assignment provides an insufficient signal to maintain diversity among dominated individuals. To address this issue, we propose an improved variant, SPEA2+, that considers all pairwise distances. The new algorithm achieves the same performance guarantees as the other prominent algorithms on OneTrapZeroTrap, while matching the performance of the original SPEA2 on simpler problems. Experimental results complement our theoretical findings.