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

[Gubian, Sylvain]

Hi everyone,

We would like to propose a new method, GenSA,  for global optimization to be included in the optimize module.

GenSA is an implementation of the General Simulated Annealing algorithm (GSA, http://www.sciencedirect.com/science/article/pii/S0378437196002713). This approach generalizes CSA (Classical Simulated Annealing) and FSA (Fast Simulated Annealing) to search for the global minimum more efficiently. The algorithm is explained in more detail in this reference: http://journal.r-project.org/archive/2013-1/xiang-gubian-suomela-etal.pdf.

SciPy has already in the past included a method based on simulated annealing, called anneal, which has been deprecated in 0.14 (with an advice to use basinhopping) and eventually removed in 0.16.

A previously published comparison of 18 optimization methods in the R language (http://www.jstatsoft.org/v60/i06/paper) shows that GenSA is, among the methods tested, one of the “most capable of consistently returning a solution near the global minimum of each test function”. This paper however did not consider basinhopping, so we have performed some tests which tend to show that GenSA is more efficient than basinhopping  for high dimension problems. The results have been presented in a poster in PyCon UK 2015 (Coventry).

The code is ready and passes unit tests and PEP8. We hope it would be a useful addition to SciPy and would be happy to have your opinion.

Thanks,

Sylvain.