# ReportZ .pdf

Nom original:

**ReportZ.pdf**

Ce document au format PDF 1.5 a été généré par TeX / pdfTeX-1.40.13, et a été envoyé sur fichier-pdf.fr le 13/09/2014 à 21:15, depuis l'adresse IP 129.31.x.x.
La présente page de téléchargement du fichier a été vue 682 fois.

Taille du document: 4.3 Mo (31 pages).

Confidentialité: fichier public

### Aperçu du document

Abstract

Continuous and discrete version of the classic particle swarm optimization

algorithm are presented and compared. Algorithm’s variant are then introduced to increase its efficiency. Finally, a efficient version of the algorithm

based on the addition of noise is discussed.

Acknowledgements

I would like to express my gratitude to my supervisors, Dr. Martin and

Prof. Carrilo. Their advices and patient guidance helped me a lot during the

writing of my thesis.

1

Contents

1 Classic Particle Swarm Optimization Algorithms

1.1 Discrete Particle Swarm Optimization . . . . . . . .

1.1.1 Optimization problem, basic definitions . . .

1.1.2 Presentation . . . . . . . . . . . . . . . . . .

1.1.3 First examples of the PSO . . . . . . . . . .

1.1.4 PSO parameters . . . . . . . . . . . . . . . .

1.2 Continuous PSO . . . . . . . . . . . . . . . . . . .

1.2.1 Presentation of the C-PSO . . . . . . . . . .

1.2.2 CPSO Parameters . . . . . . . . . . . . . .

1.3 CPSO and PSO results and limitation . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

5

5

5

5

7

9

13

13

15

15

2 Modified PSO Algorithms

2.1 Literature overview of PSO variants .

2.2 Completely smooth C-PSO . . . . . .

2.2.1 Presentation of the CSC-PSO

2.2.2 Results . . . . . . . . . . . . .

2.3 Random Jump C-PSO . . . . . . . .

2.4 Leaders Follower . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

17

17

19

19

19

20

21

.

.

.

.

.

.

22

22

22

24

24

24

25

3 Noisy PSO Algorithms

3.1 Noise on the velocity . . . . . . . . .

3.1.1 Presentation of the NVC-PSO

3.1.2 NVC-PSO results . . . . . . .

3.2 Noise on the position . . . . . . . . .

3.2.1 The NPC-PSO . . . . . . . .

3.2.2 NPC-PSO’s results . . . . . .

A Function benchmark

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

28

B Matlab code’s

30

B.1 PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

B.2 C-PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

B.3 NVC-PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2

Introduction

In scientific applications, we can often redefine an optimization problem as the discovery of the minimum of a real valued function. Therefore, given a function f : E → F

we define the solution of an optimization problem for f in the following way :

Definition 1. x0 ∈ E is solution of the optimization problem if and only if :

∀x ∈ E, f (x0 ) ≤ f (x) (minimization problem) or f (x0 ) ≥ f (x) (maximization

problem).

To solve this problem, there exists a wide number of different methods. Many

deterministic methods are based on the differential properties of the function and

evaluate the gradient, a gradient’s approximation or other mathematical operators

to iterate the candidate solution. As instance in the gradient descent method, the

new point xn+1 is iterated from xn using :

xn+1 = xn − δn ∇f (xn ),

(1)

where δn is a variable step size and ∇ represent the gradient operator. With certain

assumptions on the function and a right choice of δ, convergence to a local minimum

can be guaranteed [1].

Particle swarm optimization algorithms have a totally different approach. They

do not require any informations about the function gradient and only use primitive

mathematic operators. Consequently they are an interesting alternative to solve optimization problems with a fairly easy implementation and a very low computational

cost [2].

Introduced by Eberhart and Kennedy in 1995 [2], the particle swarm optimization

algorithm is a heuristic method, part of the swarm intelligence methods. Its main

idea is to represent the candidate solution of the optimization problem by an evolving

population of particles deployed on the function space.

3

This algorithm derives directly from previously introduced algorithms used to

simulate social behavior or artificial life as the behavior of birds flocking, fish schooling or swarming population.

Indeed, a swarm of zerglings can be simulated for instance by admitting that each

zergling follows very simple individual rules [5]. To avoid collision, each zergling is

repulsed by its close neighbors : it is modeled by a short range force and simulates

an individual behavior. Moreover, zerglings want to remain close to the zerg swarm.

It is modeled by a long range attraction toward the barycenter of the swarm, a piece

of informations shared by all the zerglings. It is also interesting to add a heading rule

which steers the heading of each gling’ toward the average of the swarm. The result

of those simple individual interactions will simulate the swarm in a very complex and

realistic fashion. Furthermore, the resulting swarm seems to have its own intelligence,

designed by swarm intelligence. The particle swarm optimization algorithms are very

similar to the zergling’s simulator. It uses the zerglings as a way to probe the space

functions. Similarly to the swarm algorithm where the zergs exchange informations

about the swarm average position and its heading, the particles of the PSO share

informations about the function value and uses those information to modify their

behavior and locate the global minima.

Figure 2: A swarm of zergling getting ready to bust a marine’s wall. The flock

can count up to thousand of individuals changing headings instantly with a perfect

synchronization. Starcraft II, Blizzard, 2010.

Classic results on the discrete and continuous versions of the particle swarm optimization algorithm are presented in section 1. In section 2, more complex variant of

the algorithm are introduced to prevent premature convergence. Finally, algorithms

using brownian motion to increase the mobility of particles are discussed and tested.

4

1

1.1

1.1.1

Classic Particle Swarm Optimization Algorithms

Discrete Particle Swarm Optimization

Optimization problem, basic definitions

The Particle Swarm Algorithm (PSO) is used to solved optimization problems on a

cost function f : E → F as defined in definition 1. We also define :

Definition 2. x0 ∈ E is the global minimum and solution of the optimization problem if and only if :

