Shrink the differential evolution population over the run, floored at the processor count (L-SHADE's population-size reduction)

[wshlavacek]

Gated on #698. Plain ade currently collapses its population and stops early on small models, so its benchmark rows measure that fault rather than the method; the comparison this issue needs, de and ade with and without the schedule from the same seeds, is only meaningful once #698 has landed and its re-score has produced sound baseline rows.

What happens now

population_size is fixed for the whole run. The population that is right for exploring at the start, large so the initial spread covers the box, is not the one that is right for refining at the end, where a small population around the best members converges faster with the same budget. #667 adopted SHADE's success-history adaptation of the mutation settings (ADR-0142) and deliberately left this half of L-SHADE out, on the grounds that it is a separate mechanism and interacts with how many processors a run keeps busy. It should be judged on its own, and this is the issue for that.

The suggestion

Shrink the population linearly over the run, as Tanabe and Fukunaga's L-SHADE does: at the end of each generation compute the population size the schedule calls for at that point in the budget, and remove the worst members until the population is that size. L-SHADE runs from 18 times the number of parameters down to 4 over the evaluation budget.

Two adaptations to PyBNF:

• Floor the population at the processor count. The number in flight is the population for ade, and a generation's parallel width for de, so a population that shrinks below the machine idles it. The run already knows how many workers it has, from the parallelism report (Nothing warns when a fit uses far fewer processors than were reserved #621, Parallelism warning is computed from the initialization round, so scatter search fits are wrongly told to lower population_size #655), so the schedule can shrink toward L-SHADE's floor on a laptop and stop at the worker count on an allocation. That turns the objection that deferred this into a design constraint.
• Schedule in iterations, against max_iterations. L-SHADE schedules in evaluations against a known budget. PyBNF's budget is max_iterations generations; the convergence stop can end the run before it, which only means the schedule did not reach its floor.

Removing members touches the bookkeeping: de indexes its population by slot and its candidates by name, ade names candidates gen<i>ind<j> and may have a candidate in flight for a slot that no longer exists when its result comes back. de with islands shrinks each island.

Off by default, or on under the modern edition and off under the legacy one as ADR-0137 did, so an existing configuration is byte-identical.

Why it is worth doing

• In the literature it is the larger part of L-SHADE. SHADE was among the top entrants at CEC 2013; SHADE with this schedule won CEC 2014. If the adaptation was worth adopting on that record, the schedule has at least as much behind it.
• The uncertainty is PyBNF's regime, and it is cheap to measure. The literature runs populations of 18 times the dimension for thousands of generations; PyBNF runs 20 to 50 for a few hundred, on simulations that cost seconds to minutes. Whether the schedule helps at those sizes is not known, and a crude version (drop the worst member every few generations toward a floor) can be scored on the analytical harness in minutes and on the stochastic recovery benchmark (Build a parameter recovery benchmark for fitting stochastic rule-based models #663) in an afternoon, since the runner is single-process and parallelism does not enter. Build the proper version only if the crude one shows a gain.

Care needed

• On a stochastic objective the worst members are partly the unlucky draws, so removing them is not the same operation it is on a deterministic function. Measure on the stochastic benchmark, not only on analytical targets, and look at whether the run's reported best gets worse as the population thins.
• The interaction with de_adapt_mutation: measure the schedule alone and with the learned settings, from the same seeds, so the two effects stay separable. The same discipline as Learn the differential evolution mutation settings during a run instead of asking the user for them #667's control.
• A driven test that the bookkeeping stays consistent as slots vanish under both methods, including a result arriving for a removed ade slot, and the fake-rng oracles in tests/test_diff_evolution.py pinning that the off path makes no extra draw.

Related

• ade collapses its population onto one parameter set and stops early, because a candidate can be an exact copy of its base #698, the gate: the copy guarantee that gives ade a sound baseline.
• Learn the differential evolution mutation settings during a run instead of asking the user for them #667 and ADR-0142, where this was deferred and why.
• Build a parameter recovery benchmark for fitting stochastic rule-based models #663, the benchmark that will judge it.
• Nothing warns when a fit uses far fewer processors than were reserved #621 and Parallelism warning is computed from the initialization round, so scatter search fits are wrongly told to lower population_size #655, the parallelism report the floor would read.
• Tanabe, R. and Fukunaga, A. S. (2014). Improving the search performance of SHADE using linear population size reduction. IEEE Congress on Evolutionary Computation, 1658 to 1665.