Recent Advances in Multi-Modal
Optimization using niching methods
Michael G. Epitropakis,
Data Science InstituteDepartment of Management Science,
Lancaster University, Lancaster, UK
Email: m.epitropakis@lancaster.ac.uk
Xiaodong Li,
School of Science,
RMIT University, Melbourne, Australia
Email: xiaodong.li@rmit.edu.au
Andries Engelbrecht
Department of Computer Science,
School of Information Technology,
University of Pretoria, Pretoria, South Africa
Email: engel@driesie.cs.up.ac.za
IEEE CEC’2017, Donostia - San Sebastián, Spain, June, 2017

Instructors
Andries Engelbrecht
Department of Computer
Science, School of Information
Technology,
University of Pretoria, Pretoria
South Africaengel@driesie.cs.up.ac.za
Xiaodong Li,
School of Science,
RMIT University, Melbourne,
Australia
xiaodong.li@rmit.edu.au

2/6/17

Michael G. Epitropakis,
Data Science Institute,
Department of Management
Science,
Lancaster University,
Lancaster, United Kingdom
m.epitropakis@lancaster.ac.uk
2

Multi-Modal
Optimization?
Curiosity's view of "Mount
Sharp" (September 9,
2015)

Mount Sharp rises from the
middle of Gale Crater; the green
dot marks Curiosity's landing site
(north is down).
Source: https://en.wikipedia.org/wiki/Curiosity_(rover)

2/6/17

3

General Notes• More questions than answers in Multi-Modal
Optimization (MMO)• Limited theoretical advances/strict formulations• Huge amount of literature (from the 80s onwards)• Tutorial: a “short” presentation on advances in thefield.
• Stay connected… More to come in the near future…
• Please interrupt for questions/comments• Suggestions for future work are more than welcome
2/6/174

Outline• Background on multimodal optimization• What are the benefits for studying MMO?
• What are niching methods?
• Some real-world examples• Classic niching methods• Niching methods derived from PSO and DE• Other state-of-the-art niching methods• Niching benchmark suites and performance measures• Niching in specialized tasks– Dynamic and multi-objective optimization– Clustering, feature selection, and machine learning• IEEE CIS Taskforce on Multi-Modal Optimization• Discussion and summary• References
2/6/175

What is multi-modal optimization?
• Multi-modal Optimization (MMO): to locate multiple optimal (or close
to optimal) solutions in the search space– This is different from a conventional optimization method which has a common
goal of seeking to locate a single global optimum• A rough definition:
In a multimodal optimization task, the main purpose is to find multiple
optimal solutions (global and local), so that the user can have a betterknowledge about different optimal solutions in the search space and as
and when needed, the current solution may be switched to anothersuitable optimum solution
Deb, Saha: Multimodal Optimization Using a Bi-Objective Evolutionary Algorithm, ECJ, 2012

2/6/17

6

What is multi-modal optimization? (II)• MMO problems represent an important class of optimization
problems• Many real-world optimization problems:– multimodal by nature– multiple satisfactory solutions exist (several real-world examples of MMO
problems are provided in subsequent slides)• From a decision maker’s point of view:– it might be desirable to locate all global optima and/or some local optima
that are also considered as being satisfactory– Better knowledge of alternative solutions

2/6/17

7

Methods for MMO• Optimization methods specifically designed for solving MMO
problems:– often called multimodal optimization or niching methods– predominately developed from the field of meta-heuristic algorithms– Covers the family of population-based stochastic optimization algorithms,
including evolutionary algorithms, evolutionary strategies, particle swarm
optimization, differential evolution, and so on• These meta-heuristic algorithms are shown particularly effective
in solving multimodal optimization problems, if equipped withspecifically designed diversity preserving mechanisms, commonlyreferred to as niching methods• Two-fold aim: accurately locate and robustly maintain multiple
optima2/6/178

What are the benefits?
• A decision maker may be interested to know whether there exist
multiple equally good solutions before making a final decision• Important for a sensitivity study of a problem, and helps develop
more robust solutions to the problem• Plays an important role in keeping a diverse population ofcandidate solutions, hence helps prevent the population fromconverging prematurely to a sub-optimum• May increase the probability of finding the global optimum

2/6/179

Different scenarios• One-global optimum:– Looking for the global optimum solution only (not MMO)

• All-global optima:– Find all the global optimum solutions– Benchmark problems of the CEC 2013/2015/2016 nichingcompetition series belong here

• All-known optima:– Find all local and/or global optimal solutions• Approximate set of solutions:– Locate as many as possible (subset) optimal solutions(global/local) that are well distributed over the search space
Mike Preuss. 2015. Multimodal Optimization. GECCO Companion '15, http://dx.doi.org/10.1145/2739482.2756572

2/6/1710

Ecological inspiration• In natural ecosystems, individual species must compete to survive bytaking on different roles. Different species evolve to fill different niches (orsubspaces) in the environment that can support different types of life

2/6/1711

What are niching methods?
• According to the Oxford Dictionary, a niche refers to “a role taken bya type of organism within its community”; and a species refers to “agroup of living organisms consisting of similar individuals capable ofexchanging genes or interbreeding”• These concepts of niches, species and speciation can be adopted in
an EA to encourage an EA population to evolve different species
targeting different optimal solutions in the search space

2/6/17

12

MMO Publication trends• Despite niching methods first appeared more than 30
years ago, currently niching techniques are experiencing arevival, attracting researchers from across a wide range of
research fields
Query:"multimodal optimization" OR niching
Source:

●

IEEE

●

niching

Real-world Applications trend

Scopus

200

20

●

●

●

●

15

●
●

●

●

●
●

●
●

●
●

●
●

●

●
●
●

●
●
●

●
●

●

●

●
●

●

●
●

●
●

●

●
●
●
●

1990

2/6/17

●

●
●

●

●

●
●

●

●
●

●

●

●
●

●
●

●

●

●

●

●
●

●
●

●

●

●

●

●

●

50

●

10

●

●

●

0

●

●

# articles# articles

●

●

●

●

●

●
●

●

●

100

●

●

150

●

●

●

●
●

●

●
●

5

●

●

●

●

●

●
●

●
●
●

1995

2000

2005

2010

2015

●

1995

●

2000

2005

2010

2015

13

MMO Application areas
Subject

Agricultural and Biological Sciences
Arts and Humanities
Biochemistry, Genetics and Molecular Biology
Business, Management and Accounting
Chemical Engineering
ChemistryComputer Science
Decision Sciences
Earth and Planetary Sciences
Economics, Econometrics and Finance
EnergyEngineering
Environmental Science
Immunology and Microbiology
Materials Science
Mathematics
Medicine
Multidisciplinary
Neuroscience
NursingPharmacology, Toxicology and Pharmaceutics
Physics and Astronomy
Psychology
Social Sciences
2/6/17

14

Multi-Modal Optimization

REAL-WORLD APPLICATIONS

2/6/1715

Engineering example: truss topology design• In topology optimization, the connectivity of members in a truss is tobe determined. There exist multiple different topologies with almost
equal overall weight in truss-structure design problems as themembers in the ground structure increase• The resulting solution of truss-structure optimization design problems
becomes ‘‘multi-modal’’ with large number of truss members
Some nodes in the groundstructure may or may not be
removed. The optimal structure isfound as a subset of the groundstructure

Deb K, Gulati S. “Design of truss-structures for minimum weight using genetic algorithms,” Finite Elements Anal Des 2001;
37: 447–65.
G.-C. Luh and C.-Y. Lin, “Optimal design of truss-structures using particle swarm optimization,” Computers and Structures,vol. 89, no.23-24, pp. 2221 – 2232, Dec. 2011.
2/6/1716

Truss topology design• Sharing scheme is used to compute the similarity between
different topology design solutions• The sharing fitness is a reduced one from the original fitness,in order to discourage solutions in the vicinity
Binary PSO is run basedon the sharing fitness
values, and multiple
dissimilar truss
topologies are derived
and saved

2/6/1717

Truss topology design

Multiple optimal truss topologies found by BPSO with niching.
2/6/1718

Trust structure design using Bilevel andniching aspects• Formulate the truss problem asa bilevel optimization problem• A new bilevel PSO niching
method locates multiple
optimal solutions• Stable topologies can be foundin the upper level• The optimized sizes of themembers of these topologies
can be found in the lower level• Niching at the upper level• Standard optimizer is used at
the lower level to optimize abilevel truss problem
Md. Jakirul Islam, Xiaodong Li, and Kalyanmoy Deb. 2017. Multimodal Truss Structure Design Using Bilevel and Niching Based Evolutionary Algorithms. In
Proceedings of GECCO ’17, Berlin, Germany, July 15-19, 2017, DOI: h p://dx.doi.org/10.1145/3071178.3071251

2/6/1719

Trust structure design examples

Figure 8: Illustration of a two-tire, 39-member, 12-node
ground structure.

ed Evolutionary Algorithms
GECCO ’17, July 15-19, 2017, Berlin, Germany
Figure 6: Illustration of 25-member, 10-node ground struc120 in
120 in120 in120 in
ture.

31

22
24

37

25

7

19

12
30

21
23

27
6

11

39
29

28
32
8

26

120 in10

Weight=191.16 lb

22
22
21 Bilevel and Niching
21
Multimodal
Truss Structure
Design Using
Based Evolutionary Algorithms
GECC
23
24
37
20
19
26
25
37
14
5
6 5
6
7
8
13
10
10
9
9
3
3
4
4
20 klb920

20 klb 20 klb

(a)

(b)

Weight=192.80 lb

Weight=193.42 lb

7

1

35
15

33
11

9

1

13

3

2

3

36
16
14

8

4

4

34

18 6
10 12

120 in

38
5 17

39
27

5

20000 lb

20000 lb

9

34

33
13

22

21

28
17

2
5

20000 lb

Weight=191.18 lb

18

14

10

6

37

5

10

9

6

Figure 8: Illustration
ground structure.

3
4 July 15-19, 2017, Berlin,3 Germany
4
Multimodal Truss Structure Design Using Bilevel and Niching Based Evolutionary Algorithms
GECCO
’17,

Figure 6: Illustration of 25-member, 10-node ground structure.

(c)
(d)
z
Figure 8: Illustration of a two-tire,
39-member, 12-node
Weight=524.99 lb
Weight=524.99 lb
ground structure.
L=25 inFigure 9: Optimal trusses for 39-member, 12-node ground
1

2

1

3

6

3

6

4

4

5

5
7

9

11

5

4L

7

10

12
13

3

6

2

4

2

structure derived employing the proposed niching method.

7

3L

1

0

8

10

0
0
(Amin
) and upper (Amax) bounds of the member areas are set to2(b)
0.0 and 2.5 in , respectively
and a critical member
area of 0.05 in2
(a)
8

10
22

14

21

8

9

17

3L

18

9