∀x ∈ E, f (x0 ) ≤ f (x) (minimization problem) or f (x0 ) ≥ f (x) (maximization

problem).

Definition 3. xl ∈ E is a local minimum if and only if :

∃ γ ≥ 0 such as : ∀x ∈ A verifying |x − xl | ≤ γ we have f (xl ) ≤ f (x).

1.1.2

Presentation

Particle swarm optimization algorithm (PSO) uses a population of individuals to

explore the function space. The position of each individual, called particle, represents

a potential solution of the optimization problem. Particles are governed by equations

of motion and therefore able to move on the function space. They have also a memory

and remember the position of the best value achieved so far and update this value

by evaluating the function cost at their position. Finally, the particles share their

individual informations with the whole population and therefore have access to the

best position found so far by the entire swarm of particle. Velocity of each individual

is updated using those information.

Let us supposed that we want to find the global minimum of the function (minimization problem) :

f : RN → R

x 7→ f (x)

The PSO randomly deploys on the space function a population of Ns particles.

Each particle can be described at discrete time n ∈ N by a N-dimensional vector

Xin = (xi1 , ..., xiN ) with a a velocity vector Vin = (vi1 , ..., viN ), i = 0, 1, ..., N s. The

memory of the i-th particle is represented by the vector Xblni = (xlbi1 , xlbi2 , ..., xlbiN ).

Xbli is the position of the point with the best fitness found so far by the i-th particles

and is called the local best :

5

Definition 4. The local best of the i-th particle at time n ∈ N is the position of the

best value found by the i-th particle so far :

Xblni = Xik with k ≤ n and ∀l ≤ n f (Xik ) ≤ f (Xil ).

Definition 5. At time n, the global best Xgln of the swarm is local best with the best

fitness :

Xgln = Xblnk with f (Xblk ) ≤ f (Xbli ) ∀i ≤ N s.

Equations of motion governing the i-th particle are taking into account those

informations. Indeed, each particle is attracted by its own local best as well as by

the global best of the swarm. Consequently, the equations of motion governing the

i-th birds at the iteration n+1 are :

n

Vin+1 = α φ1 Vin + β φ2 (Xlbni − Xin ) + δ φ3 (Xgb

− Xin ),

i

(2)

Xin+1 = Xin + Vin+1 .

(3)

In the equation 2, α, β and δ are real parameters and φi , i = 1..3 are random

variables uniformly distributed on [0, 1]. α is called the self momentum, β is the

local attraction coefficient and δ the global attraction coefficient. Those coefficients

will be discused in more details in section 1.1.4.

During each iteration the particles evaluate the function at their position and update

their local best if relevant. Then the swarm best is update as the best value of all

the local best of the population. Hence, the algorithm can be briefly described by

the following pseudo code :

set randomly the population of particles

while convergence did not happen or stopping criterion met do

for each particle do

update velocity

update position

update local best

end for

update global best

end while

return global best

Finding a suitable stopping criterion is important. A possible choice is to defined

a parameter evaluating the average distance between the particles of the population

and representing the swarm’s density. Once this parameter is inferior to a certain

6

value it indicates that the swarm have converged and the simulation stops. The

particles are usually initially randomly distributed on the function’s space with a

randomly distributed initial velocity. Finally, particles are reflected on the boundaries of the search domain.

1.1.3

First examples of the PSO

Square function As a first simple example, the discrete PSO algorithm is applied to the two dimensional square function which presents a global minimum at

x = (0, 0) and is defined by :

f :

R2

→

R

(x, y) 7→ x2 + y 2

Figure 3: The graph of the two-dimensional square function

We are using a population of 4 particles, randomly distributed on the function

domain −10 ≤ x, y ≤ 10 with randomized initial velocity. Figure 4 displays the

convergence of the particles plotted as black circles. Each image is taken every

two increments of the algorithm and colored line represent the contour lines of the

function.

On this fairly easy example, the algorithm finds the minimum value with a precision of 10−5 in 20.98 increments (average value out of 1000 simulations).

Ackley function It is especially interesting to use the PSO on function which

presents many local minima. This idea is illustrated using the 2 dimensional Ackley

function is defined by :

f (x, y) = −a e(−b

√1

2

(x2 +y 2 ))

7

1

− e 2 (cos(c x)+cos(c y)) +a + e,

(4)

Figure 4: Convergence of the PSO algorithm used on the square function with a

population of 4 particles. Particles are plotted as black circles. Each snapshots

is taken every two increments of the algorithm from left to right and from top to

bottom.

where a = 20, b = 0.2 and c = 2.

Figure 5: Plot of the Ackley function.

Commonly used in optimization problems, it has the particularity to present

many local minima (400 inside the function domain −10 ≤ x, y ≤ 10). The global

minimum is x = [0, 0]T with f (x) = 0. Figure 6 displays the convergence of the PSO

8

using ten particles.

Figure 6: Convergence of the PSO on the Ackley function with ten particles.

On this more complex example, the particle swarm optimization algorithm finds

the global minimum in a average of 39 increments (average out of 1000 simulations).

However, the algorithm failed in 0.6% of the cases to spot the global minimum and

converge instead to one of the local minimum.

1.1.4

PSO parameters

As we can see from (2), the PSO’s parameters are α, β and δ. The real β is the

local attraction coefficient and determine the intensity of the attraction toward the

local best when δ, the global coefficient set the intensity of the attraction toward

the global best. Setting those parameters to the right value is critical to improve

the efficiency or even allow the convergence. If δ β, particles might converge

faster to the global best but lose some mobility and might not explore the function

space efficiently. One the other hand, if δ β, particle are too individual and the

swarm loses its coherence. Setting α to a suitable value is also important. Indeed

hight value give particle a important momentum which can result the particle to

ignore some part of the space function when low value can make particle behavior

