5

I'm using scipy.optimize.minimize to find the minimum of a 4D function that is rather sensitive to the initial guess used. If I vary it a little bit, the solution will change considerably.

There are many questions similar to this one already in SO (e.g.: 1, 2, 3), but no real answer.

In an old question of mine, one of the developers of the zunzun.com site (apparently no longer online) explained how they managed this:

Zunzun.com uses the Differential Evolution genetic algorithm (DE) to find initial parameter estimates which are then passed to the Levenberg-Marquardt solver in scipy. DE is not actually used as a global optimizer per se, but rather as an "initial parameter guesser".

The closest I've found to this algorithm is this answer where a for block is used to call the minimizing function many times with random initial guesses. This generates multiple minimized solutions, and finally the best (smallest value) one is picked.

Is there something like what the zunzun dev described already implemented in Python?

Community
  • 1
  • 1
Gabriel
  • 40,504
  • 73
  • 230
  • 404
  • 1
    Your question seems pretty similar to [this](http://stackoverflow.com/questions/4227538/python-module-for-multiple-variable-global-optimization) one (though old). The answer references [`anneal`](http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.optimize.anneal.html) which uses simulated annealing that is often used in place of GA algorithms. They also mention [PyEvolve](https://github.com/perone/Pyevolve) as a library that provides genetic algorithms. – Bakuriu Feb 09 '16 at 20:04
  • anneal is deprecated but apparently [basin-hopping](http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.optimize.basinhopping.html) does precisely what I asked. Would you like to post your cmmt in the form of an answer? – Gabriel Feb 09 '16 at 20:12
  • 1
    I've had success implementing genetic algorithms using [DEAP](http://deap.readthedocs.org/en/master/). [`sklearn.grid_search`](http://scikit-learn.org/stable/modules/grid_search.html#grid-search) also has various exhaustive and stochastic methods for hyperparameter optimization. – ali_m Feb 09 '16 at 20:13

1 Answers1

5

There is no general answer for such question, as a problem of minimizing arbitrary function is impossible to solve. You can do better or worse on particular classes of functions, thus it is rather a domain for mathematician, to analyze how your function probably looks like.

Obviously you can also work with dozens of so called "meta optimizers", which are just bunch of heuristics, which might (or not) work for you particular application. Those include random sampling starting point in a loop, using genetic algorithms, or - which is as far as I know most mathematically justified approach - using Bayesian optimization. In general the idea is to model your function in the same time when you try to minimize it, this way you can make informed guess where to start next time (which is level of abstraction higher than random guessing or using genetic algorithms/differential evolution). Thus, I would order these methods in following way

  • grid search / random sampling - uses no information from previous runs, thus - worst results
  • genetic approach, evolutionary, basin-hooping, annealing - use information from previous runs as a (x, f(x)) pairs, for limited period of time (generations) - thus average results
  • Bayesian optimization (and similar methods) - use information from all previous experiences through modeling of the underlying function and performing sampling selection based on expected improvement - best results (at the cost of most complex methods)
lejlot
  • 64,777
  • 8
  • 131
  • 164