Evolutionary Multimodal Optimization: A Short Survey
Ka-Chun Wong (Department of Computer Science, University of Toronto)

arXiv:1508.00457v1 [] 3 Aug 2015

August 4, 2015

Real world problems always have different multiple solutions. For instance, optical engineers need to tune the recording parameters to get as many optimal solutions as possible
for multiple trials in the varied-line-spacing holographic grating design problem. Unfortunately, most traditional optimization techniques focus on solving for a single optimal
solution. They need to be applied several times; yet all solutions are not guaranteed to
be found. Thus the multimodal optimization problem was proposed. In that problem,
we are interested in not only a single optimal point, but also the others. With strong
parallel search capability, evolutionary algorithms are shown to be particularly effective
in solving this type of problem. In particular, the evolutionary algorithms for multimodal
optimization usually not only locate multiple optima in a single run, but also preserve their
population diversity throughout a run, resulting in their global optimization ability on multimodal functions. In addition, the techniques for multimodal optimization are borrowed
as diversity maintenance techniques to other problems. In this chapter, we describe and
review the state-of-the-arts evolutionary algorithms for multimodal optimization in terms
of methodology, benchmarking, and application.

1

Introduction and Background

Since genetic algorithm was proposed by John H. Holland [9] in the early 1970s, researchers
have been exploring the power of evolutionary algorithms [47]. For instance, biological pattern discovery [48] and computer vision [51]. In particular, its function optimization capability was highlighted [6] because of its high adaptability to different non-convex function
landscapes, to which we cannot apply traditional optimization techniques.
Real world problems always have different multiple solutions [45, 46]. For instance,
optical engineers need to tune the recording parameters to get as many optimal solutions
as possible for multiple trials in the varied-line-spacing holographic grating design problem
because the design constraints are too difficult to be expressed and solved in mathematical
forms [31]. Unfortunately, most traditional optimization techniques focus on solving for a
single optimal solution. They need to be applied several times; yet all solutions are not
guaranteed to be found. Thus the multimodal optimization problem was proposed. In that
1

problem, we are interested in not only a single optimal point, but also the others. Given
an objective function, an algorithm is expected to find all optimal points in a single run.
With strong parallel search capability, evolutionary algorithms are shown to be particularly
effective in solving this type of problem [6]: Given function f : X → R, we would like to
find all global and local maxima (or minima) of f in a single run. Although the objective
is clear, it is not easy to be satisfied in practice because some problems may have too
many optima to be located. Nonetheless, it is still of great interest to researchers how
these problems are going to be solved because the algorithms for multimodal optimization
usually not only locate multiple optima in a single run, but also preserve their population
diversity throughout a run, resulting in their global optimization ability on multimodal
functions. Moreover, the techniques for multimodal optimization are usually borrowed as
diversity maintenance techniques to other problems [42, 50].

2

Problem Definition

The multimodal optimization problem definition depends on the type of optimization (minimization or maximization). They are similar in principle and defined as follows:

2.1

Minimization

In this problem, given f :X → R, we would like to find all global and local minimums of f
in a single run.
Definition 1 Local Minimum [41]: A (local) minimum x̂l ∈ X of one (objective) function f :X → R is an input element with f (x̂l ) ≤ f (x) for all x neighboring x̂l . If X ∈ RN ,
we can write: ∀x̂l ∃ > 0 : f (x̂l ) ≤ f (x) ∀x ∈ X, |x − x̂l | < .
Definition 2 Global Minimum [41]: A global minimum xˆg ∈ X of one (objective) function
f :X → R is an input element with f (xˆg ) ≤ f (x) ∀x ∈ X.

2.2

Maximization

In this problem, given f :X → R, we would like to find all global and local maximums of f
in a single run.
Definition 3 Local Maximum [41]: A (local) maximum x̂l ∈ X of one (objective) function
f :X → R is an input element with f (x̂l ) ≥ f (x) for all x neighboring x̂l . If X ∈ RN , we
can write: ∀x̂l ∃ > 0 : f (x̂l ) ≥ f (x) ∀x ∈ X, |x − x̂l | < .
Definition 4 Global Maximum [41]: A global maximum xˆg ∈ X of one (objective) function
f :X → R is an input element with f (xˆg ) ≥ f (x) ∀x ∈ X.
2