inconsistent.

9

Stability analysis Taking a similar approach as in [2], the analysis is conducted on

a single particle with real parameters. Local and global bests are therefore coinciding

and assumed constant. The equations governing the particle motion are :

V n+1 = α Vin + β (Xlbn − X n ),

(5)

X n+1 = X n + V n+1 .

(6)

V n+1 = α Vin + β (Xlb − X n ),

(7)

(X n+1 − Xlb ) = α Vin + (1 − β)(X n − Xlb ).

(8)

It can be rewritten as :

The stability of the system defined by equation 7 and equation 8 depends on the

roots of the polynomial expression of equation 9 :

X 2 − (α − β + 1)X + α = 0.

(9)

Roots of equation 9 are :

X± =

(α − β + 1) ±

p

(α − β + 1)2 − 4α

.

2

(10)

According to [2], roots should be imaginary and close to the unit circle. Hence, we

need (α − β + 1)2 − 4α to be negative and α ≤ 1. Choosing :

β = α + 1,

(11)

allow us to meet the requirements and to have the imaginary roots :

√

X± = ±i α.

(12)

Finally, α should be taken such that :

√

α ' 1 and β = α + 1.

(13)

Experimental study To evaluate how well the algorithm performs, we define the

accuracy, the hit ratio and the hit time.

Definition 6. We say that the algorithm has found the global best x0 of a function

with the accuracy A ∈ R if the global best of the swarm Xgb returned at the end of

the simulation verifies : kXgb − x0 k ≤ A where k.k is the euclidian norm.

10

Definition 7. For N ∈ N number of simulation run and Nhit ∈ N, Nhit ≤ N the

number of simulation that have found the global best with the accuracy A, we define

the hit ratio hA as hA = NNhit .

Definition 8. We define the hit time of a simulation with the accuracy A as the

k

minimum of k ∈ N such that kXgb

− x0 k ≤ A.

Definition 9. We define the computional hit time of a simulation with the accuracy

A as the computional time in second used to find the global minimum with the accuracy A. It is an interesting criteria to test algorithms where iteration have different

computing times (for example two PSO with a different number of particles).

Local and global coefficient We work on the Ackley function defined in equation 4 with the search space −10 ≤ x, y ≤ 10. According to equation 13, α should

be close to the value 1 and the simulations are run with α = 0.7, 7 particles and an

accuracy of 10−5 . Variables of the simulations are β and δ. Simulation’s results are

display on figure 7 where the hit ratio is plotted as a function of the local and global

coefficient. X axis displays the global coefficient and Y axis the local coefficient. The

best values found from those simulation are β = 1.6 and δ = 1.6. It is similar to the

values in the literature. In [3] and [12], recommended values are β = 1.7 and δ = 1.7

and in cite15 authors are using β = 1.5 and δ = 1.5.

Figure 7: Plot of the hit ratio for the Ackley as a function of the local (β) and global

coefficient (δ). X axis display δ and Y axis β. Accuracy is set at 10−5 and a swarm of

7 particles is used. 100 simulations have been run for each point. The values which

return the best hit ratio are 1.6 for both the local and global coefficient.

11

Figure 8 displays the hit ratio as a function of the global swarm attraction coefficient for fixed values of β and α. Results show that the hit ratio increases with the

global coefficient δ until the value 2.5 where the ratio suddenly drop. Indeed in the

discrete case high values of the global coefficient prevent the convergence of the algorithm. Moreover the algorithm fails at finding the minimum efficiently for low values

of δ (less that 1). However figure 8 shows that the coefficient δ can be chosen freely

between 1 and 2.25 with very little consequences on the algorithm performances.

Figure 9 displays the hit ratio as a function of the local attraction coefficient for

fixed values of δ and α. The hit ratio slightly increases with the local coefficient.

However, the algorithm still performs fairly well for low value of β. As for the global

coefficient, the algorithm doesn’t converge for value over 2.5.

1

Hit Time

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.5

1

1.5

2

Swarm coefficinet (local = 1.6)

2.5

3

Figure 8: Average hit ratio (blue curve) and hit time (red curve) as a function of the

global attraction coefficient δ with β = 1.6. Best value is δ = 1.6.

1

Hit Time

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.5

1

1.5

2

Local attraction coefficient (Swarm = 1.6)

2.5

3

Figure 9: Average hit ratio (blue curve) and hit time(red curve) as a function of the

local attraction coefficient β with δ = 1.6

Self Attraction and number of birds With β and δ set to their best values,

simulations are run for different values of α using the same parameters. Figure 10

12

displays the hit ratio as a function of α. The optimal value is α = 0.7 ([2] recommends

0.6).

1

Hit Time

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.5

1

1.5

2

Local attraction coefficient (Swarm = 1.6)

2.5

3

Figure 10: Average Hit time and Hit ratio as a function of the friction coefficient α

Finally, setting α = 0.7, β = 1.6 and δ = 1.6 simulations are run for different

numbers of particles. Figure 11 displays the results. Hit ratio quickly increases with

the number of particles. However increasing the number of particles has an impact

on the computation hit time and setting the number of particles is a compromise

between the hit ratio and the computation hit time.

1

X: 9

Y: 1

Hit Time

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5

10

15

20

Local attraction coefficient (Swarm = 1.6)

25

30

Figure 11: Average computation hit time and hit ratio as a function of number of

particles

Remark 1. We assume that the parameters α, β and δ do not depend on the function. However, the optimum number of birds depends on how complex is the function

and on how wide is the search space.

1.2

1.2.1

Continuous PSO

Presentation of the C-PSO

PSO is directly inspired by the life swarm which is continuous by nature. In order to

imitate more closely the behavior of a swarming population, we smooth the algorithm

13

and introduce a continuous version of the PSO (C-PSO for Continuous Particle

Swarm Optimization). Continuous equations equivalent to the discrete equations 2

