What happens now
Differential evolution builds each new candidate by taking one parameter set and shifting some of its values by the scaled difference between two other members of the population. Two settings control that, both in DEFamilyConfig in pybnf/algorithms/optimizers/differential_evolution.py:
mutation_rate: float = 0.5 # how often a given parameter is changed at all
mutation_factor: float = 0.5 # how large the change is
They are read once at startup and never change during a run. A user who does not know what to set is left guessing, and the same pair of numbers is used from the first iteration to the last even though early exploration and late refinement want different values.
Both de and ade share this, since both inherit from DifferentialEvolutionBase.
The suggestion
Adopt the approach from the SHADE family of differential evolution methods, which learn both values during the run instead of asking for them up front. The idea is straightforward. Keep a short history of the settings that produced a successful candidate, meaning one that beat the parameter set it was compared against. Draw the settings for each new candidate from that history, with some spread, so values that have been working recently get used more often. As the run moves from exploring to refining, the learned values move with it.
This is well established and has been the basis of the strongest differential evolution entrants in optimization competitions for over a decade.
- Tanabe, R. and Fukunaga, A. (2013). Success-history based parameter adaptation for differential evolution. IEEE Congress on Evolutionary Computation, 71 to 78.
- Tanabe, R. and Fukunaga, A. (2014). Improving the search performance of SHADE using linear population size reduction. IEEE Congress on Evolutionary Computation, 1658 to 1665.
Why it is worth doing
It removes two settings a user cannot reasonably choose. Neither number has an obvious right value, both matter, and nothing in the documentation can tell someone what to use for their model because it depends on the model.
ade is our best method for filling a large machine. It starts a new simulation the moment one finishes, so it has no point where processors sit idle waiting for the rest of a round, and it works at any number of processors. Making the method that already uses a cluster well also search better is a good trade.
It is a contained change. The candidate construction is one method, DifferentialEvolutionBase.new_individual. The work is to carry a per-candidate pair of settings through to the point where a result comes back, record whether it succeeded, and keep the history. For ade the bookkeeping is per candidate rather than per generation, which suits the success history well since it is updated one success at a time anyway.
Care needed
- Keep it optional and off by default, so an existing configuration reproduces its current behaviour exactly.
ade returns results in whatever order simulations finish, so the record of which settings produced a candidate has to travel with that candidate rather than being held in a per-iteration variable.- The linear population reduction described in the second paper is a separate idea from the settings adaptation. It is worth considering, but it interacts with how many processors are kept busy, so it should be judged on its own rather than adopted as a package.
Note on priority
This was discussed and deliberately set aside in favour of the scatter search work in #660, on the grounds that scatter search gives better fits on our problems and is where the larger gain is. Filing it so the decision is recorded rather than forgotten. It is a smaller and more self-contained piece of work than #660, so it may be worth doing while that epic is in progress.
Related
What happens now
Differential evolution builds each new candidate by taking one parameter set and shifting some of its values by the scaled difference between two other members of the population. Two settings control that, both in
DEFamilyConfiginpybnf/algorithms/optimizers/differential_evolution.py:They are read once at startup and never change during a run. A user who does not know what to set is left guessing, and the same pair of numbers is used from the first iteration to the last even though early exploration and late refinement want different values.
Both
deandadeshare this, since both inherit fromDifferentialEvolutionBase.The suggestion
Adopt the approach from the SHADE family of differential evolution methods, which learn both values during the run instead of asking for them up front. The idea is straightforward. Keep a short history of the settings that produced a successful candidate, meaning one that beat the parameter set it was compared against. Draw the settings for each new candidate from that history, with some spread, so values that have been working recently get used more often. As the run moves from exploring to refining, the learned values move with it.
This is well established and has been the basis of the strongest differential evolution entrants in optimization competitions for over a decade.
Why it is worth doing
It removes two settings a user cannot reasonably choose. Neither number has an obvious right value, both matter, and nothing in the documentation can tell someone what to use for their model because it depends on the model.
adeis our best method for filling a large machine. It starts a new simulation the moment one finishes, so it has no point where processors sit idle waiting for the rest of a round, and it works at any number of processors. Making the method that already uses a cluster well also search better is a good trade.It is a contained change. The candidate construction is one method,
DifferentialEvolutionBase.new_individual. The work is to carry a per-candidate pair of settings through to the point where a result comes back, record whether it succeeded, and keep the history. Foradethe bookkeeping is per candidate rather than per generation, which suits the success history well since it is updated one success at a time anyway.Care needed
adereturns results in whatever order simulations finish, so the record of which settings produced a candidate has to travel with that candidate rather than being held in a per-iteration variable.Note on priority
This was discussed and deliberately set aside in favour of the scatter search work in #660, on the grounds that scatter search gives better fits on our problems and is where the larger gain is. Filing it so the decision is recorded rather than forgotten. It is a smaller and more self-contained piece of work than #660, so it may be worth doing while that epic is in progress.
Related