Dynamic Island Model based on Spectral Clustering
in Genetic Algorithm
Qinxue Meng∗ , Jia Wu∗ , John Ellis† and Paul J. Kennedy∗
∗

arXiv:1801.01620v1 [cs.NE] 5 Jan 2018

Centre for Artificial Intelligence, Faculty of Engineering and Information Technology,
University of Technology Sydney, Sydney, Australia
† School of Life Sciences, Faculty of Science, University of Technology Sydney, Sydney, Australia
Email: {Qinxue.Meng, Jia.Wu, John.Ellis, Paul.Kennedy}@uts.edu.au

Abstract—How to maintain relative high diversity is important
to avoid premature convergence in population-based optimization
methods. Island model is widely considered as a major approach
to achieve this because of its flexibility and high efficiency.
The model maintains a group of sub-populations on different
islands and allows sub-populations to interact with each other
via predefined migration policies. However, current island model
has some drawbacks. One is that after a certain number of generations, different islands may retain quite similar, converged subpopulations thereby losing diversity and decreasing efficiency.
Another drawback is that determining the number of islands to
maintain is also very challenging. Meanwhile initializing many
sub-populations increases the randomness of island model. To
address these issues, we proposed a dynamic island model (DIMSP) which can force each island to maintain different subpopulations, control the number of islands dynamically and starts
with one sub-population. The proposed island model outperforms
the other three state-of-the-art island models in three baseline
optimization problems including job shop scheduler problem,
travelling salesmen problem and quadratic multiple knapsack
problem.

I. I NTRODUCTION
Optimization refers to finding best available solutions (Rk )
for a given problem (Q) in a possible solution space (Rn )
where n >> k within reasonable time. Effectively and efficiently optimizing a given problem is of much importance in
fine-tuning parameters in machine learning and searching for
potentially global solutions for NP-hard problems [1] which
cannot be solved within polynomial time.
Population-based evolutionary optimizations, initially inspired by biological process, are considered as a major
way of solving complex optimization problems. In the past
few decades, a number of population-based evolutionary algorithms are proposed such as simulated annealing (SA),
differential evolution (DE), Artificial Immune System(AIS)
[2, 3], particle swarm optimization (PSO), bee colony optimization (BCO), genetic algorithms (GAs), populationbased increamental learning (PBIL) and ant colony optimization (ACO) [4]. Among them, SA, DE, PSO and BCO are
roughly proposed to find solutions in continuous domains
mainly for function optimization while GA, PBIL and ACO
are mainly used for solving combinatorial optimization problems [5]. These methods optimize a given problem by maintaining a population of solutions from which the new solutions
are created by using different types of evolution operators.

For example, genetic algorithms create a new solution in
the population of current generation from the mutation of a
solution or a crossover of different parts of several solutions
from the population of the previous generation.
A primary concern of population-based evolutionary algorithms is how to balance exploration and exploitation during
the process of evolutionarily generating/searching new solutions [6]. Given a solution space, exploration mainly aims to
search and evaluate solutions in new regions while exploitation
mainly aims to search and evaluate neighbours of previously
evaluated solutions. A successful population-based evolutionary algorithm needs to establish a reasonable ratio between
exploration and exploitation because exploration mainly works
in the global area attempting to cover more regions and
exploitation mainly works in a local area attempting to find
best solutions in the local area. A good ratio of exploration
and exploitation shows that an identified solution is the best in
a sufficiently large area which means this solution approaches
the globally optimized solution. How to control the ratio of
exploration and exploitation is challenging because it is often
implicit in population-based evolutionary algorithms and hard
to control directly [5]. As a result, diversity [6–8] is proposed and widely accepted within the evolutionary algorithms
community as a measure for exploration and exploitation.
This is because exploration is emphasized if the diversity
of populations is high and exploitation is emphasized if the
diversity of populations is low.
A great number of methods are proposed to balance exploration and exploitation by maintaining population diversity.
The initial work of maintaining diversity is based on population control directly including maintaining a large population [9], reinitialize populations [10], randomly introducing
new individuals [11] or replacing old individuals with new
ones [12]. However, it is hard to maintain diversity by doing
operations on populations directly as in most cases, these
methods treat the evolutionary process as a black box so as
to be hard to guide the direction of evolution. Another way
of maintaining diversity is through genetic operators such as
selection, mutation, crossover, and other new proposed genetic
operators or combining them together [13, 14]. Through these
methods better control of the whole evolutionary process is
possible. The initial fixed and constant rate of genetic operators
are hard to determine their values in an adaptive way as