3

Methodology

In the past literature, there are different evolutionary methods proposed for multimodal
optimization. In this section, we discuss and categorize them into different methodologies.

3.1

Preselection

In 1970, the doctorial thesis by Cavicchio introduced different methods for genetic algorithms [3]. In particular, the preselection scheme was proposed to maintain the population
diversity. In this scheme, the children compete with their parents for survival. If a child
has a fitness (measured by an objective function) higher than its parent, the parent is
replaced by the child in the next generation.

3.2

Crowding

In 1975, the work by De Jong [13] introduced the crowding technique to increase the chance
of locating multiple optima. In the crowding technique, each child is compared to a random sub-population of cf members in the existing parent population (cf means crowding
factor). The parent member which is most similar to the child itself is selected (measured
by a distance metric). If the child has a higher fitness than the parent member selected,
then it replaces the parent member in the population. Besides genetic algorithm, Thomsen
has also incorporated crowding techniques [13] into differential evolution (CrowdingDE) for
multimodal optimization [40]. In his study, the crowding factor is set to the population size
and Euclidean distance is adopted as the dissimilarity metric. The smaller the distance,
the more similar they are and vice versa. Although an intensive computation is accompanied, it can effectively transform differential evolution into an algorithm specialized for
multimodal optimization. In 2012, CrowdingDE has been investigated and extended by
Wong et al , demonstrating competitive performance even when it is compared to the other
state-of-the-arts methods [49].

3.3

Fitness Sharing

In 1989, Goldberg and Richardson proposed a fitness-sharing niching technique as a diversity preserving strategy to solve the multimodal optimization problem [7]. They proposed
a shared fitness function, instead of an absolute fitness function, to evaluate the fitness of
a individual in order to favor the growth of the individuals which are distinct from the
others. The shared fitness function is defined as follows:
f 0 (xi ) = Shared F itness =

Actual F itness
f (xi )
= PN
Degree of Sharing
j=1 sh(d(xi , xj ))

where f 0 (xi ) is the shared fitness of the ith individual xi ; f (xi ) is the actual fitness of the
ith individual xi ; d(xi , xj ) is the distance function between the two individuals xi and xj ;
3

sh(d) is the sharing function. With this technique, a population can be prevented from
the domination of a particular type of individuals. Nonetheless, a careful adjustment to
the sharing function sh(d) definition is needed because it relates the fitness domain f (xi )
to the distance domain d(xi , xj ) which are supposed to be independent of each other.

3.4

Species Conserving

Species conserving genetic algorithm (SCGA) [17] is a technique for evolving parallel subpopulations for multimodal optimization. Before each generation starts, the algorithm
selects a set of species seeds which can bypass the subsequent procedures and be saved into
the next generation. The algorithm then divides a population into several species based
on a dissimilarity measure. The fittest individual is selected as the species seed for each
species. After the identification of species seeds, the population undergoes the usual genetic
algorithm operations: selection, crossover, and mutation. As the operations may remove
the survival of less fit species, the saved species seeds are copied back to the population at
the end of each generation.
To determine the species seeds in a population, the algorithm first sorts the population
in a decreasing fitness order. Once sorted, it picks up the fittest individual as the first
species seed and forms a species region around it. The next fittest individual is tested
whether it is located in a species region. If not, it is selected as a species seed and another
species region is created around it. Otherwise, it is not selected. Similar operations are
applied to the remaining individuals, which are subsequently checked against all existing
species seeds.
To copy the species seeds back to the population after the genetic operations have been
executed, the algorithms need to scan all the individuals in the current population and
identify to which species they belong. Once it is identified, the algorithm replaces the
worst individual (lowest fitness) with the species seed in a species. If no individuals can
be found in a species for replacement, the algorithm replaces the worst and un-replaced
individual in the whole population. In short, the main idea is to preserve the population
diversity by preserving the fittest individual for each species.

3.5

Covariance Matrix Adaptation

Evolution strategy is an effective method for numerical optimization. In recent years, its
variant CMA-ES (Covariance Matrix Adaptation Evolution Strategy) showed a remarkable
success [8]. To extend its capability, niching techniques have been introduced to cope
with multimodal functions [35]. For instance, a concept called adaptive individual niche
radius has been proposed to solve the niche radius problem commonly found in speciation
algorithms [34].