and 3 for the i-th particle are :

V˙ i = −αVi + β (Xlbi − Xi ) + δ (Xlgi − Xi ),

(14)

X˙ = Vi .

(15)

Vi represent the velocity of the i-th birds at time t, Xi its position, Xlbi its local best

and α, β and δ are respectively the friction, local and global coefficient. 14 and 15

are differential equations that will be resolved numerically using euler’s method or

runge kutta method with a adequate step dt.

Remark 2. To simplify the notation Vi (t), Xi (t) and Xlbi (t) are denoted by Vi , Xi

and Xlbi .

Remark 3. In the continuous version of the PSO, the equations governing the particles movement are no longer randomized. However, the initial position and velocity

remain randomly distributed.

The update of the local best of each bird also need to be smoothed. Indeed,

testing at each iterations if the cost function at the current position is better that

the local best and instantly updating if relevant introduces uncontinuities in the

differential equation. To tackle this issue, a continuous update of the local best as

implemented in [3] is introduced :

X˙ lbi = γ(Xi − Xlbi ) · (1 + sign((f (Xlbi ) − f (Xi ))).(16)

where γ is a real coefficient, f the cost function and sign the function defined by :

−1 si x < 0

(17)

∀x ∈ R, sign(x) = 0

si x = 0

1

si x > 0

Consequently is the fitness of the current position is worst than its local best (so

if f (Xlb ) ≥ f (Xi )) we have sign(f (Xlbi ) − f (Xi )) = −1 and :

X˙ lbi = 0.

On the other hand, if the local value is better than the local best, f (Xlb ) ≤ f (Xi ),

and therefore sign(f (Xlbi ) − f (Xi )) = 1 and

X˙ lbi = 2γ(Xi − Xlbi ),

14

and the local best is being continuously updated. In the classic version of the C-PSO

as described [3], the global best is not continuously updated and the newly found

global best instantly replaces the previous position (discrete jump). Therefore the

update of the global best is discrete. However in section 2.2 a completely smooth

version of the continuous algorithm with smooth global update is discussed. 12 shows

the trajectories of 3 particles converging on the two-dimensional Ackley function

1

using the CPSO with dt = 30

Figure 12: Trajectories of 3 particles with continuous time PSO, dt =

Ackley function

1.2.2

1

30

on the

CPSO Parameters

Smoothing the PSO algorithm introduces new parameters : dt the step size used

to solved the ordinary differential equation and γ from equation 16 which is the

coefficient on the derivative of the Local best of the particles. Continuous value of

α, γ and δ from equation 14 must also be found. Conducting a similar study as done

in section 1.1.4 on the CPSO leads to the value α = 0.3 for the friction coefficient,

β = 1 for the local swarm attraction and δ = 1 for the global swarm attraction.

Simulation’s results give the optimum value for γ = 4. Usually used step size are

between1/10 and 1/100.

Figure 13 displays the plot of the hit ratio as a function of the coefficients β and

δ for the Ackley function.

1.3

CPSO and PSO results and limitation

Simulations are conducted for both algorithm on the benchmark’s functions defined

in the annex. Main results for the PSO and the C-PSO are reported in figure 14

15

Figure 13: Plot of the hit ratio as a function of the local and global coefficient for

the Continuous PSO. X axis is β, Y axis is δ.

where Ns is the number of particles in the population, accuracy, hit ratio and hit

time are defined in section 1.1.4, Nb of sim is the number of simulations conduct and

C. time the computational hit time.

Simulations show that C-PSO performances are considerably better than its discrete version. The hit ratio achieved with the continuous version is better for all the

functions tested except for the Egg holder function. However the hit time is worst

and the computational cost more important. Results display in figure 14 will be used

as references for testing new algorithm.

Limitations Limitations arise on very complex functions presenting many local

minima. Indeed, both PSO and C-PSO have very poor results for instance on the

Egg Holder function which is defined by :

r

p

x

|x − (y + 47)| ,

(18)

f (x, y) = − (y + 47) sin

y + + 47 − x sin

2

where 512 ≤ x, y ≤ 512 and f (512, 404.2319) = −959.6407 is the global minimum.

Indeed, the best hit ratio achieve by the PSO is very low : 0.61 for the discrete

version with 400 particles. This ratio cannot be increase by adding more particles.

The main issue is the premature convergence of the swarm population to a local

minimum instead of the global minimum. The quick convergence of the population

do not give the particles enough time to explore efficiently the function space and to

find the global minimum. In the following section, modified C-PSO algorithm will be

discussed to improve the PSO performances and notably to increase the function’s

space exploration.

16

Name

PSO

C-PSO

PSO

C-PSO

PSO

C-PSO

PSO

C-PSO

PSO

C-PSO

PSO

C-PSO

PSO

C-PSO

Ns

7

7

7

7

16

16

7

7

400

400

7

7

50

50

Accuracy

10−5

10−5

10−5

10−5

10−5

10−5

10−5

10−5

10−2

10−2

10−5

10−5

10−5

10−5

Nb of sim Hit ratio

1000

0.9610

1000

1

1000

0.3500

1000

0.4870

1000

0.7670

300

0.8200

1000

0.8660

300

1

100

0.6100

100

0.3400

1000

0.4840

1000

0.9830

300

0.7167

300

0.7567

Hit time

43.1290

644.9110

53.8457

367.0164

42.2164

302.5244

30.2252

234.1400

54.5902

328.5000

54.2955

154.2146

89.6605

311.3568

C. time

0.0150

0.2460

0.0168

0.0293

0.0268

0.0530

0.0083

0.0418

1.0504

7.0820

0.0161

0.0115

0.1756

0.1778

function

Ackley

Ackley

Rastagrin

Rastagrin

Rastagrin

Rastagrin

Levy

Levy

Egg Holder

Egg Holder

Shaffer

Shaffer

Griewank

Griewank

Figure 14: Result of the PSO and C-PSO algorithm on the optimization function

2500

2000

1500

1000

500

0

500

0

−500

−100 0

−300 −200

−500 −400

100

200

300

400

500

Figure 15: Graph of the EggHolder function

2

2.1

Modified PSO Algorithms

Literature overview of PSO variants

This section presents a quick overview of different variants of the particle swarm

algorithm that can be found in the literature. The aim is to introduce some of

the mains concepts and areas of research and a more exhaustive list can be found

in [11]. In the original paper presenting the PSO algorithm in 1995 [2], Eberhart

and Kennedy already introduce a modified version of the PSO called L-best/PSO

17

where the global best of the swarm is no longer a global value shared by the entire

swarm but rather a local value shared by connected individuals. Indeed, particles

can only compare their local best with the value of their closest neighbors. Hence,

their global attraction is toward the best local of the particles in the neighborhood.

According to [2], this version is less vulnerable to local minima and particles tend to

spread efficiently through the function space, aggregated in small groups. However

the number of iteration required to find the global minimum is drastically increased.

The topology of how the local and global best should be shared through the swarm

have been an intense area of research. Different structures of communication have

been tested [7], [8] and notably a structure called Von Neumann [9] has interesting

results. In this structure, particles have a lower number of connections (the global

best is shared by less individuals) that in the classic PSO but more than in the

L-best/PSO. Kennedy claims in [8] that highly connected swarm population tend

to perform better on simple problems when swarms with fewer connections have

better results on complex functions. Other approaches have been tried as the fully

informed swarm (FI-PSO) [9] where the attraction force results from all the weighted

local bests of particle’s neighbors and discrete equation for the i-th particle are :

N

1 X

(Xlbn − Xi ),

Vi = Vi +

N n=1

(19)

Xi = Xi + Vi ,

(20)

where N is the number of neighbors used, and Xlbn is the local best of the n-th

neighbor. According to [9], the FI-PSO has better performances but relies more

on the population topology. Finally in [6], a strategy where the global best can

be potentially picked from the local best of any particles is introduced to prevent

premature convergence.

Modifying the swarm connectivity is not the only way to improve the PSO algorithm. Adaptive PSO (A-PSO) presented in [10] defines different states : exploration,

exploitation, convergence and jumping out. Current state is estimated by evaluating

the population distribution and each state changes the algorithm parameters (attraction coefficients, friction value, etc.). A-PSO also includes a learning strategy

that allows the algorithm to jump out of the local minima. Authors of [10] report

very good results in term of mobility and convergence speed. A different method to

leave out the local minima is presented in [4] with the stretched PSO. After convergence to a local minimum, the algorithm modifies the cost function by ”stretching”

and elevates the local minimum and its neighborhood. The local minimum is therefore eliminated from the stretched function and the algorithm can use the modified

function as its new cost function.

18

Nowadays, Particle Swarm Optimization remains a extremely active field of research with many open questions.

2.2

2.2.1

Completely smooth C-PSO

Presentation of the CSC-PSO

One limitation of the continuous PSO in term of smoothest is the discrete update of

the global best. Indeed, each iteration of the C-PSO, the global best of the swarm

is instantly updated and replaced if relevant by the best value of the local bests.

This discrete jump in the continuous differential equations governing the particle’s

movement can have destabilization effects according to [3]. To solve this issue, a

smooth update have been introduced and the global best is taken as the barycenter

of the weighted local bests of the entire swarm. The cost function is supposed positive

without losing any generality and each bird is weighted by the inverse of the cost

function at its position. The new equation describing the evolution of the swarm

global best is :

1 X 1

xlb ,

(21)

xgb =

K

f (xlbk ) k

P 1

where K =

is a normalization coefficient.

f (xlbk )

It remains a discontinuity in the local best derivative X˙ lb described by equation 16.

Indeed, the sign function has a discontinuity at the point 0. In order to completely

smooth the algorithm, we replace the sign function by the continuous function arctan.

The new equation is :

x˙ lb = γ(x − xlb ) · (1 +

2.2.2

2

arctan(f (xlb ) − f (x))).

π

(22)

Results

Performances of the CSC-PSO are tested and compared with the results of the CPSO introduced in section 1.2. Figure 17 displays the results : Hit ratio ref and Hit

time ref are the hit ratio and time of the C-PSO used as a reference and tested with

the same parameters on the same test functions (complete C-PSO results are display

in figure 14). In overall, performances are slightly worst and the hit ratio is sensibly lower for the CSC-PSO (except for the Griewank and the Rastagrin function).

However, the algorithm still performs fairly well and have the merit to be completely

smooth which allows a proper mathematical study.

19

Figure 16: Graph of the function f (x) = 0.5 + sign(x) in red and g(x) = 0.5 +

1

artan(x) in black. g(x) is used in the Completely Smooth C-PSO to present any

π

discontinuities in the equation arising from the discontinuity in 0 of the sign function.

Function Tested

Ackley

Egg Holder

Levy

Griewank

Rastagrin

Shaffer

Ns

7

400

7

50

7

7

Nb of sim Hit ratio

1000

0.9960

25

0

1000

0.7560

1000

0.7850

1000

0.6260

1000

0.3060

Hit ratio ref Hit time Hit time ref

1

441.6416 644.9110

0.2667

330.8750

1

262.0357 234.1400

0.7567

299.3376 311.3568

0.4870

283.5607 367.0164

0.4840

187.9412 54.2955

Figure 17: Results of the CSC-PSO. Hit ratio Ref is the hit ratio of the classic

version of C-PSO previously introduced and used as reference. Overall performances

are slightly worst.

2.3

Random Jump C-PSO

Random jump continuous particle swarm optimization algorithm (RJC-PSO) is a

first attempt to increase the mobility of particles and their capacity to efficiently

explore the function space. At any time, any particle has a probability to be reinitialized and reset randomly on the function domain with a random velocity. The

purpose is to spread the swarm population and force it to explore the function space

longer before converging to the global minimum. However this algorithm fails at performing efficiently. Results are display in figure 18. Reinitialized particles converge

back to the global best without exploring the function space.

20

C. time

0.2185

0.0291

0.1919

0.0304

0.0194

Function Tested

Ackley

Egg Holder

Levy

Griewank

Rastagrin

Shaffer

Ns

7

400

7

50

7

7

Nb of sim Hit ratio

1000

0.9960

25

0

1000

0.7560

1000

0.7850

1000

0.6260

1000

0.3060

Hit ratio ref Hit time Hit time ref

1

441.6416 644.9110

0.2667

330.8750

1

262.0357 234.1400

0.7567

299.3376 311.3568

0.4870

283.5607 367.0164

0.4840

187.9412 54.2955

Figure 18: Results of the RJC-PSO. Hit ratio Ref is the hit ratio of the classic

version of C-PSO previously introduced and used as reference. Overall performances

are slightly worst.

2.4

Leaders Follower

Leaders and Followers C-PSO algorithm introduces two different populations of particles. One population designed as leaders have a lower value of the global attraction

coefficient as well as a lower friction coefficient. Consequently, they have a better

mobility. Their task is to probe the function space and provide useful informations

to the rest of the swarm. The other population called followers have the classic value

of the parameters. Their task is to assure a precise convergence of the algorithm to

the global best. Coefficient values used for the leading population are α = 0.1, β = 1

and δ = 0.3. Values for the following population are the usual values : α = 0.3, β = 1

and δ = 1. Figure 19 displays the results of the algorithm. Ns is total number of

particles deployed on the function space and Nl is the number of leaders. Obviously,

Nf = Ns - Nl is the number of followers.

Adding the right number of leaders in the particle population increases the algorithm performances. Indeed, with 30 particles the hit ratio of the classic C-PSO

is 0.948 on the Rastagrin function. It increases to 0.974 with 10 leaders and 20 followers. On the Egg holder function, the hit ratio is 0.2750 with 105 follower and 75

leaders instead of 0.1875 with the C-PSO. Finally on the same function the hit ratio

is 0.5 with 400 particles and 140 leaders instead of 0.34 with the C-PSO.

21

C. time

0.2185

0.0291

0.1919

0.0304

0.0194

Function Tested

Rastagrin

Rastagrin

Rastagrin

Rastagrin

Rastagrin

Rastagrin

Egg holder

Egg holder

Egg holder

Egg holder

Egg holder

Egg holder

Egg holder

Ns

30

30

30

30

30

30

180

180

180

300

300

400

400

Nl

0

8

10

14

30

30

0

50

75

0

100

0

140

Hit ratio

0.948

0.968

0.974

0.962

0.714

0.714

0.1650

0.1875

0.2750

0.2700

0.33

0.3400

0.5000

Hit time

274,69

293.4855

296.4103

306.99

702.33

702.33

333.5455

398.1

394.4364

322.2222

388

328.5000

375.2800

C. time

0.0985

0.1093

0.1051

0.108

0.253

0.253

3.1730

3.73

3.6853

5.2084

6.5

7.0820

7.9326

Num of simul

500

500

500

500

500

500

200

80

200

100

100

100

100

Figure 19: Results of the LFC-PSO.

3

Noisy PSO Algorithms

In this section, function’s space exploration is improved by adding brownian motion

to the particle’s equations. We recall that the brownian motion is the stochastic

process W(t), 0 ≤ t defined by :

Definition 10. The standard brownian W(t), 0 ≤ t is the real value stochastic

process such that :

W (0) = 0,

W (t) − W (s) follows the normal law N (0, t − s),

None overlapping increments are independent random variables.

Furthermore, we call stochastic differential equation (Ito sense) the equation :

dXt = b(t, Xt ) dt + σ(t, Xt )dWt ,

(23)

where Xt is a stochastic process, b(t, Xt ) its expectation and σ(t, Xt ) its variance.

3.1

3.1.1

Noise on the velocity

Presentation of the NVC-PSO

The main idea of the Noisy velocity C-PSO is to add a noisy component with a

variable variance to the velocity differential equation. Velocity’s differential equation

22

for the i-th particle is turned into the stochastic differential equation :

dVi = (−αVi + β (Xlbi − Xi ) + δ (Xgb − Xi )) dt + σ(t, Xi , Xgbi ) dW,

(24)

where α, β , δ are previously defined real coefficients, Vi the i-th particle velocity,

Xi its position, Xlbi its local best, dW the Ito differential of the brownian motion

and σ its variance. The choice of a suitable σ is critical. Indeed, by adding noise

to the equation we increase the particle’s mobility and improve their capacity to

explore efficiently the function space. However, important noise tends to prevent

the convergence. Consequently, setting σ to a fixed real value does not improve the

performances. In order to have interesting result and allow the convergence, σ for the

i-th particle needs to tend toward zero when the particle is near Xgb . On the other

hand, σ should increase with the particle’s distance to the global best to increase the

particle mobility. Therefore, a suitable σ(t, Xi , Xgb ) needs to verify :

σ(Xi , Xgb ) → 0 when (Xi − Xgb ) → 0,

(25)

σ(Xi , Xgb ) → ∞ or σmax when (Xi − Xgb ) → ∞.

(26)

In the NVC-PSO we use the function :

σ(Xi , Xgb ) = σ0 |X − Xbs |,

(27)

where σ0 is a real parameter and |X −Xbs | the euclidian distance between the current

position of the particle and the global best of the swarm. Finally, it is interesting

in some cases to bound the function σ by a maximum value σmax to prevent chaotic

behaviors.

Figure 20: Plot of the variance of the stochastic process σ(X - Xbs ) as a function of

(Xi − Xgb ) with σ0 = 1 and σmax = 3.

23

σ0

0.5

0.5

0.5

0.5

0.5

Ns

7

300

400

7

7

Hit ratio

0.8550

0.7033

0.8133

1

0.8933

Hit ratio ref Hit time

0.4610

573.4094

0.2700

503.1090

0.340

4472.8811

0.983

211.5320

0.7567

490.6791

Hit time ref

366.6421

344.2593

328.50

154.21

311.3568

C. time

0.1173

11.1172

11.6073

0.0363

0.6211

function

Rastagrin

Egg Holder

Egg Holder

Shaffer

Griewank

Figure 21: Results of the NVC-PSO algorithm for the different functions of the

optimization benchmark. Performances are increased drastically.

3.1.2

NVC-PSO results

NVC-PSO has excellent results on the benchmark functions, especially on the complex functions. Figure 21 display the results with as previously Hit ratio ref and Hit

time ref the results of the C-PSO. For the Rastagrin function with 7 particles, the

hit ratio goes from 0.461 with the classic C-PSO (no noise, σ0 = 0) up to 0.855 with

the NVC-PSO (σ0 = 0.5). In this case, adding noise almost doubles the hit ratio.

However, due to the noise, the average hit time is slightly longer (573 iterations in

average instead of 367). Results are also very good with the Egg holder function.

With 300 particles, the C-PSO has the extremely bad hit ratio of 0.27. Using the

same number of birds with the NVC-PSO (with σ0 = 0.5 and σmax = 30) gives a hit

ratio of 0.63.

Figure 23 displays the hit ratio and the hit time of the NVC-PSO as a function

of σ0 defined in equation 27. Hit ratio rises with σ0 until the optimum value σ0 = 0.5

where it start to drop. Hit time linearly rises with σ0 .

3.2

3.2.1

Noise on the position

The NPC-PSO

Adding noise to the velocity has the advantage to keep the particle’s trajectory

relatively smooth. However, adding directly noise to the position is a more direct

way to increase the population mobility. In the NPC-PSO’s case (Noise on Position

- Continuous PSO), stochastic differential equation governing the i-th particle is :

dXt = Vt dt + σ(Xt , t) dWt ,

(28)

where Xt is the position of the particle, Vt its velocity, σ the variance function of the

process and dW the brownian motion. The choice of the function σ is subject to the

24

n of sim

1000

300

300

1000

300

0.9

Hit Time

X: 0.5

Y: 0.8667

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.1

0.2

0.3

0.4

0.5

0.6

Swarm coefficinet (local = 1.6)

0.7

0.8

0.9

Figure 22: hit ratio and hit time of the NVC-PSO as a function of σ0 . Each point

150 simulations, 7 particles.

same constraints and defined as previously :

σ(Xi , Xgb ) = σ0 |X − Xbs |.

(29)

The function σ can also be bounded by a maximum value σmax .

3.2.2

NPC-PSO’s results

NPC-PSO algorithm have excellent results. As instance, onthe Rastagrin function

with 7 particles and σ0 = 0.5 the hit ratio is 0.8920. It is sensibly better the the

NVC-PSO which had a best hit ratio of 0.8550. Results on the Egg Holder function

are also very good. With 300 particles and σ0 = 0.5 the hit ratio (accuracy = 10−2 )

is 1. It is better than the NVC-PSO which had with the same number of particles a

hit ratio of 0.63. Results are display in figure 24 where the NVC-PSO hit ratio and

hit time are used as reference.

Results for the different functions of the optimization benchmark.

25

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

sigma

Figure 23: hit ratio and hit time of the NPC-PSO as a function of σ0 (datas from

150 simulations with 7 particles).

σ0

0.5

0.5

0.5

0.5

0.5

Ns

7

100

300

50

7

Hit ratio

0.8920

0.9900

0.9967

1

Hit ratio ref Hit time Hit time ref

0.8550

506.6816 573.4094

0.7033

216.1636 503.1090

0.8933

232.77

490.6791

1

185.0033 154.21

C. time

0.0869

3.7535

0.259

0.0338

function

Rastagrin

Egg Holder

EggHolder

Griewank

Shaffer

Figure 24: Results of the NPC-PSO algorithm for the different functions of the

optimization benchmark. Hit ratio used as reference is the hit ratio of th NVC-PSO

algorithm run with the same parameters.

Conclusion

Particle Swarm Optimization is an extremely interesting alternative to solve minimization problems on a cost function. Easy to implement, this algorithm do not use

any advance mathematic operators and have consequently a very low computational

cost. Based on the swarming theory, algorithms from the PSO family deploy a population of moving particles on the function space. Evaluating the function at their

current position, those particles keep track of the position of the values with the best

fitness achieved and communicate with each other to track down the global minimum.

The discrete version of the algorithm presented in section 1 already performs fairly

well on complex function with many local minima. Continuous version introduced to

imitate more closely the real swarm behaviors increases the performances. However

26

n of sim

1000

1000

300

300

Algorithm Name

C-PSO

LFC-PSO

NVC-PSO

NPC-PSO

Hit ratio

0.27

0.33

0.70

0.99

Comments

100 leaders, 200 followers

Noise on velocity, σ = 0.5

Noise on position, σ = 0.5

Figure 25: Results of the different algorithm introduced on the Egg Holder function.

Parameters used are 300 particles and a accuracy of 10−2 . The NPC-PSO which

adds noise on the position has the best performances.

a premature swarm convergence prevents in some cases the particles to efficiently

explore the space function and the PSO algorithms have relatively poor result on

very complex functions. Indeed, on the Egg holder function, the algorithm has the

very low hit ratio of 0.2700 with 300 particles. To tackle this issue, more complex

versions of the PSO algorithm have been presented in section 2. The Completely

Smooth C-PSO introduces a smoother version of the algorithm where discontinuities

in the differential equations have been eliminated. Even if its performances are similar or even slightly worst the the C-PSO, it can be used as a support for a theoretical

study. The Random Jump C-PSO randomly reinitializes particles in an attempt to

increase the space search. The Followers and Leader C-PSO introduces two different

populations with different characteristic parameters. A population with more mobility is used to probe the function space longer while convergence is assured by a less

individual population. The algorithm has encouraging results with notably a slight

increase of the hit ratio with the Egg holder function, going up to 0.33. Finally, real

improvements in performances come from the Noise on Velocity C-PSO and Noise on

Position C-PSO presented in section 3 which add noise to their governing equations.

To allow the convergence, the variance of the brownian process added is a function

of the distance of the particle to the global minimum. Hence, if a particle is far from

the global best of the swarm and still in its exploration phase, the noise is important

in order to enhance its mobility. On the other hand, once the particle starts converging, noise decrease to allow a accurate convergence to the solution. Results are very

good, and on the Egg holder function the NVC-PSO which adds noise to the velocity

has a hit ratio of 0.70. Adding noise directly to the position, the NPC-PSO has the

best performances with a hit ratio of 0.99. on the Egg holder function. Figure 25

sums up main results of the different algorithms using the Egg holder function as

cost function with 300 particles.

27

A

Function benchmark

Ackley function

f (x, y) = −a e(−b

√1

2

(x2 +y 2 ))

1

− e 2 (cos(c x)+cos(c y)) +a + e,

(30)

where a = 20, b = 0.2 and c = 2 and the domain is : −10 ≤ x, y ≤ 10. f(0,0) =

0 is the global minimum.

Figure 26: Plot of the Ackley function

Egg Holder function

r

p

x

f (x, y) = − (y + 47) sin

|x − (y + 47)| ,

y + + 47 − x sin

2

(31)

where 512 ≤ x, y ≤ 512 and f (512, 404.2319) = −959.6407 is the global minimum.

2500

2000

1500

1000

500

0

500

0

−500

−100 0

−300 −200

−500 −400

100

200

300

400

500

Figure 27: Graph of the EggHolder function

Griewank function

r

r

x2 + y 2

x

y

− cos(

) cos(

) + 1,

f (x, y) =

4000

2

2

Domain search is −600 ≤ x, y ≤ 600. f(0,0) = 0 is the global minimum.

28

(32)

200

150

100

50

0

−50

600

400

1000

200

500

0

0

−200

−400

−500

−600

−1000

Figure 28: Plot of the Griewank function

Levy function

f (x, y) = sin2 (3πx) + (x − 1)2 1 + sin2 (3πy) + (y − 1)2 1 + sin2 (2πy) ,

(33)

Domain search is −10 ≤ x, y ≤ 10. f(1,1) = 0 is the global minimum.

Figure 29: Plot of the Levy function

Rastagrin function

f (x, y) = 20 + (x2 − 10 cos(2πx)) + (y 2 − 10cos(2πy)).

(34)

Domain search is −10 ≤ x, y ≤ 10. f(0,0) = 0 is the global minimum.

Figure 30: Plot of the Rastagrin function

Shaffer function

f (x, y) = 0.5 +

sin2 (x2 − y 2 ) − 0.5

.

(1 + 0.001 (x2 + y 2 ))2

Domain search is −100 ≤ x, y ≤ 100. f(0,0) = 0 is the global minimum.

29

(35)

Figure 31: Plot of the Shaffer function

B

Matlab code’s

B.1

PSO Algorithm

B.2

C-PSO Algorithm

B.3

NVC-PSO Algorithm

References

[1] Mordecai Avriel, Nonlinear Programming: Analysis and Methods. Dover Publishing, 2003

[2] Russel Eberhart and James Kennedy, A New Optimizer Using Particle Swarm

Theory. Proceedings Sixth Symposium on Micro Machine and Human Science;

1995

[3] Hassan M. Emara and Hossam A. Abdel Fattah, Continuous Swarm Optimization

Technique with Stability Analysis. Boston, Massachusetts, 2004

[4] K.E. Parsopoulos and M.N. Vrahatis, Recent approaches to global optimization

problems through Particle Swarm Optimization. Kluwer Academic Publishers,

2002

[5] C. W. Reynolds, Flocks, herds and schools: a distributed behavioral model. Computer Graphics, 1987.

[6] J. J. Liang, A. K. Qin, Ponnuthurai Nagaratnam Suganthan and S. Baskar,

Comprehensive Learning Particle Swarm Optimizer for Global Optimization of

Multimodal Functions. IEEE Transaction on evolutionary computation, 2006

[7] Watts and Strogatz, Collective dynamics of small-world networks. Nature, 1998

30

[8] James Kennedy, Small worlds and mega-minds: effects of neighborhood topology

on particle swarm performance. IEEE, 1999

[9] Kennedy, J., Mendes, R., Population structure and particle swarm performance.

IEEE, 2002

[10] Zhi-Hui Zhan, Jun Zhang, Yun Li, and Henry Shu-Hung Chung, Adaptive Particle Swarm Optimization. IEEE transaction on systems, man and cybernetics,

2009

[11] Riccardo Poli, James Kennedy and Tim Blackwell, Particle swarm optimization.

An overview. Springer Science and Business Media, 2007

[12] I.C. Trelea, The particle swarm optimization algorithm: Convergence analysis

and parameter selection. Information Processing Letters, 2003

[13] M. Clerc, J. Kennedy, The particle swarm-explosion, stability, and convergence

in a multidimensional complex space. IEEE Transac-tions on Evolutionary Computation, 2002

31

## Télécharger le fichier (PDF)

ReportZ.pdf (PDF, 4.3 Mo)