evolution proceeds [15]. These methods often come with
high computational complexity and may be trapped in local
dilemma. Currently, island model [16] is widely accepted as
one of the most successful ways of maintaining diversity. This
method is proposed to maintain sub-population in each island
and individuals from different islands may migrate from one
to the other. The benefits of island model are many. Firstly it
is flexible. Islands can have different strategies to maintain
diversity individually. Secondly, it is efficient. It supports
parallel computation and can be integrated with MapReduce
framework [17] because islands are evolved independently.
However, the major drawback of this method is that after a
certain number of generations, different islands may maintain quite similar, converged sub-populations. This, on one
hand, may contribute to the loss of diversity to some extent.
Additionally, maintaining islands with similar, converged subpopulations is a waste of computational resources. Further, it
is also challenging to determine how many islands should be
maintained.
To deal with these issues, we propose a novel dynamic
island model based on spectral clustering (DIM-SP). The main
principle of the proposed method is to introduce a new migration policy. Instead of having individuals migrate from one
island to the other, the proposed migration policy is to allow
all sub-populations to migrate together and then individuals
are assigned to different islands by spectral clustering. The
number of islands are determined by the number of clusters.
The contributions of the proposed DIM-SP model can be
summarized as
1) The involvement of clustering enables DIM-SP model to
explicitly maintain exploration among islands and focus
on exploitation in islands. This provides an intuitive way
for users to control the process of evolution;
2) the proposed DIM-SP island model can avoid having
islands maintain similar, converged sub-populations;
3) the number of islands is dynamic and can be controlled
by the number of clusters;
4) DIM-SP can allocate more survival space for diversities
with few individuals;
5) DIM-SP can be initialized with one population in one
island which simplifies the initialization of island model;
To evaluate the proposed DIM-SP island model, we compared the performance of this model with three other topological island models including fully-connected, star-shape
and ring island models on a set of benchmark optimization
problems.
II. L ITERATURE REVIEW
The initial motivation of island model (Fig. 1) in genetic
algorithm was derived from the considerations of natural
evolution and parallel computing [18]. In 1964, Wright [19]
proposed a basic island model which maintains one subpopulation in one island which is implemented in one cluster
so as to achieve parallel evolution. In this model, each cluster
carries out its own evolutionary algorithm, with frequent
interchange of information among them via migration of

individuals from one cluster to the others. The major success of
island-model is to prevent inbreeding effectively so as to main
relatively high diversity in the population [20]. Inbreeding,
referring to mating among similar individuals, cannot increase
diversity and ultimately the diversity of the population decreases due to selection. To avoid this, island model isolates
populations from each other leading them to explore different
portions of the search space which has frequently proven to
improve the results [21, 22]. Isolation among sub-populations
is the key behind the island model so as to maintain diversity
and this is determined by migration policies. Consequently,
migration policies have frequently been the subject of study.
The island model for parallel evolutionary algorithms were
later converted to work sequentially [20, 21, 23]. This removes
the constraints of island model from hardware which provides
flexible and dynamic control of island number.
Migration policies have included the number of migrant
individuals, the frequency of the migration, the policy for
selecting the individuals sent to other nodes and to be replaced by the received ones, the network topology or the
synchronous and asynchronous nature of the communications [24]. The early migration policies focused on exchange
strategies amongst sub-populations including migrants replacing less fit individuals, randomly chosen individuals or the
most similar individuals [25]. These studies are based on a
broad assumption that different islands can maintain different
sub-populations. Many novel variants and extensions of migration policy were proposed which consider many different
natural processes such as biological, physical and sociological
processes [26, 27]. However, as evolution proceeds, it is
often seen that different islands maintain quite similar subpopulations because as highly fit individuals migrate to subpopulations with relatively low fitness values, they are more
likely to survive and breed which leads the whole population
to converge to those new migrated individuals.
To deal with this issue, Ursem [28] proposed a multinational
genetic algorithm (MGA) where sub-populations are selfformed on a hill-valley detection algorithm. Specially, solution
space is considered as a landscape where sub-populations
are formed and can move on. The direction of movement is
determined by the best fitted individuals who are marked as
government. Individuals can move across sub-populations and
moving to near sub-populations gives high priority. MGA is
successful in maintaining multiple, different peaks simultaneously as similar sub-populations move together and merged.
However, there are still several weaknesses. The model is not
that efficient. The moving speed of sub-populations in a given
landscape is generally slow. If there are several similar peaks
in one local area, sub-populations are likely to be trapped and
move around these peaks. In addition, the movement direction
is determined by individuals with the highest fitness within
sub-populations. It is possible to see many sub-populations
move towards to the same peak therefore losing diversity. The
model was extended and improved by subsequent studies [29–
31] which proposed more complex migration policies to maintain diversity. This practice decreased the model’s efficiency