4

3.6

Multiobjective Approach

At this point, we would like to note that the readers should not confuse evolutionary
multimodal optimization (main theme of this chapter) with evolutionary multiobjective optimization. The former aims at solving a single function for multiple opima, while
the latter aims at solving multiple functions for pareto front solutions. Nonetheless, the
techniques involved are related. In particular, Deb and Saha demonstrated that, by decomposing a single multimodal objective function problem into a bi-objective problem, they
can solve a multimodal function using a evolutionary multiobjective optimization algorithm
[4]. Briefly, they keep the original multimodal objective function as the first objective. On
the other hand, they use the gradient information to define peaks in the second objective.

3.7

Ensemble

As mentioned in the previous section, different niching algorithms have been proposed
over the past years. Each algorithm has its own characteristics and design philosophy
behind. Although it imposes difficult conditions to compare them thoroughly, it is a
double-edged sword. Such a vast amount of algorithms can provide us a “swiss army
knife” for optimizations on different problems. In particular, Yu and Suganthan proposed
an ensemble method to combine those algorithms and form a powerful method called
Ensemble of Niching Algorithms (ENA) [52]. An extension work can also be found in [32].

3.8

Others

Researchers have been exploring many different ways to deal with the problem. Those
methods include: clearing [29], repeated iterations [1], species-specific explosion [43], traps
[15], stochastic automation [25], honey bee foraging behavior [39], dynamic niching [27],
spatially-structured clearing [5], cooperative artificial immune network [21], particle swarm
optimization [10, 19, 14, 22] , and island model [2]. In particular, Stoean et al. have proposed a topological species conservation algorithm in which the proper topological separation into subpopulations has given it an advantage over the existing radius-based algorithms
[38]. Comparison studies were conducted by Singh et al. [36], Kronfeld et al. [16], and
Yu et al. [53]. Though different methods were proposed in the past, they are all based
on the same fundamental idea: it is to strike an optimal balance between convergence
and population diversity in order to locate multiple optima simultaneously in a single run
[37, 44].

5

4

Benchmarking

4.1

Benchmark Functions

There are many multimodal functions proposed for benchmarking in the past literature.
In particular, the following five benchmark functions are widely adopted in literature:
Deb’s 1st function [43], Himmelblau function [1], Six-hump Camel Back function [24],
Branin function [24], and Rosenbrock function [33]. In addition, five more benchmark
functions (PP1 to PP5) can be found in [43, 23]. For more viogorous comparisons, the IEEE
Congress on Evolutionary Computation (CEC) usually releases a test suite for multimodal
optimization every year. More than 15 test functions can be found there [20].

4.2

Performance Metrics

Several performance metrics have been proposed in the past literature [23, 18, 17, 40].
Among them, Peak Ratio (PR) and Average Minimum Distance to the Real Optima (D)
[23, 43] are commonly adopted as the performance metrics.
• A peak is considered found when there exists a individual which is within 0.1 Euclidean distance to the peak in the last population. Thus the Peak Ratio is calculated
using the equation (3):
P eak Ratio =

N umber of peaks f ound
T otal number of peaks

(3)

• The average minimum distance to the optima (D) is calculated using the equation
(4):
n
X
min d(peaki , indiv)
i=1

indiv∈pop

(4)
n
where n is the number of peaks, indiv denotes a individual, peaki is the ith peak, pop
denotes the last population, and d(peaki , indiv) denotes the distance between peaki
and indiv.
D=

As different algorithms perform different operations in one generation, it is unfair to set the
termination condition as the number of generations. Alternatively, it is also unfair to adopt
CPU time because it substantially depends on the implementation techniques for different
algorithms. For instance, the sorting techniques to find elitists and the programming languages used. In contrast, fitness function evaluation is always the performance bottleneck
[28] 1 . Thus the number of fitness function evaluations is suggested to be adopted as the
running or termination condition for convergence analysis.
1

For instance, over ten hours are needed to evaluate a calculation in computational fluid dynamics [11]

6

4.3

Statistical Tests

