Particle Swarm Optimization: A Universal
Optimizer?
AP Engelbrecht
Computational Intelligence Research Group (CIRG)
Department of Computer Science
University of Pretoria
South Africaengel@cs.up.ac.za
http://cirg.cs.up.ac.za

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

1 / 62

Instructor
Andries Engelbrecht received the Masters and
PhD degrees in Computer Science from the Universityof Stellenbosch, South Africa, in 1994 and 1999
respectively. He is a Professor in Computer Scienceat the University of Pretoria, and serves as Head ofthe department. He also holds the position of South
African Research Chair in Artificial Intelligence. His
research interests include swarm intelligence,evolutionary computation, artificial neural networks,
artificial immune systems, and the application of theseComputational Intelligence paradigms to data mining,games, bioinformatics, finance, and difficult
optimization problems. He is author of two books,
Computational Intelligence: An Introduction andFundamentals of Computational Swarm Intelligence.
He holds an A-rating from the South African National
Research Foundation.
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

2 / 62

Presentation Outline I
1Introduction

2

Optimization Problem Classes

3Standard Particle Swarm Optimization

4

Discrete-valued Variables

5

Multi-Modal Optimization

6

Dynamic Optimization Problems

7

Constrained Optimization Problems

8

Multi-Objective Optimization Problems

9Large Scale Optimization

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

3 / 62

Introduction
Original PSO has been developed to solve optimization problems
that areunconstrained/boundary constrained
staticsingle-objective
continuous-valued
However:
Can PSO be used to solve optimization problems of different
classes, without significantly changing the principles of the basic
PSO?
If this is the case, we say that PSO is a universal optimizer
For each problem class, what are the issues, and how can PSO
be adapted to address these issues, while still maintaining the
behavioral principles of PSO?
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

4 / 62

Introduction (cont)Goal:
To show that PSO is a universal optimizer
Not to present a review of the best possible approaches to solve
optimization problems of the different problem classes, but toshow that PSO can solve these problems
Focus is on simple, efficient approaches

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

5 / 62

Optimization Problem Classes

A number of different optimization problem classes can be identified
Unconstrained
Boundary constrained
Constrained
Multi-objective, many-objective
Multi-modal
Dynamic and noisy
Continuous-valued versus discrete-valued
Large scale problems

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

6 / 62

Basic Foundations of Particle Swarm Optimization
Main Components

What are the main components?
a swarm of particles
each particle represents a candidate solution
elements of a particle represent parameters to be optimized
The search process:Position updatesxi (t + 1) = xi (t) + vi (t + 1), xij (0) ⇠ U(xmin,j , xmax,j )Velocity (step size)
drives the optimization process
step sizereflects experiential knowledge and socially exchanged information

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

7 / 62

Basic Foundations of Particle Swarm Optimization
Social Network Structures

Social network structures are used to determine best
positions/attractors: Star Topology

Engelbrecht (University of Pretoria): Ring Topology

Universal PSO?

: Von Neumann
TopologyIEEE CEC, 5-8 June 20178 / 62

Basic Foundations of Particle Swarm Optimization
global best (gbest) PSO

uses the star social network
velocity update per dimension:vij (t + 1) = vij (t) + c1 r1j (t)[yij (t)xij (t)] + c2 r2j (t)[ŷj (t)xij (t)]vij (0) = 0 (preferred)c1 , c2 are positive acceleration coefficientsr1j (t), r2j (t) ⇠ U(0, 1)

note that a random number is sampled for each dimension

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 2017

9 / 62

Basic Foundations of Particle Swarm Optimization
gbest PSO (cont)yi (t) is the personal best position calculated as (assuming
minimization)⇢yi (t)
if f (xi (t + 1)) f (yi (t))
yi (t + 1) =xi (t + 1) if f (xi (t + 1)) < f (yi (t))ŷ(t) is the global best position calculated asŷ(t) 2 {y0 (t), . . . , yns (t)}|f (ŷ(t)) = min{f (y0 (t)), . . . , f (yns (t))}
or (removing memory of best positions)ŷ(t) = min{f (x0 (t)), . . . , f (xns (t))}
where ns is the number of particles in the swarm
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201710 / 62