Fig. 1. An example of traditional island model. There are five islands from A
to E and each island maintains one sub-population. Individuals are allowed to
migrate from one island to the other according to a specific migration policy.

further.
Another important contribution of MGA is to consider the
distance between sub-populations and fitness landscape. Subsequently more complex island models were proposed [32, 33]
including ring model, centralized and compete graph models.
They consider the structure of islands as a network and
proposed migration policy based on island topology. However, complex policies make the control of exploration and
exploitation more difficult and implicit.
As a result, we propose a dynamic island model based on
spectral clustering (DIM-SP) aiming to improve efficiency of
island model, simplify migration policy and provide explicit
control of exploration and exploitation (Fig. 2). In this study,
the performance of the proposed DIM-SP island model is compared ot the other three topological island models including
fully-connected, star-shape and ring island models (Fig. 3) on
a set of benchmark optimization problems.
III. P RELIMINARIES
This section begins with a discussion of the problem definition followed by a description of basic island model so as
to emphasize the difference between traditional island model
and the proposed dynamic island model based on spectral
clustering (DIM-SP).
A. Optimization
For a given problem Q(f, S) where S is a search space
where elements represent potential solutions of the problem
and f is a single or combined fitness function to evaluate
the performance of individual element s∗ where s∗ ∈ S. The
purpose of optimization is to find one or a set of most fitted
elements s∗ .
B. Island model
Consider an island model Φ(P, O, M ), there are an overall
population P (P ⊂ S) which is partitioned into N subpopulations P1 , P2 , ..., PN and each sub-population is assigned to one island. The sub-populations in different islands

Fig. 2. An example of the proposed dynamic island model based on spectral
clustering (DIM-SP). Periodically sub-populations from old Island A to E
migrate together. Similar individuals are assigned to new Island F to H by
the results of spectral clustering and old islands are destroyed. The number
of new islands are determined by the number of clusters.

are evolved independently with the same/different evolving
operators, marked by O. Sub-populations interact based on
static/dynamic migration policy M .
C. Evolutionary process
The principle of island model is to create isolated subpopulations so as to maintain high diversity. A migration policy is applied to allow sub-populations to interact with others
for finding potential global solutions from local solutions.
The evolutionary process of island model can be described
in Algorithm 1. For every generation, each sub-population,
e.g. Pi evolves and is evaluated independently. The migration
policy then checks whether elements in this sub-population
Algorithm 1 Evolution process of basic island model
Initialization:
Set an optimization problem Q(f, S);
Set num island = n;
Set P = {P1 , P2 , . . . , Pn };
Set O = {O1 , O2 , . . . , On };
Set migration policy M ;
Iteration:
1: for i = 1 to n do
2:
Pi = Oi (Pi );
3:
for s ∈ Pi do
4:
vs = f (s);
5:
for k = 1 to n do
6:
if M (s, vs , Pi , Pj ) == 1 then
7:
Pj = Pj ∩ s;
8:
Pi = Pi \ s;
9:
end if
10:
end for
11:
end for
12: end for
13: s∗ = s∗ ∩ best(Pi );

(a) Fully-connected island model

(b) Start-shaped island model

(c) Ring island model

Fig. 3. Examples of the baseline, topological island models. (a) is a fully-connected island model where individuals can migrate from one island to the others;
(b) is a star-shaped island model where there is a main island connecting all the other islands and individuals can migrate to the other islands via the main
island; (c) is a ring island model where individuals can only migrate to islands next to them.

