API to control iteration in differential evolution #6923
Hi, Recently there have been discussions about possible extensions of scipy.optimize.differential_evolution() : * https://github.com/scipy/scipy/issues/6878 is about having the callback function receive the function value * https://github.com/scipy/scipy/issues/6879 is about customizing of population initialization The differential_evolution function being already quite complex, we thought it would be better to expose a "lower level" API to control the iteration in the algorithm. This would be done by making the DifferentialEvolutionSolver class (in scipy/optimize/_differentialevolution.py) public and cleaning it a bit. I submitted a pull request for this : https://github.com/scipy/scipy/pull/6923 One noticeable thing is that it also makes the class a context manager to encapsulate the population initialization (in enter step) and final polishing (in exit step). Ultimately, usage of this class (renamed as DifferentialEvolution) would be: with DifferentialEvolution(func, bounds) as solver: # iterate until maxiter/maxfev is reached or the algorithm converged for step in solver: if mycallback(step.x, step.fun): break result = solver.result I might look a bit fancy, but I think it makes sense to regard a computation as a kind of context. Feedback welcome! Cheers, Denis.
On Wed, Jan 11, 2017 at 12:38 PM, Denis Laxalde <denis@laxalde.org> wrote:
Hi,
Recently there have been discussions about possible extensions of scipy.optimize.differential_evolution() :
* https://github.com/scipy/scipy/issues/6878 is about having the callback function receive the function value
* https://github.com/scipy/scipy/issues/6879 is about customizing of population initialization
The differential_evolution function being already quite complex, we thought it would be better to expose a "lower level" API to control the iteration in the algorithm. This would be done by making the DifferentialEvolutionSolver class (in scipy/optimize/_differentialevolution.py) public and cleaning it a bit.
I submitted a pull request for this : https://github.com/scipy/scipy/pull/6923 One noticeable thing is that it also makes the class a context manager to encapsulate the population initialization (in enter step) and final polishing (in exit step). Ultimately, usage of this class (renamed as DifferentialEvolution) would be:
with DifferentialEvolution(func, bounds) as solver: # iterate until maxiter/maxfev is reached or the algorithm converged for step in solver: if mycallback(step.x, step.fun): break result = solver.result
I might look a bit fancy, but I think it makes sense to regard a computation as a kind of context. Feedback welcome!
FWIW, +1 from me. (I'm not a heavy user however) Exposing the iteration API seems reasonable and better than relying on callbacks. Small details, feel free to take or leave: 1. What is `step` in `for step in solver`? If it's a current "state of the minimizer", then can its contents be retrieved from the solver object itself (step vs `solver.result` above)? Or is it just a step number and the solver holds all the information at each step via `solver.result?` This needs to be specified and documented. 2. Since the solver class is iterable, just iterating it without the context manager should be equivalent. Something like this (pseudocode) solver = DifferentialEvolutionSolver(...) while not_converged: result = next(solver) should be equivalent to your example above (modulo callback). 3. My mental model would be that the solver being iterable and the context manager are both a syntax sugar for a pair of methods, roughly `Solver.make_a_single_step_then_pause()` and `Solver.do_full_minimization_until_convergence()` which repeatedly calls the first one. (This might be influenced by a DIY MC code I had a while ago, https://github.com/evbr/mcba/blob/master/mcba/abstract_walker.py#L80, not sure how well it maps onto this case, so feel free to disregard) 4. Having the solver class iterable, with or without the context manager, forces the iteration to happen at the python level. This is likely not a problem with the current code, where the whole class is in python anyway. However if some future refactoring moves parts of the implementation to a compiled code, the overhead can get significant. This seems to argue for a blackbox `do_a_full_simulation` method. (Again, this might be my MCMC background talking, where a single step is cheap and the python generator overhead is nontrivial.) Cheers, Evgeni
I also give a big +1 to exposing the individual steps in the algorithm. However I echo Evgeni in that treating it as an iterable `for step in solver:` is a bit unintuitive and I prefer the more straightforward `solver. make_a_single_step_then_pause()`. For what it's worth the underlying solver in basinhopping uses this mechanism, although it's not exposed publicly. for i in range(niter): new_global_min = bh.one_cycle() If we expose this functionality in differential_evolution we could do the same in basinhopping using whatever common syntax is agreed upon. On Sat, 14 Jan 2017 at 13:49 Evgeni Burovski <evgeny.burovskiy@gmail.com> wrote:
On Wed, Jan 11, 2017 at 12:38 PM, Denis Laxalde <denis@laxalde.org> wrote:
Hi,
Recently there have been discussions about possible extensions of scipy.optimize.differential_evolution() :
* https://github.com/scipy/scipy/issues/6878 is about having the callback function receive the function value
* https://github.com/scipy/scipy/issues/6879 is about customizing of population initialization
The differential_evolution function being already quite complex, we thought it would be better to expose a "lower level" API to control the iteration in the algorithm. This would be done by making the DifferentialEvolutionSolver class (in scipy/optimize/_differentialevolution.py) public and cleaning it a bit.
I submitted a pull request for this : https://github.com/scipy/scipy/pull/6923 One noticeable thing is that it also makes the class a context manager to encapsulate the population initialization (in enter step) and final polishing (in exit step). Ultimately, usage of this class (renamed as DifferentialEvolution) would be:
with DifferentialEvolution(func, bounds) as solver: # iterate until maxiter/maxfev is reached or the algorithm converged for step in solver: if mycallback(step.x, step.fun): break result = solver.result
I might look a bit fancy, but I think it makes sense to regard a computation as a kind of context. Feedback welcome!
FWIW, +1 from me. (I'm not a heavy user however)
Exposing the iteration API seems reasonable and better than relying on callbacks.
Small details, feel free to take or leave:
1. What is `step` in `for step in solver`? If it's a current "state of the minimizer", then can its contents be retrieved from the solver object itself (step vs `solver.result` above)? Or is it just a step number and the solver holds all the information at each step via `solver.result?` This needs to be specified and documented.
2. Since the solver class is iterable, just iterating it without the context manager should be equivalent. Something like this (pseudocode)
solver = DifferentialEvolutionSolver(...) while not_converged: result = next(solver)
should be equivalent to your example above (modulo callback).
3. My mental model would be that the solver being iterable and the context manager are both a syntax sugar for a pair of methods, roughly `Solver.make_a_single_step_then_pause()` and `Solver.do_full_minimization_until_convergence()` which repeatedly calls the first one. (This might be influenced by a DIY MC code I had a while ago, https://github.com/evbr/mcba/blob/master/mcba/abstract_walker.py#L80, not sure how well it maps onto this case, so feel free to disregard)
4. Having the solver class iterable, with or without the context manager, forces the iteration to happen at the python level. This is likely not a problem with the current code, where the whole class is in python anyway. However if some future refactoring moves parts of the implementation to a compiled code, the overhead can get significant. This seems to argue for a blackbox `do_a_full_simulation` method. (Again, this might be my MCMC background talking, where a single step is cheap and the python generator overhead is nontrivial.)
Cheers,
Evgeni _______________________________________________ SciPyDev mailing list SciPyDev@scipy.org https://mail.scipy.org/mailman/listinfo/scipydev
Jacob Stevenson a écrit :
I also give a big +1 to exposing the individual steps in the algorithm. However I echo Evgeni in that treating it as an iterable `for step in solver:` is a bit unintuitive and I prefer the more straightforward `solver.make_a_single_step_then_pause()`. For what it's worth the underlying solver in basinhopping uses this mechanism, although it's not exposed publicly.
for i in range(niter): new_global_min = bh.one_cycle()
See my answer to Evgeni's point; it's implemented as a `__next__` method.
If we expose this functionality in differential_evolution we could do the same in basinhopping using whatever common syntax is agreed upon
That'd be nice, indeed.
Evgeni Burovski a écrit :
Small details, feel free to take or leave:
1. What is `step` in `for step in solver`? If it's a current "state of the minimizer", then can its contents be retrieved from the solver object itself (step vs `solver.result` above)? Or is it just a step number and the solver holds all the information at each step via `solver.result?` This needs to be specified and documented.
This `step` is an `OptimizeStep`. It's a new class introduced here to wrap any useful information produced by the solver during one iteration. In this case, it holds the current `x` and function value along with iteration number. The idea is to return an extensible object instead of, say, a tuple that may cause bw compat issues in the future. I think this is documented, feel free to comment further if things are not clear enough.
2. Since the solver class is iterable, just iterating it without the context manager should be equivalent. Something like this (pseudocode)
solver = DifferentialEvolutionSolver(...) while not_converged: result = next(solver)
should be equivalent to your example above (modulo callback).
It's already possible as: while not solver.converged(): step = next(solver) (only the `converged()` is new from this PR.) Also, the context manager interface is actually orthogonal to the iteration API. The context manager abstracts out the solver *initialization* (population initialization and energies calculation) and *termination* (possible polishing and build of the `OptimizeResult`). In the PR, there have been discussions to expose these steps as public methods to make the use of the context manager optional; I'm fine with this if it makes things clearer (though the use case is not clear to me).
3. My mental model would be that the solver being iterable and the context manager are both a syntax sugar for a pair of methods, roughly `Solver.make_a_single_step_then_pause()` and `Solver.do_full_minimization_until_convergence()` which repeatedly calls the first one. (This might be influenced by a DIY MC code I had a while ago, https://github.com/evbr/mcba/blob/master/mcba/abstract_walker.py#L80, not sure how well it maps onto this case, so feel free to disregard)
This `make_a_single_step_then_pause` method is just called `__next__` (this is not new). I personally find `step = next(solver)` explicit enough not to require a more specific method, but that's arguable. The `Solver.do_full_minimization_until_convergence()` is basically the (convenience) function `differential_evolution`. There used to be a `solve()` method on the solver class but I dropped it as I did not see any use case where one would want this over just using the convenience function (also arguable).
4. Having the solver class iterable, with or without the context manager, forces the iteration to happen at the python level. This is likely not a problem with the current code, where the whole class is in python anyway. However if some future refactoring moves parts of the implementation to a compiled code, the overhead can get significant. This seems to argue for a blackbox `do_a_full_simulation` method. (Again, this might be my MCMC background talking, where a single step is cheap and the python generator overhead is nontrivial.)
Can't really comment on this point. The "problem" already exists in the current implementation AFAICT. Maybe this means we'll ultimately have to move the whole class to a compiled code implementation? Thank you for your feedback.
On 15 January 2017 at 05:03, Denis Laxalde <denis@laxalde.org> wrote:
Evgeni Burovski a écrit :
Small details, feel free to take or leave:
1. What is `step` in `for step in solver`? If it's a current "state of the minimizer", then can its contents be retrieved from the solver object itself (step vs `solver.result` above)? Or is it just a step number and the solver holds all the information at each step via `solver.result?` This needs to be specified and documented.
This `step` is an `OptimizeStep`. It's a new class introduced here to wrap any useful information produced by the solver during one iteration. In this case, it holds the current `x` and function value along with iteration number. The idea is to return an extensible object instead of, say, a tuple that may cause bw compat issues in the future. I think this is documented, feel free to comment further if things are not clear enough.
Best `x` and best energy are already available as `solver.x` and `solver.population_energy[0]`, but I think this kind of object being returned from `__next__` is a good idea. Does it have to be an `OptimizeStep`, or can we return an preliminary `OptimizeResult`? 2. Since the solver class is iterable, just iterating it without the
context manager should be equivalent. Something like this (pseudocode)
solver = DifferentialEvolutionSolver(...) while not_converged: result = next(solver)
Also, the context manager interface is actually orthogonal to the iteration API. The context manager abstracts out the solver *initialization* (population initialization and energies calculation) and *termination* (possible polishing and build of the `OptimizeResult`).
Whilst the context manager is orthogonal to the iteration API, Evgeni's example would not be possible with the PR is it currently exists  the only way of initialising the solver (population initialization and energies calculation) would be to go through the context manager. Denis suggested that a way around this would be to have a separate initialize_population() method. It's a good idea to have this method (for reasons I outline later). However, if you create the object outside a context manager I don't think that one should have to call an additional initialize_population() method to be able to iterate the object. There are a few reasons for this: (a) it's an extra line to type (b) iterating the object without going through the context manager is not equivalent (c) the solver object possesses public population and population_energies attributes, these attributes need to be present in a newly created object, not be created at a later stage (d) if the population and population_energies attributes are present I'd argue it makes more sense for them to contain relevant values (e) given a solver object how does one know if initialize_population has already been called (which would be a common occurrence when used in an interactive interpreter)? (f) you can't call next(solver) if the population hasn't been initialised. You shouldn't need to know the state of the solver object to be able to iterate it, it should be iterable straightaway. Currently the initial energy calculations are done in `__init__` and one uses the object as: # stepwise solver = DifferentialEvolutionSolver(...) while not solver.converged: next(solver) or # all at once solver = DifferentialEvolutionSolver(...) result = solver.solve() The proposed PR: with solver as DifferentialEvolutionSolver(...): while not solver.converged(): next(solver) result = solver.result or possibly solver = DifferentialEvolutionSolver(...) # extra line to type, solver.initialize_population() while not solver.converged: next(solver) Perhaps the following course could be followed: (1) make the __next__ method return an OptimizeStep object (or OptimizeResult). (2) add a polish() method that takes the current best solution and polishes it. Having a separate polish method is useful as you can polish the object at any step, getting functionality similar to optimize.brute. (3) Add __enter__() and __exit__() methods to allow the object to be used as a context manager. The __exit__() method can use the public polish() method. I'd like to keep the existing solve() method, it can call __exit__() at the end. (4) population initialization and the initial energy calculation is moved to a public method, initialize_population(). This method is either called from __init__ (the status quo), or it is called on the first call to __next__(), making the first call to __next__ take twice as long. My preference is to keep the status quo because one can create the solver and immediately polish the best population member (c.f. optimize.brute), as well as the points raised above. The rationale for making it public is that once you've done one optimization you can reinitialise it with a different method ('latinhypercube' or 'random') and solve again or you could imagine reinitialising the population with a given population array (which has been requested previously) and start iterating again. A.
On Sat, Jan 14, 2017 at 11:20 PM, Andrew Nelson <andyfaff@gmail.com> wrote:
On 15 January 2017 at 05:03, Denis Laxalde <denis@laxalde.org> wrote:
Evgeni Burovski a écrit :
Small details, feel free to take or leave:
1. What is `step` in `for step in solver`? If it's a current "state of the minimizer", then can its contents be retrieved from the solver object itself (step vs `solver.result` above)? Or is it just a step number and the solver holds all the information at each step via `solver.result?` This needs to be specified and documented.
This `step` is an `OptimizeStep`. It's a new class introduced here to wrap any useful information produced by the solver during one iteration. In this case, it holds the current `x` and function value along with iteration number. The idea is to return an extensible object instead of, say, a tuple that may cause bw compat issues in the future. I think this is documented, feel free to comment further if things are not clear enough.
Best `x` and best energy are already available as `solver.x` and `solver.population_energy[0]`, but I think this kind of object being returned from `__next__` is a good idea. Does it have to be an `OptimizeStep`, or can we return an preliminary `OptimizeResult`?
2. Since the solver class is iterable, just iterating it without the context manager should be equivalent. Something like this (pseudocode)
solver = DifferentialEvolutionSolver(...) while not_converged: result = next(solver)
Also, the context manager interface is actually orthogonal to the iteration API. The context manager abstracts out the solver *initialization* (population initialization and energies calculation) and *termination* (possible polishing and build of the `OptimizeResult`).
Whilst the context manager is orthogonal to the iteration API, Evgeni's example would not be possible with the PR is it currently exists  the only way of initialising the solver (population initialization and energies calculation) would be to go through the context manager. Denis suggested that a way around this would be to have a separate initialize_population() method. It's a good idea to have this method (for reasons I outline later). However, if you create the object outside a context manager I don't think that one should have to call an additional initialize_population() method to be able to iterate the object. There are a few reasons for this: (a) it's an extra line to type (b) iterating the object without going through the context manager is not equivalent (c) the solver object possesses public population and population_energies attributes, these attributes need to be present in a newly created object, not be created at a later stage (d) if the population and population_energies attributes are present I'd argue it makes more sense for them to contain relevant values (e) given a solver object how does one know if initialize_population has already been called (which would be a common occurrence when used in an interactive interpreter)? (f) you can't call next(solver) if the population hasn't been initialised. You shouldn't need to know the state of the solver object to be able to iterate it, it should be iterable straightaway.
Currently the initial energy calculations are done in `__init__` and one uses the object as:
# stepwise solver = DifferentialEvolutionSolver(...) while not solver.converged: next(solver)
or
# all at once solver = DifferentialEvolutionSolver(...) result = solver.solve()
The proposed PR:
with solver as DifferentialEvolutionSolver(...): while not solver.converged(): next(solver) result = solver.result
or possibly
solver = DifferentialEvolutionSolver(...) # extra line to type, solver.initialize_population() while not solver.converged: next(solver)
Perhaps the following course could be followed:
(1) make the __next__ method return an OptimizeStep object (or OptimizeResult). (2) add a polish() method that takes the current best solution and polishes it. Having a separate polish method is useful as you can polish the object at any step, getting functionality similar to optimize.brute. (3) Add __enter__() and __exit__() methods to allow the object to be used as a context manager. The __exit__() method can use the public polish() method. I'd like to keep the existing solve() method, it can call __exit__() at the end. (4) population initialization and the initial energy calculation is moved to a public method, initialize_population(). This method is either called from __init__ (the status quo), or it is called on the first call to __next__(), making the first call to __next__ take twice as long. My preference is to keep the status quo because one can create the solver and immediately polish the best population member (c.f. optimize.brute), as well as the points raised above. The rationale for making it public is that once you've done one optimization you can reinitialise it with a different method ('latinhypercube' or 'random') and solve again or you could imagine reinitialising the population with a given population array (which has been requested previously) and start iterating again.
It seems to me we are all saying pretty much the same thing: 1. If an instance of DifferentialEvolutionSolver is used as a context manager, __init__ is called before __enter__ anyway, so all initialization can happen in __init__, like it does in master: In [33]: class C(object): def __init__(self): print('init') def __enter__(self): print('enter') def __exit__(self, *args, **kwds): print('exit', args, kwds) ....: In [34]: with C() as c: ....: pass ....: init enter ('exit', (None, None, None), {}) This way it seems there's no need for either having a special `init_population` method or doing something special at first call to __next__ 2. Since __init__ is always called, various initialization strategies can be handled as a keyword arg in __init__(..., init_method="latinhypercube"), possibly overloaded for a callable or a population from a previous run? Or maybe the latter (reusing a population) is better handled by an alternative constructor. But this is certainly separate from both the context manager or iteration. 3. I agree with Denis that `make_a_step_then_stop` is spelled __next__ in python :). 4. `.solve` method is indeed the standalone `differential_evolution` function. 5. It seems natural to use __exit__ for polishing, if desired. 6. OptimizeStep could be a (current version of) OptimizeResult. In fact, I'd suggest it *is* an OptimizeResult. Am I missing something? Evgeni
Evgeni Burovski a écrit :
It seems to me we are all saying pretty much the same thing:
More or less ;) I agree with most of your points, some more comments below.
2. Since __init__ is always called, various initialization strategies can be handled as a keyword arg in __init__(..., init_method="latinhypercube"), possibly overloaded for a callable or a population from a previous run? Or maybe the latter (reusing a population) is better handled by an alternative constructor. But this is certainly separate from both the context manager or iteration.
We can certainly do that. As mentioned in the PR thread, it seems to me that __init__ method is not the proper place to run (possibly long) calculations such as population initialization. This is just a matter of separation of concerns.
6. OptimizeStep could be a (current version of) OptimizeResult. In fact, I'd suggest it *is* an OptimizeResult.
Not sure I agree here. It seems to me that there's some value in distinguishing a step from a final result and using a different type looks appropriate. If you get an OptimizeResult at every iteration of the loop, it would be incomplete; missing in particular the "status" and "message" attributes, unless we set them to, e.g., status=None, message="in progress". This could bring confusion to the user who wouldn't know if its result is actually a result or just a step unless they introspect its content. To continue discussion on technical aspects, I would suggest moving back to the PR thread.
participants (4)

Andrew Nelson

Denis Laxalde

Evgeni Burovski

Jacob Stevenson