Basic Foundations of Particle Swarm Optimization
local best (lbest) PSO

uses the ring social networkvij (t + 1) = vij (t) + c1 r1j (t)[yij (t)xij (t)] + c2 r2j (t)[ŷij (t)xij (t)]ŷi is the neighborhood best, defined asŷi (t + 1) 2 {Ni |f (ŷi (t + 1)) = min{f (x)}, 8x 2 Ni }with the neighborhood defined as
Ni = {yi nN (t), yi nN +1 (t), . . . , yi 1 (t), yi (t), yi+1 (t), . . . , yi+nN (t)}iiiwhere nNi is the neighborhood sizeneighborhoods based on particle indices, not spatial informationneighborhoods overlap to facilitate information exchange
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201711 / 62

Basic Foundations of Particle Swarm Optimization
Velocity Components

previous velocity, vi (t)inertia component
memory of previous flight direction
prevents particle from drastically changing direction

cognitive component, c1 r1 (yixi )quantifies performance relative to past performances
memory of previous best position
nostalgia

social component, c2 r2 (ŷixi )quantifies performance relative to neighbors
envy

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201712 / 62

Basic Foundations of Particle Swarm Optimization
PSO Iteration Strategies

Synchronous Iteration Strategy
Asynchronous Iteration Strategy
Create and initialize the swarm;
repeatCreate and initialize the swarm;
for each particle dorepeatEvaluate particle’s fitness;for each particle doUpdate particle’s personal
Update the particle’s velocity;
best position;
Update the particle’s position;
Update particle’s
Evaluate particle’s fitness;neighborhood best position;
Update the particle’s personal
best position;
end
Update the particle’s
for each particle doneighborhood best position;
Update particle’s velocity;
Update particle’s position;end
end
until stopping condition is true;
until stopping condition is true;
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201713 / 62

Discrete-Valued Variables
Introduction

What is the problem?
PSO was originally developed for optimizing continuous-valued
variables
That is xij 2 R

Uses vector algebra on floating-point vectors to adjust search
positions
How do we adapt PSO so that xij 2 {0, 1}?

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201714 / 62

Discrete-Valued Variables
Binary PSO

Adapting PSO for binary-valued variables: Binary PSO
Velocity remains a floating-point vector, but meaning changes
Velocity is no longer a step size, but is used to determine aprobability of selecting bit 0 or bit 1
Position is a bit vector, i.e. xij 2 {0, 1}

How to interpret velocity as a probability?
pij (t) =1
1 + e vij (t)Then, position update changes to⇢
1 if U(0, 1) < pij (t + 1))
xij (t + 1) =0 otherwise
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201715 / 62

Discrete-Valued Variables
Binary PSO (cont)

Velocity clamping:sets the minimal probability for a bit change
if Vmax,j = 4, then sig(Vmax,j ) = 0.982 is the probability of xij tochange to bit 1, and 0.018 the probability to change to bit 0
small values for Vmax,j promotes exploration
for Vmax,j = 0, the search changes to a random searchlarge values for Vmax,j promotes exploitation
start with small Vmax,j that increases over timeEngelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201716 / 62

Discrete-Valued Variables
Binary PSO (cont)

Inertia weight:
w < 1 works against convergence, as vij becomes zero over time,and each bit then has a 50% change of changing
velocity should not become zerostart with small w, increase over time
Velocity initialization: Initialize to zero.
for vij > 1, limt!1 sig(vij (t)) ! 1 and the probability that all bitschange to 1 increases
for vij < 1, limt!1 sig(vij (t)) ! 0 and the probability that all bitschange to 0 increases

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201717 / 62

Discrete-Valued Variables
Binary PSO (cont)Some issues with the binary PSO:
Changes the meaning of the velocity update
No longer a step size
No longer a search trajectory