Weight=524.99 lb
Weight=524.99 lb
is chosen.
Fig. 9 shows the four optimal/near-optimal designs obtained by
20
Figure 7: Four design solutions
obtainedby the proposed
4L
theniching
member areasof these trusses
Figure 9: Optimal trus
Figure 8:proposed
Illustrationof amethod.
two-tire,�e
39-member,
12-nodemethod from 25-member, 10-node ground structure.
8L
structure derived empl
arestructure.
listed in Table 4. It can be observed that the obtained trusses
ground8L
have almost the same weight values (191.16 lb, 191.18 lb, 192.80 lb,
Table 3: Member areas (in2 ) of the optimized trusses of 250
0
and 193.42 lb), but either their members’ connectivity i.e., topol(Amin) and upper (Amaxmember, 10-node ground structure.
2
0.0 and 2.5 in , respective(c)ogy, or members’ cross-sectional
areas i.e.,(d)sizes, are very di�erent
Figure 6: Illustration of 25-member, 10-node ground strucis chosen.
Md. Jakirul Islam, Xiaodong Li, and Kalyanmoy Deb. 2017. Multimodal
Truss
Structure
DesignUsing
BilevelandNiching
Based
Evolutionary
ture.
from
each
other
(see
Table
4).
�is
shows
that
for
the
39-member
Fig. 9 shows the four oFigure 7: Four design solutions obtained by the proposed
Proposed
the proposed
Algorithms. In Proceedings of GECCO ’17, Berlin, Germany, July 15-19,
2017,
DOI:from
h p://dx.doi.org/10.1145/3071178.3071251
2/6/1720 niching me
truss,
theproposedmethodcanprovidemultiple
topology
andsize
method25-member,
10-nodegroundstructure.
Mem. No. Fig. 7(a) Fig. 7(b) Fig. 7(c) Fig. 7(d) Deb [4] Li [18] Kaveh [10]are listed in Table 4. It casolutions simultaneously in a single
run.
2
have almost the same we
00.00000.0000
0.010
0.010
19

24

23

16

1

1

15

2

2

3

3

6

6

4

4

5

5

7

7

10

10

8

9

8

9

Table 3: Member areas (in ) of the optimized trusses of 25-

Continuum structural topology optimization

G.-C. Luh, C.-Y. Lin, Y.-S. Lin, “A binary particle swarm optimization for continuum structural topology optimization”,
Applied Soft Computing, Volume 11, Issue 2, March 2011, Pages 2833-2844, ISSN 1568-4946,
2/6/1721

Drug Molecule Design (I)• Search for molecular structures with specificpharmacological or biological activity that influence
the behavior of certain targeted cells• Objectives: Maximization of potency of drug &Minimization of side-effects• Aim: provide the medicinal chemist a set of diverse
molecular structures that can be promising candidates
for further research– Fit solutions may result in finding structures that fail inpractice– The chemist desires a set of promising structures rather
than only one single solution

J. W. Kruisselbrink, A. Aleman, M. T. M. Emmerich, A. P. Ijzerman, A. Bender, T. Baeck, and E. van der Horst, “Enhancing search spacediversity in multi-objective evolutionary drug molecule design using niching,” GECCO’09, 2009, pp. 217–224.

2/6/1722

Drug Molecule Design (II)• Dynamic Niche Sharing technique incorporated to MOEA

Without (left) and with (right) niching
J. W. Kruisselbrink, A. Aleman, M. T. M. Emmerich, A. P. Ijzerman, A. Bender, T. Baeck, and E. van der Horst, “Enhancing search spacediversity in multi-objective evolutionary drug molecule design using niching,” GECCO’09, 2009, pp. 217–224.

2/6/1723

HFKQLTXHWRVSDFH 7KH$Q LGHDOQPDQ\UHDOKH FRPSXHUHIRUHZH
QJ PHWKRGVLPHQWV DUHDWLRQV 

9h/(5¶6%(1&+0$5.

1LFKLQJ H[SHULPHQWV ZHUH DOVR FDUULHG RXW RQ DQ
HOHFWURPDJQHWLF EHQFKPDUN VLPLODU WR WKDW UHSRUWHG LQ >@
7KH PDJQHWL]HU JHRPHWU\ KDV EHHQ PRGLILHG WR GHSHQG RQ
WKUHH SDUDPHWHUV RQO\ 7KH SROH VKDSH FRQVLVWV RI D FLUFXODUDUFFHQWHUHGDWWKHSRLQWO of coordinates (  [ ) and joining
the point P of coordinates ( [  [ ) (see Fig. 2).

Electromagnetics Optimization
2XWHUVKLHOGP U 

QJ *$V RQ
UHODWLYH WR%

P U 

600(QG
&KL6TXDUH

[

)
)
 
 
 
 

HQVLW\QHG
WR
QV00
PRGLILHG
LRQLVDOORSWLPD
SWLPDODXVH
RI WKH
DQ EHHFHVVDU\WRPDLQWDLQ DOO VXUSDVVHG
ULWVKRXOGDV REWDLQHG Q 

GHDQGHYLRXVHQ WKH
J WKH

$

SROH

[ [
3 

&RLO

[
2 




>PP@


$PPð[  

CEGELY - UPRESA CNRS 5005 - Ecole Centrale de Lyon
BP 163 - 69131 Ecully Cedex - France.






AbstractIn this paper, we present a new approach for)LJ*HRPHWU\RIWKHPDJQHWL]HU
A
x-axisautomatic design of electrodes. The investigated method consists
than
We point out 16
that
the rangeshapeof thefrom
designvariablesused inby the previous methods.
inTableidentifying
an optimal
an those
optimalfoundequipotential
0.6 III shows
external
thismagnetizer
Anpoint
additional
constraint
LPSRVHVD
without
normalization(i.e. when using
fixed
constraints
resultingfrom aproblem.
system ofcharges.
The electricfield andboundarynon optimized
configuration
PLQLPXP
RI  PP
EHWZHHQ
WKH SRLQW
DQG
WKH
potentialarecomputed
using
the
point
chargesimulation
0.5 GLVWDQFH
relativeto 3(2))
anddeath penalty method no feasible solution
SRLQW
2
WR
SUHYHQWWKH
LQWHUFHSWLRQ
RI
WKH
SROH
ZLWK
WKH
y- axismethod. Niching genetic algorithms and constrained
in benchmark
20000 fitness function evaluations for all GAs.
PDWHULDOWREHPDJQHWL]HG
optimization
techniques are appliedwas
to thefoundelectrode
0.4
internal
In fact, 6 819 500 fitness function evaluations
were necessary
in order to find multiple optimal
profiles.
7$%/(,,,
boundary(6,*19$5,$%/(65$1*(6
simple'GA
0.3
to evaluateRTS
10 feasible solutions witharbitrarily
random search.
Index termsGenetic algorithms, niching, shape optimization,
8
Design variable
Minimum value
Maximum value
electrode
constrained
charge-5 mm techniques, electrodes,
25 mm
0.2 [ optimization, penalty
shapecompared.
simulation[method.
25 mm C. Penalty
45.9 methods
mm
Magnetic Flux Density (T)

RPELQLQJ D
HWHFWLRQ RI
DLQWDLQ ORZDWLRQV EXWREWDLQWHFKQLTXHVWHRYHU
SUHVHQWHG

Many niching techniques have been used toaddress real-world problems inElectromagnetics:• Restricted
Tournament Selection
Niching Genetic Algorithms for Optimization
in Electromagnetics
II. Shape Optimization of Electrodes
using the CSM• Deterministic
Crowding
B. Sareni, L. Krähenbühl, D.
• MullerSharing• Clearing

0DWHULDOWREHPDJQHWL]HGP U 





(a)

(b)

(c)

chargeschargescharges



0.1

[

25 mm

I. INTRODUCTIONTable

26.5 mm4
III shows statistics obtained for different nichingGAs
withexternal
normalization.
Exterior
penaltymethodIn [1], we have outlined the interest of Niching Genetic
40
50
60
70computed
80
90 w =0.1 (which corresponds to theA'worst
using
Algorithms
for optimizationin wasElectromagnetics.
Niching1
methods extend Genetic Algorithms(GAs)
promotingthe function in the feasible domain foundA-B path
(deg)
0
value
ofbytheobjective
formation of stable subpopulations
in random
the neighborhoodwithsearch)ofand w2=100.
0.0

non optimized shape
optimal shape)LJ([DPSOHVRIXQLIRUPLQGXFWLRQOHYHOVGHWHFWHGE\DUXQRI5HVWULFWHG
8420
local and global optima. In this paper, we present a process
7RXUQDPHQW
6HOHFWLRQ design
576  2SWLPDOVROXWLRQV DUHFRPSDUHGWKDW
for automaticof electrodes
using
the ZLWK
ChargeFig. 1. Electrode template
T
ABLE IIIREWDLQHGZLWKDVLPSOH*$DQGDQRQRSWLPL]HGFRQILJXUDWLRQ
Simulation Method (CSM) [2][3]Ccoupled
withOniching
OMPARISON
F THE Pand
ENALTY TECHNIQUES FOR DIFFERENT NICHING GAS

optimal shape

Fig. 3. Examples of profiles with the corresponding electric field
distribution
The system is considered to be symmetrical in relation toc Field

L. Krahenbuhl,
A. Nicolas,“Nichingisgenetic algorithms for optimization in electromagnetics. i. fundamentals,” IEEE Transactions on
constrained
optimization andtechniques.
Our approachon the B. Sareni,
Therefore,
0.09
computationof34,thedistances
betweenindividuals.
of we must
Besttake into accountradically
different
from
those
developed
elsewhere.
In effect, the x-axis and y-axis. Number
Magnetics,
vol.
no.
5,
pp.
2984–2987,
1998.
d to aOptimization
Penaltyfour Exploration
identical
chargeswithsymmetricalcoordinatesin
Nevertheless,thisdesign
drawbackis minorin relation
to theshape
optimalisgenerally
carriedoutbydirectly
optimalprofilessolution2
0.08"Nichingtechniquegenetic
algorithms
for optimizationin electromagnetics.
II. Shapenon
optimizationof(a)electrodes using theon the B. Sareni, L. Krahenbuhl and D. Muller,
optimized profile
schemeratethex-axisfor the computationof the electricadvantagesof thesebenefitof theThedetectionof relation toparametrizing
the methods.
shape ofThedevices[3][4].
proposed(Emax<0.06)(Emax)g GAs CSM," in IEEE Transactions on Magnetics, vol. 34, no.potential.
5,pp.
2988-2991,
1998.
0.07
We can express it at one point of coordinates x andoptimized profile (b)distinct
optimalsolutionsis particularlyinterestingshapemethodconsists
in identifying
an optimal
shape for
from
an
RTS
death
8.20%
11.50
0.0561
results
2/6/1724
optimization
problems andfor whichthe y as follows,
optimal equipotential
line inverse
resultingproblems
from a systemof point
optimized profile (c)0.06
RTS
exterior
19.26%
33.75 80.0561
ormedcharges. ofThe
exploresefficiency
uniquenessthestudy
solution
is notthefulfilled[11].of many niching
1
DC
death
2.97% V ( x, y) 2.50
0.0571
ulation0.05(1)
q ln rGAs when applied to the proposed electrode benchmark: inCamera Positioning in “Virtual” Worlds

Preuss, Burelli, Yannakakis. Diversified Virtual Camera Composition. In EvoApplications
2012, pp. 265-274. Springer, 2012
2/6/1725

Bðp,vp Þ ¼ fðu,vÞ A R : ( q A AðpÞ such that Tvp ðqÞ ¼ ðu,vÞg is thetransformation of A(p) under Tvp (see Fig. 1) and S(IR(A(p)),
Ic(B(p,vp)) is an image similarity measure between the restrictionof IR on A(p), IR(A(p)), and the restriction of IC on B(p,vp),
IC(B(p,vp)),
then
theproblemofestablishingpoint
correspondence between the two images can be formulated asfollows:
Find the points pi ¼(xi,yi)ADR and the transformation parameters vpi that optimize the objective function

following offspring placement operators: the deterministic
crowding (DC) technique and the restricted tournament selection(RTS) (see Section 2.3 for details). DC and RTS are used in amutually exclusive manner and may be combined with RM. If RM
is not applied, then selection takes place according to the roulette
wheel (RW) described in [41].
K. Delibasis et al. / Pattern Recognition 43 (2010) 4011–4027
4024
K. Delibasis
The proposed multimodal
GAs-based algorithm can bede- et al. / Pattern Recognition 43 (2010) 4011–4027
scribed in the following pseudocode.

Medical Informatics

f ðp,vp Þ & SðIR ðAðpÞÞ,Ic ðBðp,vp ÞÞÞ

ð1Þ

Table 6
Quantitative results of the performance of the multimodal GAs-based algorithm and the ICP algorithm in terms of (a) normalized mutual information and (b) root mean

' GAs-based Algorithm
Initializationsquaredistance, RMSD , between I and I for Set-III. The results for the proposed multimodal GAs-based algorithm have been averaged over ten independent algorithm

Automatic determination of point
correspondence between images
E

C

TR
R

executions.
J Apply the Cannyedge detector operator on IR to obtain the

2.2. The proposed algorithm

binary edge image
BWR
SET-III

Normalized Mutual Information

J Apply the distance transform on the BWR image to obtain
Multimodal GAs-based Algorithm

DT, such that DT(i,j) carries the position of the nearest edge
This work proposes a multimodal GAs-based algorithm thatpixel of the pixelPair-1(i,j) of the IR. 0.394
automatically determines the point correspondence between two
Pair-2
0.397
J Initialize a population
images by locating multiple optima of the objective functionof N0 individuals.
Pair-3
0.414
J Calculate the fitness
defined above. The proposed algorithm is initialized by ai.
Pair-4 fi of each individual
0.370
Pair-50.393
randomly generated population of individuals. Each individual i
While (stopping criterion
is not met)doPair-6of the population contains the position parameters (xi,yi) of aoperator of0.378
roulette wheel to select' J Apply the selection
Pair-70.396
point pi in the image IR as well as a transform parameter vector
parent p1.
Pair-80.437
Pair-90.370
J If RM is active then select parent p2 according to restricted
vpi as defined above. The fitness of the individual i,fi, is evaluated4020
Pair-10
0.382
K. Delibasis ettheal. / Pattern Recognition
43 (2010)
4011–4027
as the square 4024
of the cross correlation coefficient between
mating,else
selectp27Std.dev.
according tothe70.021
selection operator of
Mean
0.393
restrictions IR(A(pi)) and IC ðBðpi ,vpi ÞÞ of the two images, according
roulette wheel.

Niching techniques (RTS) successfully discovered
optimal solutions that are measured by thesimilarity between patches of the two images

RMSDE
ICP Algorithm
0.381
0.381
0.372
0.369
0.380
0.366
0.347
0.407
0.359
0.364
0.372 7 0.016

Multimodal GAs-based Algorithm

ICP Algorithm

FFD Method

1.60
2.43
1.51
1.13
2.00
1.18
1.73
2.63
1.73
1.27
1.90
1.33
0.44
2.58
0.57
0.57
1.48
0.69
0.79
1.68
0.84
0.82
1.54
0.91
1.11
2.24
1.10
K.0.43
Delibasis et al. / Pattern Recognition 431.09(2010) 4011–4027 0.53
0.997 0.459
1.9757 0.514
1.0397 0.403

SET-III

Pair-1Pair-2Pair-3Pair-4Pair-5Pair-6
Pair-7Pair-8Pair-9Pair-10
Mean 7Std.dev.

2w+1

Table 6
Quantitative results of the performance of the multimodal GAs-based algorithm and the ICP algorithm in terms of (a) normalized mutual information and (b) root meansquare distance, RMSDE, between IC and IRTR for Set-III. The results for the proposed multimodal GAs-based algorithm have been averaged over ten independent algorithm
2w+1
executions.

pNormalized Mutual Information

A (p)

Tvp

RMSDE

Multimodal GAs-based Algorithm

ICP Algorithm

Multimodal GAs-based Algorithm

ICP Algorithm

FFD Method

0.394
0.397
0.414
0.370
0.393
0.378
0.396
DR
0.437
0.370
0.382
0.393 70.021

0.381
0.381
0.372
0.369
0.380
0.366
0.347
0.407
0.359
0.364
0.372 7 0.016

1.60
1.13
1.73
1.27
0.44
0.57
0.79
Dc
0.82
1.11
0.43
0.997 0.459

2.43
2.00
2.63
1.90
2.58
1.48
1.68
1.54
2.24
1.09
1.9757 0.514

1.51
1.18
1.73
1.33
0.57
0.69
0.84
0.91
1.10
0.53
1.0397 0.403

B (p)Fig. 1. Schematic representation of the point correspondence problem formulation.

Fig. 9. Application of the proposed GAs-based algorithm to pairs of corresponding transverse CT slices, obtained at different time from the same patient, imaging the lung(first row) and the pelvis region (second row). On the left column, pairs of corresponding points are shown superimposed on I (‘o’ denotes a point from I and ‘ +’ denotes aK. Delibasis, P. A. Asvestas, and G. K. Matsopoulos, “Multimodal
genetic
algorithm
for automatic
point correspondence,”
Fig. 4. algorithms-based
Comparative results of the proposed
GAs-based algorithm(first row) the dual-bootstrap
ICP method (second row) and the FFD method (thirpoint from I ). Only point pairs with squared correlation coefficient greater than a threshold of 0.95 are shown. On the right column, the transformed edges from I are
pair of Set-Ia. On the left column, the transformed grid points using (8) are marked by ‘‘o’’, whereas the determined positions of the grid points
Pattern Recognition, vol. 43, no. 12, pp. 4011-4027, 2010superimposed on I . image
FFD) are marked by ‘‘ +’’. On the right column, the transformed edges of the original image are superimposed on the similarity transformed image.
C

C

R

R

C

2/6/1726

heavily on the size of the square patch, the value of w was set
proposed algorithm. As can be seen (Fig. 11a), for values of image
to 11 (thus producing a 23 ! 23 square patch) for all subsequent
similarity threshold in the range [0.90, 0.95], the optimal RMSDG
TR
wherealgorithm
to Set-III.
and toHðI13Þfordenotethe entropy
executionsfor SET-IThepairs, whereas
w wasH(Iset) equalallerror is achieved for transformations,values of w in thethe
range
between 9wasand appliedScheduling Problems• Project Management– Optimize productivity• Makespan, Due dates– Maximize revenue– Minimize delays• Job shop Scheduling• Pérez, E., Posada, M. & Lorenzana, A. Taking advantage of solving the resource
constrained multi-project scheduling problems using multi-modal genetic algorithms, Soft
Comput (2016) 20: 1879. doi:10.1007/s00500-015-1610-z• E. Prez, F. Herrera, and C. Hernndez, “Finding multiple solutions in job shop schedulingby niching genetic algorithms,” Journal of Intelligent Manufacturing, vol. 14, no. 3-4, pp.
323–339, 2003.
• E. Prez, M. Posada, and F. Herrera, “Analysis of new niching genetic algorithms forfinding multiple solutions in the job shop scheduling,” Journal of Intelligent Manufacturing,
vol. 23, no. 3, pp. 341–356, 2012.
Pictures from: http://www.ymc.ch/en/lego-resource-scheduling-wall

2/6/1727

Artificial examples

X. Li, A. Engelbrecht, and M. Epitropakis, “Benchmark functions for cec’2013 special session and competition on niching
methods for multimodal function optimization,” Technical Report, Evolutionary Computation and Machine Learning Group, RMIT
University, 2013.
2/6/1728

Multi-Modal Optimization

RESEARCH QUESTIONS

2/6/1729

Main Research Questions• In which situations are MMO methods actually
better than “usual” EC optimization algorithms?
– Problems (problem classes)– Performance measures– Properties, e.g. time/space complexity• What are the advantages/characteristics ofdifferent MMO methods, which one shall wechoose?
• What are the limits for further improvement?
• How can we rigorously define the field(Theoretical justifications/analyses)?
2/6/1730

Multi-Modal Optimization

CLASSIC NICHING METHODS

2/6/1731

Fitness sharing• A sharing function canbe used to degrade an
individual’s fitness based f(x)on the presence of otherneighbouring individuals• During selection, many
individuals in the sameneighbourhood would
degrade each other’s
fitness– Limiting the number ofindividuals occupying
the same nichex
An example to illustrate fitness sharing.

D. E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function optimization,” in Proc. of the Second International
Conference on Genetic Algorithms, J. Grefenstette, Ed., 1987, pp. 41–49.

2/6/1732

Crowding methods• Originally by De Jong (1975), and later modified by
Mahfoud (1995)• Crowding usually consists of two phases:– Pairing phase: pairing each offspring with a similar individualin the current population– Replacement phase: which of the two will remain in the
population?

• Deterministic Crowding selects the fittest individual ineach pair in the replacement phase• Probabilistic Crowding selects the surviving individualfor each pair based on a probabilistic formula that takes
fitness into accountS. W. Mahfoud. Niching Methods for Genetic Algorithms. PhD thesis, Department of General Engineering,
University of Illinois at Urbana-Champaign, Urbana, IL, 1995.
K. A. de Jong. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, Department ofComputer and Communication Sciences, University of Michigan, Ann Arbor, MI, 1975.
2/6/1733

Deterministic crowding

p1

p2

c1

c2

Each offspring tends tocompete for survival withits most similar parent.

2/6/1734

Clearing• Proposed by Petrowski (1996); inspired by the principle of sharingof limited resources within each subpopulation (or species).
• The clearing procedure only supplies the resources to the bestindividuals in each subpopulation• All individuals fall within r distance from the best k individuals(below shows k = 2) from the population are cleared. This process
is repeated until the whole population is considered.

r

A. Petrowski. A clearing procedure as a niching method for genetic algorithms. In Proceedings of Third IEEE International Conference on
Evolutionary Computation(ICEC’96), pages 798–803. Piscataway, NJ:IEEE Press, 1996.

2/6/1735

Restricted Tournament Selection• Proposed by Harik (1997)• A modification of standard tournament selection,
based on local competition• Two individuals x and y are picked, and crossover andmutation is performed in the standard way, creating
new individuals x’ and y’• Then w (i.e., window size) individuals are randomly
chosen from the population, and among these theclosest one to x’, namely x’’, competes with x’ for a spotin the new population
G. Harick. Finding multi-modal solutions using restricted tournament selection. In Proceedings of the Sixth
International Conference on Genetic Algorithms(ICGA-95), pages 24–31, 1997.
2/6/1736

Other methods• Clustering based
methods (Yin andGermay 1991)• Species conserving GA(SCGA) by Li et al. (2002)• Modified clearing bySingh and Deb (2006)• Also sequential niching
methods, and so on
G. Singh and K. Deb, “Comparisons of multi-modal optimization algorithms based on evolutionary algorithms,” in Proc. of
the Genetic and Evolutionary Computation Conference 2006 (GECCO’06), Washington, USA, 2006, pp. 1305 – 1312.
2/6/1737

Multi-Modal Optimization

NICHING WITH PSO AND DE

2/6/1738

PSO niching methods• In Particle Swarm Optimization (PSO), each particle has
its own memory remembering its best known positionso far, and share this information with other particles• At each iteration, each particle is propelled towards
the area defined by the stochastic average of its own
known best position and the swarm best position• The notion of memory associated with each particle isunique to PSO, and this property can be used to induce
niching behaviour• A swarm can be divided into two parts:– an explorer-swarm consisting of the current particles– a memory-swarm, comprising of only best known
positions of individual particles

X. Li, “Developing niching algorithms in particle swarm optimization,” in Handbook of Swarm Intelligence, ser. Adaptation,
Learning, and Optimization, B. Panigrahi, Y. Shi, and M.-H. Lim, Eds. Springer Berlin Heidelberg, 2011, vol. 8, pp. 67–88.
2/6/1739

Speciation-based PSO
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

f

s3

p

s2

s1

2rs

x
D. Parrott and X. Li, “Locating and tracking multiple dynamic optima by a particle swarm model using speciation,”
IEEE Trans. on Evol. Comput., vol. 10, no. 4, pp. 440–458, August 2006.
2/6/1740

Speciation-based PSO
Step 1: Generate an initial population with randomly generated particles;
Step 2: Evaluate all particle individuals in the population;
Step 3: Sort all particles in descending order of their fitness values (i.e., fromthe best-fit to least-fit ones);
Step 4: Determine the species seeds for the current population;
Step 5: Assign each species seed identified as the gBest to all individuals
identified in the same species;
Step 6: Adjusting particle positions according to the PSO velocity andposition update equation (1) and (2);
Step 7: Go back to step 2), unless termination condition is met.

2/6/1741

Ring topology based niching PSO• Given a reasonably large population uniformly distributed in the
search space, the ring topology based niching PSOs are able toform stable niches across different local neighbourhoods,
eventually locating multiple global/local optima• This method can operate as a niching algorithm by using
individual particles’ local memories to form a stable network
retaining the best positions found so far

X. Li, “Niching without niching parameters: Particle swarm optimization using a ring topology,” IEEE Trans. on Evol. Comput.,vol. 14, no. 1, pp. 150 – 169, February 2010.
2/6/1742

Ring topology based niching PSO• Results on Shubert 2D function (two snapshots
during a simulation run)

X. Li, “Niching without niching parameters: Particle swarm optimization using a ring topology,” IEEE Trans. on Evol. Comput.,vol. 14, no. 1, pp. 150 – 169, February 2010.
2/6/1743

Stretching and Deflation in PSO• Aims to compute all global minimizers, while avoiding
local minimizers, through PSO• Iteratively modifies the objective function by
deflection and stretching– Knowledge of previously detected optima are incorporated
in the new form
– “Mexican hat” effect: introduction of new local optima– Overcome such issues by using repulsion technique– Addition of new control parameters– Applications in non-linear dynamic systems (periodic
orbits) & game theory (Nash equilibria)
K. E. Parsopoulos, V. P. Plagianakos, G. D. Magoulas, and M. N. Vrahatis, “Objective function ”stretching” to alleviate convergence to local minima,”
Nonlinear Analysis, vol. 47, no. 5, pp. 3419–3424, 2001.
K. E. Parsopoulos and M. N. Vrahatis, “On the computation of all global minimizers through particle swarm optimization,” IEEE Trans. on Evol. Compu., vol.
8, no. 3, pp. 211–224, June 2004.

2/6/1744

Stretching and Deflation in PSO (II)PARSOPOULOS AND VRAHATIS: ON THE COMPUTATION OF ALL GLOBAL MINIMIZERS THROUGH PSO
PARSOPOULOS AND VRAHATIS: ON THE COMPUTATION OF ALL GLOBAL MINIMIZERS THROUGH PSO
217

MINIMIZERS THROUGH PSO

oint

oint

Fig. 5. Deflection transformation of the function defined in (9), at the point
215
, for
.

Fig. 13. Stretching transformations(dashed line) andFig.stage
13. Stretchingtransformations(dashedFig. 15. Firstof the stretchingtransformation (13)for the line)
Levy and, for MINIMIZERS(dash-dottedline) ofAND
the function
definedin (12),at the point OF ALL GLOBALPARSOPOULOS
VRAHATIS:
ON THECOMPUTATION
THROUGH
PSOline) of the function defined in (12), at the point
217(dash-dotted
no. 5 function.
,
, and
.
,
, and
.

Fig. 7.

Deflection transformation of the function defined in (12), at the point Fig. 6.
, for
.

, for

Deflection transformation of the function defined in (12), at the point, for.

B. Stretching Technique
A different recently proposed technique, developed to address the problem of local minima, is the stretching technique[26], [64], [67], [68]. This technique consists of a two-phasetransformation of the objective function. The first phase of thetransformation, stretches the objective function upwards, eliminating all minima with values higher than the value of the obtained minimizer. In the second stage of the transformation, thedetected minimum is turned to a maximum. All minima withlower values of the objective function remain unaltered by thetransformation.
Let
be an obtained minimizer of the objective function .
Then, stretching is defined as [26], [64], [67], [68]Fig. 7.
216

217

Deflection transformation of the function defined in (12), at the point
IEEE T, for.

Fig. 15. First stage
no. 5 function.

of the stretching transformation (13) for the Levy

Fig.
line)
and in (12),(dash-dotted
Fig.9.8. Stretching
Deflectiontransformationstransformation of the(dashedfunctiondefinedat the point, forline) of the function, for defined .in (9), at the point
,
, and
.

where , , and are arbitrary parameters. The
function is the well known three-valued sign function, defined as

The effect of the stretching transformation on the func,tion defined in (9) is illustrated in Fig. 9, for, and
10 . The parameter
controls the
upward stretching of the objective function, performed by, in (13). Due to this transformation, the local minima
with function values higher than the one found are eliminated.
in the aforementioned
The effect of increasing the value ofexample,isexhibited
in
Fig.
10,
for
. In practice,Fig. 16. Levy no. 5 function after the stretching transformation (14).
Stretchingtransformations(dashedFig.Fig.
14. 13.
Original
plot of the
Levy no. 5 function in therange line) and.
(13) Fig.
Fig. 15. First stageof the stretching transformation (13) for the Levy
16. values
Levy no.of
5 function
after 10the stretchingtransformation
(14).
high
[e.g.,
]
are
used
in
multidimensional
Fig.
14.
Original
plot
of
the
Levy
no.
5
function
in
the
range
.
, for
(dash-dotted line) of the function defined in (12), at the point
no. 5 function.
problems to ensure that the local minima with function
,
, and
.
2/6/1745 values
In conclusion, the stretching technique can be used in cases(14)
An applicationof the stretching transformation on a twohigher
thanthedetected
one,
will
be
eliminated.
In
conclusion,
thestretching
technique
can
be
used
in cases
applicationof theis stretchingtransformation
the global
minimizer
required since
it alleviates on a twodimensional (2-D) function, namely the Levy no. 5 function, where only An
Fig. 8.

Deflection transformation of the function defined in (12), at the point
dimensional (2-D) function, namely the Levy no. 5 function,
the local ones.

where only the global minimizer is required since it alleviates

Other recent niching PSO variants•

LIPS: Euclidean-distance-based niching PSO forms niches by using the nearest neighbors to each personal
best in the Fully Informed PSO (FIPS)–•

NichePSO, nbest PSO, and Multi-swarms
–
–
–

•

S. Bird and X. Li, “Adaptively choosing niching parameters in a PSO,” in GECCO 2006, 2006, pp. 3–10.

Vector-based PSO (VPSO) treats each particle as a vector and niche identification is done by carrying out
vector operations of the particles. A niche is determined by the radius value based on the distance
between the swarm best and the nearest particle with a negative dot product (i.e., moving in an opposite
direction)–•

A. P. Engelbrecht. R. Brits and F. van den Bergh, “A niching particle swarm optimizer,” SEAL 2002, pp. 692–696.
R. Brits, A. P. Engelbrecht, and F. van den Bergh, “Solving systems of unconstrained equations using particle swarm optimizers,”
Proc. of the IEEE Conf. on Systems, Man, Cybernetics, pp. 102–107, 2002.
T. Blackwell and J. Branke, “Multi-swarms, exclusion, and anti- convergence in dynamic environments,” Evolutionary
Computation, IEEE Transactions on, vol. 10, no. 4, pp. 459–472, 2006.

Adaptive Niching PSO (ANPSO) adaptively determines the niche radius by calculating population statistics
at each iteration–•

B. Y. Qu, P. N. Suganthan, and S. Das, “A distance-based locally informed particle swarm model for multimodal optimization,”
IEEE Transactions on Evolutionary Computation, vol. 17, no. 3, pp. 387– 402, June 2013.

I. L. Schoeman and A. P. Engelbrecht, “Using vector operations to identify niches for particle swarm optimization,” in Proc. of the2004 IEEE Conf. on Cybernetics and Intelligent Systems, 2004, pp. 361 – 366.

Recent Developments in PSO, please refer to:––

2/6/17

J. Barrera and C. A. C. Coello, “A review of particle swarm optimization methods used for multimodal optimization,” inInnovations in Swarm Intelligence, ser. Studies in Computational Intelligence, C. Lim, L. Jain, and S. Dehuri, Eds. Springer Berlin
Heidelberg, 2009, vol. 248, pp. 9–37.
X.Li,“Developing niching algorithms in particle swarm optimization,” in Handbook of Swarm Intelligence, ser. Adaptation,
Learning, and Optimization, B. Panigrahi, Y. Shi, and M.-H. Lim, Eds. Springer Berlin Heidelberg, 2011, vol. 8, pp. 67–88.

46

Niching in Differential Evolution• Differential Evolution (Storn & Price 1995)• DE belongs in the class of EAs• Population-based, few control parameters• Basic Operations:– Mutation, Crossover, Selection• DE in MMO:
– niching technics,– specialized search operators (mostly mutation str.)
2/6/1747

The
DE mutation
mutationstrategies
strategies
Theimpact
impactofofthe
thedynamics
dynamics ofof DE

Mining Differential Evolution’s dynamics
Observation:
Observation:
DEDE
mutation
theindividuals
individualsofofthe
themutationstrategies
strategiestend
tend toto distributedistribute thepopulationof thetheobjective
objectivefunction.
function.
populationininthe
thevicinity
vicinityofof thethe minima
minima of
Exploitative
gather allallthetheindividuals
individualstoto
Exploitativestrategies:
strategies: rapidly
rapidly gather
thebasin
basinofofattraction
attraction ofof aa single minimum,theminimum,
Explorativestrategies:
strategies: tend
tend to spread
Explorative
spread thetheindividuals
individuals
aroundmany
manyminima.
minima.
aroundCase study: Shekel’s Foxholes• Twenty four separable local minima• One global minimum• @ f(-32,32) = 0.998004
M.G. Epitropakis, D.K. Tasoulis, N.G. Pavlidis, V.P. Plagianakos, and M.N. Vrahatis,“Enhancing differential evolution utilizing proximity- based mutation operators,”, IEEE

2/6/17

Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 99-119, 2011.

48

DE dynamics
DE/best/1 population

DE/rand/1 population

DE/best/1 and DE/rand/1 population’s positions after 1 generation

2/6/1749

DE dynamics
DE/best/1 population

DE/rand/1 population

DE/best/1 and DE/rand/1 population’s positions after 5 generation

2/6/1750

DE dynamics
DE/best/1 population

DE/rand/1 population

DE/best/1 and DE/rand/1 population’s positions after 10 generation

2/6/1751

DE dynamics
DE/best/1 population

DE/rand/1 population

DE/best/1 and DE/rand/1 population’s positions after 20 generation

2/6/1752

DE’s cluster tendency• Cluster Tendency (H-measure, Hopkins test)– Determines the presence or absence of aclustering structure in a data set

B. Hopkins and J. G. Skellam, “A new method for determining the type of distribution of plant individuals,” Ann. Botany, vol. 18, no. 2, pp. 213–227, 1954.
M.G.Epitropakis, D.K.Tasoulis, N.G.Pavlidis, V.P.Plagianakos, and M. N. Vrahatis, “Enhancing differential evolution utilizing proximity- based mutation
operators,” Evolutionary Computation, IEEE Transactions on, vol. 15, no. 1, pp. 99–119, Feb 2011.

2/6/1753

Exploit the spatial characteristics of DE’s population structure

It takes advantage from the dynamics of the classic
DE/rand/1 and DE/rand/2 (tend to spread the individuals
around many optima)

Niching DE: DE/nrand family• Inspired by this observation, classic DE mutation operators
incorporates
spatial information
about the neighborhood
wereIt altered
to incorporate
spatial information
about theof eachpotential
solutionnearestneighbourconcept
Inducea nichingformation,
withoutany• Induce
the nichingeffect,without
usingincorporating
any additional
additional parameter.
parameter• Instead of using the base vector the usual way, its nearest
The
DE/nrandmutationstrategies
neighbouris always
chosenas thefamily
actual[Epitropakisbase vector et al.
2011]:
1

DE/nrand/1: vig+1 = xgNNi + F(xgr1

xgr2 ),

2

DE/nrand/2: vig+1 = xgNNi + F(xgr1

xgr2 ) + F(xgr3

xgr4 ),

xgNNi is the nearest neighbor of the current individual xgi .
Michael G. Epitropakis, Xiaodong Li, and Edmund K. Burke

Niching Differential Evolution with Dynamic Archive10

M. G. Epitropakis, V. P. Plagianakos, and M. N. Vrahatis, , “Finding multiple global optima exploiting differential evolution’s
niching capability,” in Differential Evolution (SDE), 2011 IEEE Symposium on, April 2011, pp. 1–8.
2/6/1754

DE/nrand family behavior

2/6/1755

Multi-Modal Optimization:
https://mikeagn.github.io/DeMatDEnrand/

DE/NRAND/1 DEMO

2/6/1756

Niching DE: dADE/nrand family• Similar search as DE/nrand family• Self-adaptive control parameters (JADE selfadaptation)• Utilize dynamic archive:– put only better solutions in– if near better contained, re-initialize individual– identification radius R adapted during run• Substantially improved performance• Less sensitive to the population size
• Top participant in CEC 2013/2015 competitions
M. G. Epitropakis, X. Li, and E. K. Burke, “A dynamic archive niching differential evolution algorithm for multimodal optimization,” in
Evolutionary Computation (CEC), 2013 IEEE Congress on, June 2013, pp. 79–86.

2/6/1757

Niching DE: dADE/nrand family
Crowding DE

DE/nrand/1

Crowding DE

DE/nrand/1

dADE/nrand/1

Function F12(5D)Function F7(3D)8200
Number of distinct global optima

180
160
140
120
100
80
60
40
20

7
6
5
4
3
2
1
0

0
500

1000

1500 2000 2500
Generations

3000

3500

Crowding DE

DE/nrand/1

0

4000

dADE/nrand/1

500

DE/nrand/1

Function F7(3D) (216 global optima)

1500
2000
2500
3000
3500
Generations
Crowding DE
dADE/nrand/1

4000

Function F7(2D) (36 global optima)

100

Population size

200

190

180

170

160

150

140

0
130

200

190

180

170

160

150

140

130

120

110

100

80

70

60

50

40

30

20

90

Population size

5
120

10

10

110

20

100

30

15

90

40

20

80

50

60

60

25

50

70

30

40

80

30

90

20

Number of distinct global optima

35

0

2/6/17

1000

70

0

Number of distinct global optima

Number of distinct global optima

dADE/nrand/158

Niching DE: Other recent variants•

DE with restricted neighborhood mutations (speciation, crowding, sharing): eachindividual is mutated by randomly selecting individuals within the m-th
neighborhood niche of its base vector–•

DE with probabilistic parent selection scheme based on fitness and proximity
information–•

S. Biswas, S. Kundu, and S. Das, “An improved parent-centric mutation with normalized neighborhoods for inducing
niching behavior in differential evolution,” IEEE Transactions on Cybernetics, vol. 44, no. 10, pp. 1726–1737, Oct 2014.

Ensemble of niching techniques–•

S. Biswas, S. Kundu, and S. Das, “Inducing niching behavior in differential evolution through local information sharing,”
Evolutionary Computation, IEEE Transactions on, vol. 19, no. 2, pp. 246–263, April 2015.

DE with parent centric mutation strategies combined with crowding–•

B. Y. Qu, P. N. Suganthan, and J. J. Liang, “Differential evolution with neighborhood mutation for multimodal
optimization,” Evolutionary Computation, IEEE Transactions on, vol. 16, no. 5, pp. 601–614, Oct 2012.

S. Hui and P. N. Suganthan, “Ensemble and arithmetic recombination- based speciation differential evolution for
multimodal optimization,” IEEE Transactions on Cybernetics, vol. 46, no. 1, pp. 64–74, Jan 2016

DE with index-based neighborhoods to induce the niching effect–

2/6/17M. G. Epitropakis, V. P. Plagianakos, and M. N. Vrahatis, “Multi- modal optimization using niching differential evolution
with index- based neighborhoods,” in Proceedings of 2012 IEEE Congress on Evolutionary Computation (CEC’12), June
2012, pp. 1–8.
59

Multi-Modal Optimization

SOME OTHER STATE-OF-THE-ARTNICHING METHODS
2/6/1760

Nearest-better Clustering (I)• The basic idea: Connect every solution to the nearest
one that is better (in terms of fitness), clustering is done
via cutting the longest lines• Assumption: Longest edges are connections between
optimaM. Preuss. "Niching the CMA-ES via nearest-better clustering." In Proceedings of the 12th annual conferencecompanion on Genetic and evolutionary computation (GECCO ’10). ACM, New York, NY, USA, pp. 1711-1718, 2010
2/6/1761

Nearest-better Clustering (II)• NBC works with clustered (left) and randomized(right) samples• It incorporates (&needs) heuristic rule to remove“the right” longest edges

M. Preuss. "Niching the CMA-ES via nearest-better clustering." In Proceedings of the 12th annual conferencecompanion on Genetic and evolutionary computation (GECCO ’10). ACM, New York, NY, USA, pp. 1711-1718, 2010
2/6/1762

NEA2: Niching Evolutionary Algorithm 2• NEA2: clustering + local optimization• NBC combined with CMA-ES produces a nichingalgorithm that won the top place in the CEC’2013
niching competition• However, it still needs to set a few niching parameters
M. Preuss. "Niching the CMA-ES via nearest-better clustering." In Proceedings of the 12th annual conferencecompanion on Genetic and evolutionary computation (GECCO ’10). ACM, New York, NY, USA, pp. 1711-1718, 2010
2/6/1763

Niching Migratory Multi-swarm
Optimiser (NMMSO)• Built on an analysis of top ranked algorithms in CEC’2013 nichingcompetition to exploit similar characteristics of the winnersüüü

self-adaption of search parameters
dynamic mode maintenanceexploitative local search• The basic idea:– uses concurrent swarms each having strong local search– each swarm fine-tunes its local mode estimates– swarms which have improved their mode/niche estimate are pairedwith their closest adjacent swarm for potential merging (preventing
duplication of labour)– New regions in which to search for modes are identified by splitting
away particles from existing (large) swarms

J. E. Fieldsend, "Running Up Those Hills: Multi-Modal Search with the Niching Migratory Multi-Swarm Optimiser," in IEEE
Congress on Evolutionary Computation, 2014, pp. 2593 - 2600.
2/6/1764

NMMSO #swarms maintained

1000

2000

30
20
10
0
0

1000

150

Iteration
F12# Swarms

15
10
5
0
0

# Swarms

F11

1000

Iteration
F16
400

200

0
0

2000

4000

Iteration

6000

400

200

2000

4000

Iteration

200

400
200
0
0

20

Iteration
F18
300
200
100
0
0

2

100
50
2000

4

200

100

5

Iteration
F19

200

x 10

Iteration

4
4
x 10

200

400
200

40

400

100

Iteration
F15

0
0

4000

2

150

F10

600

2000

100

10

0
0

4000

F14

0
0

4

Iteration# Swarms

150

0
0

4000

50

Iteration

Iteration

40

2000

0
0

1000

F9

0
0

1000 2000 3000

F13

60

0
0

2000

Iteration
F17

0
0

F8

Iteration

50

1000

500

F5

5

Iteration

600

2000

100

0
0

2000

# Swarms# Swarms

20

0
0

80

# Swarms

40

Iteration

60# Swarms

0040# Swarms

100

F7# Swarms

200

20

5

Iteration# Swarms

F6# Swarms# Swarms

50
300

0
0

100

Iteration

10

F4# Swarms

50

5# Swarms00200

Iteration

10

F3# Swarms

100

5# Swarms00# Swarms

5

F2# Swarms

10

10

F1
# Swarms# Swarms

10

2000

4000

Iteration
F20

30
20
10
0
0

2

4

Iteration

6
4

x 10

Fig. 2. Number of swarms maintained by each run on each problem, recorded at each iteration until all global optima have converged to within 10 5 , or
2/6/1765
the function evaluations allowed are exhausted. Swarms recorded at line 11 of Figure 1. Mean of runs plotted in red (when a run has terminated, the size of
its final population is used in the calculation of the mean swarm size until all runs complete).

NMMSO distribution of swarms
25

F6

25000

250000

10

10

10

10

10

5

5

5

5

5

0

0

0

0

0

−5

−5

−5

−5

−5

−10
−10

−5

0

5

10

−10
−10

−5

0

5

10

−10
−10

−5

0

5

10

−10
−10

−5

0

5

10

−10
−10

5

5

5

5

5

F11 0

0

0

0

0

−5
−5

0

5

−5
−5

0

5

−5
−5

0

5

−5
−5

0

5

−5
−5

5

5

5

5

5

F12 0

0

0

0

0

−5
−5

2/6/17

Function evaluations
2500

250

0

5

−5
−5

0

5

−5
−5

0

5

−5
−5

0

5

−5
−5

5

5

5

5

5

F13 0

0

0

0

0

−5
−5

0

5

−5
−5

0

5

−5
−5

0

5

−5
−5

0

5

−5
−5

−5

0

5

10

0

5

0

5

0

5

Fig. 3. Swarm gbests (marked with a ‘⌦’), and swarm particles (marked with a ‘·’) of NMMSO at different numbers of function evaluations for five of the66

RS-CMSA-ES: Covariance Matrix Self
Adaption ES with Repelling Subpopulations• RS-CMSA adapts and reformulates multiple existing
concepts from different methods• RS-CMSA can learn the relative size and possibly theshape of the basins, and properly handle the challengeof non-circular basins• No assumption on the distribution of global minima,
the shape or the size of the basins is required.
• No niche radius parameters and for all otherparameters, the default values are shown to be robust(given a rough estimate for the expected number ofminima)Multimodal Optimization by Covariance Matrix Self-Adaptation Evolution Strategy with Repelling Subpopulations, Ali Ahrari, Kalyanmoy
Deb and Mike Preuss, doi: 10.1162/EVCO_a_00182

2/6/1767

3.1 First descriptive experiment
In the first descriptive experiment, RS-CMSA is tested on the 2D Vincent function. It
has 36 minima, all global, which significantly vary in size and relative distance (Figure4a). Restarts are performed, but for this experiment, the population size is kept unchanged ( = 10, Ns0 = 50). Initialized subpopulations are depicted with black circles,
where the center and radius of each circle represent xmeani and dˆ0 meani , respectively.
The gray circles correspond to the archived points and their taboo regions (dˆm mean ),respectively. At this point of each restart, Ci = 9.752 I and meani = mean ; therefore, all of
the taboo regions are spherical and the difference in size of the taboo regions originates
merely from the difference in the normalized taboo distances (dˆm ). It is remarkable that
illustration of these regions is much harder for an arbitrary point during the restart,
since the shape, the size, and the number of taboo regions would be different for each
subpopulation.
Figure 4b depicts the generated subpopulations immediately after the initialization part in the zeroth restart. There is no archived point at this moment, and thecenters of the subpopulations are at least 3dˆ0 ū mean far from each other, in which ū isthe geometric average of the square root of the initial covariance matrix eigenvalues.

RS-CMSA-ES: Main Components (I)• Sub-populations to capture different niches• Archive with adaptive Taboo regions• Taboo regions are adaptively
re-sized and reshaped, differ
for different subpopulations.
• The size of the taboo region isadapted to the basin size.
• Taboo regions are thepreviously identified basins
and the center of fitter
subpopulations.
• Only critical taboo regions arechecked.

10

10

x2

x2

5

5

0
0

(a) Top view of the landscape

5

x1

0
10

0

(b) Restart #0: ū mean = 0.33
10

10

x2

x2

x2

5

5

5

0

5

x1

0
10

(d) Restart #2: ū mean = 0.35

0

5

x1

0
10

(e) Restart #3:: ū mean = 0.32

x110(c) Restart #1: ū mean = 0.39

10

0

5

0

5

x1

10

(f) Restart #4: ū mean = 0.18

Figure 4: Taboo regions around the archived points (gray circles) and the centers of the
subpopulations (black circles) at different restarts, immediately after initialization.

Multimodal Optimization by Covariance Matrix Self-Adaptation Evolution Strategy with Repelling Subpopulations, Ali Ahrari, Kalyanmoy
Deb and Mike Preuss, doi: 10.1162/EVCO_a_00182
20
Evolutionary Computation Volume x, Number x

2/6/1768

RS-CMSA-ES: Main Components (II)• Core algorithm: Adapted CMSA-ES with elitism(Beyer and Sendhoff, 2008)• A restart mechanism with dependent restarts• Hill-valley function (Ursem, 1999): checks
whether two solutions share the same basin.
• Semi-random Initialization: maximize the initial
distance between subpopulations and the archive• Very promising performance: Winner of the
GECCO 2017 competition on niching methods.
Multimodal Optimization by Covariance Matrix Self-Adaptation Evolution Strategy with Repelling Subpopulations, Ali Ahrari, Kalyanmoy
Deb and Mike Preuss, doi: 10.1162/EVCO_a_00182

2/6/1769

RLSIS: Restarted Local Search with
Improved Selection of Starting Points• Stratified sampling procedure for efficient
initialization• Nearest-better clustering to approximate
modes• Local search procedure to accurately locate
mode (Nelder-Mead or CMAES)• Restart procedure
S. Wessing, M. Preuss, and G. Rudolph. Assessing basin identification methods for locating multiple optima. In: Advances in Stochastic
and Deterministic Global Optimization. Springer, 2016.
Simon Wessing. Two-stage methods for multimodal optimization. PhD thesis, Technische Universität Dortmund, 2015.
Many thanks to Simon Wessing for providing us slides for RLSIS

2/6/1770

One-dimensional Problems

RLSIS: One-dimensional Problems

1. Stratified sample of 300
Procedure:points1.
sample of clustering
300 points of
2. Stratified
Nearest-better
2. Nearest-betterthe sample,clustering
to obtainof thesample,to localobtainoptima
approx. local
approx.
optima3. Nelder-Mead simplex
3. Nelder-Meadsearch forsearch for simplex
each selectedeach selected point, to increase
point, to increase precision
precision (initial step size 10≠4 )(initial step size 10−4)
budget¥ 1000≈ evalutions•Consumed
Consumedbudget1000
evaluations
2/6/17

Example71

RLSIS: Maximin Reconstruction
Maximin Reconstruction
Algorithm(MmR)(MmR)
Algorithm
I Basic• Basic
principle:
minimaldistance
principle:maximization
maximization of ofminimaldistance
I Complementwith
Complement
methods
for effects
edge effects
with correction
correction methods
for edge

I Torusæ periodicedge
correction (PEC)(PEC)– Torus→ periodicedge
correction
I Mirroring æ reflection edge correction (REC) (not used here)– Mirroring→ reflection edge correction (REC) (not used here)

I Optional: consider a set of existing points (green points in (c))• Optional:
consider a set of existing points (green points in(c))(a) p = 0.5
2/6/17(b) p = 2(c) +PEC, +REC, p = 2

S. Wessing, M. Preuss, and G. Rudolph. Assessing basin identification methods for locating multiple optima. In: Advancesin Stochastic and Deterministic Global Optimization. Springer, 2016.

Restarted Local Search with Improved Sampling72

RLSIS: Multi-dimensional
Problems
Multi-dimensional Problems
Restarted Local Search (RLS)• Restarted Local Search (RLS):
1. Determine a starting point
1. Determine a2. starting
point
Execute local
search (CMA-ES) with this starting p
3. Go
to 1. (CMA-ES) with this
2. Execute local
searchstarting point
3. Go to 1. (restart)
GlobalPhase

New: starting points and found optima are saved in
an archive and considered by MmR in following
iterations
2/6/17

Local
Phase

New: starting points and found optima are saved73in anMulti-Modal Optimization

CHALLENGES IN NICHING METHODS

2/6/1774

Challenges in Niching Methods• Searching Efficiency (local/global search)• Maintaining found solutions (archives,…)• Specifying niching parameters (No parameters!)– Attempting to find a single uniform niche radius– Dynamic niche radius, instead of fixed one– Avoid to specify/use niche parameters• Scalability (dimension, #optima)• Measuring performance– Benchmarks or Real-World applications
2/6/1775

Multi-Modal Optimization

BENCHMARK TEST FUNCTIONS FOR
MULTI-MODAL OPTIMIZATION
2/6/1776

CEC’2013 niching benchmark• A common platform for fair and easy evaluation andcomparisons of different niching algorithms• 20 benchmark multimodal functions with different
characteristics• 5 accuracy levels: ε  {10−1 ,10−2 ,10−3 ,10−4 ,10−5}• The benchmark suite and the performance measures
have been implemented in: C/C++, JAVA, MATLAB &Python (R to come soon)
X. Li, A. Engelbrecht, and M.G. Epitropakis, “Benchmark Functions for CEC’2013 Special
Session and Competition on Niching Methods for Multimodal Function Optimization”,
Technical Report, Evolutionary Computation and Machine Learning Group, RMIT University,
Australia, 2013.
2/6/1777

CEC 2013/2015/2016 competitions• IEEE CEC niching competitions at 2013,2015 and 2016, with the latest
results available at the following URL:
http://goanna.cs.rmit.edu.au/~xiaodong/cec13-niching/competition/
http://goanna.cs.rmit.edu.au/~xiaodong/cec15-niching/competition/
http://www.epitropakis.co.uk/cec16-niching/competition/
https://github.com/mikeagn/CEC2013

2/6/1778

20 test functions

X. Li, A. Engelbrecht, and M.G. Epitropakis, “Benchmark Functions for CEC’2013 Special Session and Competition on Niching
Methods for Multimodal Function Optimization”, Technical Report, Evolutionary Computation and Machine Learning Group, RMIT
University, Australia, 2013.

2/6/1779

20 test functions (graphs)

2/6/1780

Determining found global optima• First we need to specify a level of accuracy (typically 0 <ε ≤ 1)– a threshold value under which we would consider a global
optimum is found• Second, we assume that for each test function, thefollowing information is available:– The number of global optima– The fitness of the global optima (or peak height), which is
known or can be estimated– A niche radius value that can sufficiently distinguish two
closest global optima

X. Li, A. Engelbrecht, and M. Epitropakis, “Benchmark functions for cec’2013 special session and competition onniching methods for multimodal function optimization,” Technical Report, Evolutionary Computation and Machine
Learning Group, RMIT University, 2013.
2/6/1781

Determining found global optima
Initialization: Uniform random initialization within the
search space;• Termination of a run: Terminate when reaching MaxFEs.
• Number of runs: 50.
•

Note that ✏ and r are to be used only at the end of a run,or evaluations of the final solutions. Table I shows different
MaxFEs used for the 3 ranges of test functions.
TABLE IM AX FE S USED FOR 3 RANGES OF TEST FUNCTIONS .
Range of functions
F1 to F5 (1D or 2D)
F6 to F11 (2D)F6 to F12 (3D or higher)

MaxFEs
5.0E+04
2.0E+05
4.0E+05

For F8 (2D), we set k1 = 3 and k2 = 4, as shown in
Fig. 8. Table II shows an example of presenting PR and SR
alues of a typical niching algorithm. Note that in this example
he PR and SR values are calculated based on the results ofbaseline model, DE/nrand/1/bin algorithm (see details in aection below).
2/6/17TABLE IVPARAMETERS USED FOR PERFORMANCE MEASUREMENT.
Function
F1 (1D)F2 (1D)F3 (1D)F4 (2D)F5 (2D)F6 (2D)F7 (2D)F6 (3D)F7 (3D)F8 (2D)F9 (2D)F10 (2D)F11 (2D)F11 (3D)
F12 (3D)
F11 (5D)F12 (5D)
F11 (10D)F12 (10D)F12 (20D)

r
0.01
0.01
0.01
0.01
0.5
0.5
0.2
0.5
0.2
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01

Peak height
200.0
1.0
1.0
200.0
1.03163
186.7311.0
2709.0935
1.0
-2.0
0
0
0
0
0
0
0
0
0
0

No. global optima
2
5
1
4
2
18
36
81
216
12
6
8
6
6
8
6
8
6
8
8

TABLE VC ONVERGENCE SPEEDS OF THE DE/ NRAND /1/ BIN ALGORITHM ( WITH
ACCURACY LEVEL ✏ = 1.0E-04).
82
Function F1 (1D)F2 (1D)F3 (1D)F4 (2D)F5 (2DMean
22886.01552.01258.013610.03806.

Performance measures

2/6/1783

CEC 2013/2015 niching competition
top 4 entries•(NMMO) Niching Migratory Multi-Swarm Optimiser:– J. E. Fieldsend, "Running Up Those Hills: Multi-Modal Search with the Niching
Migratory Multi-Swarm Optimiser," in IEEE Congress on Evolutionary Computation,
2014, pp. 2593 – 2600.

•(NEA2) Niching the CMA-ES via Nearest-Better Clustering:– M. Preuss. "Niching the CMA-ES via nearest-better clustering." In Proceedings ofthe 12th annual conference companion on Genetic and evolutionary computation(GECCO ’10). ACM, New York, NY, USA, pp. 1711-1718, 2010.

•(LSEAGP) Localised Search Evolutionary Algorithm using a Gaussian Process:– J. E. Fieldsend, "Multi-Modal Optimisation using a Localised Surrogates Assisted
Evolutionary Algorithm," in UK Workshop on Computational Intelligence (UKCI2013), 2013, pp. 88-95.

•(dADE/nrand/1) A Dynamic Archive Niching Differential Evolution algorithm
for Multimodal Optimization:– M. G. Epitropakis, Li, X., and Burke, E. K., "A Dynamic Archive Niching Differential
Evolution Algorithm for Multimodal Optimization", IEEE Congress on Evolutionary
Computation, 2013. CEC 2013. Cancun, Mexico, pp. 79-86, 2013.

2/6/1784

Results

CEC 2013/2015 niching competitions
Results
Summary:
6 new search algorithms
4 comparators based on the competition @ CEC2013
20 multi-modal benchmark functions
5 accuracy levels e 2 {10 1 , 10 2 , 10 3 , 10 4 , 10 5 }Results: per accuracy level & over all accuracy levels
In total (CEC2013 & CEC2015) 21 algorithms in therepository: https://github.com/mikeagn/CEC2013

2/6/1785

Accuracy level 10-1
Accuracy level 1.0e−1

Accuracy level 1.0e−1
1.00

20

0.8

0.6

10
0.4

0.2

5

0.75

●

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1

0.50

LSEAEA●LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●
●

0.0

SO

2
M

M

EA
N

N

O
PS

EA
M

SS
M

P
AG

A

●

LS
E

AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

ng
D

AL

●

ro
w
di

N

M

●

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d

D

E/

ra
E/
n

dA

D

ro
w

2/6/17

LS
E

nd
/1

E
ng
D
di

AL
N

M

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

86

Accuracy level 10-2
Accuracy level 1.0e−2

Accuracy level 1.0e−2
1.00

20

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●
●

0.0

SO

2
M

M

EA
N

N

O
PS

EA

SS

M

P
AG

A

●

LS
E

AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

M

ng
D

N
AL

ro
w
di

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d
E/

D

LS
E

nd
/1
ra

dA

D

ro
w

E/
n

di

ng
D

E

M
AL
N

2/6/17

●

M

●

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

87

Accuracy level 10-3
Accuracy level 1.0e−3

Accuracy level 1.0e−3
1.00

●

20

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE●

dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●

0.0

●

SO

2
M

M

EA
N

N

O
PS

EA
M

SS
M

P
AG

A

●

LS
E

AE

LS
E

nr

an

1

d/
1

●

D
E/

E

an
d/

dA
D
E/

nr

ng
D

AL

ro
w
di

N

M

●

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d

D

E/

ra
E/
n

dA

D

ro
w

2/6/17

LS
E

nd
/1

E
ng
D
di

AL
N

M

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

88

Accuracy level 10-4
Accuracy level 1.0e−4

Accuracy level 1.0e−4
1.00

●

20

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●
●

SO

2
M

M

EA
N

N

O
PS

EA

SS

M

P
AG

A
AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

M

ng
D

N
AL

ro
w
di

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d
E/

D

LS
E

nd
/1
ra

dA

D

ro
w

E/
n

di

ng
D

E

M
AL
N

2/6/17

●
●

●

M

●
●

0.00

LS
E

0.0

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

89

Accuracy level 10-5
Accuracy level 1.0e−5

Accuracy level 1.0e−5
1.00

●
●
●

20

●
●

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

0.0
●

●

N

M

M

EA

2

SO

●

N

O
PS

EA
M

SS
M

P
AG

A

LS
E

AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

M

ng
D

N
AL

ro
w
di

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d

D

E/

ra
E/
n

dA

D

ro
w

2/6/17

LS
E

nd
/1

E
ng
D
di

AL
N

M

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

90

2/6/17
C
dA row AL
D di N
E n M
D /nr gD
E/ an En dLSran /1d
LS EA /1
EA EA
M MGP
SS E
PS A
N NE O
M A
M 2
SCdA row AL O
D di N
E n M
D /nr gD
E/ an En dLSran /1d
LS EA /1
EA EA
M MGP
SS E
PS A
N NE O
M A
M 2
S
C
r
dA ow AL O
D di N
E n M
D /nr gD
E/ an En dLSran /1d
LS EA /1
EA EA
M MGP
SS E
PS A
N NE O
M A
M 2
SCdA row AL O
D di N
E n M
D /nr gD
E/ an En dLSran /1d
LS EA /1
EA EA
M MGP
SS E
PS A
N NE O
M A
M 2
S
C
r
dA ow AL O
D di N
E n M
D /nr gD
E/ an En dLSran /1d
LS EA /1
EA EA
M MGP
SS E
PS A
N NE O
M A
M 2SO

Peak Ratio

Performance per benchmark

1.00

1.00

0.00

01: F_1(1D)

0.75

1.00

0.25

0.00

●

1.00

●

0.75

●
●

●
●
●

●
●
●

●

0.25

●

02: F_2(1D)●

06: F_6(2D)

0.75

0.50

●

●

11: F_9(2D)

0.00

16: F_11(5D)

●

0.50
●

●

●

03: F_3(1D)●

07: F_7(2D)●

12: F_10(2D)
●

0.75
●

●

●

17: F_12(5D)●●●

04: F_4(2D)●●●

08: F_6(3D)
●

●
●
●

13: F_11(2D)●●

18: F_11(10D)

●

●

●

●
●

●

●

●
●

05: F_5(2D)

●
●
●

0.50

0.25

0.00
●

09: F_7(3D)●

10: F_8(2D)

●
●
●
●

●
●
●
●

14: F_11(3D)●●●

19: F_12(10D)

15: F_12(3D)
●

●
●
●
●

0.50

0.25
●

●

●
●

●
●

●

20: F_12(20D)

●

●
●
●
●
●

●
●
●

91

Performance per algorithm
ALNM
1.00

CrowdingDE

dADE/nrand/1

DE/nrand/1●

LSEAEA

●

●

0.75

0.50

0.25

Peak Ratio

●
●

0.00

●

●

●
●
●

●

●

LSEAGP

1.00

●

MEA

●

MSSPSO
●
●

●

●

●

NEA2

NMMSO

●
●

●
●

0.75
●
●

0.50

●
●
●

●

0.25
●
●

0.00

●

●

●

−
10 1
^−
10 2
^−
10 3
^−
10 4
^−
5
10
^−
10 1
^−
10 2
^−
10 3
^−
10 4
^−
5
10
^−
10 1
^−
10 2
^−
10 3
^−
10 4
^−
5
10
^−
10 1
^−
10 2
^−
10 3
^−
10 4
^−
5
10
^−
10 1
^−
10 2
^−
10 3
^−
10 4
^−
5

●

10
^

2/6/17●

Accuracy Level

92

Results

Statistical Analysis
Statistical analysis

CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEALSEAGPMEA
MSSPSO
NEA2
NMMSO

ALNM
p/pb
–/=
–/–
–/=
+/+
–/–
–/–
–/–
+/+
+/+

CrowdingDE
p/pb
N/A
+/+
=/=
+/+
+/+
–/–
–/–
+/+
+/+

dADE/nrand/1
p/pb
N/A
N/A
–/–
=/=
=/=
–/–
–/–
+/+
+/+

DE/nrand/1
p/pb
N/A
N/A
N/A
+/+
+/+
–/–
–/–
+/+
+/+

LSEAEA
p/pb
N/A
N/A
N/A
N/A
=/=
–/–
–/–
–/=
+/+

LSEAGP
p/pb
N/A
N/A
N/A
N/A
N/A
–/–
–/–
+/=
+/+

MEA
p/pb
N/A
N/A
N/A
N/A
N/A
N/A
–/–
+/+
+/+

MSSPSO
p/pb
N/A
N/A
N/A
N/A
N/A
N/A
N/A
+/+
+/+

NEA2
p/pb
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
=/=

p: Wilcoxon rank-sum test
pb : Bonferroni correction+ row wins column,– row loses from column,= non-significant differences
N/A: Not Applicable
2/6/1793

Overall performance
All Accuracy levels
1.00

●
●
●
●

Peak Ratio in all benchmark functions

●

0.75

Algorithms
●

ALNM

●

CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGP●MEA
MSSPSO
NEA2
NMMSO

0.25

●
●
●
●
●

2

SO

●

N

M

M

EA
N

SS

PS

EA

O

●

M

P
AG

A

LS
E

AE

/1

LS
E

1

nr
an
d

D
E/

ra
nd
/

E/
n
D

di
n

dA

2/6/17

C
ro
w

AL

N

gD

E

M

0.00

●

M

●
●
●

94

Results

Overall Participants’performance (3) CEC2013+ CEC2015
performance
Algorithm

2/6/17NMMSONEA2LSEAEAdADE/nrand/1
LSEAGP
CMA-ES
N-VMO
ALNM
PNA-NSGAII
NEA1
DE/nrand/2
dADE/nrand/2
DE/nrand/1
DELS-aj
CrowdingDE
DELG
DECG
IPOP-CMA-ES
MEA
A-NSGAIIMSSPSO

Statistics
Median Mean
0.9885 0.8221
0.8513 0.7940
0.9030 0.7477
0.7488 0.7383
0.7900 0.7302
0.7550 0.7137
0.7140 0.6983
0.7920 0.6594
0.6660 0.6141
0.6496 0.6117
0.6667 0.6082
0.7150 0.6931
0.6396 0.5809
0.6667 0.5760
0.6667 0.5731
0.6667 0.5706
0.6567 0.5516
0.2600 0.3625
0.2075 0.3585
0.0740 0.3275
0.0000 0.2188

St.D.
0.25380.23320.32360.30100.32680.28070.33070.38970.3421
0.32800.31300.31740.33380.38570.3612
0.39250.39920.31170.38520.4044
0.3913

Friedman’s Test
Rank
Score
1
16.1900
2
16.1150
414.5050514.2450314.75506
14.0800
7
13.7600
9
12.4900
11
11.2700
14
10.5250
10
11.29508
12.8100
13
10.6150159.69501210.620016
9.4400178.9900185.8700195.2750204.7200213.735095

Discussion• The competitions gave a boost to the MMO
community• New competitive and very promising approaches• Key characteristics of the algorithms:– New methodologies: active learning, surrogates,
Gaussian Processes, probabilistic classifier forprediction, archives, hill-valley approaches– Usage of local models to maintain diversity andexploit locally the neighborhoods– Algorithms: EAs, DE, CMA-ES, Multi-swarms, andBootstrap-LV sampling.
2/6/1796

Other niching benchmark sets•

Earliest work on designing niching benchmark functions was carried out by Deb in
his master thesis!
– K. Deb, “Genetic algorithms in multimodal function optimization (master thesis and tcga
report no. 89002),” Tuscaloosa: University of Alabama, The Clearinghouse for Genetic
Algorithms, 1989.

•

Tunable cosine and quadratic function families– J. Ronkkonen, “Continuous Multimodal Global Optimization with Differential Evolution Based
Methods. Acta Universitatis Lappeenrantaensis 363, 2009.

•

Preuss/Lasarczyk generator: mixture of polynomials (MPM)– Preuss, Lasarczyk. On the importance of information speed in structured populations. In Proc.
PPSN VIII, pp. 91–100, 2004
– improved version (MPM2) in the dissertation of Simon Wessing: Two-stage Methods forMultimodal Optimization. TU Dortmund, 2015•

Gallagher/Yuan tunable generator: mixture of Gaussian distributions– Gallagher and B. Yuan. A general-purpose tunable landscape generator. IEEE Trans.
Evolutionary Computation, 10(5):590–603, 2006•

Simple and composition multimodal functions– Qu et al. B. Y. Qu, J. J. Liang, Z. Y. Wang, Q. Chen, and P. N. Suganthan, “Novel benchmark
functions for continuous multimodal optimization with comparative results,” Swarm andEvolutionary Computation, vol. 26, pp. 23–34, 2016.

2/6/1797

Performance Measuring• Two main components:– Subset solution selection– Performance measuring

M. Preuss, Multimodal Optimization by Means of Evolutionary Algorithms, ser. Natural
Computing Series. Springer International Publishing, 2016.
2/6/1798

A note on Performance Measures•••

Different advantages/disadvantages
Many connections with multi-objective metrics.
Mostly used currently in literature:• Peak Ratio (PR), (problematic)

Preuss, Wessing, Measuring Multimodal Optimization Solution Sets with a View to Multiobjective Techniques. In EVOLVE IV, pp. 123–137, 2013
M. Preuss, Multimodal Optimization by Means of Evolutionary Algorithms, ser. Natural Computing Series. Springer International Publishing, 2016.

2/6/1799

2/6/17100

GECCO 2016 Competition (I)Introduction

GECCO Competition (I)• Largely follows the procedures of the 2013/2015 CEC nichingcompetitions,new performance
criteria:
Largely followsadopt
the proceduresof the 2013/2015
CEC nichingcompetitions, adopt new performance criteria:
Improved Scenarios
Include information on the resources (time, function
evaluations) needed to find the global optima, not only thefraction of successes within a given time period (number of
evaluations), andTake into account the size of the final solution set, andreward small sets that mostly consist of the sought optima
only.

2/6/17

101
M. G. Epitropakis, M. Preuss, A. Engelbrecht and X. Li

GECCO 2016 Competition on Niching Methods

6Introduction

GECCO
Competition(II)
GECCO 2016 Competition (II)Three different Scenarios (performance evaluation):
Scenario I: Adopt the CEC2013/2015 competition ranking
procedure (based on average Peak Ratio), to facilitatestraight forward comparisons with all previous competition
entries.
Scenario II: Adopt the (static) F1 measure to take into
account the recall and precision of the final solution sets
Scenario III: Adopt the (dynamic) F1 measure integral
over the whole runtime to take into account thecomputational efficiency of the submitted algorithm
Ranking based on average values across all
problems/accuracy levels of the aforementioned measures areused to decide the winner.
2/6/17102

ParticipantsParticipantsParticipants

Submissions to the competition:(rlsis): Restarted Local Search with Improved Selection ofStarting Points, Simon Wessing(rs-cmsa-es): Benchmarking Covariance Matrix Self
Adaption Evolution Strategy with Repelling Subpopulations
for GECCO 2016 Competition on Multimodal Optimization,
Ali Ahrari, Kalyanmoy Deb and Mike Preuss(ascga): Adaptive species conserving genetic algorithm,
Jian-Ping Li, Felician Campean(nea2+): Niching the CMA-ES via Nearest-Better
Clustering: First Steps Towards an Improved Algorithm,
Mike Preuss(nmmso) Niching Migratory Multi-Swarm Optimiser, J.
Fieldsend
M. G. Epitropakis,
M. Preuss, A.CMA-ES,
Engelbrecht and
X. Li
GECCO 2016
Competition
on Niching Methods
Baselinealgorithms:
IPOP-CMA-ES,
NEA1,
NEA2

2/6/17

8

103

Results

Results
GECCO 2016 Competition Setup

Summary:
5 new search algorithms
4 classic algorithm comparators
20 multi-modal benchmark functions
5 accuracy levels e 2 {10 1 , 10 2 , 10 3 , 10 4 , 10 5 }Results: per accuracy level & over all accuracy levels
Latest version always in the repository:
https://github.com/mikeagn/CEC2013

2/6/17

104

Scenario I: Accuracy level 10-1
Accuracy level 1.0e−1

Accuracy level 1.0e−1
1.00

20

0.8

0.6

10
0.4

0.2

5

0.75

●

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1

0.50

LSEAEA●LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●
●

0.0

SO

2
M

M

EA
N

N

O
PS

EA
M

SS
M

P
AG

A

●

LS
E

AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

ng
D

AL

●

ro
w
di

N

M

●

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d

D

E/

ra
E/
n

dA

D

ro
w

2/6/17

LS
E

nd
/1

E
ng
D
di

AL
N

M

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

105

Scenario I: Accuracy level 10-2
Accuracy level 1.0e−2

Accuracy level 1.0e−2
1.00

20

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●
●

0.0

SO

2
M

M

EA
N

N

O
PS

EA

SS

M

P
AG

A

●

LS
E

AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

M

ng
D

N
AL

ro
w
di

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d
E/

D

LS
E

nd
/1
ra

dA

D

ro
w

E/
n

di

ng
D

E

M
AL
N

2/6/17

●

M

●

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

106

Scenario I: Accuracy level 10-3
Accuracy level 1.0e−3

Accuracy level 1.0e−3
1.00

●

20

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE●

dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●

0.0

●

SO

2
M

M

EA
N

N

O
PS

EA
M

SS
M

P
AG

A

●

LS
E

AE

LS
E

nr

an

1

d/
1

●

D
E/

E

an
d/

dA
D
E/

nr

ng
D

AL

ro
w
di

N

M

●

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d

D

E/

ra
E/
n

dA

D

ro
w

2/6/17

LS
E

nd
/1

E
ng
D
di

AL
N

M

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

107

Scenario I: Accuracy level 10-4
Accuracy level 1.0e−4

Accuracy level 1.0e−4
1.00

●

20

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

●
●

SO

2
M

M

EA
N

N

O
PS

EA

SS

M

P
AG

A
AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

M

ng
D

N
AL

ro
w
di

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d
E/

D

LS
E

nd
/1
ra

dA

D

ro
w

E/
n

di

ng
D

E

M
AL
N

2/6/17

●
●

●

M

●
●

0.00

LS
E

0.0

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

108

Scenario I: Accuracy level 10-5
Accuracy level 1.0e−5

Accuracy level 1.0e−5
1.00

●
●
●

20

●
●

0.8

0.6

10
0.4

0.2

5

0.75

Algorithms
ALNM
CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGPMEA
MSSPSO
NEA2
NMMSO

0.25

0.0
●

●

N

M

M

EA

2

SO

●

N

O
PS

EA
M

SS
M

P
AG

A

LS
E

AE

d/
1

LS
E

1

an
nr

D
E/

E

an
d/

dA
D
E/

nr

M

ng
D

N
AL

ro
w
di

C

SO
N

M

M

EA
2
N

O

EA

PS
M
SS

M

AG
P
LS
E

AE
A

/1
nr
an
d

D

E/

ra
E/
n

dA

D

ro
w

2/6/17

LS
E

nd
/1

E
ng
D
di

AL
N

M

0.00

C

Benchmark function

15

Peak Ratio in all benchmark functions

1.0

109

Scenario I: Overall performance
All Accuracy levels
1.00

●
●
●
●

Peak Ratio in all benchmark functions

●

0.75

Algorithms
●

ALNM

●

CrowdingDE
dADE/nrand/1
DE/nrand/1
LSEAEA

0.50

LSEAGP●MEA
MSSPSO
NEA2
NMMSO

0.25

●
●
●
●
●

2

SO

●

N

M

M

EA
N

SS

PS

EA

O

●

M

P
AG

A

LS
E

AE

/1

LS
E

1

nr
an
d

D
E/

ra
nd
/

E/
n
D

di
n

dA

2/6/17

C
ro
w

AL

N

gD

E

M

0.00

●

M

●
●
●

110

-1
Scenario II: Accuracy level 10

2/6/17

111

-2
Scenario II: Accuracy level 10

2/6/17112

-3
Scenario II: Accuracy level 10

2/6/17113

-4
Scenario II: Accuracy level 10

2/6/17114

-5
Scenario II: Accuracy level 10

2/6/17115

Scenario II: Overall performance

2/6/17

116

-1
Scenario III: Accuracy level 10

2/6/17

117

-2
Scenario III: Accuracy level 10

2/6/17118

-3
Scenario III: Accuracy level 10

2/6/17119

-4
Scenario III: Accuracy level 10

2/6/17120

-5Scenario III: Accuracy level 10

2/6/17121

Scenario III: Overall Performance

2/6/17122

Overall performance

GECCO 2016: Overall Performance

Alg.
ascga
nea2+
nmmso
rlsis
rs-cmsa

Sc.I
0.349
0.688
0.701
0.698
0.827

Rank
5
4
2
3
1

Sc.II
0.065
0.720
0.091
0.799
0.900

Rank
5
3
4
2
1

Sc.III
0.236
0.811
0.218
0.663
0.839

Rank
4
2
5
3
1

Mean Rank
4.666
3.000
3.666
2.666
1.000

Final Rank
5
3
4
2
1

Note: The algorithms have not been fine-tuned for the specific benchmark suite!

2/6/17123

GECCO 2016: Winners

2/6/17124

Discussion: GECCO 2016
• The competitions gave a boost to the MMO
community• New competitive and very promising approaches• Key characteristics of the algorithms:– New methodologies: repelling, restarts, clustering,surrogates, hill-valley approaches, post-processing– Usage of local models to maintain diversity andexploit locally the neighborhoods– Algorithms: CMA-ES, GAs, Evolutionary Algorithms,
and Multi-swarms
2/6/17125

2/6/17126

Multi-Modal Optimization

NICHING IN SPECIALIZED TASKS

2/6/17127

Niching In Specialized Tasks• Niching provides
more effective
problem solving ina diverse range oftasks• It also benefits fromits interaction withthese areas
2/6/17

128

Multi-Modal Optimization

NICHING IN DYNAMIC
OPTIMIZATION
2/6/17129

SPSO for tracking optima• In a dynamic environment the goal is to track as closely as possible thedynamically changing optima• A useful strategy to ensure good tracking of the global optimum is tomaintain multiple species at all the optima found so far, regardlesswhether they are globally or locally optimal• By maintaining individual species at each local optimum, it helps
tremendously in case when such a local optimum turns into a global
optimum

X. Li, J. Branke, and T. Blackwell, “Particle swarm with speciation and adaptation in a dynamic environment,”in Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO ’06. New
York, NY, USA: ACM, 2006, pp. 51–58.
2/6/17130

Niching in Dynamic Environments•

Vector-based PSO: utilize directional information provided by theparticles in a swarm to adaptively form niches in parallel to track multiple
dynamically changing optima–•rSPSO: simple regression method with Speciation-based PSO to speed up
local convergence and to estimate and predict the positions of thechanging optima––•

I. Schoeman and A. Engelbrecht, “Niching for dynamic environments using particle swarm optimization,” in
SEAL, 2006, vol. 4247, pp. 134–141.

S. Bird and X. Li, Computational Intelligence in Expensive Optimization Problems. Springer, 2010, Improving
Local Convergence in Particle Swarms by Fitness Approximation Using Regression, pp. 265–293.
S. Bird and X. Li, “Using regression to improve local convergence,” in Evolutionary Computation, 2007. CEC
2007. IEEE Congress on, Sept 2007, pp. 592–599.

Multi-population niching based algorithms––––

2/6/17

D. Parrott and X. Li, “Locating and tracking multiple dynamic optima by a particle swarm model using
speciation,” IEEE Trans. on Evol. Comput., vol. 10, no. 4, pp. 440–458, August 2006.
T. Blackwell and J. Branke, “Multi-swarms, exclusion, and anti- convergence in dynamic environments,”
Evolutionary Computation, IEEE Transactions on, vol. 10, no. 4, pp. 459–472, 2006.
X.Li, J.Branke, and T.Blackwell, “Particle swarm with speciation and adaptation in a dynamic environment,” inProceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, ser. GECCO ’06. New
York, NY, USA: ACM, 2006, pp. 51–58.
T. Blackwell, J. Branke, and X. Li, Swarm Intelligence: Introduction and Applications. Berlin, Heidelberg:
Springer Berlin Heidelberg, 2008, ch. Particle Swarms for Dynamic Optimization Problems, pp. 193–217.
131

Multi-Modal Optimization

NICHING IN MULTI-OBJECTIVE
OPTIMIZATION
2/6/17132

EMO solution diversity• Although diversity maintenance is a much common issue in any
population-based meta-heuristics, it is possible to use niching
methods for maintaining solution diversity– Early example is the Niched-Pareto GA (NGPA) (Horn, et al., 1994) ,which is a multi-objective GA using a variant of fitness sharing tomaintain Pareto solution diversity in the objective space– Another example is the crowding distance metric used in NSGA-II(Deb, et al., 2002)• Much attention has been given to maintaining solution
diversity in the objective space• However, little attention has been given to how to maintainsolution diversity in the decision space
J. Horn, N. Nafpliotis, and D. E. Goldberg, “A Niched Pareto Genetic Algorithm for Multiobjective Optimization,” in Proc. of
the First IEEE Conference on Evolutionary Computation, vol. 1. IEEE Service Center, 1994, pp. 82–87.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” Evolutionary
Computation, IEEE Transactions on, vol. 6, no. 2, pp. 182–197, Apr 2002.
2/6/17133

Diversity in both spaces• A MOEA (e.g., MOEA Niching-CMA) can produce a much more diverse
set of efficient solutions (i.e., solutions in the decision space), without
sacrificing objective space diversity (Shir, et. al. 2009)

Decision space

Objective space

An example where two solutions that are close in the objective space but theircorresponding points in the decision space are further apart
O. M. Shir, M. Preuss, B. Naujoks, and M. Emmerich, “Enhancing decision space diversity in evolutionary multiobjective
algorithms,” in Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization, ser. EMO’09. Berlin, Heidelberg: Springer- Verlag, 2009, pp. 95–109.
2/6/17134

Omni-Optimizer• Allows degeneration of NSGA-II into a single objective
multimodal optimization method (i.e., a niching method)• A variable space crowding distance metric is used toencourage distant solutions in the decision space toremain in the population• Distant solutions with similar or equal objective function
values will survive• Omni-Optimizer can degenerate to a niching method forsingle/multi-objective multi-modal optimization, capableof finding multiple Pareto-optimal fronts
K. Deb and S. Tiwari, “Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization.”
European Journal of Operational Research, vol. 185, no. 3, pp. 1062–1087, 2008.
2/6/17135

Multi-Modal Optimization

NICHING FOR CLUSTERING AND
MACHINE LEARNING
2/6/17136

Clustering• Aim: to group data points into clusters, such that– points in each cluster have a high degree of similarity– points in different clusters have a high degree of
dissimilarity– A similarity metric is often based on some distancemeasure between these data points• Both clustering and niching share some common
features:– data points seen as individuals– clusters as niches• Clustering methods can be used to do niching,and vice versa.
2/6/17137

Clustering examples

2/6/17

Figure from: http://scikit-learn.org

138

Clustering for Niching• Clustering methods (k-means, NBC, etc) can be used to
sub-divide the population into clusters (or niches)– Identification of species/niches– Species conserving, topological species conservation• Exploit each of the niches accordingly– CMA-ES (NEA2), GAs (SCGA, TSC), DE/PSO• Other characteristic examples include:– Clustering-based niching methods based on dynamic nichesharing, dynamic niche clustering, and dynamic fitness
sharing– Automatically estimate clustering parameters (such as k in
k-means)

X. Yin and N. Germay, “A fast genetic algorithm with sharing scheme using cluster analysis methods in multi-modal
function optimization,” in the International Conference on Artificial Neural Networks and Genetic Algorithms, 1993, pp.
450–457.
2/6/17139

Clustering for Niching (references)• X. Yin and N. Germay, “A fast genetic algorithm with sharing scheme using cluster analysis methods
in multi-modal function optimization,” in the International Conference on Artificial Neural Networks
and Genetic Algorithms, 1993, pp. 450–457.
• M. Preuss. "Niching the CMA-ES via nearest-better clustering." In Proceedings of the 12th annual
conference companion on Genetic and evolutionary computation (GECCO ’10). ACM, New York,NY, USA, pp. 1711-1718, 2010
• A. Della Cioppa, C. De Stefano, and A. Marcelli, “Where are the niches? dynamic fitness sharing,”
Evolutionary Computation, IEEE Transactions on, vol. 11, no. 4, pp. 453–465, Aug 2007.
• B. L. Miller and M. J. Shaw, “Genetic algorithms with dynamic niche sharing for multimodal function
optimization,” in Proceedings of the 1996 IEEE International Conference on Evolutionary
Computation, May 1996, pp. 786–791.
• J. Gan and K. Warwick, “Dynamic niche clustering: a fuzzy variable radius niching technique formultimodal optimisation in gas,” in Proc. of the 2001 Congress on Evolutionary Computation. IEEE
Press, 2001, pp. 215–222.
• J.-P. Li, M. E. Balazs, G. T. Parks, and P. J. Clarkson, “A species conserving genetic algorithm for
multimodal function optimization,” Evol. Comput., vol. 10, no. 3, pp. 207–234, 2002.
• C. Stoean, M. Preuss, R. Stoean, and D. Dumitrescu, “Multimodal optimization by means of a
topological species conservation algorithm,” Evolutionary Computation, IEEE Transactions on, vol.
14, no. 6, pp. 842–864, Dec 2010.
• D. K. Tasoulis, V. P. Plagianakos, and M. N. Vrahatis, “Clustering in evolutionary algorithms toefficiently compute simultaneously local and global minima,” in 2005 IEEE Congress on
Evolutionary Computation, vol. 2, Sept 2005, pp. 1847–1854 Vol. 2.
• V. P. Plagianakos, “Unsupervised clustering and multi-optima evolutionary search,” in 2014 IEEE
Congress on Evolutionary Computation (CEC), July 2014, pp. 2383–2390.
2/6/17140

Niching for clustering (I)• A clustering problem can be formulated as a multi-modal
optimization problem, and be handled by a niching method.
• We can define a density-based fitness function that would
reach a maximum at every good cluster center.
• The value of the fitness function will be high for points fallingwithin the boundary of a cluster, and low for points fallingoutside of the cluster.
• The results in Nasraoui, et al. (2005) suggested that theniching approach for clustering to be less prone than nonniching techniques to premature convergence, noise, andinitialization.
O. Nasraoui, E. Leon, and R. Krishnapuram, “Unsupervised niche clustering: Discovering an unknown number of clusters in noisy data
sets,” in Evolutionary Computation in Data Mining, ser. Studies in Fuzziness and Soft Computing, A. Ghosh and L. Jain, Eds. Springer
Berlin Heidelberg, 2005, vol. 163, pp. 157–188.

2/6/17141

Niching for clustering (II)Nasraoui, et al. (2005) proposed an
Unsupervised Niche Clustering
algorithm (UNC) and evaluated its
performance under different conditions
related to cluster size, density, noisecontamination, orientation, and numberof clusters. Their results were presented
on the 9 noisy data sets (see the figureon the right):(a) original data set;(b) results of UNC;(c) results of K-means with prespecified correct c (the number ofclusters);(d) results of PCM with pre-specified
correct c;O. Nasraoui, E. Leon, and R. Krishnapuram, “Unsupervised niche clustering: Discovering an unknown number of clusters in noisy data sets,” in
Evolutionary Computation in Data Mining, 2005, vol. 163, pp. 157–188.

2/6/17142

Feature Selection• The aim of feature selection is to choose featuresthat allow us to discriminate patterns belonging
to different classes• Feature selection algorithms are generallyclassified into
– wrapper methods make use of a learning classifier’s
performance to evaluate the suitability of the feature
subset– filter methods treat the selection of feature subsets
as a pre-processing step, independent from thelearning classifier.
2/6/17143

Niching for Feature Selection• Optimal subset of features might not be unique– Merit for obtaining all such optimal subsets before the final choice• Different optimal subsets of features are considered as different optima
on a multi-modal fitness landscape (searched by niching methods)• Example representation of a subset of the selected features: binary
string– 1 indicates that the i-th feature is included in the subset, otherwise (0) thefeature is excluded• Evaluate the goodness of a subset:– the binary string is fed into a learning classifier (e.g., neural network)• Fitness function takes into account:– the classifier accuracy term and– the penalty for selecting a large number of features

F. Brill, D. Brown, and W. N. Martin, “Fast generic selection of features for neural network classifiers,” Neural Networks,
IEEE Transactions on, vol. 3, no. 2, pp. 324–328, Mar 1992.
2/6/17
144

Niching for Machine Learning• Machine Learning (ML) plays an increasingly important rolein data analytics these days:– predict by learning from data

• Many real-world problems are often too large and complex
to be solved by a single machine learning model• An effective approach may be to employ an ensemble oflearning models, each specializing in solving a subtask of amuch larger problem.
• Meta-heuristic algorithms can be used to evolve a
population of ML models– e.g., an ensemble of neural networks, or a set of knowledge
rules.
Y. Liu and X. Yao, “Simultaneous training of negatively correlated neural networks in an ensemble,” IEEE Transactions on Systems, Man, andCybernetics, Part B (Cybernetics), vol. 29, no. 6, pp. 716–725, Dec 1999.
M. L. Wong and K. S. Leung, Data Mining Using Grammar-Based Genetic Programming and Applications. Norwell, MA, USA: Kluwer
Academic Publishers, 2000.

2/6/17145

Evolving neural network ensembles• Niching techniques (Speciation) used to evolve a diverse but accurate
set of specialist modules, which can be then combined to perform
learning tasks• Evolutionary Ensembles with Negative Correlation Learning (EENCL)[Liuet al. (2000)] automatically determine the number of individual
neural networks in an ensemble• Motivation: A population contains more information than a single
individual• Fitness sharing was adopted to promote diversity in the ensemble:– If one training example is learnt correctly by n individual neural networks,
then each of these n neural networks receives a fitness value 1/n, and theremaining neural networks in the ensemble receive zero fitness– This procedure is repeated for all examples in the training set– The final fitness of an individual is determined by summing up its fitness
values over all training examples

Y. Liu, X. Yao, and T. Higuchi, “Evolutionary ensembles with negative correlation learning,” IEEE Transactions on Evolutionary
Computation, vol. 4, no. 4, pp. 380–387, Nov 2000.

2/6/17146

Learning multiple rules from data
• In data mining: meta-heuristics can be used to extract knowledge suchas rules and use these rules to solve classification problems– the Michigan approach: where each individual encodes a single
rule, and– the Pittsburgh approach where each individual represents multiple
rules, i.e., a rule set.
• Since it is often difficult to capture the knowledge of a data set by asingle rule, multiple rules are often required• Niching methods can be used to evolve multiple different good
individuals that are required to produce a rule set:
– See for example, in the idea of “token competition” [Wong andLeung (2000)]
M. L. Wong and K. S. Leung, Data Mining Using Grammar-Based Genetic Programming and Applications. Norwell, MA, USA: Kluwer
Academic Publishers, 2000.
K. Tan, Q. Yu, C. Heng, and T. Lee, “Evolutionary computing for knowledge discovery in medical diagnosis,” Artificial Intelligence in Medicine,vol. 27, pp. 129–154, 2003.

2/6/17147

Multi-Modal Optimization

IEEE CIS TASK FORCE ON MULTIMODAL OPTIMIZATION
2/6/17148

IEEE CIS Taskforce on MMO

•

•
•
•

The key objective is to promote research on multi-modal optimization,
including its development, education and understanding of sub topic areas ofmulti-modal optimization. Further info: http://www.epitropakis.co.uk/ieeemmo/
Current chair: Michael G. Epitropakis (Lancaster University, UK).
Vice-Chairs: Andries Engelbrecht (University of Pretoria, South Africa), andXiaodong Li (RMIT University, Australia).
Members: Carlos A. Coello Coello, Kalyanmoy Deb, Andries Engelbrecht,
Michael G. Epitropakis, Jonathan Fieldsend, Jian-Ping Li, Xiaodong Li, Jonathan
Mwaura, Konstantinos Parsopoulos, Vassilis Plagianakos, Mike Preuss, Bruno
Sareni, Ofer M. Shir, Patrick Siarry, P. N. Suganthan, Michael N. Vrahatis, Simon
Wessing, Xin Yao.
2/6/17149

IEEE CIS Taskforce on MMO•

Past and planned activities:– IEEE CEC 2010, 2013, 2015, 2016 and 2017 special sessions and/or
competitions on “Niching Methods for Multimodal Optimization”.
– GECCO 2016, 2017 competitions on “Niching Methods for Multimodal
Optimization”.
– International Workshop on "Advances in Multimodal Optimization", PPSN
2014, PPSN 2016.
– Tutorials at WCCI 2016, PPSN 2014, CEC 2017.
– More activities to come soon…
• A repository for related material, publications and source code.
2/6/17150

Summary• Niching methods have been studied for the past few decades, andnow experience a revival, as more people from diverse backgrounds
find its relevance in their own disciplinary areas.
• Niching methods can be developed using other meta-heuristics, apartfrom evolutionary algorithms.
• Niching has its application in many problem solving domains, e.g.,
dynamic optimization and multi-objective optimization.
• A good starting point for new comers: several survey papers areavailable, plus recently a new book by Mike Preuss.
• Many open research questions and challenges to be addressed.
• Many possible real-world applications of niching methods.
S. Das, S. Maity, B.-Y. Qu, and P. Suganthan, “Real-parameter evolutionary multimodal optimization - a survey of the state-ofthe-art,” Swarm and Evolutionary Computation, vol. 1, pp. 71–88, June 2011.
O. Shir, “Niching in evolutionary algorithms,” Handbook of Natural Computing: Theory, Experiments, and Applications, pp.
1035–1069, 2012.
X. Li, “Developing niching algorithms in particle swarm optimization,” in Handbook of Swarm Intelligence, ser. Adaptation,
Learning, and Optimization, B. Panigrahi, Y. Shi, and M.-H. Lim, Eds. Springer Berlin Heidelberg, 2011, vol. 8, pp. 67–88.
M. Preuss, Multimodal Optimization by Means of Evolutionary Algorithms, ser. Natural Computing Series. Springer
International Publishing, 2016.
2/6/17151

New book on MMO!!!
• Describes state of the art inalgorithms, measures and test
problems• Approaches multimodal
optimization algorithms via
model-based simulation andstatistics• Valuable for practitioners withreal-world black-box problems

Natural Computing Series

Mike Preuss

Multimodal
Optimization
by Means of
Evolutionary
Algorithms

DOI:10.1007/978-3-319-07407-8
http://www.springer.com/gp/book/9783319074061
2/6/17152

Recent Survey on MMO @ IEEE TEVC
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TEVC.2016.2638437, IEEE
Transactions on Evolutionary Computation
JOURNAL OF LATEX CLASS FILES, VOL. 11, NO. 4, DECEMBER 2012

1

Seeking Multiple Solutions: An Updated Survey on
Niching Methods and Their Applications
Xiaodong Li, Michael G. Epitropakis, Kalyanmoy Deb, Andries Engelbrecht

Abstract—Multi-Modal Optimization (MMO) aiming to locate
multiple optimal (or near-optimal) solutions in a single simulation
run has practical relevance to problem solving across many fields.
Population-based meta-heuristics have been shown particularly
effective in solving MMO problems, if equipped with specificallydesigned diversity-preserving mechanisms, commonly known asniching methods. This paper provides an updated survey on niching methods. The paper first revisits the fundamental concepts
about niching and its most representative schemes, then reviews
the most recent development of niching methods, including novel
and hybrid methods, performance measures, and benchmarks
for their assessment. Furthermore, the paper surveys previous
attempts at leveraging the capabilities of niching to facilitate
various optimization tasks (e.g., multi-objective and dynamic
optimization) and machine learning tasks (e.g., clustering, feature
selection, and learning ensembles). A list of successful applications of niching methods to real-world problems is presented
to demonstrate the capabilities of niching methods in providing
solutions that are difficult for other optimization methods tooffer. The significant practical value of niching methods is clearly
exemplified through these applications. Finally, the paper poseschallenges and research questions on niching that are yet to beappropriately addressed. Providing answers to these questions is
crucial before we can bring more fruitful benefits of niching toreal-world problem solving.
Index Terms—Niching methods, Multi-modal optimization,
Meta-heuristics, Multi-solution methods, Evolutionary computation, Swarm intelligence.

I. I NTRODUCTIONHIS paper presents an updated survey on niching methods, which are Multi-Modal Optimization (MMO) methods aiming at locating multiple optimal solutions in a single
execution run. In many real-world situations, a decision makerprefers to have multiple optimal (or close to optimal) solutionsat hand before making a final decision. If one solution is notsuitable, an alternative solution can be adopted immediately. A
good practical example is the well-publicized Second Toyota

The goal of locating multiple optimal solutions in a single
run by niching methods contrasts sharply with the goal of aclassic optimization method [2], which usually starts from an
initial single point and iteratively improving it, before arriving
at one final solution. Since it is not guaranteed that startingat different initial points will arrive at different solutions withmultiple runs, classic optimization methods are not suited forthe purpose of locating multiple solutions. This goal is also
different from the usual single-optimum seeking mechanism
employed by a standard meta-heuristic method. In literature,sometimes “multi-modal optimization” also refers to seeking asingle optimum on a multi-modal fitness landscape. To avoid
this confusion and to be more precise, in this paper we also
refer to niching methods as “multi-solution” methods.
Classic niching methods, including fitness sharing [3] andcrowding methods [4], were developed in the early 70s and80s. In subsequent years, many niching methods have been
proposed. Some representative examples include deterministic
crowding [5], derating [6], restricted tournament selection[7], parallelization [8], clustering [9], stretching and deflation[10], [11], and speciation [12], [13]. Initially, niching methods
were developed for Evolutionary Algorithms (EAs). However, recently niching methods were also developed for othermeta-heuristic optimization algorithms [14], such as Evolution Strategies (ES), Particle Swarm Optimization (PSO), andDifferential Evolution (DE).
It is interesting to note that though several subareas of metaheuristics, such as evolutionary multi-objective optimization(EMO) and constrained optimization, have gained widespread
acceptance going even beyond the meta-heuristic researchcommunity, niching methods are perceived to have failed in
making a similar impact. Research on niching methods is seen
by many as a byproduct of research on population diversity
preservation, which is an important issue to deal with instandard meta-heuristic algorithms. It is a common perception

X. Li; M. Epitropakis; K. Deb; A. Engelbrecht, "Seeking Multiple Solutions: an Updated Survey on
TNiching Methods and Their Applications," in IEEE Transactions on Evolutionary Computation, doi:
10.1109/TEVC.2016.2638437
2/6/17153

Thank you!
Questions?
Closely follow
IEEE CIS Taskforce on MMO
activities!

References
•
•
•
•
•
•
•

Deb K, Gulati S. “Design of truss-structures for minimum weight using genetic algorithms,”
Finite Elements Anal Des 2001;37:447–65.
G.-C. Luh and C.-Y. Lin, “Optimal design of truss-structures using particle swarm optimization,”
Computers and Structures, vol. 89, no.23-24, pp. 2221 – 2232, Dec. 2011.
S. W. Mahfoud. Niching Methods for Genetic Algorithms. PhD thesis, Department of General
Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, 1995.
K. A. de Jong. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis,
Department of Computer and Communication Sciences, University of Michigan, Ann Arbor, MI,
1975.
G. Harick. Finding multi-modal solutions using restricted tournament selection. In Proceedingsof the Sixth International Conference on Genetic Algorithms(ICGA-95), pages 24–31, 1997.
A. Petrowski. A clearing procedure as a niching method for genetic algorithms. In Proceedingsof Third IEEE International Conference on Evolutionary Computation(ICEC’96), pages 798–803.
Piscataway, NJ:IEEE Press, 1996.
J.-P. Li, M. E.B., G. T.P., and C. P.J. A species conserving genetic algorithm for multi-modal
function optimization. In Evolutionary Computation, volume 10(3), pages 207–234, 2002.

2/6/17155

References
•
•
•
•
•
•
•
•
•

M. Epitropakis, D. Tasoulis, N. Pavlidis, V. Plagianakos, and M. Vrahatis, “Enhancing differential evolution
utilizing proximity-based mutation operators,” IEEE Trans on Evol. Comput., vol. 15, no. 1, pp. 99–119,
Feb 2011.
X. Li, “Niching without niching parameters: Particle swarm optimization using a ring topology,” IEEE
Trans. on Evol. Comput., vol. 14, no. 1, pp. 150 – 169, February 2010.
J. Horn, N. Nafpliotis, and D. E. Goldberg, “A Niched Pareto Genetic Algorithm for Multiobjective
Optimization,” in Proc. of the First IEEE Conference on Evolutionary Computation, IEEE World Congress
on Computational Intelligence, vol. 1. Piscataway, New Jersey: IEEE Service Center, 1994, pp. 82–87.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm:
Nsga-ii,” Evolutionary Computation, IEEE Transactions on, vol. 6, no. 2, pp. 182–197, Apr 2002.
X. Li, J. Branke, and T. Blackwell, “Particle swarm with speciation and adaptation in a dynamic
environment,” in Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation,
ser. GECCO ’06. New York, NY, USA: ACM, 2006, pp. 51–58.
D. Parrott and X. Li, “Locating and tracking multiple dynamic optima by a particle swarm model using
speciation,” IEEE Trans. on Evol. Comput., vol. 10, no. 4, pp. 440–458, August 2006.
G. Singh and K. Deb, “Comparisons of multi-modal optimization algorithms based on evolutionary
algorithms,” in Proc. of the Genetic and Evolutionary Computation Conference 2006 (GECCO’06),
Washington, USA, 2006, pp. 1305 – 1312.
D. E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function
optimization,” in Proc. of the Second International Conference on Genetic Algorithms, J. Grefenstette,
Ed., 1987, pp. 41–49.
X. Li, A. Engelbrecht, and M. Epitropakis, “Benchmark functions for cec’2013 special session andcompetition on niching methods for multimodal function optimization,” Technical Report, Evolutionary
Computation and Machine Learning Group, RMIT University, 2013.
2/6/17156

References••••

K. Deb and S. Tiwari, “Omni-optimizer: A generic evolutionary algorithm for single andmulti-objective optimization.” European Journal of Operational Research, vol. 185, no.
3, pp. 1062–1087, 2008.
X. Li, “Developing niching algorithms in particle swarm optimization,” in Handbook of
Swarm Intelligence, ser. Adaptation, Learning, and Optimization, B. Panigrahi, Y. Shi,and M.-H. Lim, Eds. Springer Berlin Heidelberg, 2011, vol. 8, pp. 67–88.
S. Das, S. Maity, B.-Y. Qu, and P. Suganthan, “Real-parameter evolutionary multimodal
optimization - a survey of the state-of-the-art,” Swarm and Evolutionary Computation,
vol. 1, pp. 71–88, June 2011.
O. Shir, “Niching in evolutionary algorithms,” Handbook of Natural Computing: Theory,
Experiments, and Applications, pp. 1035–1069, 2012.

2/6/17157