Transcript Particle Swarm Optimization

Multimodal Optimization
(Niching)
A/Prof. Xiaodong Li
School of Computer Science and IT, RMIT University
Melbourne, Australia
Email: [email protected]
April 2015
Niching


The notion of niching is inspired by nature. In natural
ecosystems, individual species must compete to survive
by taking on different roles. Different species evolve to fill
different “niches” (or subspaces) in the environment that
can support different types of life.
Instead of evolving a single population of individuals
indifferently, natural ecosystems evolve different species
(or subpopulations) to fill different niches. The terms
species and niche are sometimes interchangeable.
28/07/2015
2
Speciation and niching
28/07/2015
3
Speciation and niching
Biological species concept: a species is a group of actually
or potentially interbreeding individuals who are reproductively
isolated from other such groups.
The definition of a species is still debatable.
Most researchers believe either the morphological species
concept (ie., members of a species look alike and can be
distinguished from other species by their appearance), or the
biological species concept (a species is a group of actually
or potentially interbreeding individuals who are reproductively
isolated from other such groups). Both definitions have their
weaknesses.
28/07/2015
4
Niching in Evolutionary Algorithms


Niching methods were introduced to EAs to allow
maintenance of a population of diverse individuals so
that multiple optima within a single population can be
located.
As Mahoud described “A niching method must be able to
form and maintain multiple, diverse, final solutions,
whether these solutions are of identical fitness or of
varying fitness. A niching method must be able to
maintain these solutions for an exponential to infinite
time period, with respect to population size.”
28/07/2015
5
Why niching?


Many real-world problems are “multimodal” by nature,
that is, multiple satisfactory solutions exist. For an
optimization problem with multiple global and local
optima, it might be desirable to locate all global optima
and/or some local optima that are also considered as
being satisfactory.
A niching method can be incorporated into a standard EA
to promote and maintain formation of multiple stable
subpopulations within a single population, with an aim to
locate multiple optimal or suboptimal solutions.
28/07/2015
6
Multimodal problems
28/07/2015
7
Example 1 – Truss topologies
Multiple optimal truss
topologies (i.e., optimal
solutions) found by using
a niching method.
28/07/2015
8
Example 2 – sports car chassis
Between coupe and open-top,
various different combinations of
load cases. Each combination of
load cases lead to different
topologies. Interpretation of the
results can become quite hard.
28/07/2015
9
Classic niching methods



Fitness sharing and Crowding methods
(early 70s and 80s).
In subsequent years, many niching methods
have been proposed. Some representative
examples include deterministic crowding,
derating, restricted tournament selection,
parallelization, clustering, and speciation.
More recently, NichePSO, Speciationbased PSO, Ring topology PSO.
28/07/2015
10
Multimodal functions
28/07/2015
11
Fitness Sharing
28/07/2015
12
Fitness sharing
The most widely used sharing function is the following:
However, there is no easy task to set the niche radius parameter.
28/07/2015
13
Crowding



De Jong’s crowding was initially designed only to
preserve population diversity.
In crowding, an offspring is compared to a small random
sample taken from the current population, and the most
similar individual in the sample is replaced.
A parameter crowding factor (CF) is commonly used to
determine the size of the sample.
28/07/2015
14
Deterministic crowding


Mahfoud found that De Jong’s crowding method was
unable to maintain more than two peaks of a five peaks
fitness landscape due to stochastic replacement errors.
Mahfoud then made several modifications to crowding to
reduce replacement errors, restore selection pressure,
and also eliminate the crowding factor parameter. The
resulting algorithm, deterministic crowding, was able to
locate and maintain multiple peaks.
28/07/2015
15
Speciation-based PSO
f
s2
s3
s1
p
2rs
x
An example of how to determine the species seeds from the population at each
iteration. s1, s2, and s3 are chosen as the species seeds. Note that p follows s2.
28/07/2015
16
Performance measures
Peak Ratio (PR) and Success Rate (SR):
28/07/2015
17
How to determine solutions found?
Here we assume the number of global
peaks, and the distance between two
closest global peaks are known in
advance.
For further information, see the technical
report on CEC’13 competition benchmark
on multimodal optimization.
28/07/2015
18
Multimodal functions
28/07/2015
19
Simulation runs
Refer to Li (2004)
for details.
28/07/2015
20
Niching parameters
Difficulty in choosing the niching parameters such as the species radius r . For
example, for Shubert 2D, there is no value of r that can distinguish the global
optima without individuals becoming overly trapped in local optima.
Some recent works in handling this problem (Bird & Li, 2006a; Bird & Li, 2006b).
28/07/2015
21
Ring topology based PSO
28/07/2015
22
Ring topology based PSO
A PSO algorithm using the ring topology can operate as a niching algorithm by using
individual particles’ local memories to form a stable network retaining the best
positions found so far, while these particles explore the search space more broadly.
See (Li , 2010).
28/07/2015
23
Further readings


Li, X. (2010), “Niching without Niching Parameters:
Particle Swarm Optimization Using a Ring Topology”,
IEEE Transactions on Evolutionary Computation,
Volume 14, No.1, February 2010, pp.150-169.
Li, X., Engelbrecht, A. and Epitropakis,M.G. (2013),
“Benchmark Functions for CEC’2013 Special Session
and Competition on NichingMethods for Multimodal
Function Optimization”. Technical Report, Evolutionary
Computation and Machine Learning Group, RMIT
University, Australia, 2013.
28/07/2015
24