optimize - add algorithm for global optimization: GenSA
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.
In my opinion a robust implementation of a simulated annealing based optimizer would be welcome. There are cases when this would be preferable to basinhopping, e.g. when non-smooth or non-continuous functions make the local optimization step in basinhopping less effective. I think the first step is to make a pull request (or send a link if you already did) where we can review the code and have discussions. Best, Jake On Fri, 23 Oct 2015 at 14:10 Gubian, Sylvain <Sylvain.Gubian@pmi.com> wrote:
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. _______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org https://mail.scipy.org/mailman/listinfo/scipy-dev
I have a scipy PR for testing global optimisers. It has approx 120 functions, which is 2.5 times more than in the linked paper. I think for any global optimisers to be added it should give a good performance against those benchmarks. The main criterion is the number of successes and the avg number of function evaluations. Time is of secondary importance. Any optimisers added to scipy.optimize should conform to the generally standardised syntax (naming conventions, etc) used by the module. On 24 Oct 2015 1:06 am, "Jacob Stevenson" <jstevenson131@gmail.com> wrote:
In my opinion a robust implementation of a simulated annealing based optimizer would be welcome. There are cases when this would be preferable to basinhopping, e.g. when non-smooth or non-continuous functions make the local optimization step in basinhopping less effective.
I think the first step is to make a pull request (or send a link if you already did) where we can review the code and have discussions.
Best, Jake
On Fri, 23 Oct 2015 at 14:10 Gubian, Sylvain <Sylvain.Gubian@pmi.com> wrote:
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. _______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org https://mail.scipy.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org https://mail.scipy.org/mailman/listinfo/scipy-dev
On Fri, Oct 23, 2015 at 7:10 AM, Gubian, Sylvain <Sylvain.Gubian@pmi.com> wrote:
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.
I'm a bit concerned about license issues If any of the code comes from R. R has an incompatible license. Chuck
"Gubian, Sylvain" <Sylvain.Gubian@pmi.com> wrote:
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.
anneal was thrown out because it was very weak, not because we dislike SA in general. Although it was not clear if the weakness was due to the particular implementation or due to classical SA per se. If an implementation of SA can be shown to be strong I personally see nothing wrong with including it. Sturla
participants (5)
-
Andrew Nelson -
Charles R Harris -
Gubian, Sylvain -
Jacob Stevenson -
Sturla Molden