Since evolutionary multimodal optimization is stochastic in nature, multiple runs are
needed to evaluate each method on each test function. The means and standard deviations
of performance metrics are usually reported for fair comparison. To justify the results,
statistical tests are usually adopted to assess the statistical significances. For instance,
t-tests, Mann-Whitney U-tests (MWU), and Kolmogorov-Smirnov test (KS).

5

Application

Holographic gratings have been widely used in optical instruments for aberration corrections. In particular, Varied-Line-Spacing (VLS) holographic grating is distinguished by the
high order aberration eliminating capability in diffractive optical systems. It is commonly
used in high resolution spectrometers and monochromaters. A recording optical system of
VLS holographic grating is outlined in [31].

5.1

Problem Modelling

The core component descriptions of the optical systems are listed as follows [30]:
M1 , M2 : Two spherical mirrors
C, D
: Two coherent point sources
G
: A grating blank
In this system, there are two light point sources C and D. They emit light rays which are
then reflected by mirrors M1 and M2 respectively. After the reflection, the light rays are
projected onto the grating blank G. More details are given in [31, 26]. The objective for
the design is to find several sets of design variables (or recording parameters [31]) to form
the expected groove shape of G (or the distribution of groove density [30]). The design
variables are listed as follows:
γ :
ηC :
δ :
ηD :
pC :
qC :
pD :
qD :

The
The
The
The
The
The
The
The

incident angle of the ray O1 O
incident angle of the ray CO1
incident angle of the ray O2 O
incident angle of the ray DO2
distance between C and M1 (CO1 )
distance between M1 and G (O1 O)
distance between D and M2 (DO2 )
distance between M2 and G (O2 O)

7

Mathematically, the goal is to minimize the definite integral of the square
R w error between
the expected groove density and practical groove density [31]: min J = −w0 0 (np − ne )2 dw
where w0 is the half-width of the grating, np is the practical groove density, and ne is
the expected groove density. These two groove densities are complicated functions of the
design variables. Ling et al. have further derived the above formula into a simpler one [30]:
min J = r12 +

w02 (2r1 r3 + r22 ) w04 (r32 + 2r2 r4 ) w06 r42
+
+
3
5
7
j20
− n0 b2
λ0
j40
r4 =
− n0 b4
2λ0

j10
− n0 ,
λ0
3j30
r3 =
− n0 b3 ,
2λ0

r2 =

r1 =

where j10 , j20 , j30 and j40 are the functions of the design variables, which are n10 , n20 ,
n30 and n40 respectively in [26]. Theoretically, the above objective is simple and clear.
Unfortunately, there are many other auxiliary optical components in practice, which constraints are too difficult to be expressed and solved in mathematical forms. An optimal
solution is not necessarily a feasible and favorable solution. Optical engineers often need to
tune the design variables to find as many optimal solutions as possible for multiple trials.
Multimodal optimization becomes necessary for this design problem.

5.2

Performance measurements

As the objective function is an unknown landscape, the exact optima information is not
available. Thus the previous performance metrics cannot be adopted. We propose two
new performance metrics in this section. The first one is the best fitness, which is the
fitness value of the fittest individual in the last population. The second one is the number
of distinct peaks, where a distinct peak is considered found when there exists a individual
which fitness value is below a threshold 0.0001 and there isn’t any other individual found as
a peak before within 0.1 Euclidean distance in the last population. The threshold is chosen
to 0.0001 because the fitness values of the solutions found in [31] are around this order of
magnitude. On the other hand, the distance is chosen to 0.1 Euclidean distance because
it has already been set for considering peaks found in peak ratio [43, 23]. Nonetheless, it
is undeniable that such a threshold may not be suitable for this application because the
landscape is unknown, although the value of 0.1 is the best choice we can adopt in this
study.

5.3

Parameter setting

CrowdingDE-STL [49], CrowdingDE-TL [49], CrowdingDE-SL [49], Crowding Genetic Algorithm (CrowdingGA) [13], CrowdingDE [40], Fitness Sharing Genetic Algorithm (SharingGA) [7], SharingDE [40], Species Conserving Genetic Algorithm (SCGA) [17], SDE
8

