[SciPy-Dev] optimize: add algorithm for global optimization basin hopping

[Ralf Gommers]

On Tue, Oct 9, 2012 at 11:30 PM, Jacob Stevenson <jstevenson131 at gmail.com>wrote:

> Hi everyone, I just submitted a pull request to incorporate a basinhopping
> routine in the optimize package.  Basinhopping is a powerful algorithm,
> but all the hard work would be done by the minimizers that already exist in
> scipy.optimize, so the additional code needed is really not very much.
>
> The following is from the documentation notes:
>
> Basin hopping is a random algorithm which attempts to find the global
> minimum of a smooth scalar function of one or more variables.  The
> algorithm was originally described by David Wales
> http://www-wales.ch.cam.ac.uk/ .  The algorithm is iterative with each
> iteration composed of the following steps
>
> 1) random displacement of the coordinates
>
> 2) local minimization
>
> 3) accept or reject the new coordinates based on the minimized function
> value.
>
> This global minimization method has been shown to be extremely efficient
> on a wide variety of problems in physics and chemistry.  It is especially
> efficient when the function has many minima separated by large barriers.
>  See the Cambridge Cluster Database http://www-wales.ch.cam.ac.uk/CCD.htmlfor database of molecular systems that have been optimized primarily using
> basin hopping.  This database includes minimization problems exceeding 300
> degrees of freedom.
>
> Thanks,
> Jake
>
> p.s. this is my first post and first submission
>

Hi Jake, welcome!

It looks to me like basin hopping would be a nice addition to
scipy.optimize. It looks quite similar to simulated annealing, which we
already have, and may be more efficient for certain classes of problems.
You're hinting at that already in the notes section, but more details on
that comparison would be good to put in the docs. A benchmark comparing
your algorithm with anneal() would be good to see also.

This PR made me wonder what other algorithms would be good to have, and
what's out of scope for scipy. My feeling is that some similar stochastic
algorithms to this one could be nice to have, but that other types of
global optimizers are out of scope - there's OpenOpt, IPOPT, PyGMO,
PyEvolve etc. for that.

Cheers,
Ralf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20121010/631fb6f3/attachment.html>