File: pso_basic.rst

package info (click to toggle)
deap 1.3.1-2
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 3,500 kB
  • sloc: python: 8,558; ansic: 1,054; cpp: 592; makefile: 94; sh: 5
file content (107 lines) | stat: -rw-r--r-- 4,171 bytes parent folder | download
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
    search-space according to simple mathematical formulae. The movements of
    the particles are guided by the best found positions in the search-space
    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: 16-24

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 search-space 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: 26-28

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: 50-54

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