1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

==================================
Particle Swarm Optimization Basics
==================================
The implementation presented here is the original PSO algorithm as presented
in [Poli2007]_. From Wikipedia definition of PSO
`PSO optimizes a problem by having a population of candidate solutions,
here dubbed particles, and moving these particles around in the
searchspace according to simple mathematical formulae. The movements of
the particles are guided by the best found positions in the searchspace
which are updated as better positions are found by the particles.`
Modules
=======
Before writing functions and algorithms, we need to import some module from
the standard library and from DEAP.
.. literalinclude:: /../examples/pso/basic.py
:lines: 1624
Representation
==============
The particle's goal is to maximize the return value of the function at its
position.
PSO particles are essentially described as positions in a searchspace of D
dimensions. Each particle also has a vector representing the speed of the
particle in each dimension. Finally, each particle keeps a reference to the
best state in which it has been so far.
This translates in DEAP by the following two lines of code :
.. literalinclude:: /../examples/pso/basic.py
:lines: 2628
Here we create two new objects in the :mod:`~deap.creator` space. First, we
create a :class:`FitnessMax` object, and we specify the
:attr:`~deap.base.Fitness.weights` to be ``(1.0,)``, this means we want to
maximise the value of the fitness of our particles. The second object we
create represent our particle. We defined it as a :class:`list` to which we
add five attributes. The first attribute is the fitness of the particle, the
second is the speed of the particle which is also going to be a list, the
third and fourth are the limit of the speed value, and the fifth attribute
will be a reference to a copy of the best state the particle has been so far.
Since the particle has no final state until it has been evaluated, the
reference is set to ``None``. The speed limits are also set to ``None`` to
allow configuration via the function :func:`generate` presented in the next
section.
Operators
=========
PSO original algorithm uses three operators : initializer, updater and
evaluator. The initialization consist in generating a random position and a
random speed for a particle. The next function creates a particle and
initializes its attributes, except for the attribute :attr:`best`, which will
be set only after evaluation :
.. literalinclude:: /../examples/pso/basic.py
:pyobject: generate
The function :func:`updateParticle` first computes the speed, then limits the
speed values between ``smin`` and ``smax``, and finally computes the new
particle position.
.. literalinclude:: /../examples/pso/basic.py
:pyobject: updateParticle
The operators are registered in the toolbox with their parameters. The
particle value at the beginning are in the range ``[100, 100]``
(:attr:`pmin` and :attr:`pmax`), and the speed is limited in the range
``[50, 50]`` through all the evolution.
The evaluation function :func:`~deap.benchmarks.h1` is from [Knoek2003]_. The
function is already defined in the benchmarks module, so we can register it
directly.
.. literalinclude:: /../examples/pso/basic.py
:lines: 5054
Algorithm
=========
Once the operators are registered in the toolbox, we can fire up the
algorithm by firstly creating a new population, and then apply the original
PSO algorithm. The variable `best` contains the best particle ever found (it is
known as gbest in the original algorithm).
.. literalinclude:: /../examples/pso/basic.py
:pyobject: main
Conclusion
==========
The full PSO basic example can be found here : :example:`pso/basic`.
References
==========
.. [Poli2007] Ricardo Poli, James Kennedy and Tim Blackwell, "Particle swarm optimization an overview". Swarm Intelligence. 2007; 1: 33–57
.. [Knoek2003] Arthur J. Knoek van Soest and L. J. R. Richard Casius, "The merits of a parallel genetic algorithm in solving hard optimization problems". Journal of Biomechanical Engineering. 2003; 125: 141–146