needs to migrate and which population to go to. At the end
of each generation, the elements of best fit will be kept in
s∗ . The algorithm behind the basic island model shows that
migration policy adds to the complexity of the computation
which inspires us to propose a more efficient one.
IV. M ETHODOLOGY OF DIM-SP
In contrast to the traditional island models that involve
complex migration policies, the proposed island model simplifies it by introducing a centralization-clustering framework.
This practice can sufficiently reduce the computational cost of
island model. Meanwhile it can also provide simple, explicit
control of exploration and exploitation so as to maintain diversity easily. The whole evolutionary process of the proposed
dynamic island model based on spectral clustering (DIM-SP)
is illustrated in Fig. 4.
The proposed island model starts with one island instead
of many which relieves the workload of initializing multiple
islands in traditional island models. In DIM-SP model, Island
0 is initialized in Generation 0.
When the proposed model runs to a specific generation,
say i, the Island 0 is split into a set of new islands, labelled
with 0, . . . , p by spectral clustering based on the similarities
of individuals. Similar individuals are assigned to the same
island while dissimilar ones are assigned to different islands.
The number of new islands are determined by the number
of clusters which can be controlled dynamically. In this way,
increasing the number of clusters or decreasing the pressure of
clustering can promote exploration. After splitting, each new
island evolves independently.
As it continues to Generation j, individuals of all islands 0, . . . , p migrate together and they are clustered based on
their similarities into new islands 0, . . . , q where p and q can
be equal or not. New islands are assigned a set of evolution
operators randomly including selection, mutation, crossover
and so on. Each centralization and clustering, like Generation
j is marked as one epoch. This migration policy has several
benefits. Firstly, because each island has a limitation on subpopulation size, individuals in large clusters are more likely
to be removed and those in small clusters will be kept.

Secondly, this policy increases the selection pressure on large
clusters as they are mature communities and decrease the
selection pressure on small clusters. In this way, individuals
of minor clusters can have more survival space to grow so
as to avoid die out before maturity. This can contribute to
maintaining diversity to some extend. In large clusters, well
fitted individuals can survive so as to promote exploitation.
After a number of epochs, in the final Generation l, all subpopulations migrate together and top ranked individuals are
considered as potential global optimized solutions.
As a result, the pseudocode of the proposed DIM-SP model
is described in Algorithm 2. The model is initialized with one
island and starts to evolve. If Generation i is an epoch, the
model starts to apply the centralization-clustering migration
policy; otherwise, each island is evolved independently. In
epochs, individuals from all islands P1 , . . . , Pn migrate together marked by Pa . Matrix W is the similarity matrix of
individuals calculated by similarity function Θ and spectral
clustering (Λ) is applied to cluster population (Pa ) into a new
set of sub-populations (P ) based on the similarity matrix (W ).
Each island will be assigned a set of evolution operators by
function Υ and the number of islands will be updated.

A. Similarity measure
Another advantage of the proposed DIM-SP model controls
individual migration policy based on the similarities of individuals which are used to evaluate population diversity. In
other words, the migration policy of the proposed island model
works on population diversity directly.
There are two major ways of measuring diversity of a given
population based on individual similarities. Firstly, diversity
refers to the difference amongst individuals. In this way, it
is a measure of the similarities between individuals. If the
genome of individuals are continuous values, the similarities
of individuals can be measured by a distance measure such
as Euclidian distance or cosine. If the genome of individuals
are continuous values, the similarities of individuals can be
measured based on their difference. For example, given two

Fig. 4. Evolutionary process of the proposed dynamic island model based on spectral clustering (DIM-SP). It starts from one island with an initialized
sub-population. As evolution proceeds to Generation i, sub-population of Island 0 migrate to new islands based on their similarities. As it continuous to
Generation j, sub-populations migrate together and then migrate to different islands based on similarity. This centralization-clustering process is repeated until
to the final Generation l where all sub-populations migrate together and individuals with top highest fitness values are considered as solutions.