Effect of control parameters change
Theoretical analysis of standard PSO no longer applies

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201718 / 62

Discrete-Valued Variables
Angle Modulated PSO (AMPSO)

An approach to solve a Bnx -dimensional problem in R4
Velocities and particle positions remain floating-point vectors
Find a bitstring generating function, used to generate the bitstring
solution
The generating function:g(x) = sin(2⇡(xa) ⇥ b ⇥ cos(2⇡(xa) ⇥ c)) + d

where x is a single element from a set of evenly separated
intervals determined by the required number of bits that need tobe generated

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201719 / 62

Discrete-Valued Variables
AMPSO (cont)g(x) = sin(2⇡(xa) ⇥ b ⇥ cos(2⇡(x

The coefficients determine the shapeof the generating function:1

a: horizontal shift of generating
functionc: frequency of the cos function
d: vertical shift of generating
function

Engelbrecht (University of Pretoria)

Universal PSO?

0.8
0.6
0.4
0.2
g(x)

b: maximum frequency of the sinfunctiona) ⇥ c)) + d

0
-0.2
-0.4
-0.6
-0.8
-1
-2

-1.6

-1.2

-0.8

-0.4

0
x

0.4

0.8

1.2

IEEE CEC, 5-8 June 2017

1.6

2

20 / 62

Discrete-Valued Variables
AMPSO (cont)Use a standard PSO to find the best values for these coefficients
Generate a swarm of 4-dimensional particles;
repeatApply any PSO for one iteration;for each particle do
Substitute values for coefficients a, b, c and d into generating
function;
Produce nx bit-values to form a bit-vector solution;
Calculate the fitness of the bit-vector solution in the original
bit-valued space;end
until a convergence criterion is satisfied;Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201721 / 62

Multi-Modal Optimization (Niching)Introduction

Assuming minimization,
Boundary constrained optimization problem:
minimize f (x),x = (x1 , x2 , . . . , xnx )subject toxj 2 dom(xj )where x 2 F = S, and dom(xj ) is the domain of variable xj .
Multi-solution problem: Find a set of solutions,
X = {x⇤1 , x⇤2 , . . . , x⇤nX }such that each x⇤ 2 X is a minimum of the general optimization
problemEngelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201722 / 62

Multi-Modal Optimization (Niching)Introduction (cont)

Niching capability of PSO:
Can the gbest PSO find more than one solution?
Formal proofs showed that all particles converge to a weighted
average of their personal best and global best positions
lim xi (t) =t!1

c1 yi + c2 ŷ
c1 + c2

Therefore, only one solution can be found
What if we re-run the algorithm? No guarantee to find different
solutions

What about lbest PSO?
Neighborhoods may converge to different solutions
However, due to overlapping neighborhoods, particles are still
attracted to one solution
Formal proof exist to show that all particles converge in the limit
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201723 / 62

Multi-Modal Optimization (Niching)
Objection Function Stretching

