How it works
AMM does not contain a new search method. It decides which classical method gets the evaluation budget, and when, by reading the function with cheap probes. It is given the dimension D, the budget B, the box and the function values at the points it evaluates, and nothing else: no function name, no optimum value. The thresholds depend on D and B only. Every probe evaluation counts against B, and every evaluated point lies in the box. One configuration serves all functions.
The pipeline
Section titled “The pipeline”
Reproduce this figure
- command
- rendered by the paper figure pipeline from latex/figs/src/overview_diagram.tex
- seed
- pending: filled from the run manifest
- instance ids
- pending: filled from the run manifest
- budgets
- pending: filled from the run manifest
- commit
- draft v3: preset c43, hash 781edd1e0767c7e2. Frozen preset: c46, hash 2153948ebed51150
- competitors
- pending: filled from the run manifest
- hardware
- not applicable
- cost
- not applicable
Five stages, in the order a run meets them. D is the dimension, B the budget and b the evaluations left. Symbols and thresholds are those of the paper draft’s Table 2.
- Whole-budget gates. Three gates can hand the whole budget to one engine. At D up to 3 and B up to 10D, restarted COBYQA runs, because no probe would pay for itself. From D = 5 and B of at least 100D, a pair test reads whether the function is additive over pairs of coordinates: a separable reading goes to STEP restarts, and a reading where only adjacent coordinates interact (confirmed by a band check, from 300D) goes to a coordinate search along decoupled directions. At D = 2 to 3 from 100D, a basin reading sends a landscape with several smooth basins to MLSL. A gate that does not fire costs only its evaluations.
- The prefix (B up to 100D). The prefix spends the whole budget: a uniform design, STEP from 30D, then a curvature probe that sends a smooth reading to restarted SLSQP and a rugged one to a (1+1)-CMA-ES (or, at 100D, to populations ranked by a quadratic surrogate). Below 31D and 200 evaluations the probe is skipped: one SLSQP descent, then the (1+1)-CMA-ES. At D of 2 or less, Nelder–Mead restarts replace the evolution strategy.
- The ATM stage (B above 100D). The ATM sampler takes a fifth of the budget (at most 60D from D = 10), then STEP takes half of what is left, with a separability check.
- Local probes (D of 5 or more, non-separable). A plateau probe and the curvature probe classify the incumbent. A plateau goes to IPOP-aCMA-ES with four times the default population. A rugged reading with much budget left goes to the same schedule, unless a fractal probe diverts it to restarted SLSQP. A smooth reading goes to an SLSQP stage, which its exit status, a hill-valley test and a kink reading can end early.
- The finisher. A restarted (1+1)-CMA-ES that hands stalls to IPOP-aCMA-ES populations.
The probes
Section titled “The probes”Each probe reads points the run evaluated anyway or a few extra ones, and its cost is charged to B. When a
probe does not fire, the run stays on its default path. Function names in the last column are in
src/amm_optimizer/ of the public repository (the development code lived in src/atm/).
| Probe | What it reads | Cost (evaluations) | Fires: sends the budget to | Default when it does not fire | Code |
|---|---|---|---|---|---|
| Pair test | Additivity residual of f over adjacent and random distant coordinate pairs. A residual of at least 1e-6 on a distant pair reads non-separable; on adjacent pairs only, a chain | 3D+1 | Separable: STEP restarts. Chain, after a band check (6D evaluations): coordinate search | Non-separable: the run continues | chain_phase.pair_test, band_consistency |
| Basin reading | Rank-quadratic R² on a Sobol design (at most 0.5 reads several basins), and the change of second differences between two scales (at most 0.1 reads smooth) | Design, then 4D | Several basins: MLSL. One smooth basin up to 300D: one SLSQP descent first | Continue from the design’s best point | basin_phase.rank_quadratic_r2, local_reading, multi_basin_route |
| Curvature β | Slope of the log of the mirrored loss against log step at three scales (a quadratic gives 2). At least 1.45 reads smooth | 24 (12 below 30D) | Smooth: restarted SLSQP (prefix) or the smooth route | (1+1)-CMA-ES or populations | qn_phase.curvature_beta |
| Plateau | Four mirrored probes at 3e-4 of the box width; at least half repeat f(x) exactly | 4 | IPOP-aCMA-ES with four times the default population | Curvature probe | qn_phase.plateau_check |
| STEP separability check | A stored point re-evaluated after the incumbent moved along another axis; from 1000D a two-axis check once STEP stalls | Re-evaluations | Separable: straight to the finisher | Local probes | step_phase.run_step_phase |
| Fractal (D of 20 or more) | Mirrored second differences at four scales from 1e-7 to 1e-4 of the box width | 32 | Fractal: restarted SLSQP | IPOP schedule | qn_phase.micro_slopes |
| Kink | Mirrored second difference at 1e-7 of the box width, at least 5e7 | 6 | Scaled finite-difference BFGS | Finisher | qn_phase.kink_check |
| Hill-valley | Whether a point between two converged descent ends is worse than both | Up to 9 | Separate basins: sampled SLSQP restarts | Finisher | qn_phase.multi_basin |
| Exit status and stall monitor | SLSQP’s own exits and iterations (a majority of failed exits; progress of the first descent) | 0 | Failed majority: L-BFGS-B | Finisher | qn_phase.failure_majority |
The curvature, pair, local-basin and fractal readings are invariant to f → af + c with a > 0, and the
plateau, rank and hill-valley tests to any increasing transformation of f. The kink threshold is absolute and is
tied to the scale of bbob’s function values. Sources: paper draft v3, section 3.2 and appendix B.1; the constants
were checked against the frozen code (for example BETA_THRESHOLD, TIE_SCALE, KINK_D2, SEP_TOL).
The engines
Section titled “The engines”All engines return when they converge, spend their share or stall, and every result is offered to an incumbent that never gets worse. Restarted engines restart from uniform points until their share is spent.
| Engine | What it is | Used for |
|---|---|---|
| COBYQA | SciPy’s trust-region method on quadratic models, restarted; initial trust radius 0.25 of the box width | Whole-budget gate at small D and B |
| SLSQP | SciPy’s, box bounds, forward-difference step 1e-9 | Prefix, basin descents, MLSL, the smooth local route |
| L-BFGS-B | SciPy’s, ten correction pairs | Takes the rest when most SLSQP descents fail |
| Scaled finite-difference BFGS | Nonsmooth BFGS in the style of Lewis and Overton | One try on smooth readings at small budgets; after a kink |
| Nelder–Mead restarts | Simplex method | D of 2 or less |
| STEP | Round-robin coordinate search in the style of BSrr | Separable route; a stage after the ATM sampler |
| Coordinate search | Global line searches along decoupled directions | Chain reading |
| MLSL | SLSQP descents from Sobol points that no better point nearby beats | Several-basin reading at D = 2 to 3 |
| (1+1)-Cholesky-CMA-ES | With active update and quadratic-model steps | Prefix and finisher |
| IPOP-aCMA-ES | (μ/μw,λ)-CMA-ES with active update and box clipping, restarted with growing populations | Plateau and rugged routes; stalls of the finisher |
| ATM sampler | Population-based random search: four sub-samplers, a resource allocator, success-rate control of step widths | The stage after the prefix range |
References for the engines are on the paper page; the draft still marks several identifiers as to be found.
The routing map
Section titled “The routing map”The map shows, for each dimension and budget multiplier, which stage runs first and the stage list a run follows when no probe routes the whole budget. Hover, focus or tap a cell. The map was produced by a dry run of the configuration’s own control flow with the probe outcomes forced, so it shows what is possible in a cell and what the default path is, not which route a given function takes.
| D \ B | 10×D | 30×D | 100×D | 300×D | 1000×D | 3000×D |
|---|---|---|---|---|---|---|
| D = 2 | COBYQA | prefix | basin | basin | basin | basin |
| D = 3 | COBYQA | prefix | basin | basin | basin | basin |
| D = 5 | prefix | prefix | pair | pair | pair | pair |
| D = 10 | prefix | prefix | pair | pair | pair | pair |
| D = 20 | prefix | prefix | pair | pair | pair | pair |
| D = 40 | prefix | prefix | pair | pair | pair | pair |
- COBYQA spends the whole budget
- prefix: one SLSQP descent, then (1+1)-CMA-ES
- prefix with the curvature probe (SLSQP or CMA-ES)
- prefix with Nelder–Mead (D = 2)
- ATM stage, STEP, then local tests (D ≥ 5)
- ATM stage, STEP, then the finisher (D = 2–3)
The word in a cell is the first stage that spends evaluations: COBYQA, the prefix, the pair test or the basin reading. The colours mark paths, not methods.
Hover, focus or tap a cell for its default stage list. Arrow keys move between cells.
Text version: all 36 cells
| D | Budget | Default stages (no route fires) | Whole-budget routes possible here |
|---|---|---|---|
| 2 | 10×D = 20 |
|
|
| 2 | 30×D = 60 |
|
|
| 2 | 100×D = 200 |
|
|
| 2 | 300×D = 600 |
|
|
| 2 | 1000×D = 2000 |
|
|
| 2 | 3000×D = 6000 |
|
|
| 3 | 10×D = 30 |
|
|
| 3 | 30×D = 90 |
|
|
| 3 | 100×D = 300 |
|
|
| 3 | 300×D = 900 |
|
|
| 3 | 1000×D = 3000 |
|
|
| 3 | 3000×D = 9000 |
|
|
| 5 | 10×D = 50 |
|
|
| 5 | 30×D = 150 |
|
|
| 5 | 100×D = 500 |
|
|
| 5 | 300×D = 1500 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 5 | 1000×D = 5000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 5 | 3000×D = 15000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 10 | 10×D = 100 |
|
|
| 10 | 30×D = 300 |
|
|
| 10 | 100×D = 1000 |
|
|
| 10 | 300×D = 3000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 10 | 1000×D = 10000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 10 | 3000×D = 30000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 20 | 10×D = 200 |
|
|
| 20 | 30×D = 600 |
|
|
| 20 | 100×D = 2000 |
|
|
| 20 | 300×D = 6000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 20 | 1000×D = 20000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 20 | 3000×D = 60000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 40 | 10×D = 400 |
|
|
| 40 | 30×D = 1200 |
|
|
| 40 | 100×D = 4000 |
|
|
| 40 | 300×D = 12000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 40 | 1000×D = 40000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
| 40 | 3000×D = 120000 |
If STEP’s separability check reads separable, the local tests are skipped and the finisher follows. |
|
Source: dry run of the configuration’s own control flow with the probe outcomes forced, configuration c43, hash 781edd1e0767c7e2. Evaluation counts are the dry run’s allocations.
Which route each bbob function actually takes in the final test: pending (the harness did not log routes).
Watch it work
Section titled “Watch it work”The player replays one recorded run of AMM (preset c46) and one run of pycma IPOP on the same two-dimensional function, from the same start point and seed, with the same budget. The shading shows the landscape in powers of ten of the distance from the optimum value. Play, pause, step with the arrow keys, reset with R, or drag the slider.
Reproduce this run
The timeline strip under the slider shows only what the frozen code reports. AMM can report the blocks of its ATM
sampler through the documented profiler hook, so those evaluations are marked. The other stages (COBYQA, SLSQP,
Nelder–Mead, STEP, MLSL, CMA-ES, the probes) are not reported by any hook in the frozen code, and the strip does
not guess them. A run that never enters the ATM stage, such as a Gallagher run routed to MLSL, shows no strip.
Full stage tracing needs a change to the code and waits for the post-FT1 branch; the exact hook is in
data/demo/README.md.
What c46 adds
Section titled “What c46 adds”The frozen preset builds on c43 with the changes below, as described in src/amm_optimizer/presets.py. They affect the prefix
and the local routes rather than the gates drawn in the figure.
c44: a plateau check in the prefix above 30D from D = 5, which hands plateau functions to restarted CMA-ES populations; and, at budgets up to 10D for D = 4 to 20, a reading of the prefix’s first SLSQP descent that hands rugged or non-quadratic runs to restarted COBYQA.c45: the capped BFGS try on rugged readings continues where its best point reads a kink; a ridge reading in the prefix hands a descent that overshoots a sharp ridge to restarted COBYQA; the one-descent prefixes retry a descent that did not move; the finisher’s populations start at once on a band of rugged readings; and any box is mapped onto [-5, 5]D.c46: in the prefix at 100D, a very low finite rugged curvature reading keeps the (1+1)-CMA-ES instead of switching to lq2 populations.
The confirmation of each change on fresh instance ids is recorded in that docstring. Each probe and engine above is
named in src/amm_optimizer/, so every statement on this page can be checked against the code of the public repository (https://github.com/BjBodner/amm-optimizer, commit c4f0ab1).