Algorithm 2 Evolution process of DIM-SP model
Initialization:
Set an optimization problem Q(f, S);
Set n = 1;
Set P = {P1 };
Set O = {O1 };
Set migration policy M ;
Iteration:
1: for i = 1 to n do
2:
if i in epochs then
3:
Pa = P1 ∪ P2 ... ∪ Pn ;
4:
W = Θ(Pa );
5:
P = Λ(W );
6:
O = Υ (P );
7:
n = |P |;
8:
else
9:
Pi = Oi (Pi );
10:
end if
11: end for
12: s∗ = s∗ ∩ best(Pi );

individuals x and y with genome length as n.
(
1, if xi = yi ,
sf (x, y) =
0, otherwise,

In this study, we use normalized spectral clustering to do
clustering. Given a similarity matrix W of individuals, the
normalized Laplacian matrix L is defined as
L = I − D−1/2 W D−1/2

(2)

where matrix I is the identity matrix and D is the diagonal
matrix of W . The first leading k smallest eigenvalues and each
eigenvalue is mapped to a cluster.
C. Evaluation
We compare the performance of DIM-SP with the other
three state-of-the-art island models including ring, start-shaped
and fully-connected island model with the same configuration of evolution operators and migration policy on a set
of combinatorial optimization problems including job shop
scheduler (JSSP), Travelling Salesman (TSP) and the quadratic
multiple knapsack (QMKP) problems. The performance of results were evaluated by fitness score and population diversity.
The population diversity, in this paper, is calculated via the
average distance between individuals of best fit and the other
individuals. The proposed method and the other compared
methods runs for ten times with different random seeds. The
results are the averaged results of ten-time running.
(1)

Diversity can also refer to the difference between fitness values
of individuals and tries to retain best fitted individuals. The
DIM-SP model can integrate different types of similarities to
achieve different types of diversities.
In this study, we evaluate the proposed island model in combinational domain so we choose difference-based similarities
of individuals.
B. Spectral clustering
Spectral clustering is introduced to perform clustering based
on an individuals’ similarity rather than other methods such as
k-means, hierarchical clustering or DBSCAN because it can
achieve a global optimization solution, is easily implemented
and supports parallel computing [34].

V. T EST FUNCTIONS
The classic JSSP with the objective of makespan minimization consists of a set of n jobs that needs to be processed on
a set of m machines. The processing of job Jj on machine
Mr is called the operation Ojr . The solutions of this problem
should satisfy two constraints: job should be processed on
each machine according to a predefined sequence and each
machine can process only one job at a time. The time needed
for completion times for all operations is called makespan,
denoted as C and the objective of the problem is to minimize
C. In this paper, we evaluate the performance of island models
on an instance (ft20) of Fisher and Thompson [35].
The TSP [36] assumes that there is a salesman travelling
among m cities from the starting city s and returning to it.
The constraint is that each city can be travelled only once.
In this problem, the cost of travelling from city i to city j is

(a) Avg scores of JSSP Problem

(b) Avg scores of TSP problem

(c) Avg scores of QMKP problem

(d) Diversity of JSSP problem

(e) Diversity of TSP problem

(f) Diversity of QMKP problem

Fig. 5. Experimental results using DIM-SP island model. Specifically, (a), (b) and (c) illustrate the changes of average scores in different generations while
(d), (e) and (f) illustrates the changes of diversities in the benchmark problems. In each sub figure, D, DIM-SP island model, F, Full-connected island model,
S, Star-shape island model and R, Ring island model. The results of different models are marked with different colours and types of line.

denoted as cij , the best solution of this problem is to minimise
the distance the salesman travels. We use an instance from
TSPLIB1 which is extended to 2000 cities.
The quadratic multiple knapsack problem considers that
given a set of knapsacks of limited capacity and a set of
objects, each object is associated with a weight, an individual profit and a pairwise profit with them. QMKP aims to
maximize the profit being subject to the capacity constraint of
each knapsack. The selected instance is from QKPInstance2
and includes 20,000 objects and a density of 50%.
VI. E XPERIMENT
DIM-SP was coded in Java based on ECJLib3 and run
on a PC with 3.2 GHz Intel(R) Core (TM) i7-3770 CPU
and 8.00GB memory. In this study, the performance of DIMSP was compared with the three other state-of-the-art island
models with the same configuration of evolution operators and
migration policy on JSSP, TSP and QMKP. In order to evaluate
the performance of DIM-SP, we modified the datasets of these
1 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
2 http://cedric.cnam.fr/
3 https://cs.gmu.edu/

soutif/QKP/QKP.html
eclab/projects/ecj/

three problems. JSSP is a small scale problem with 200 jobs,
TSP is a median scale problem with 2000 cities and QMKP
is a large scale problem with 20,000 objects.
In the experiment, we set up the number of islands as
ten for baseline island models as they are not dynamic. For
the proposed island model, ten is the upper-limit of island
number. The island size is 200 and the maximum number
of generations is 2000. All islands were assigned to the
same evolution operators: crossover probability was 0.8, the
mutation probability was 0.2 and migration frequency was
50 generations. In each migration, 5% of randomly selected
individuals migrate to the other connected islands evenly.
The experimental results are shown in Fig. 5 where Fig. 5a,
Fig. 5b and Fig. 5c show the changes of average scores
in different generations, which can be regarded as accuracy
estimation in traditional machine learning issues [37, 38].
Fig. 5d, Fig. 5e and Fig. 5f show the changes of diversities in
the benchmark problems.
In terms of scores, it can been seen that the proposed DIMSP island model outperforms the other three island models.
Generally, in the early generations, the scores of DIM-SP are
worse than the other three models because it is initialized with

TABLE I
E XPERIMENTAL RESULTS OF THE PROPOSED DIM-SP ISLAND MODEL , F ULLY- CONNECTED ISLAND MODEL , S TAR - SHAPE ISLAND MODEL AND R ING
ISLAND MODEL ON JSSP, TSP AND QMKP PROBLEMS .
Island Model
DIM-SP
Ring
Star-shape
Fully-connected

Avg score

JSSP
Bst score

Diversity

Avg score

TSP
Bst score

Diversity

Avg score

QMKP
Bst score

Diversity

1,216
1,927
2,479
2,877

1,180
1,892
2,136
2,623

0.291
0.107
0.107
0.107

13,962
14,946
15,278
15,917

13,225
14,349
14,436
15,112

0.347
0.137
0.136
0.136

28,937
23,874
21,943
20,932

29,286
24,148
22,822
21,327

0.416
0.319
0.289
0.271

just one island while the other models are initialized with ten
islands. However, the performance of the proposed DIM-SP
island model matches and overtakes the other models as evolution proceeds. This is because DIM-SP imposes high selection
pressure on relatively mature sub-populations which enables
it to find better solutions quickly. Specifically, JSSP, DIMSP achieves lowest scores in both average (1,216) and best
(1,180) scores followed by Ring model (average score1,927,
best score 1,892), Star-shape model (average score 2,479, best
score 2,136) and Ring model (average score 2,877, best score
2,623) because DIM can effectively maintain high diversity
compared to the other three. Similar patterns can also be found
in TSP and QMKP. Another interesting finding is that Ring
island model is generally better than Star-shape island model
followed by Full-connected island model. This is because
Ring island can maintain isolation among sub-populations for
relatively longer periods of time compared to the other two
models. This shows that it is important to create and maintain
isolation as evolution proceeds to achieve good scores. DIMSP can always generate a solution by clustering in epochs.
In terms of diversity shown in Fig. 5d, Fig. 5e and Fig. 5f,
DIM-SP can maintain diversity at a relatively high level
compared to the other three island models. This is because
the other island models tend to converge into the same subpopulation while DIM-SP can maintain diversity by forcing
sub-populations to be different via clustering. With DIM-SP,
diversity is also stable as evolutionary proceeds. The reason
is that we predefine the upper-limit of the number of islands.
On the other hand, the topological features significantly contributes to diversity loss. The frequency of migration in Fullyconnected island model is clearly larger than it is in Starshape island model and Ring island model and sub-populations
converge into the same one more quickly than the other two.
This also reveals that one major weakness of island model
is that they tend to converge into the same one because of
migration. The DIM-SP model is proposed to overcome this to
maintain different sub-populations effectively and efficiently.
Overall, with the same configurations of evolution operators
of islands, the proposed DIM-SP island model outperform
the other three island models in achieving high scores and
maintaining diversities. The details are included in Tab. I.
VII. C ONCLUSION
In this paper, we propose a dynamic island model based
on spectral clustering (DIM-SP) for overcoming the major

drawbacks of traditional island models. The proposed model
can force each island to maintain different sub-populations,
control the number of islands dynamically and start with one
sub-population. The experimental results confirms the proposed dynamic island model can achieve better performance
than the other three baseline topological island models in
both fitness score and diversity in three baseline optimization
problems including job shop scheduler, travelling salesmen
and quadratic multiple knapsack problems. We will further test
the performance of the proposed island models in continuous
domains with other population-based methods.
R EFERENCES
[1] M. Gendreau and J.-Y. Potvin, Handbook of metaheuristics. Springer, 2010, vol. 2.
[2] J. Wu, Z. Cai, and X. Zhu, “Self-adaptive probability estimation for naive bayes classification,” in The
2013 International Joint Conference on Neural Networks
(IJCNN), 2013, pp. 1–8.
[3] J. Wu, Z. Cai, S. Zeng, and X. Zhu, “Artificial immune
system for attribute weighted naive bayes classification,”
in The 2013 International Joint Conference on Neural
Networks (IJCNN), 2013, pp. 1–8.
[4] Y.-C. Lin, M. Clauß, and M. Middendorf, “Simple probabilistic population-based optimization,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 2, pp.
245–262, 2016.
[5] M. Črepinšek, S.-H. Liu, and M. Mernik, “Exploration
and exploitation in evolutionary algorithms: A survey,”
ACM Computing Surveys (CSUR), vol. 45, no. 3, p. 35,
2013.
[6] A. E. Eiben and C. A. Schippers, “On evolutionary
exploration and exploitation,” Fundamenta Informaticae,
vol. 35, no. 1-4, pp. 35–50, 1998.
[7] Á. E. Eiben, R. Hinterding, and Z. Michalewicz, “Parameter control in evolutionary algorithms,” IEEE Transactions on evolutionary computation, vol. 3, no. 2, pp.
124–141, 1999.
[8] T. Back, Evolutionary algorithms in theory and practice:
evolution strategies, evolutionary programming, genetic
algorithms. Oxford university press, 1996.
[9] M. L. Mauldin, “Maintaining diversity in genetic search.”
in AAAI, 1984, pp. 247–250.
[10] Z. Li and X. Wang, “Chaotic differential evolution algorithm for solving constrained optimization problems,”

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]
[24]

