[SciPy-Dev] optimize - add algorithm for global optimization: GenSA
Gubian, Sylvain
Sylvain.Gubian at pmi.com
Tue Nov 10 09:05:36 EST 2015
Dear All,
Thanks a lot for Jake, Andrew, Chuck and Sturla comments.
I would like to address some comments so that I would know how to go forward, like doing a pull request whenever you think it makes sense.
@Jake: As you mentioned, there are situations where basinhopping may not work as well as PyGenSA, especially in cases of high number of parameters. This implementation has actually been focused on solving high dimension problems. However, it also works for very simple problems, but in those cases it might show non-optimal performance (in terms of avg number of function calls). The battery test shows that in general, the number of successes is almost always better than basinhopping, PyGenSA is a robust implementation.
As attached, a PDF version of the poster I presented to PyCon UK Coventry in September 2015 showing a performance benchmark.
@Chuck: About license, I am the author and maintainer of the R version. The python version is a pure python implementation and there is no code taken from R. Therefore, I don't think there is any license issue.
Best regards,
Sylvain.
------------------------------------------------------------------------------------------------------------------------------------
Date: Sat, 24 Oct 2015 08:39:44 -0600
From: Charles R Harris <charlesr.harris at gmail.com<mailto:charlesr.harris at gmail.com>>
To: SciPy Developers List <scipy-dev at scipy.org<mailto:scipy-dev at scipy.org>>
Subject: Re: [SciPy-Dev] optimize - add algorithm for global
optimization: GenSA
Message-ID:
<CAB6mnxJy8n+yfJ9TMJAZWNGLJ4J4_hs58T-W3snrgdsmRs0b0w at mail.gmail.com<mailto:CAB6mnxJy8n+yfJ9TMJAZWNGLJ4J4_hs58T-W3snrgdsmRs0b0w at mail.gmail.com>>
Content-Type: text/plain; charset="utf-8"
...
I'm a bit concerned about license issues If any of the code comes from R. R has an incompatible license.
Chuck
------------------------------------------------------------------------------------------------------------------------------------
Date: Sat, 24 Oct 2015 10:00:22 +1100
From: Andrew Nelson <andyfaff at gmail.com<mailto:andyfaff at gmail.com>>
To: SciPy Developers List <scipy-dev at scipy.org<mailto:scipy-dev at scipy.org>>
Subject: Re: [SciPy-Dev] optimize - add algorithm for global
optimization: GenSA
Message-ID:
<CAAbtOZctBQeqjc5+QucA4XADC=F1MqKjPTHJDMb6XQjB-dkM7w at mail.gmail.com<mailto:CAAbtOZctBQeqjc5+QucA4XADC=F1MqKjPTHJDMb6XQjB-dkM7w at mail.gmail.com>>
Content-Type: text/plain; charset="utf-8"
...
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.
------------------------------------------------------------------------------------------------------------------------------------
Date: Fri, 23 Oct 2015 14:06:17 +0000
From: Jacob Stevenson <jstevenson131 at gmail.com<mailto:jstevenson131 at gmail.com>>
To: SciPy Developers List <scipy-dev at scipy.org<mailto:scipy-dev at scipy.org>>
Subject: Re: [SciPy-Dev] optimize - add algorithm for global
optimization: GenSA
Message-ID:
<CAEEL3ux+0Wxa+v6Azv6kdRZKBN8qts_RdU1pEG3S+hjeYNry-w at mail.gmail.com<mailto:CAEEL3ux+0Wxa+v6Azv6kdRZKBN8qts_RdU1pEG3S+hjeYNry-w at mail.gmail.com>>
Content-Type: text/plain; charset="utf-8"
...
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
------------------------------------------------------------------------------------------------------------------------------------
Date: Fri, 23 Oct 2015 13:10:38 +0000
From: "Gubian, Sylvain" <Sylvain.Gubian at pmi.com<mailto:Sylvain.Gubian at pmi.com>>
To: "scipy-dev at scipy.org<mailto:scipy-dev at scipy.org>" <scipy-dev at scipy.org<mailto:scipy-dev at scipy.org>>
Subject: [SciPy-Dev] optimize - add algorithm for global optimization:
GenSA
Message-ID:
<A3786E9825AE3D4F8CC0EC80FBFAD32E02349A0696 at PMICHLAUEXM23.PMINTL.NET<mailto:A3786E9825AE3D4F8CC0EC80FBFAD32E02349A0696 at PMICHLAUEXM23.PMINTL.NET>>
Content-Type: text/plain; charset="Windows-1252"
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20151110/b1e70e4c/attachment.html>
More information about the SciPy-Dev
mailing list