Table 1: Results for all algorithms tested on the VLS holographic grating design problem
(50 runs)
Measurement
Mean of Best Fitness
StDev of Best Fitness
Mean of Peaks Found
StDev of Peaks Found
Measurement
Mean of Best Fitness
StDev of Best Fitness
Mean of Peaks Found
StDev of Peaks Found

CrowdingDE-STL [49]
8.29E-08
2.91E-07
41.42
13.07
SharingGA [7]
1.87E+04
6.82E+04
0.0
0.0

CrowdingDE-TL [49]
7.17E-07
5.01E-06
45.54
9.00
SharingDE [40]
1.74E+02
2.65E+02
0.0
0.0

CrowdingDE-SL [49]
1.18E-07
4.04E-07
43.38
10.69
SDE [18]
1.13E+00
1.56E+00
0.06
0.31

CrowdingGA [13]
9.02E-06
3.40E-05
8.94
5.04
SCGA [17]
1.24E+02
4.59E+02
0.02
0.14

CrowdingDE [40]
3.66E-06
2.31E-05
41.98
14.26
UN [12]
9.19E-04
3.15E-03
7.22
3.92

[18], and UN [12] are selected for illustrative purposes in this application. All the algorithms were run up to a maximum of 10000 fitness function evaluations. The above performance metrics were obtained by taking the average and standard deviation of 50 runs.
The groove density parameters followed the setting in [31]: n0 = 1.400 × 103 (line/mm),
b2 = 8.2453 × 10−4 (1/mm), b3 = 3.0015 × 10−7 (1/mm2 ) and b4 = 0.0000 × 10−10 (1/mm3 ).
The half-width w0 was 90mm. The radii of spherical mirrors M1 and M2 were 1000mm.
The recording wavelength (λ0 ) was 413.1nm. The population size of all the algorithms
was set to 50. The previous settings remained the same, except the algorithm-specific
parameters: The species distance of SDE and SCGA was set to 1000. The scaling factor
and niche radius of SharingDE and SharingGA were set to 1 and 1000 respectively. The
discount factor of the temporal locality was set to 0.5. The survival selection method of
the non-crowding algorithms was set to binary tournament [12].

5.4

Results

The result is tabulated in Table 1. It can be observed that CrowdingDE-STL can achieve
the best fitness whereas CrowdingDE-TL can acheive the best number of peaks found. To
compare the algorithms rigorously, statistical tests have also been used. The results are
depicted in Figure 1. One can observe that there are some statistically significant performance differences among them. In particular, CrowdingDE-based methods are shown to
have the results statistically different from CrowdingGA, SharingGA, SharingDE, SDE,
and SCGA. Some configurations obtained after a run of CrowdingDE-STL on this problem
are depicted in Figure 2. It can be seen that they are totally different and feasible configurations with which optical engineers can feel free to perform multiple trials after the single
run.

6

Discussion

To conclude, we have briefly reviewed the state-of-the-arts methods of evolutionary multimodal optimization from different perspectives in this chapter. Different evolutionary
9

multimodal optimization methodologies are described. To compare them fairly, we described different benchmarking techniques such as performance metrics, test functions,
and statistical tests. An application to Varied-Line-Spacing (VLS) holographic grating
is presented to demonstrate the real-wold applicability of evolutionary multimodal optimization. Nonetheless, we would like to note several current limitations of evolutionary
multimodal optimization as well as the possible solutions at the end of this chapter.
First, most of the past studies just focus on low dimensional test functions for benchmarking. More high dimensional test functions should be incorporated in the future. Second, we would like to point out that evolutionary multimodal optimization is actually
far from just finding multiple optima because the algorithms for multimodal optimization
usually not only locate multiple optima in a single run, but also preserve their population
diversity throughout a run, resulting in their global optimization ability on multimodal
functions. Moreover, the techniques for multimodal optimization are usually borrowed as
diversity maintenance techniques to other problems. Third, the computational complexities of the methods are usually very high comparing with the other methods since they
involve population diversity maintenance which implies that the related survival operators
need to take into account the other individuals, resulting in additional time complexity.