[25]

Information Technology Journal, vol. 10, no. 12, pp.
2378–2384, 2011.
W. Wongseree, N. Chaiyaratana, K. Vichittumaros,
P. Winichagoon, and S. Fucharoen, “Thalassaemia classification by neural networks and genetic programming,”
Information Sciences, vol. 177, no. 3, pp. 771–786, 2007.
D. Jia, G. Zheng, and M. K. Khan, “An effective memetic
differential evolution algorithm based on chaotic local
search,” Information Sciences, vol. 181, no. 15, pp. 3175–
3187, 2011.
G. Chen, C. P. Low, and Z. Yang, “Preserving and
exploiting genetic diversity in evolutionary programming
algorithms,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 3, pp. 661–673, 2009.
R. Mallipeddi, P. N. Suganthan, Q.-K. Pan, and M. F.
Tasgetiren, “Differential evolution algorithm with ensemble of parameters and mutation strategies,” Applied Soft
Computing, vol. 11, no. 2, pp. 1679–1696, 2011.
A. Zamuda and J. Brest, “Self-adaptive control parameters randomization frequency and propagations in differential evolution,” Swarm and Evolutionary Computation,
vol. 25, pp. 72–99, 2015.
A. Leitão, F. B. Pereira, and P. Machado, “Island models
for cluster geometry optimization: how design options
impact effectiveness and diversity,” Journal of Global
Optimization, vol. 63, no. 4, pp. 677–707, 2015.
P. Salza, F. Ferrucci, and F. Sarro, “elephant56: Design
and implementation of a parallel genetic algorithms
framework on hadoop mapreduce,” in Genetic and Evolutionary Computation Conference (GECCO Companion),
2016.
W. N. Martin, J. Lienig, and J. P. Cohoon, “Island
(migration) models: evolutionary algorithms based on
punctuated equilibria,” Handbook of evolutionary computation, vol. 6, no. 3, 1997.
S. Wright, “Stochastic processes in evolution,” Stochastic
models in medicine and biology, vol. 25, pp. 199–241,
1964.
R. J. Collins and D. R. Jefferson, Selection in massively
parallel genetic algorithms. University of California
(Los Angeles). Computer Science Department, 1991.
M. Tomassini, “Spatially distributed evolutionary algorithms,” Natural Computing Series. Springer-Verlag,
Berlin Heidelberg, 2005.
E. Alba, A. J. Nebro, and J. M. Troya, “Heterogeneous
computing and parallel genetic algorithms,” Journal of
Parallel and Distributed Computing, vol. 62, no. 9, pp.
1362–1385, 2002.
E. Alba and B. Dorronsoro, Cellular genetic algorithms.
Springer Science & Business Media, 2009, vol. 42.
S. Limmer and D. Fey, “Comparison of common parallel
architectures for the execution of the island model and
the global parallelization of evolutionary algorithms,”
Concurrency and Computation: Practice and Experience,
2016.
E. Alba and J. M. Troya, “A survey of parallel distributed

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