Sequential niching, stretching the function to remove found minima
Create and initialize a nx -dimensional swarm, S, and X = ;;repeatPerform a single PSO iteration;
if f (S.ŷ)  ✏ thenIsolate S.ŷ;
Perform a local search around S.ŷ;
if a minimizer x⇤N is found by the local search thenX
X [ {x⇤N };Let f (x)
H(x);
end
end
Reinitialize the swarm S;
until stopping condition is true;
Return X as the set of multiple solutions;
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201724 / 62

Multi-Modal Optimization (Niching)
Objection Function Stretching (cont): Effect of Sequential Niching for One Dimension

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201725 / 62

Multi-Modal Optimization (Niching)
Niche PSO

Parallel niching PSO
Create and initialize a nx -dimensional main swarm, S;
repeatTrain main swarm, S, for one iteration using cognition-only model;
Update the fitness of each main swarm particle, S.xi ;for each sub-swarm Sk do
Train sub-swarm particles, Sk .xi , using a full model PSO;
Update each particle’s fitness;
Update the swarm radius Sk .R;
endFor
If possible, merge sub-swarms;
Allow sub-swarms to absorb any particles from the main swarm
that moved into the sub-swarm;
If possible, create new sub-swarms;
until stopping condition is true;
Return Sk .ŷ for each sub-swarm Sk as a solution;
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201726 / 62

Dynamic Optimization Problems
Introduction

Objective: To find and track solutions in dynamically changing
search spacesx⇤ (t) = min f (x, $(t))

x⇤where x (t) is the optimum found at time step t, and $(t) is avector of time-dependent objective function control parameters
Environment types:
Location of optima may change
Value of optima may change
Optima may disappear and newones appear
Change frequencey
Change severity: Environment Classes
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201727 / 62

Dynamic Optimization Problems
Introduction (cont)

Can PSO be applied to track an optimum?
Only for quasi-static environments, to some success
What are the problems?
Loss of diversity
MemoryChange detection

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201728 / 62

Dynamic Optimization Problems
Introduction (cont)What can be done to address these problems?
Diversity
Inject diversity into the swarm, but how much, and how?
Maintain diversity

MemoryRe-evaluate personal best and neighborhood best positions

Change detection
Use sentry particles

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201729 / 62

Dynamic Optimization Problems
Charged PSO

Maintains diversity throughout the search process
Some particles attract one another, and others repell one another
Velocity changes tovij (t +1) = wvij (t)+c1 r1 (t)[yij (t) xij (t)]+c2 r2 (t)[ŷj (t) xij (t)]+aij (t)where ai is the particle acceleration, determining the magnitude ofinter-particle repulsionai (t) =nsXail (t)l=1,i6=l

The repulsion force between particles i and l is
⌘
( ⇣
Qi Ql
(xi (t) xl (t)) if Rc  dil  Rp
dil3
ail (t) =0otherwise
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201730 / 62

Dynamic Optimization Problems
Quantum PSO

Based on quantum model of an atom, where orbiting electrons are
replaced by a quantum cloud which is a probability distribution
governing the position of the electron
Developed as a simplified and less expensive version of thecharged PSO
Swarm contains
neutral particles following standard PSO updates
charged, or quantum particles, randomly placed within amulti-dimensional sphere⇢xi (t) + vi (t + 1) if Qi = 0
xi (t + 1) =Bŷ (rcloud )if Qi 6= 0
charged particles uniformly sampled within the sphere

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201731 / 62

Dynamic Optimization Problems
Quantum PSO (cont)

Can use different distributions:xi (t + 1) ⇠ P(ŷ(t), rcloud )where P is some probability distribution and rcloud is the quantum
radiusSome alternative distributions to consider:
Non-uniform (decreasing probability)
Gaussian
CauchyExponential
Beta
Triangular
WeibullBest distribution depends on type of dynamism
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201732 / 62

Dynamic Optimization Problems
Quantum PSO (cont)Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201733 / 62

Constrained Optimization Problems
Introduction

Constrained optimization problem:
minimizef (x),

x = (x1 , . . . , xnx )subject to

gm (x)  0, m = 1, . . . , ng

hm (x) = 0, m = ng + 1, . . . , ng + nh
xj 2 dom(xj )where ng and nh are the number of inequality and equality constraints
respectively

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201734 / 62

Constrained Optimization Problems
Introduction (cont)

How do we ensure that only feasible solutions are found?
Boundary versus functional constraints
For boundary constraints:
Do not allow particles that violate boundary constraints to become
personal best positions
Reinitialize those elements that violate the boundary constraints
within the bounds

Reject infeasible solutions
Do not allow infeasible particles to become personal best or
neighborhood best positions
Replace infeasible solutions with randomly generated, feasible
solutions

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201735 / 62

Constrained Optimization Problems
Penalty Methods

Optimization problem is reformulated asminimize

F (x, t) = f (x, t) + p(x, t)

is the penalty coefficien, and p(x, t) is the (possibly) time-dependent
penalty function
How to find the best penalty coefficients?
And the penalty?
ng +nhp(xi , t) =Xm (t)pm (xi )

m=1

where
pm (xi ) =⇢max{0, gm (xi )↵ } if m 2 [1, . . . , ng ]|hm (xi )|↵if m 2 [ng + 1, . . . , ng + nh ]↵ is a positive constant, representing the power of the penalty
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201736 / 62

Constrained Optimization Problems
Penalty Methods (cont)f (x1 , x2 ) =x1 cos(x1 )22+ 2e x1 (x2 1) + 0.01x1 x2
20f(x1,x2)

F(x1,x2)

f(x1,x2)

f(x1,x2)

2
1.5
1
0.5
0
-0.5
-1
-1.5

2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5
-2
-2.5
10

10

5
-10

0

-5

0
x1

5

-5

x2

-10

0

-5

0
x1

10-10

(a) Original function

Engelbrecht (University of Pretoria)

5

5

-5

x2

10-10

(b) With penalty p(x1 , x2 ) = 3x1 and= 0.05
Universal PSO?

IEEE CEC, 5-8 June 201737 / 62

Constrained Optimization Problems
Penalty Methods (cont)Constrained problem 1: Minimize the function
f (x) = 100(x2x12 )2 + (1x1 )2

subject to the nonlinear constraints,
x1 + x22
x12 + x200with x1 2 [ 0.5, 0.5] and x2  1.0.
The global optimum is x⇤ = (0.5, 0.25), with f (x⇤ ) = 0.25

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201738 / 62

Constrained Optimization Problems
Penalty Methods (cont): Function LandscapeEngelbrecht (University of Pretoria): Violation Space

Universal PSO?

IEEE CEC, 5-8 June 201739 / 62

Constrained Optimization Problems
Penalty Methods (cont): With: With=1

Engelbrecht (University of Pretoria)

Universal PSO?

= 100

IEEE CEC, 5-8 June 201740 / 62

Constrained Optimization Problems
Lagrangian Approach

Convert the constrained (primal) problem to an unconstrained problem
by defining the Lagrangian for the constrained problem:
L(x,

g,

h ) = f (x) +ng
Xng +nh
gm gm (x) +m=1

Xhm hm (x)m=ng +1

Then maximize the Lagrangian (dual problem):maximize g , hsubject toEngelbrecht (University of Pretoria)

L(x,
gm

g,

0,

h)

m = 1, . . . , ng + nh

Universal PSO?

IEEE CEC, 5-8 June 201741 / 62

Constrained Optimization Problems
Lagrangian Approach (cont)

The vector x⇤ that solves the primal problem, as well as the Lagrange
multiplier vectors, ⇤g and ⇤h , can be found by solving the min-max
problem,min max L(x, g , h )xEngelbrecht (University of Pretoria)

g, hUniversal PSO?

IEEE CEC, 5-8 June 201742 / 62

Constrained Optimization Problems
Lagrangian Approach (cont)A coevolutionary PSO approach to solve the above min-max problem
uses two swarms
Swarm S1 uses fitness function
f (x) = max L(x,g , h 2S2

g,

h)

g,

h)

Swarm S2 uses fitness functionf ( g,Engelbrecht (University of Pretoria)h ) = min L(x,x2S1

Universal PSO?

IEEE CEC, 5-8 June 201743 / 62

Constrained Optimization Problems
Lagrangian Approach (cont)

Create and initialize two swarms, S1 and S2 , where S1 isnx -dimensional and S2 is ng + nh dimensional;
repeatRun a PSO algorithm on swarm S1 for S1 .nt iterations;Re-evaluate S2 .yi (t), 8i = 1, . . . , S2 .ns ;Run a PSO algorithm on swarm S2 for S2 .nt iterations;Re-evaluate S1 .yi (t), 8i = 1, . . . , S1 .ns ;until stopping condition is true;

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201744 / 62

Constrained Optimization Problems
Reformulate as Multi-Objective Problem

Reformulate as a boundary constrained multi-objective optimization
problem:f(x) = (f (x), p(x))
Solve using any multi-objective PSO algorithm

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201745 / 62

Multi-Objective Problems
Introduction

Multi-objective problem:
minimize f(x)subject to gm (x)  0, m = 1, . . . , ng
hm (x) = 0, m = ng + 1, . . . , ng + nh
x 2 [xmin , xmax ]nx
where

f(x) = (f1 (x), f2 (x), . . . , fnk (x)) 2 O ✓ Rnk

O is referred to as the objective space
The search space, S, is also referred to as the decision space

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201746 / 62

Multi-Objective Problems
Introduction (cont)

Important things to note:
Goals are in conflict with one another
Need to achieve a balance between these objectives
A balance is achieved when a solution cannot improve any
objective without degrading one or more of the other objectives
There is not just one solution
Solutions are referred to as non-dominated solutions
Set of solutions is referred to as the Pareto-optimal set, and thecorresponding objective vectors are referred to as the Pareto front

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201747 / 62

Multi-Objective Problems
Weighted Aggregation

Definition:
Pnk
minimizek =1 !k fk (x)subject to gm (x)  0, m = 1, . . . , ng
hm (x) = 0, m = ng + 1, . . . , ng + nh
x 2 [xmin , xmax ]nx!k 0, k = 1, . . . , nk
It is also usually assumed that

Engelbrecht (University of Pretoria)

Pnk

k =1 !k = 1

Universal PSO?

IEEE CEC, 5-8 June 201748 / 62

Multi-Objective Problems
Weighted Aggregation (cont)

Aggregation methods have the following problems:
The algorithm has to be applied repeatedly to find different
solutions if a single-solution algorithm is used
It is difficult to get the best weight values, !k , since these areproblem-dependent
Aggregation methods can only be applied to generate members of
the Pareto-optimal set when the Pareto front is concave,
regardless of the values of !kEngelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201749 / 62

Multi-Objective Problems
Pareto-Optimality

Domination: A decision vector, x1 dominates a decision vector, x2(denoted by x1 x2 ), if and only if
x1 is not worse than x2 in all objectives, i.e.
fk (x1 )  fk (x2 ), 8k = 1, . . . , nk , andx1 is strictly better than x2 in at least one objective, i.e.
9k = 1, . . . , nk : fk (x1 ) < fk (x2 ).
So, solution x1 is better than solution x2 if x1x2 ), which happens when f1 f2

Engelbrecht (University of Pretoria)

Universal PSO?

x2 (i.e. x1 dominates

IEEE CEC, 5-8 June 201750 / 62

Multi-Objective Problems
Pareto-Optimality (cont)

Pareto-optimal: A decision vector, x⇤ 2 F is Pareto-optimal if there
does not exist a decision vector, x 6= x⇤ 2 F that dominates it. That is,@k : fk (x) < fk (x⇤ ). An objective vector, f⇤ (x), is Pareto-optimal if x is
Pareto-optimal.
Pareto-optimal set: The set of all Pareto-optimal decision vectors
form the Pareto-optimal set, P ⇤ . That is,P ⇤ = {x⇤ 2 F| 6 9x 2 F : xx⇤ }Pareto-optimal front: Given the objective vector, f(x), and thePareto-optimal solution set, P ⇤ , then the Pareto-optimal front,
PF ⇤ ✓ O, is defined as
PF ⇤ = {f = (f1 (x⇤ ), f2 (x⇤ ), . . . , fk (x⇤ ))|x⇤ 2 P}

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201751 / 62

Multi-Objective Problems
Vector-Evaluated PSO (VEPSO)

A multi-swarm approach:
Assume K sub-objectives
K sub-swarms are used, where each optimizes one of theobjectives
Need a knowledge transfer strategy (KTS) to transfer information
about best positions between sub-swarms
Exchanged information are via selection of global guides,
replacing the global best positions in the velocity updates
Standard KTS: the ring KTS
Sub-swarms are arranged in a ring topology
Global guide of swarm Sk is swarm S(k +1) mod K

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201752 / 62

Multi-Objective Problems
VEPSO (cont)Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201753 / 62

Multi-Objective Problems
VEPSO (cont)

Assume two objectives
S1 .vij (t + 1) = wS1 .vij (t) + c1 r1j (t)(S1 .yij (t)+ c2 r2j (t)(S2 .ŷi (t)S1 .xij (t))

S2 .vij (t + 1) = wS2 .vij (t) + c1 r1j (t)(S2 .yij (t)+ c2 rij (t)(S1 .ŷj (t)S1 .xij (t))
S2 .xij (t))

S.x2j (t))

where sub-swarm S1 evaluates individuals on the basis of objective
f1 (x), and sub-swarm S2 uses objective f2 (x)Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201754 / 62

Multi-Objective Problems
VEPSO (cont)

Local guide selection:
Local guide replaces the personal best
Update personal best position only if the new particle position
dominates the previous personal best position
Global guide selection:
Global guide replaces the neighborhood best
Selection dictated by a knowledge transfer strategy (KTS):
Ring KTS
Random KTS

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201755 / 62

Multi-Objective Problems
VEPSO (cont)

Using archives
Objective of archive is to keep
track of all non-dominatedsolutionsNon-dominated solutions
added to archive after each
iteration
Fixed-sized archives versus
unlimited sizes
Local versus global guides

Engelbrecht (University of Pretoria)

Let t = 0;
Initialize the swarm, S(t), andarchive, A(t);repeatEvaluate (S(t));
A(t + 1)
Update(S(t), A(t));
S(t + 1)
Generate(S(t), A(t));
t = t + 1;
until stopping condition is true;

Universal PSO?

IEEE CEC, 5-8 June 201756 / 62

Large Scale Optimization
Introduction

Curse of dimensionality:
As dimensionality increases, performance deteriorates
What to do?
Increase number of particles
Increases computational complexity
Reduces step sizes, due to smaller difference vectors

Reduce the complexity of the problem, using divide-and-conquer

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201757 / 62

Large Scale Optimization
Cooperative PSO (CPSO)

Each particle is split into K separate parts of smaller dimension
Each part is then optimized using a separate sub-swarm
If K = nx , each dimension is optimized by a separate sub-swarm
What are the issues?
Problem if there are strong dependencies among variables
How should the fitness of sub-swarm particles be evaluated?

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201758 / 62

Large Scale Optimization
CPSO (cont)K1 = nx mod K and K2 = K (nx mod K );Initialize K1 dnx /K e-dimensional and K2 bnx /K c-dimensional swarms;
repeatfor each sub-swarm Sk ,k = 1, . . . , K dofor each particle i = 1, . . . , Sk .ns do
if f (b(k , Sk .xi )) < f (b(k , Sk .yi )) thenSk .yi = Sk .xi ;end
if f (b(k , Sk .yi )) < f (b(k , Sk .ŷ)) thenSk .ŷ = Sk .yi ;end
end
Apply velocity and position updates;
end
until stopping condition is true;
Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201759 / 62

Large Scale Optimization
CPSO (cont)

How to cope with variable dependencies?
Pre-processing to determine correlations and group correlated
variables in same sub-swarm
Random grouping
Top-down versus bottom-up approaches

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201760 / 62

Summary
Particle swarm optimization is an extremely simple, yet powerful
optimization method
Without changing the basic principles of PSO, minor modifications
allow PSO to be applied to a wide range of problem classes,
including:
Unconstrained
Constrained
Unimodal and multimodal
Continuous-valued and discrete-valued
Dynamically changing landscapesMulti-objective
Multiple solutions

Various combinations of the above problem types

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201761 / 62

Summary

We can therefore safely say that PSO is a universal optimizer
We do not say that PSO is the best for all classes of problems,and all landscape characteristics, only that it can be applied tosolve a wide range of problem classes
This tutorial is based on the content of the following reference:
AP Engelbrecht, Fundamentals of Computational SwarmIntelligence, Wiley, 2005.

Engelbrecht (University of Pretoria)

Universal PSO?

IEEE CEC, 5-8 June 201762 / 62