References
[1] David Beasley, David R. Bull, and Ralph R. Martin. A sequential niche technique for
multimodal function optimization. Evol. Comput., 1(2):101–125, 1993.
[2] Mourad Bessaou, Alain Pétrowski, and Patrick Siarry. Island model cooperating with
speciation for multimodal optimization. In PPSN VI: Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, pages 437–446, London,
UK, 2000. Springer-Verlag.
[3] Daniel Joseph Cavicchio. Adaptive search using simulated evolution. 1970.
[4] Kalyanmoy Deb and Amit Saha. Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach. In Proceedings of
the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO ’10,
pages 447–454, New York, NY, USA, 2010. ACM.
[5] G. Dick. Automatic identification of the niche radius using spatially-structured clearing methods. In 2010 IEEE Congress on Evolutionary Computation (CEC), pages 1
–8, july 2010.
[6] David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.

10

[7] David E. Goldberg and Jon Richardson. Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the Second International Conference
on Genetic algorithms and their application, pages 41–49, Hillsdale, NJ, USA, 1987.
L. Erlbaum Associates Inc.
[8] Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation
in evolution strategies. Evol. Comput., 9:159–195, June 2001.
[9] John H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge,
MA, USA, 1992.
[10] Zhen Ji, Huilian Liao, Yiwei Wang, and Q.H. Wu. A novel intelligent particle optimizer
for global optimization of multimodal functions. In CEC 2007. IEEE Congress on
Evolutionary Computation, 2007, pages 3272 –3275, sept. 2007.
[11] Yaochu Jin, M. Olhofer, and B. Sendhoff. A framework for evolutionary optimization
with approximate fitness functions. IEEE Transactions on Evolutionary Computation,
6(5):481–494, 2002.
[12] Kenneth A. De Jong. Evolutionary Computation. A Unified Approach. MIT Press,
Cambridge, MA, USA, 2006.
[13] Kenneth Alan De Jong. An analysis of the behavior of a class of genetic adaptive
systems. PhD thesis, University of Michigan, Ann Arbor, MI, USA, 1975.
[14] Yau-Tarng Juang, Shen-Lung Tung, and Hung-Chih Chiu. Adaptive fuzzy particle
swarm optimization for global optimization of multimodal functions. Information
Sciences, 181(20):4539 – 4549, 2011. Special Issue on Interpretable Fuzzy Systems.
[15] Naoya Karatsu, Yuichi Nagata, Isao Ono, and Shigenobu Kobayashi. Globally multimodal function optimization by real-coded genetic algorithms using traps. In 2010
IEEE Congress on Evolutionary Computation (CEC), pages 1–8, 2010.
[16] M. Kronfeld and A. Zell. Towards scalability in niching methods. In 2010 IEEE
Congress on Evolutionary Computation (CEC), pages 1 –8, july 2010.
[17] Jian Ping Li, Marton E. Balazs, Geoffrey T. Parks, and P. John Clarkson. A species
conserving genetic algorithm for multimodal function optimization. Evol. Comput.,
10(3):207–234, 2002.
[18] Xiaodong Li. Efficient differential evolution using speciation for multimodal function
optimization. In GECCO ’05: Proceedings of the 2005 conference on Genetic and
evolutionary computation, pages 873–880, New York, NY, USA, 2005. ACM.

11

