[SciPy-Dev] Extending scipy.optimize.minimize with particle swarm

Thu May 14 13:13:11 EDT 2020

Hi all,

Please take my naive opinions with a grain of salt. I appreciate these
contributions. Please let me know if I offend.

I found some info on Particle Swarm optimization (PSO) that might be
relevant. It looks really interesting to me! If I understand correctly PSO
is a "global optimization method" perhaps similar in that respect to a
generic algorithm. But I hadn't heard of PSO before, which isn't that
surprising ;)

https://en.wikipedia.org/wiki/Particle_swarm_optimization

https://pypi.org/project/psopy/
https://pyswarms.readthedocs.io/en/latest/
https://pythonhosted.org/pyswarm/
https://nathanrooy.github.io/posts/2016-08-17/simple-particle-swarm-optimization-with-python/
http://www.swarmintelligence.org/tutorials.php

A friend and colleague of mine was more skeptical, they said (not my words):

"metaheuristic methods are computationally intensive, lack convergence
bounds/guarantees, tend to not have strong mathematical explanations, and
are plagued by low-quality research. See, for example:
https://web.archive.org/web/20131102075645/http://antor.ua.ac.be/system/files/mme.pdf
"

 *In a review paper (De Corte and Sörensen, 2012), we list the different
methods that have been applied to this challenging optimization problem.
The list includes genetic algorithms, memetic algorithms, the shuffled frog
leaping algorithm, cross entropy search, differential evolution, simulated
annealing, the immune algorithm, and particle swarm harmony search. The
most complicated of these algorithms takes almost seven pages to explain.
The algorithms are tested on a very small number of instances (three or
four), all of which are very small in size, and unsurprisingly, all
algorithms achieve excellent performance on this unchallenging instance
set. Yet, as we show in De Corte and Sörensen (2012), none of the mentioned
methods is able to outperform a simple constructive heuristic that can be
explained in a single paragraph.*

So apparently this is a hot topic? I personally have found global
optimization methods quite useful. For example in solving for reaction
rates in
chemical kinetics of multistep smoldering combustion, we used genetic
algorithms to find several good candidates of coefficients. We also used a
similar approach in solar for optimizing layout design of super large pv
systems in complex terrain.

But because this method could be misused or misunderstood, it should have
good documentation. For example, I think it would be very useful to explain
what types of problems are best suited for PSO, how it's different from
other algorithms, and explain it's advantages, disadvantages.

Also perhaps consider whether it should be party of scikit learn instead of
SciPy?

Thanks!
Mark

On Thu, May 14, 2020, 9:25 AM Nathan Rooy <nathanrooy at gmail.com> wrote:

> Thanks for the quick reply Andrew. I'll go ahead and get started on those
> benchmarks.
>
> - Nathan
>
> On Wed, May 13, 2020 at 9:55 PM Andrew Nelson <andyfaff at gmail.com> wrote:
>
>> As a global optimizer in the first instance it would probably be added as
>> a separate function (`particle_swarm`), rather than be added as a method to
>> minimize. I'm not familiar with particle swarm, are there various
>> types/flavours of the approach?
>>
>> The general route to adding new global optimizers is:
>>
>> - is it a recognised solver approach that is proven in the scientific
>> literature?
>> - run it against the global benchmark suite, which would involve
>> modifying
>> https://github.com/scipy/scipy/blob/master/benchmarks/benchmarks/optimize.py (do
>> this before you do any modification of scipy library code). Running those
>> global benchmarks for the `particle_swarm` function would check that the
>> solver is performant enough. By performant we mean that the percentage
>> success rate against the problems is as good as the other global solvers.
>> Also of interest is the average number of function evaluations to reach
>> that success rate. (Time taken is probably related to number of function
>> evaluations). Ideally the function fills holes that the other solvers can't
>> handle.
>>
>> If it's performant then we can go further towards adding it to scipy
>> (these steps would be after a further discussion on this list):
>>
>> - code needs to be compatible with the scipy licence (i.e. no GPL/LGPL)
>> - the changes need a comprehensive test suite.
>> - I strongly suggest that you have a public `particle_swarm` function,
>> and a private ParticleSwarm class that does the solving behind the scenes.
>> If possible make the ParticleSwarm object an iterator with a __next__
>> method so that individual iteration steps can be taken. See
>> https://github.com/scipy/scipy/blob/master/scipy/optimize/_differentialevolution.py as
>> an example. A full solve could be done with a `solve` method.
>> - keep the API as close as possible to other optimizers, i.e. same
>> parameter names, same keyword names, parameter order is similar to other
>> minimizers.
>> - differential_evolution benefitted from offering a reduced set of
>> functionality when it was first added. Additional features came afterwards
>> and the delayed introduction of them meant that the API/design of the
>> solver benefitted from a lot of thought over a prolonged period.
>> - if `particle_swarm` uses random number generation then the solver
>> should be able to generate random numbers with either
>> `np.random.RandomState` or `np.random.Generator` (
>> https://github.com/scipy/scipy/blob/master/scipy/optimize/_differentialevolution.py#L560).
>> This means using methods that belong to both type of objects.
>> - the random number generation needs to be reproducible (function should
>> have `seed` keyword).
>> - total number of function evaluations needs to be tracked.
>> - consider parallelisation aspects of your function. Can calls to the
>> objective function be done in parallel? (`workers` keyword).
>> - vectorisation is nice.
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200514/fe2829c3/attachment-0001.html>