genetic algorithms,” Complexity, vol. 4, no. 4, pp. 31–52,
1999.
B. Chen, W. Zeng, Y. Lin, and D. Zhang, “A new
local search-based multiobjective optimization algorithm,” IEEE Transactions on Evolutionary Computation,
vol. 19, no. 1, pp. 50–73, Feb 2015.
I. Boussaı̈D, J. Lepagnot, and P. Siarry, “A survey on
optimization metaheuristics,” Information Sciences, vol.
237, pp. 82–117, 2013.
R. K. Ursem, “Multinational gas: Multimodal optimization techniques in dynamic environments,” in Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation. Morgan Kaufmann Publishers
Inc., 2000, pp. 19–26.
A. Baykasoglu and F. B. Ozsoydan, “A constructive
search algorithm for combinatorial dynamic optimization
problems,” in Evolving and Adaptive Intelligent Systems
(EAIS), 2015 IEEE International Conference on. IEEE,
2015, pp. 1–7.
F. B. Ozsoydan and A. Baykasoglu, “A multi-population
firefly algorithm for dynamic optimization problems,” in
Evolving and Adaptive Intelligent Systems (EAIS), 2015
IEEE International Conference on. IEEE, 2015, pp.
1–7.
B. Nasiri and M. R. Meybodi, “Improved speciationbased firefly algorithm in dynamic and uncertain environments,” Journal of Information Science and Engineering,
vol. 32, no. 3, pp. 661–676, 2016.
Q. Lin, J. Chen, Z. H. Zhan, W. N. Chen, C. A. C. Coello,
Y. Yin, C. M. Lin, and J. Zhang, “A hybrid evolutionary
immune algorithm for multiobjective optimization problems,” IEEE Transactions on Evolutionary Computation,
vol. 20, no. 5, pp. 711–729, Oct 2016.
L. Li and K. Tang, “History-based topological speciation for multimodal optimization,” IEEE Transactions on
Evolutionary Computation, vol. 19, no. 1, pp. 136–150,
2015.
U. Von Luxburg, “A tutorial on spectral clustering,”
Statistics and computing, vol. 17, no. 4, pp. 395–416,
2007.
H. Fisher and G. L. Thompson, “Probabilistic learning
combinations of local job-shop scheduling rules,” Industrial scheduling, vol. 3, no. 2, pp. 225–251, 1963.
K. L. Hoffman, M. Padberg, and G. Rinaldi, “Traveling
salesman problem,” in Encyclopedia of Operations Research and Management Science. Springer, 2013, pp.
1573–1578.
J. Wu, Z.-h. Cai, and S. Ao, “Hybrid dynamic k-nearestneighbour and distance and attribute weighted method
for classification,” Int. J. Comput. Appl. Technol., vol. 43,
no. 4, pp. 378–384, 2012.
J. Wu, S. Pan, X. Zhu, C. Zhang, and P. S. Yu, “Multiple
structure-view learning for graph classification,” IEEE
Transactions on Neural Networks and Learning Systems,
vol. PP, no. 99, pp. 1–16, 2017.