[19] Xiaodong Li. Niching without niching parameters: Particle swarm optimization using
a ring topology. IEEE Transactions on Evolutionary Computation, 14(1):150 –169,
feb. 2010.
[20] Xiaodong Li, Ke Tang, Mohammad N. Omidvar, Zhenyu Yang, and Kai Qin. Benchmark functions for the cec 2013 special session and competition on large-scale global
optimization, 2013.
[21] Li Liu and Wenbo Xu. A cooperative artificial immune network with particle swarm
behavior for multimodal function optimization. In CEC 2008. (IEEE World Congress
on Computational Intelligence). IEEE Congress on Evolutionary Computation, 2008,
pages 1550 –1555, june 2008.
[22] Lili Liu, Shengxiang Yang, and Dingwei Wang. Force-imitated particle swarm optimization using the near-neighbor effect for locating multiple optima. Information
Sciences, In Press, Uncorrected Proof:–, 2010.
[23] Rodica I. Lung, Camelia Chira, and D. Dumitrescu. An agent-based collaborative
evolutionary model for multimodal optimization. In GECCO ’08: Proceedings of the
2008 GECCO conference companion on Genetic and evolutionary computation, pages
1969–1976, New York, NY, USA, 2008. ACM.
[24] Zbigniew Michalewicz. Genetic algorithms + data structures = evolution programs
(3rd ed.). Springer-Verlag, London, UK, 1996.
[25] K. Najim and A.S. Poznyak. Multimodal searching technique based on learning automata with continuous input and changing number of actions. IEEE Transactions
on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(4):666 –673, aug. 1996.
[26] Takeshi Namioka and Masato Koike. Aspheric wave-front recording optics for holographic gratings. Appl. Opt., 34(13):2180–2186, 1995.
[27] A. Nickabadi, M.M. Ebadzadeh, and R. Safabakhsh. Evaluating the performance of
dnpso in dynamic environments. pages 2640 –2645, oct. 2008.
[28] Yew S. Ong, Prasanth B. Nair, and Andrew J. Keane. Evolutionary optimization of
computationally expensive problems via surrogate modeling. AIAA Journal, 41(4):687
–696, 2003.
[29] A. Petrowski. A clearing procedure as a niching method for genetic algorithms. In
Proceedings of IEEE International Conference on Evolutionary Computation, 1996,
pages 798–803, Nagoya, Japan, May 1996.
[30] Ling Qing, Wu Gang, and Wang Qiuping. Restricted evolution based multimodal
function optimization in holographic grating design. In The 2005 IEEE Congress
12

on Evolutionary Computation, 2005, volume 1, pages 789–794, Edinburgh, Scotland,,
September 2005.
[31] Ling Qing, Wu Gang, Yang Zaiyue, and Wang Qiuping. Crowding clustering genetic
algorithm for multimodal function optimization. Appl. Soft Comput., 8(1):88–95, 2008.
[32] Bo-Yang Qu and P.N. Suganthan. Novel multimodal problems and differential evolution with ensemble of restricted tournament selection. In 2010 IEEE Congress on
Evolutionary Computation (CEC), pages 1 –7, july 2010.
[33] Yun-Wei Shang and Yu-Huang Qiu. A note on the extended rosenbrock function.
Evol. Comput., 14(1):119–126, 2006.
[34] Ofer Shir and Thomas Back. Niche radius adaptation in the cma-es niching algorithm.
In Thomas Runarsson, Hans-Georg Beyer, Edmund Burke, Juan Merelo-Guervos,
L. Whitley, and Xin Yao, editors, Parallel Problem Solving from Nature - PPSN IX,
volume 4193 of Lecture Notes in Computer Science, pages 142–151. Springer Berlin /
Heidelberg, 2006.
[35] Ofer M. Shir, Michael Emmerich, and Thomas Bäck. Adaptive niche radii and niche
shapes approaches for niching with the cma-es. Evol. Comput., 18:97–126, March
2010.
[36] Gulshan Singh and Dr. Kalyanmoy Deb. Comparison of multi-modal optimization
algorithms based on evolutionary algorithms. In GECCO ’06: Proceedings of the 8th
annual conference on Genetic and evolutionary computation, pages 1305–1312, New
York, NY, USA, 2006. ACM.
[37] M. Srinivas and L.M. Patnaik. Adaptive probabilities of crossover and mutation in
genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics, 24(4):656
–667, apr. 1994.
[38] C. Stoean, M. Preuss, R. Stoean, and D. Dumitrescu. Multimodal optimization by
means of a topological species conservation algorithm. IEEE Transactions on Evolutionary Computation, 14(6):842 –864, dec. 2010.
[39] K. Sundareswaran and V.T. Sreedevi. Development of novel optimization procedure
based on honey bee foraging behavior. pages 1220 –1225, oct. 2008.
[40] R. Thomsen. Multimodal optimization using crowding-based differential evolution.
In CEC2004. IEEE Congress on Evolutionary Computation, 2004, volume 2, pages
1382–1389, June 2004.
[41] Thomas Weise. Global Optimization Algorithms ? Theory and Application. Thomas
Weise, july 16, 2007 edition, July 2007. Online available at http://www.itweise.de/projects/book.pdf.
13

