Contour-Assisted Evolutionary Computation: Estimating Peaks From the Contour Lines of Evaluated Solutions
Organizations: Hanyang University ERICA, Republic of Korea · Nankai University, Tianjin, China · Zhejiang Normal University · Chaoyang University of Technology, Taiwan ·
Abstract
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
| band | band | band | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Peak shape | |||||||||
| 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 |
| 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) |
| Func. | CA-SAEA | DYCORS | lq-CMA-ES | IPOP-CMA-ES | MVMO | CA-DE | CA-GA | GA ( ) | DE ( ) |
|---|---|---|---|---|---|---|---|---|---|
| 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) + |
| Func. | CA-SAEA | DYCORS | lq-CMA-ES | IPOP-CMA-ES | MVMO | GA ( ) | DE ( ) |
|---|---|---|---|---|---|---|---|
| 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) ≈ |
| , 500 evaluations | , 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 |
Evolutionary Optimization
Evolutionary optimization searches for strong solutions through population-based variation, selection, and adaptation.
See all 304 papers