[42] Ka-Chun Wong, Tak-Ming Chan, Chengbin. Peng, Yue Li, and Zhaolei Zhang. DNA
motif elucidation using belief propagation. Nucleic Acids Res., 41(16):e153, Sep 2013.
[43] Ka-Chun Wong, Kwong-Sak Leung, and Man-Hon Wong. An evolutionary algorithm
with species-specific explosion for multimodal optimization. In GECCO ’09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages
923–930, New York, NY, USA, 2009. ACM.
[44] Ka-Chun Wong, Kwong-Sak Leung, and Man-Hon Wong. Effect of spatial locality
on an evolutionary algorithm for multimodal optimization. In EvoApplications 2010,
Part I, LNCS 6024. Springer-Verlag, 2010.
[45] Ka-Chun Wong, Kwong-Sak Leung, and Man Hon Wong. Protein structure prediction
on a lattice model via multimodal optimization techniques. In GECCO ’10: Proceedings of the 12th annual conference on Genetic and evolutionary computation, pages
155–162, New York, NY, USA, 2010. ACM.
[46] Ka-Chun Wong, Yue Li, Chengbin. Peng, and Zhaolei Zhang. SignalSpider: probabilistic pattern discovery on multiple normalized ChIP-Seq signal profiles. Bioinformatics,
Sep 2014.
[47] Ka-Chun Wong, Chengbin Peng, Yue Li, and Tak-Ming Chan. Herd clustering: A synergistic data clustering approach using collective intelligence. Applied Soft Computing,
23:61–75, 2014.
[48] Ka-Chun Wong, Chengbin Peng, Man-Hon Wong, and Kwong-Sak Leung. Generalizing and learning protein-dna binding sequence representations by an evolutionary
algorithm. Soft Computing - A Fusion of Foundations, Methodologies and Applications, 15:1631–1642, 2011. 10.1007/s00500-011-0692-5.
[49] Ka-Chun Wong, Chun-Ho Wu, Ricky KP Mok, Chengbin Peng, and Zhaolei Zhang.
Evolutionary multimodal optimization using the principle of locality. Information
Sciences, 194:138–170, 2012.
[50] Ka-Chun Wong and Zhaolei Zhang.
SNPdryad: predicting deleterious nonsynonymous human SNPs using only orthologous protein sequences. Bioinformatics,
Jan 2014.
[51] Chun-Ho Wu, Na Dong, Waihung Ip, Ching-Yuen Chan, Kei-Leung Yung, and
Zengqiang Chen. Chaotic hybrid algorithm and its application in circle detection.
In EvoWorkshops, pages 302–311, 2010.
[52] E. L. Yu and P. N. Suganthan. Ensemble of niching algorithms. Inf. Sci., 180:2815–
2833, August 2010.
14

[53] E. L. Yu and P.N. Suganthan. Empirical comparison of niching methods on hybrid
composition functions. In CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on Evolutionary Computation, 2008, pages 2194 –2201, june
2008.

15

(a) Best Fitness

(b) Best Fitness

(c) Peaks Found

(d) Peaks Found

Figure 1: For Table 1, we depict the statistical significance test results for the pairwise
performance differences between all algorithms tested on the VLS holgraphic grating design
problem by Mann-Whitney U-test (MWU) and Two-sample Kolmogorov-Smirnov test (KS)
with p=0.05. Each sub-figure correspond to the performance comparison using a metric
by a statistical test. The vertical axis is the same as the horizontal axis. Each algorithm is
represented by a number on each axis. The numbering of the algorithms follows the order
in Table 1. For instance, 1 refers to CrowdingDE-STL, 2 refers to CrowdingDE-TL......10
refers to UN. The color of each block represents whether the algorithm indicated by the
horizontal axis shows a performance different from the algorithm indicated by the vertical
axis in a statistically significant way. The black color denotes the p-values higher than
0.05 whereas the white color denotes the p-values lower than 0.05. The even numbered
sub-figures are the results obtained by MWU, whereas the odd numbered sub-figures are
the results obtained by KS.

16

(a)

(b)

Figure 2: Configurations obtained by a single run of CrowdingDE-STL on the VLS holographic grating design problem. It can be seen that they are totally different and feasible
configurations with which optical engineers can feel free to perform multiple trials after
the single run.

17

