Exploration and Exploitation in Evolutionary Algorithms A Survey
35
Exploration and Exploitation in Evolutionary Algorithms:A Survey
MA TEJˇCREPINˇSEK,University of Maribor
SHIH-HSI LIU,California State University,Fresno
MARJAN MERNIK,University of Maribor
“Exploration and exploitation are the two cornerstones of problem solving by search.”For more than a decade,
Eiben and Schippers’advocacy for balancing between these two antagonistic cornerstones still greatly in-
?uences the research directions of evolutionary algorithms(EAs)[1998].This article revisits nearly100
existing works and surveys how such works have answered the advocacy.The article introduces a fresh treatment that classi?es and discusses existing work within three rational aspects:(1)what and how EA components contribute to exploration and exploitation;(2)when and how exploration and exploitation are controlled;and(3)how balance between exploration and exploitation is achieved.With a more comprehen-
sive and systematic understanding of exploration and exploitation,more research in this direction may be motivated and re?ned.
Categories and Subject Descriptors:I.2.8[Arti?cial Intelligence]:Problem Solving,Control Methods,and Search—Heuristic method
General Terms:Algorithms
Additional Key Words and Phrases:Diversity,exploration and exploitation,evolutionary algorithms
ACM Reference Format:
ˇCrepinˇs ek,M.,Liu,S.-H.,and Mernik,M.2013.Exploration and exploitation in evolutionary algorithms:A
survey.ACM Comput.Surv.45,3,Article35(June2013),33pages.
DOI:https://www.wendangku.net/doc/e012739641.html,/10.1145/2480741.2480752
1.INTRODUCTION
Every search algorithm needs to address the exploration and exploitation of a search space.Exploration is the process of visiting entirely new regions of a search space,
whilst exploitation is the process of visiting those regions of a search space within
the neighborhood of previously visited points.In order to be successful,a search al-gorithm needs to establish a good ratio between exploration and exploitation.In this respect,evolutionary algorithms(EAs)[De Jong2002;Eiben and Smith2008],such as genetic algorithms(GAs)[Michalewicz1996;Goldberg2008],evolutionary strategies (ES)[B¨ack1996],evolutionary programming(EP)[Fogel1999],and genetic program-
ming(GP)[Koza1992],to name the more well-known instances,are no exception. Herrera and Lozano[1996]emphasized this by saying,“The genetic algorithm be-haviour is determined by the exploitation and exploration relationship kept throughout
the run.”Many researchers believe that EAs are effective because of their good ratio
Authors’addresses:M.ˇCrepinˇs ek and M.Mernik,Faculty of Electrical Engineering and Computer Science,University of Maribor,Smetanova ulica17,2000Maribor,Slovenia;email:{matej.crepinsek, marjan.mernik}@uni-mb.si;S.-H.Liu,Department of Computer Science,California State University,Fresno,
CA;email:shliu@https://www.wendangku.net/doc/e012739641.html,.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for pro?t or commercial advantage and that
copies show this notice on the?rst page or initial screen of a display along with the full citation.Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted.
To copy otherwise,to republish,to post on servers,to redistribute to lists,or to use any component of this
work in other works requires prior speci?c permission and/or a fee.Permissions may be requested from Publications Dept.,ACM,Inc.,2Penn Plaza,Suite701,New York,NY10121-0701USA,fax+1(212)
869-0481,or permissions@https://www.wendangku.net/doc/e012739641.html,.
c 2013ACM0360-0300/2013/06-ART35$15.00
DOI:https://www.wendangku.net/doc/e012739641.html,/10.1145/2480741.2480752
35:2M.ˇCrepinˇs ek,et al. between exploration and exploitation.Michalewicz[1996]stated,“Genetic Algorithms are a class of general purpose(domain independent)search methods which strike a remarkable balance between exploration and exploitation of the search space.”In spite of the fact that exploration and exploitation are fundamental concepts,they are often misunderstood by EA practitioners or even EA researchers.
Eiben and Schippers[1998]provided an early discussion on evolutionary exploration and exploitation.Their work raised several questions and demonstrated the need for more research.The aim of their work was to question the common belief that exploita-tion in EAs is done by selection,whilst exploration is performed by search operators (e.g.,mutation and crossover).Eiben and Schippers also reviewed ten papers in order to consider existing views,at the time of their writing,about exploration and exploita-tion in EAs.They found that there was no generally accepted agreement on this topic. Yet,it seems that their paper,cited by only32papers1,has been mainly overlooked. Perhaps the problem of how to control and measure exploration and exploitation is still too dif?cult and/or implicit.
The main objective of this article is to remedy this situation by providing a more complete treatment of evolutionary exploration and exploitation.Hence,common mis-understandings and incorrect beliefs about exploration and exploitation in EAs could be gradually diminished.More importantly,better EAs could be developed by devel-oping a better understanding of exploration and exploitation.For example,a better understanding could clarify why one selection mechanism within a particular setting is better than another,or which crossover/mutation operator to choose.Furthermore,dif-ferences among EAs might be better understood.B¨ack and Schwefel[1993]conducted an early discussion on differences among GAs,ESs,and EP.They were astonished by the differences that drive evolution in EAs:
“It is a remarkable fact that each algorithm emphasizes different features
as being most important for a successful evolution process....Both ESs and
EP concentrate on mutation as the main search operator,while the role of
(pure random)mutation in canonical GAs is usually seen to be of secondary
(if any)importance.On the other hand,recombination plays a major role in
canonical GAs,is missing completely in EP,and is urgently necessary for use
in connection to self-adaptation in ESs.One of the characteristics of EP is the
strict denial of recombination being important for the search.Finally,both
canonical GAs and EP emphasize on a necessarily probabilistic selection
mechanism,while from the ESs point of view selection is completely deter-
ministic without any evidence for the necessity of incorporating probabilistic
rules.In contrast,both ESs and EP de?nitely exclude some individuals from
being selected for reproduction,i.e.,they use extinctive selection mecha-
nisms,while canonical GAs generally assign a nonzero selection probability
to each individual,which we term a preservative selection mechanism.”
These differences among EAs can be dif?cult to understand,not only by beginners within the?eld of EAs but also by many experienced EA practitioners,without the notion of balance between exploration and exploitation.Differences not only appear among EA instances but also inside the same type of EA.For example,diametrical recommendations might confuse many if the rationale for including such a feature is unexplained or misunderstood.Similarly,how to explain that some successful GAs prevent inbreeding(e.g.,by incest prevention[Eshelman and Schaffer1991])whilst, on the other hand,the others(e.g.,shifting balance GA[Oppacher and Wineberg1999]) promote inbreeding?How do we understand such dichotomies?Actually,it is all about 1Search performed on July12,2011,using SCOPUS.
Exploration and Exploitation in Evolutionary Algorithms35:3 achieving a proper ratio between exploration and exploitation.No evolutionary process should be studied in isolation,and balance should be achieved synergistically.For example,the aforementioned inbreeding dichotomy may be explained in the following manner.Instead of trying to enhance variety by penalizing similarities(e.g.,incest prevention),you could use inbreeding(e.g.,shifting balance GA)that may cause genetic drift if a population is small enough(subpopulations).This will make it possible to surpass valleys and promote exploration.A stabilizing effect is achieved when such subpopulations are integrated into a large population with high selection pressure, achieving equilibrium between exploration and exploitation.Another example may be found in the recombination of(dis)similar parents,where Horn et al.[1994]concluded that“information from very different types of trade-offs could be combined to yield other kinds of good trade-offs,”whilst Ishibuchi et al.’s empirical study[2008]on NSGA-II showed that similar parents improved the diversity of solution without degrading their convergence.
Yet another example:inexperienced EA users might?nd it dif?cult to understand that the same EA behaves equally,in terms of the best solution found,despite very different control parameter settings.Smit and Eiben[2009]showed that by using algorithmic parameter tuning to solve a simple optimization problem,the Rastrigin function performed equally well using the following settings:population size14vs. 448,tournament proportion0.8782vs.0.3503,and generational gap0.8443vs.0.0215. The proportion of the population size that is replaced by each generation was much larger than in the case of smaller populations;there is also a distinctive difference in the selection pressure.We are convinced that all the aforementioned differences are much easier to understand in terms of exploring and exploiting the search space, especially in understanding the balance between exploration and exploitation.The fact that until now exploration and exploitation have only been implicitly de?ned in EAs comes as a big surprise.
From existing papers on survey/taxonomy in metaheuristics,Blum and Roli[2003] provided different classi?cations of metaheuristics(nature-inspired vs.non-nature in-spired,population-based vs.single point search,dynamic vs.static objective function, one vs.various neighborhood structures,and memory usage vs.non-memory usage), described inner workings of different metaheuristics(e.g.,simulated annealing,tabu search,evolutionary algorithms,ant colony optimization),and provided a uni?ed view on diversi?cation and intensi?cation.(Exploration and exploitation by Blum and Roli [2003]refers to rather short-term strategies tied to randomness,while diversi?cation and intensi?cation refer to medium-to long-term strategies based on the usage of mem-ory).Another classi?cation of hybrid metaheuristics was introduced by Talbi[2002]. Yet,diversi?cation and intensi?cation were excluded as the criteria for taxonomy.Liu et al.[2009]also classi?ed EAs into uniprocess-and multiprocess-driven approaches regarding how the balance between exploration and exploitation is achieved.In order to make the classi?cation[Liu et al.2009]more thorough,another objective of this article is to provide more comprehensive literature studies and new classi?cations for existing approaches.
This article is organized as follows.Section2presents the reviews of how exploration and exploitation can be achieved in EAs.We reemphasize that delimitation of the two cornerstones is dif?cult and as yet unachievable within the existing work.Section3 presents the discussions of when and how to control exploration and exploitation.We speci?cally emphasize diversity measurements because of their core role in delimiting exploration from exploitation.Section4provides a comprehensive review of existing work done in the?eld of balancing exploration and exploitation in terms of diversity-driven and other direct criteria.Section5concludes the article by indicating future research directions.
35:4M.ˇCrepinˇs ek,et al.
2.ACHIEVING EXPLORATION AND EXPLOITATION IN EAS
The question of how exploration and exploitation are achieved in EAs may seem trivial,but this is not so.For example,the discussion on this topic where Eiben and Schippers[1998]noticed that a common opinion about EAs is that search space is explored by crossover/mutation operators,whilst exploitation is done by selection, is at least questionable.Moreover,ultimately Eiben and Schippers concluded that there was no generally accepted perception about exploration and exploitation in EAs.Another important conclusion derived from Eiben and Schippers[1998]is that more intensive research is needed for a deeper understanding of the fundamentals of evolutionary search processes.Overall,in many papers,oversimpli?ed views are perceived on this subject.For example,Wong et al.[2003]wrote:“In order to optimize the ef?ciency and effectiveness,Genetic Algorithms(GAs)must maintain a balance between the exploitation of bene?cial aspects of existing solutions(by crossover)in order to improve them,and the exploration of the solution space(by mutation)so as to increase the probability of?nding the optimal solution.This balance is determined by the crossover rate and the mutation rate.”
In this article,more complete treatment on evolutionary exploration and exploitation is given,along with those selection processes and other factors that were ignored in the aforementioned quote.Selection drives the search toward the regions of the best individuals.Hence,it can be mainly seen as an exploitation operator.However, B¨ack[1994]showed that selection processes can control the level of exploration or exploitation by varying selection pressure.Higher selection pressure pushes the search towards more exploitation,and lower selection pressure urges the search towards more exploration.Maintaining accurate selection pressure and hence a balance between exploration and exploitation is needed for many optimization problems[Goldberg and Deb1991].Additionally,a mutation operator randomly modi?es individuals with a given probability and thus increases the structural diversity of a population.From this point of view,a mutation operator is more of an exploration operator.Such an operator facilitates the recovery of genetic diversity lost during the selection phase and explores new solutions.Conversely,a mutation operator can also be seen as an exploitation operator because most of the genetic materials are preserved.The role of mutation in different EAs is slightly different,too.In ES,mutation is more of an exploration operator,whilst in GAs,mutation is more of an exploitation operator if the locality property[Galv′an-L′o pez et al.2010],described in Section3.1,holds.A crossover operator combines two or more parents to generate the possibility of better offspring. Such a combination can be derived from the idea that an exchange of information between good individuals will generate an even better offspring.From this perspective, a crossover operator is more of an exploitation operator.However,a good crossover operator should also generate individuals within the exploration zone.The potential number of ways in which an operator can generate a new individual is called its exploratory power[De Jong and Spears1992].In many cases,it is dif?cult to predict if newly generated individuals produced by a crossover and/or mutation operator will fall into the exploration or exploitation zones.It is crucial to understand that we can never call a crossover/mutation operator a pure exploration/exploitaton operator.At best,we can hope that most generated individuals will fall into that particular zone.
As can be seen from the preceding discussion,exploration and exploitation in EAs is achieved by selection,mutation,and crossover.But it is dif?cult to distinguish between exploration from exploitation in these processes.The line between exploration and ex-ploitation is blurred.Furthermore,these are not the only factors that have an impact on exploration and exploitation.Population size and the representation of individuals have important impacts,too.Directing an evolution process towards exploration or
Exploration and Exploitation in Evolutionary Algorithms35:5 exploitation is also possible by population resizing[Harik and Lobo1999;Smith and Smuda1995].With a larger population size,the search space is explored more than with a smaller population size.This is an easier way to maintain the diversity but is often an unsatisfactory solution.Without proper handling,even larger populations can converge and waste processing time.Moreover,population size also in?uences other operators.For example,Spears[1995]showed that uniform crossover outperforms two-point crossover regarding a small population on a particular problem,but just the op-posite is true with a large population.It is almost impossible,or at least less possible,to study a particular feature in isolation.Another tricky point is representation.Mutation and crossover operators that in?uence exploration and exploitation mostly depend on representation of individuals.Hence,representation really matters,and only in a few cases was representation independence achieved(e.g.,geometric crossovers/mutations derived from the theories of topology and geometry[Moraglio et al.2007]).It is im-portant to know at which levels mutation/crossover operators work:at the individual, sub-individual,or gene level[Smith and Fogarty1997].Indeed,many researchers point out that representation is a critical factor in the success of an EA(e.g.,Ishibuchi et al. [2010b]introduced a representation-dependent nongeometric binary crossover to fur-ther improve diversity without degrading convergence in evolutionary multiobjective optimization(EMO)).But,the relationship between an individual’s representation and the balance between exploration and exploitation is still not well understood,and more research is needed.
The next important question is how the balance between exploration and exploitation is achieved in an EA.What is observed from the previous discussion is that the selection process and variation operators(e.g.,crossovers and mutations)are able to somehow establish and,in most cases,?nd a good ratio between exploration and exploitation of the search space.Until now,achieving balance between exploration and exploitation has been managed by proper control-parameter settings.If crossover and mutation rates are very high,much of the space will be explored,but there is a high probability of missing good solutions and of failing to exploit existing solutions.In such a case,EAs head toward random search.If crossover and mutation rates are low,the search space is unexplored.In such a case,EAs are closer to hill climbing algorithms.Moreover, crossover and mutation operators are usually into interactions,and optimizing both parameters(crossover and mutation rates)cannot be done independently.In such cases,all combinations of crossover and mutation rates should be experimented.Which control-parameter settings are most likely to produce the best results is a question that every EA developer/user has to face.In the EA community the following approaches have been tried[Lobo et al.2007].
(1)Trial-and-error approach,which is a time-consuming and tedious method,usually
performed in an ad-hoc manner.
(2)Following general guidelines(e.g.,[De Jong1975;Harik and Lobo1999;Schaffer
et al.1989]),which are often inapplicable for speci?c cases.It is often found that recommended parameter settings from literature do not lead to the best solutions for particular cases(e.g.,[Smit and Eiben2009;Zielinski et al.2009]).
(3)Using parameter-less EA[Harik and Lobo1999]or GAs without parameters[B¨ack
et al.2000],which are robust but mostly less-ef?cient approaches.
(4)Using experiences from previous similar applications,which is inapplicable when
such experiences do not exist.
(5)Identifying the features of?tness landscapes by a classi?er in order to propose
good control parameter settings[Bogon et al.2011].
(6)Statistical analysis of control parameter interactions and their effect on algorithms’
performances[Czarn et al.2004].
35:6M.ˇCrepinˇs ek,et al.
(7)Using mathematical models,which is important but often too simple to be realistic
or too dif?cult to be understood by ordinary users.
(8)Algorithmic parameter tuning,where the search for the best control parameters
is seen as an optimization problem that can be solved using speci?c methods.
The more well-known examples are the meta-evolutionary approach(evolution of evolution)[Grefenstette1986],racing algorithm[Birattari et al.2002],se-quential parameter optimization[Bartz-Beielstein et al.2005],meta-estimation of distribution algorithm[Nannen and Eiben2006],hyper-heuristics[Ochoa et al.2008],multiobjective optimization[Dr′e o2009],and reinforcement learning [Montero and Riff2011].Work in this category has been recently surveyed and categorized into sampling methods,model-based methods,screening methods,and meta-evolutionary algorithms[Eiben and Smit2011].
It is well known among EA researchers that the control parameter setting is problem-dependent.The control parameter setting which produces the best result for a partic-ular problem might not lead to the best result for another problem[Smit and Eiben 2009;Zielinski et al.2009].From the exploration/exploitation perspective,this means that different problems require different amounts of exploration and exploitation.This implies that a good ratio between exploration and exploitation,and hence a proper or good balance,is problem-dependent too.For example,for unimodal function optimiza-tion,less exploration is probably needed than for multimodal function optimization. Therefore,the goal of any search algorithm is to inherently?nd a good balance between exploration and exploitation for different problems.To make the problem even more dif?cult,different values for control parameters might be optimal at different stages of an evolution process,and hence different amounts of exploration and exploitation are needed during the evolution process.For example,in the early stages,a larger popula-tion is needed than in the later stages when?ne tuning of suboptimal solutions is done. Eiben et al.[1999]provided an excellent overview of this problem,where parameter tuning and parameter control were distinguished.For parameter tuning,parameters are de?ned before a run(also called of?ine approach)and do not change during the evolution process.All the aforementioned approaches(e.g.,trial-and-error,algorithmic parameter tuning)are examples of parameter tuning.Conversely,the parameters in the latter approach are changed during the run(also called the online approach).Eiben et al.[1999]classi?ed the methods on how parameters are controlled into deterministic, adaptive,and self-adaptive categories.
(1)The deterministic category adjusts the parameters by deterministic rules.
(2)The adaptive category utilizes the feedback of an evolution process to control the
directions and magnitudes of the parameters.
(3)The self-adaptive category encodes parameters into individuals and undergoes mu-
tation and recombination(simultaneous evolution of evolution).
Deterministic and adaptive parameter control can also be expressed in algorithmic ways by using a domain-speci?c language[Mernik et al.2005]for programming pa-rameter control[Liu et al.2004].Note that classic meta-evolutionary approaches are mainly classi?ed under parameter tuning(of?ine approach),because control param-eters,evolved at the meta level,remain unchanged during an evolution process at the base level.Recently,some hybridization between parameter tuning and parameter control has been proposed(e.g.,meta GA combined with an adaptation strategy for the GA control parameters[Fernandez-Prieto et al.2011]).As for the meta-EP mentioned in B¨ack and Schwefel[1993],the parameters are encoded and evolved along with the process and hence are self-adaptive.We also utilize Eiben et al.’s classi?cation[1999] for classifying the explicit control of exploration and exploitation.
Exploration and Exploitation in Evolutionary Algorithms35:7 One common belief is that EAs should start with exploration and then gradually change into exploitation.Such a policy can be easily described with deterministic ap-proaches,where the mutation rate decreases along with the evolution(e.g.,[Fogarty 1989]).This is generally correct,but such a policy tends to face dif?culties when solving certain problems(e.g.,multimodal functions with many optima[Liu et al.2009;Yao et al.1999]or when dynamic environments are evolved),since premature takeover of exploitation over exploration occurs.Hence,more promising(self-)adaptive approaches have been proposed.They range from utilizing simple information available from cur-rent processes,such as?tness values(e.g.,[Harik and Lobo1999]),the number of gen-erations with no improvements(e.g.,[Eiben et al.2004]),diversity(e.g.,[Ursem2002]), and entropy(e.g.,[Rosca1995]),to more advanced techniques,such as adaptive genetic operators and selection[Herrera and Lozano1996],adaptive representation[Whitley et al.1991],and adaptive?tness functions[Majig and Fukushima2008].Yet,we en-visage that new and better(self-)adaptive approaches will be proposed in the future. It is important to note that with the different settings of control parameters(before or during the run)one explicitly controls speci?c processes(e.g.,selection,mutation,and crossover)but only implicitly controls exploration and exploitation.In order to answer the question of how a good ratio between exploration and exploitation is achieved,Liu et al.[2009]classi?ed two approaches.
(1)Uniprocess-driven approach.
(2)Multiprocess-driven approach.
For the uniprocess-driven approaches,a good balance between exploration and ex-ploitation is achieved separately by an individual process(e.g.,selection,mutation, crossover).Each process is independently responsible for the balance,and there is no coordination between processes for achieving the balance.An illustrative exam-ple is the crossover operator itself.In the beginning,whilst the population is still diverse,crossover performs exploration.At the end of the search,the population loses diversity,and by recombining,similar individuals’crossover exploratory powers are lost.The crossover operator itself,without changing the probability of crossover,shifts gradually from exploration to exploitation.In a similar manner,the non-uniform mu-tation operator[Zhao2011]performs search uniformly at the early stage and very locally at the later stage.Another example is described in Gao and Xu[2011],where the Henon mutation operator is used as a global or local mutation operator.There is much additional work categorized within this area(e.g.,[B¨ack1994;Eiben et al.2004; Harik and Lobo1999;Ronald1995;Smith et al.1993;Tsutsui et al.1997b],amongst others).Note that uniprocess approaches do not mean that other processes are unin-volved in an exploration/exploitation process.Instead,a unique process is focused on balancing exploration and exploitation by using different techniques(e.g.,adjusting corresponding control parameters).The challenge in this approach is how to achieve synergy among operators if they are uncooperative.To a lesser extent,researchers try to achieve balance using a multiprocess-driven approach.Balance is then coordi-nated among different processes(e.g.,with high selection pressure for exploitation, a high rate mutation/crossover operator is chosen that is biased towards more explo-ration).An early example of multiprocess-driven approaches was the CHC algorithm [Eshelman1991]that combined selection that always preserves the best individuals so far(exploitation)with a crossover operator that produces maximally different individ-uals(exploration).Another good example was reported in Fonseca and Fleming[1995], where it was found that proper collaboration between selection(?tness sharing)and crossover(mating restriction)signi?cantly improved the performance of multiobjec-tive GA.McGinley et al.[2011]also introduced ACROMUSE GA that synergistically
35:8M.ˇCrepinˇs ek,et al. employs crossover for exploitation,mutation for exploration,and adjustable selection pressure for both exploration and exploitation.
3.ON CONTROLLING EXPLORATION AND EXPLOITATION
When and how should exploration and exploitation be controlled?Let us start with the easier part of this question,namely when.
Exploration and exploitation can be controlled of?ine by the proper settings of control parameters that will have an in?uence on algorithm search capabilities.However,de-veloped algorithms will be applied to a vast variety of optimization problems,which will require different amounts of exploration and exploitation.Since a problem is unknown in advance,the algorithm’s search capabilities could be enhanced if the amounts of ex-ploration and exploitation were to be dynamically changed during a run.On the other hand,due to the conceptual advantages of parameter control over parameter tuning and existing experimental studies(e.g.,[Alba and Dorronsoro2005;Brest et al.2006; Liu et al.2009;Pan et al.2011]),exploration and exploitation should be controlled online during the run.
A tricky issue is to determine on what occasion?Here,again,some deterministic schema(e.g.,every k generations[Hesser and M¨anner1991])or adaptive schema(e.g., when best?tness did not change for several generations[Eiben et al.2004],and when the diversity of a population drops under some threshold value[Shimodaira1997; Ursem2002]),can be applied.There is a need for intelligently controlling the balance between exploration and exploitation at different stages.The more intelligent the con-trol,the better the results can be expected and/or the faster the algorithm will converge. How to control exploration and exploitation balance is the more dif?cult part of the question.Balance between exploration and exploitation is implicit in EAs,and as such, directly controlling balance is dif?cult.But before controlling it,we need to know how to measure it.This is a fact in all scienti?c and engineering disciplines.How to measure exploration and exploitation is an open question in EAs[Beyer and Deb2001],as far as we are aware.Intrinsic to this problem is that we need to know how these two phases are identi?ed.If,in each process,both phases can be clearly identi?ed,then some direct measures can be invented.Currently,indirect measures for exploration and exploitation are mostly used(see Section4).
We describe and classify different diversity measures currently in use in the following section,because exploration is possible only if populations are diverse enough.Those diversity measures can be used to de?ne the neighborhood relationships needed to delimit between exploration and exploitation.
3.1.Diversity
Diversity refers to differences among individuals,which can be at the genotype or phe-notype levels.It is widely accepted within the EA community that the high diversity of a population greatly contributes to EA performance[Michalewicz1996].McPhee and Hopper[1999]vividly described this viewpoint.“Progress in evolution depends funda-mentally on the existence of variation of population.Unfortunately,a key problem in many Evolutionary Computation(EC)systems is the loss of diversity through prema-ture convergence.This lack of diversity often leads to stagnation,as the system?nds itself trapped in local optima,lacking the genetic diversity needed to escape.”Until now,diversity has been extensively investigated only in GP[Burke et al.2004],whilst in other EAs,there has been no such treatment.Mattiussi et al.[2004]pointed out that diversity measures for individuals of a population with variable lengths and structures are much more complicated and might be more computationally extensive.Burke et al. [2004]investigate how one could improve?tness by controlling the diversity in GP,
Exploration and Exploitation in Evolutionary Algorithms35:9 whilst in this article,the similarity between individuals and their offspring,computed using different diversity measures,will de?ne the exploration or exploitation zones. There exist many different measures for diversity—genotypic as well as phenotypic—but there is no single measure that?ts all problems and different types of EAs.As some authors[Burke et al.2004;Galv′an-L′o pez et al.2010;Paenke et al.2009]have already pointed out,diversity measures are problem-speci?c.Moreover,if such diversity mea-sures are going to be used in guiding evolution processes,we need to investigate if positive correlations exist.Burke et al.[2004]showed that there is not always a posi-tive correlation between diversity measures and?tness in GP.In such cases,controlling diversity to improve?tness is unsuccessful.
It is worth mentioning that diversity is only roughly related to exploration and ex-ploitation.High diversity does not necessarily mean that a diverse population was ob-tained by a good ratio between exploration and exploitation.Such a diverse population can be obtained by mere exploration without requiring a good balance between explo-ration and exploitation.Moreover,a diverse population does not mean that individuals are?t,just that they are different from each other(e.g.,[Bosman and Thierens2003] presented some good examples in multiobjective evolutionary algorithms(MOEAs)). We are interested in diversity that helps to?nd?t individuals.For this purpose, Mahfoud[1995]introduced the term useful diversity.A poor but diverse population is less attractive.Nevertheless,a diverse population is a prerequisite for exploration in order to avoid premature convergence to local optima.On the other hand,promoting diversity at all stages of an evolutionary process might even be counterproductive in a phase where high exploitation is needed.The relationship between diversity and exploration and exploitation is still unclear,and more research is needed,especially when identifying the types(phenotypic/genotypic)and amounts of diversity at different evolutionary stages[Burke et al.2004].
As already mentioned,diversity can be measured at three levels.
(1)Genotype level(structural/syntactic/genotypic):differences among genomes within
a population.
(2)Phenotype level(behavioural/semantic/phenotypic):differences among?tness val-
ues within a population.
(3)A complex or composite measure:a combination of the previous two cases[Burke
et al.2004].Hence,we do not explicitly cover it in this article.
In most cases,identical genotypes will produce the same phenotype in EAs.So one might assume that a decrease in genotype diversity would necessarily cause a decrease in phenotype diversity.However,the relationship between genotype and phenotype is not always straightforward(e.g.,noisy functions[Liu et al.2007],changing environ-ments).Multiple genes can in?uence a single phenotypic variable,or a single gene can in?uence multiple phenotypic variables.Another important issue is the concept of local-ity that tells us how well neighboring genotypes correspond to neighboring phenotypes, which is a key concept affecting exploration and exploitation of EAs.Galv′an-L′o pez et al. [2010]demonstrated that for an ef?cient search,the neighborhood has to be preserved. Namely,neighboring genotypes are mapped to neighboring phenotypes.This is called ‘high locality’.If this is not the case,the distances at both levels do not correspond, and a search could be misleading.Representation with the property of high locality enables a more ef?cient search.Hence,representation really matters.Wineberg and Oppacher[2003]argued that diversity measures should not only include individuals, but also whole populations.In other words,distance between populations is needed. High genotype diversity does not necessarily mean high phenotype diversity.This is true when one-to-one mapping between genotype and phenotypes does not exist.Such a mapping depends on the representation used and on the problem to be solved.For
35:10M.ˇCrepinˇs ek,et al. example,Darwen and Yao[2001]reported that with the Iterated Prisoner’s Dilemma, high genetic diversity can perversely correspond to low phenotypical diversity.Tsutsui et al.[1997a;1997b]experimented with genotype and phenotype diversities.They found that performance depends on the type of problem under consideration,despite the fact that phenotype-based measures,usually perform better.There are also some other bene?ts of phenotype-based measures,such as the independence of the used representation schemes.It is often easier and less costly to calculate phenotypic diversity.This is especially true for GP[Burke et al.2004].Moreover,in multiobjective optimization,phenotype-based measures are more useful,because in this case,the goal is to?nd several nondominated solutions.In the following,we categorize and summarize the work using genotype and phenotype measures,respectively.These studies discuss population diversity in a qualitative manner,whilst Leung et al.[1997] provided quantitative analyses of population diversity.Their analyses revealed that to prevent premature convergence,increases in population size are more important than the role of variation regarding mutation probability.In Section3.1.3,we will use different diversity measures to de?ne neighborhood relationships,which are needed to delimit exploration from exploitation.
3.1.1.Genotype Measures.We classi?ed genotypic diversity measures into the following.
—Difference-based.Numerous measures can be classi?ed into this group—from count-ing different genotypes[Langdon1998]and counting differently activated neurons representing particular search regions[Amor and Rettinger2005],to counting fre-quencies of alleles[De Jong1975;D’haeseleer and Bluming1994].Two early mea-sures of allele frequencies proposed by De Jong[1975]are lost alleles and converged alleles.McPhee and Hopper[1999]proposed a simple measure,namely the number of different nodes in GP,and compared it with ancestry-based measures.The latter approach was extended to subtree variety measures in GP[Burke et al.2002],which are the ratios of unique subtrees to total subtrees.
—Distance-based.This is probably the most widely used type of diversity measure nowadays.Various distances are taken into account:Hamming distance,Minkowski distance(Euclidean distance and Manhattan distance are special cases),cosine dis-tance of similarity[Fister et al.2010],edit distance[De Jong et al.2001],distance to average point[Ursem2002],to name a few.One of the?rst such measures to monitor population diversity was proposed by Whitley and Starkweather[1990],where the Hamming distance between the best and worst individuals is calculated.In diver-sity control oriented genetic algorithms(DCGA)[Shimodaira1997],the Hamming distance between the best individual and candidates that determines candidates’selection pressure has been utilized,and more exploration or exploitation can be de-termined accordingly.Genotypical-forking GA,as proposed by Tsutsui et al.[1997a], also utilizes canonical Hamming distance as one of the conditions for performing forking.McGinley et al.[2011]employed Euclidean distance to adaptively control mutation and crossover rates.Additionally,healthy population diversity(HPD)is proposed for controlling selection pressure.Each individual is weighed—expressed by its?tness proportion to total?tness—when computing Euclidean distance so that more?t and diverse individuals may be selected.
—Entropy-based.Entropy is a very succinct measure for diversity which is gaining popularity.It represents the amount of population disorder,where increase in entropy represents increase in diversity.An additional bene?t over previous approaches is that the distribution of values is also included within this measure,albeit the precise distribution is unknown.Entropy was shown to be a useful measure for genotypic diversity[Li et al.2004;Liu et al.2007;Masisi et al.2008;Miseviˇc ius2011].
Exploration and Exploitation in Evolutionary Algorithms35:11—Probability-based.Simpson’s diversity index falls into this group,which is often used to quantify the biodiversity of a habitat in ecology.It takes into account the number of species present,as well as the abundance of each species.Simpson’s diversity index
D measures the probability of whether two individuals,randomly selected from a sample,belong to the same species.D=0denotes that the diversity of a population is in?nite,and conversely D=1denotes no diversity.Simpson’s diversity index has been recently applied in EAs[Masisi et al.2008;Paenke et al.2009].
—Ancestry(History)-based.Diversity measure is obtained by contrasting the current population with those populations of previous generations,hence taking into ac-count ancestries or history.McPhee and Hopper[1999]proposed several techniques for measuring population diversity based on genetic history.They noticed that an indicator of genetic diversity in the?nal population can be the number of individuals from the initial population that contributed genetic materials to the?nal population. They found that this number is extremely low in GP.Moreover,they found that in 90%of their runs,there was a single individual who was the root ancestor of ev-ery individual within the?nal population.In most cases,this leads to premature convergence.
3.1.2.Phenotype Measures.We classify phenotypic diversity measures into the following.
—Difference-based.The simplest difference-based diversity measure is the number of different phenotypes[Rosca1995].This measure can be easily extended to count different numbers of classes/ranks,where similar?tness values conform to the same class/rank producing histograms[Hutter and Legg2006].Luerssen[2005]proposed different ranking techniques,such as mean rank difference,mean rank difference across?tness cases,and mean rank difference across?tness cases for nondominated solutions.Luerssen reported that difference-based measures were overall signi?-cantly more effective than distance-based measures on his set of problems.Another example of a difference-based measurement is to count the number of individuals within the neighborhood hypercube,as used in phenotypic forking GA introduced by Tsutsui et al.[1997a].
—Distance-based.Various distance measures(e.g.,Euclidian distance)can be used to?nd similarity between individuals within a population.For example,average distance to other individuals within a population is particularly popular in MOEAs, where the average distance between the nondominated solutions to the true Pareto front has been used[Zitzler et al.2000],or similarly,a distance between an individual and a nondominated individual[Chaiyaratana et al.2007].Adra and Fleming[2011] also introduced a diversity indicator(I s),which is the normalization measurement of the Euclidean distance of“the diagonal of the hypercube with vertices set to the extreme objective values observed in the achieved approximation set”with respect to the optimal spread.Another example was presented in Ursem[2002],where the distance to average-point was used.Distances can also be computed as differences in ranks in order to reduce any bias caused by a speci?c?tness function.—Entropy-based.Entropy as a measure of diversity was?rst proposed by Rosca[1995] and since then has mainly been used as a succinct measure of phenotypic diversity [Burke et al.2004;Liu et al.2009].
—Probability-based.Simpson’s diversity measure can also be applied to phenotypic diversity[Paenke et al.2009].
Note that under phenotypic diversity measures,the ancestry(history)-based classi?-cation has been omitted.To the best of our knowledge,no such measures currently exist.
35:12M.ˇCrepinˇs ek,et al.
3.1.3.De?nition of Exploration and Exploitation by Diversity/Similarity.Despite the fact that many researchers in their works have frequently mentioned exploration and exploita-tion,to date,both processes have never been formally de?ned.Often informal and somewhat vague de?nitions of exploration and exploitation processes have been used, similar to the informal de?nitions in Section1,where exploration was de?ned as the process of visiting entirely new regions of a search space,whilst exploitation was de?ned as the process of visiting those regions of a search space within the neighbor-hood of previously visited https://www.wendangku.net/doc/e012739641.html,ing different genotype and phenotype diversity measurements,as de?ned in Section3,we are now able to de?ne both processes,explo-ration and exploitation,in a sound manner.Let d(·,·)denote the diversity/similarity measurements between two individuals within a population P.Formally,d is a func-tion P×P→R measuring the similarities between two individuals at genotype or at phenotype levels(see Sections3.1and3.2).
An example of computing similarity between two individuals x and y within a Euclidian space R n is the Euclidian distance d E.This is an example of a distance-based
measurement.
d E(x,y)=
n
i=1
(x i?y i)2.(1)
Yet another example of computing similarity between two individuals x and y using
the difference-based measurement d R is
d R(x,y)=
1if R x=R y,
0otherwise,
(2)
where two individuals x and y belong to the class/rank R x and R y,respectively. Crucial for delimiting exploration from exploitation is a de?nition of similarity to the closest neighbor SCN.However,when a new individual ind ne w is created,a similarity measurement to the closest neighbor SCN can be de?ned in several ways.
—As a similarity to its parent(s),ind parent.
—As a similarity to the most similar individual within the whole population P.—As a similarity to the most similar individual in the subpopulation P ∧(P ?P) (e.g.,only to individuals which belong to the same niche).
—As a similarity to the most similar individual throughout the history of populations {P t|t=0..current gen},where P t denotes a population within a generation t.
In the?rst case,similarity to the closest neighbor SCN can be de?ned as follows.
SCN(ind ne w,P)=d(ind ne w,ind parent),where ind parent∈P.(3)
If two or more parents(ind parent
i ,i=1..k∧k>1)are used for creating a new
individual,then ind parent is the most similar contributing parent.
ind parent=ind parent i w ith min d(ind ne w,ind parent i).
i=1..k
(4) In the second case,similarity to the closest neighbor SCN can be de?ned as follows.
SCN(ind ne w,P)=min d(ind ne w,ind).
ind∈P
ind ne w=ind.
(5) In the third case,similarity to the closest neighbor SCN can be de?ned as follows.
SCN(ind ne w,P )=min d(ind ne w,ind).
ind∈P ∧(P ?P)
ind ne w=ind.
(6)
Exploration and Exploitation in Evolutionary Algorithms 35:13In the fourth case,similarity to the closest neighbor SCN can be de?ned as follows.SCN ind ne w ,P t =min d ind ne w ,ind .ind ∈P t ,t =0..current gen
ind ne w =ind
(7)Note that in the ?rst case,we are only looking for similarity to the closest parent,whilst in the second and the third cases,the whole population or subpopulation is taken into account.According to the informal de?nition of exploitation,where visiting is within the neighborhood of previously visited points (e.g.,not only from current contributing parent(s)or within a current population),the fourth de?nition of SCN seems to be the most appropriate.
Finally ,the process of exploration happens when SCN (ind ne w ,P )>X ,where X is a threshold value that de?nes the boundary of the neighborhood of the closest neighbor and is problem-dependent.In other words,the exploration process visits points which are outside of the current neighborhood of the closest neighbor.Similarly ,the process of exploitation happens when SCN (ind ne w ,P )≤X .
SCN (ind ne w ,P )>X
(exploration);(8)SCN (ind ne w ,P )≤X (exploitation).(9)
4.CLASSIFICATION OF CURRENT APPROACHES FOR BALANCING BETWEEN
EXPLORATION AND EXPLOITATION
The diversity of a population has already been recognized as one of the important fac-tors from the early years of EAs.From the exploration and exploitation viewpoints,an increase in diversity indicated that EA was in the phase of exploration,whilst a de-crease in diversity indicated that EA was in the phase of exploitation.The relationship between exploration and diversity is indeed profound,and the exploration operators can also be de?ned as those that allow for maintaining the diversity of the population
[Soza et al.2011].One of the simplest methods for achieving a good balance between exploration and exploitation is to maintain a diverse population.However,a diverse population is simply a prerequisite for a good balance between exploration and exploita-tion rather than a guarantee.For previously mentioned reasons,our classi?cation is heavily based on diversity ,although balance between exploration and exploitation can also be achieved by other means.The simplest one is ?tness.A number of approaches utilize ?tness to indirectly guide exploration and exploitation.For example,the 1/5success rule uses ?tness to determine whether an individual has mutated successfully and then decides if the mutation rate needs to be changed.On the other hand,in such cases,diversity is frequently included in the individual’s ?tness,and the boundary between both approaches becomes blurred.
We classify the current approaches regarding the balance between exploration and exploitation into achieving exploration and exploitation balance through diversity maintenance,through diversity control,diversity learning,and other more direct ap-proaches.Whilst the former three groups are primarily interested in population di-versity and hence only implicitly address exploration and exploitation,the last group more directly tackles the problem of balance between exploration and exploitation.This classi?cation is also presented in Figure 1,whilst Table I chronologically presents the cited papers.
4.1.Achieving Exploration and Exploitation Balance through Diversity Maintenance
In this section,our focus is on maintaining diversity through different techniques.In-stead of measuring diversity and using this measure as feedback for further enhanced
35:14M.ˇCrepinˇs ek,et al.
maintaining
through selection through crossover/mutation through changing population cultural learning self-organizing maps binary space partitioning trees estimation of distribution using different subpopulations for exploration and exploitation triggers cause alternation between exploration and exploitation
Approaches for controlling exploration and exploitation balance through diversity
fitness-based replacement-based
niching deterministic crowding probabilistic crowding restricted tournament selection
explicit and implicit fitness sharing clearing modified clearing clustering
species conserving GA
preservation-based
hybrid
controlling
learning other direct approaches
population-based selection-based
crossover/mutation-based
non-niching
changing selection pressure replacement restrictions
varying population size duplicate elimination infusion techniques external archives migration between subpopulations
mating restrictions disruptive operators hybrid ancestry-based Fig.1.Current approaches to balancing exploration and exploitation.
diversity ,and to improve the balance between exploration and exploitation,it is simply assumed that the proposed techniques will maintain diversity per se,and hence the balance between exploration and exploitation will be achieved.However,it is dif?cult to determine a useful amount of diversity .High diversity is needed to escape from local optima,whilst low diversity is needed to ?ne-tune the solutions.Numerous different methods,developed mostly in the 1990s,have been used for diversity maintenance.Mahfoud’s study was one of the ?rst towards a comprehensive theory of diversity for GAs [Mahfoud 1995],where methods were classi?ed as non-niching and niching.Both non-niching and niching methods are able to maintain a population of diverse individuals,whilst niching methods are also capable of locating multiple optimal solutions.Since this classi?cation also appears in other work (e.g.,[Toffolo and Benini
Exploration and Exploitation in Evolutionary Algorithms35:15
T able I.Classi?cation of the Cited Work in Chronological Order
Maintenance(Non-niching)
Population-based[Mauldin1984;Grefenstette1992;Koza1992;Ramsey and Grefenstette
1993;McPhee and Hopper1999;Greenwood et al.1999;Martin et al.
1999;Zitzler and Thiele1999;Krink et al.2000;Ursem2000;Zitzler et al.
2000;Leung and Wang2001;Bosman and Thierens2003;Koumousis and
Katsaras2006;Chaiyaratana et al.2007;Gong et al.2008;Rahnamayan
et al.2008;Yang2008;Zhang and Sanderson2009;Araujo and Merelo
2011;Jia et al.2011;Li and Wang2011;Wang et al.2012]
Selection-based[De Jong1975;Grefenstette1986;Michalewicz1996;Gen and Cheng1997;
Matsui1999;Hutter and Legg2006;Lozano et al.2008;Chen et al.2009] Crossover/Mutation-based[Deb and Goldberg1989;Eshelman and Schaffer1991;Eshelman1991;
De Jong and Spears1992;Cobb and Grefenstette1993;Ronald1995;
Joan-Arinyo et al.2011]
Hybrid[Ghosh et al.1996;Harik et al.1999;Paenke et al.2009;Qin et al.2009;
Lee et al.2011;Mallipeddi et al.2011]
Maintenance(Niching)
Fitness-based[Holland1975;Goldberg and Richardson1987;Smith et al.1993;Yin and
Germay1993;Petrowski1996;Singh and Deb2006]
Replacement-based[Mahfoud1995;Harik1995;Mengshoel and Goldberg1999] Preservation-based[Li et al.2002]
Hybrid[Yu and Suganthan2010;Liang and Leung2011]
Controlling
Through selection[Mori et al.1995;Shimodaira1997;Bersano-Begey1997;Bosman and
Thierens2003;Wong et al.2003;Chaiyaratana et al.2007;Adra and
Fleming2011;McGinley et al.2011]
Through crossover and mutation [Whitley and Starkweather1990;Srinivas and Patnaik1994;Wong et al. 2003;Li et al.2004;Jose-Revuelta2007;McGinley et al.2011]
Through changing
population
[Rosca1995;Tsujimura and Gen1998;Liu et al.2009]
Learning
Cultural learning[Jin and Reynolds1999;Curran and O’Riordan2006;Becerra and Coello
Coello2006;Soza et al.2011]
Self-organizing maps[Amor and Rettinger2005]
Binary space-partition-
ing tree
[Yuen and Chow2009;Chow and Yuen2011]
Estimation of distribution[M¨uhlenbein and Paa?1996]
Other Direct Approaches
Using different
sub-populations for exploration and exploitation [Tsutsui et al.1997b,1997a;Oppacher and Wineberg1999;Goh et al. 2003]
triggers cause alternation between exploration and exploitation [Hart1994;Freisleben and Merz1996;Moscato1999;Merz and Freisleben 2000;Ursem2002;Ishibuchi et al.2003,2010a;Alba and Dorronsoro2005; Krasnogor and Smith2005;Ong et al.2006;Miseviˇc ius and Rubliauskas 2008;Nguyen et al.2009;Liao2010;Blum et al.2011;Mashinchi et al. 2011;Lin and Chen2011;Mongus et al.2012]
Ancestry-based[ˇCrepinˇs ek et al.2011]
2003;Zitzler and Thiele1999]),this article adopts it.This article further classi?es non-niching methods into the following.
—Population-based.Diversity is achieved by varying population size,duplicate elimi-nation,infusion techniques,external archives,or migration between subpopulations.—Selection-based.Diversity is achieved by changing selection pressure or replacement restrictions.
35:16M.ˇCrepinˇs ek,et al.—Crossover/mutation-based.Diversity is achieved by mating restrictions or disruptive operators.
—Hybrid.Diversity is achieved by ensembles or other speci?c approaches.
Brief descriptions of non-niching methods are shown as follows.
—Increasing population size.It is among the simplest approaches,but several studies (e.g.,[McPhee and Hopper1999])reported that increasing population size does not always lead to correspondingly increased diversity.
—Duplicate elimination.By using this approach,an individual that already exists in a population is eliminated,and another randomly generated individual is in-serted.Duplicate elimination is an important part of the algorithms presented in Chaiyaratana et al.[2007].An improvement in duplicate elimination is the uniqueness-assurance method by Mauldin[1984],where individuals,instead of be-ing eliminated,are mutated as long as they become suf?ciently different(at least for k bits,where k is decreasing over generations).Hence,this approach can also be regarded as an example of infusion,which is described next.
—Infusion techniques.New individuals are randomly inserted after a certain number of generations or special initialization techniques are used(e.g.,chaotic initializa-tion[Li and Wang2011],orthogonal design[Leung and Wang2001]).The former approach is also called reseeding or extinction[Greenwood et al.1999;Krink et al. 2000].An early approach is Grefenstette’s random immigrants approach[1992], where random individuals are inserted into the population every generation.Koza [1992]introduced decimation,where a substantial percentage of a population has been replaced by random individuals at regular intervals.Reinitialization has been proven successful in dynamic and changing environments,where the re-seeding of good individuals from past cases has been proposed every150generations[Ramsey and Grefenstette1993].Koumousis and Katsaras[2006]proposed a Saw-Tooth GA with periodic reinitialization and variable population sizes achieving better population diversity and overall performance.Rahnamayan et al.[2008],instead of inserting random individuals,recently proposed the concept of opposition,inserting opposite individuals for diversity maintenance.A more sophisticated approach is presented by Jia et al.[2011],where a chaotic local search was proposed.Since local search may result in premature convergence,the authors enhanced diversity and hence exploration abilities by chaotic random local search,where the search space of the chaotic local search shrinks with the growth of the function evaluations. Orthogonal crossover[Leung and Wang2001],which is based on orthogonal design, can also be seen as a systematic and rational local search maintaining a diversity of population[Gong et al.2008;Wang et al.2012].If replacement is done as a response to a lack of progress or a change in a dynamic environment,then these techniques can be classi?ed as diversity control(as described in the next section).Yang[2008] recently proposed new immigrant schemes—memory-based and elitism-based immigrants—for dynamic optimization problems using historical information.—External archives.External archives have been also used as a diversi?cation technique.Whilst archives in EMO have been used primarily for keeping track of nondominated solutions[Zitzler and Thiele1999;Zitzler et al.2000;Bosman and Thierens2003]and inherently maintaining a diverse population,there have also been some other proposals for using external archives during single-objective optimization.For example,Zhang and Sanderson[2009]also used external archives to maintain diverse population by archiving recently explored inferior solutions.—Migration between subpopulations(islands).Many(parallel)GAs introduce diversity and prevent premature stagnation by simply exchanging individuals between sub-populations.Migrants can replace less?t individuals,randomly chosen individuals,
Exploration and Exploitation in Evolutionary Algorithms35:17 or the most similar individuals,etc.The main idea behind this approach is that differ-ent subpopulations can maintain different promising regions of the search space and hence maintain diversity[Martin et al.1999].The dynamics of exploration and ex-ploitation are further in?uenced by the number of subpopulations,the sizes of these subpopulations,differences in subpopulation interconnections(often referred to as communication topology),frequency of communication(epoch length),and the qual-ity of the migrants.Ursem[2000]proposed a multinational genetic algorithm(MGA), where subpopulations,called nations,are self-formed based on a hill-valley detection algorithm.A nation consists of a population,government(?ttest individuals),and policy(point in the search space to which a nation is approaching).The hill-valley detection is responsible for the migration of individuals among nations,the creation of new nations within unexplored regions,and the merging of nations if they have the same policy.Ursem showed that diversity maintenance in MGA could lead to better performance and the ability to track multiple peaks simultaneously,and as such, could also be regarded as a niching method.Araujo and Merelo[2011]introduced a MultiKulti algorithm,where subpopulations are constructed as a ring topology, and migrations will only occur between neighboring subpopulations.Migrants are selected from a subpopulation if they possess the most different genotype(s)from the selected representative of the receiving/neighboring subpopulation,where either the best individual or the consensus sequence(i.e.,the sequence that re?ects the most common base or amino acid found at each position in a genome[Watson et al. 2004])is picked as the representative.Araujo and Merelo showed that such selection policies and topology increased the diversity and outperformed nonadaptive random and best-individual migration policies on two discrete optimization problems.—Changing selection pressure.Many techniques have been proposed to prevent selec-tion being biased towards highly?t individuals.Two of the simplest techniques are ranking selection[Michalewicz1996]and scaling[Grefenstette1986].Some more sophisticated selection mechanisms that try to ensure that the?ttest individual will not always be selected and the weakest individual not always rejected are brie?y described next.Matsui[1999]proposed two selection methods—correlative tour-nament selection and correlative family-based selection—for improving population diversity.Hutter and Legg[2006]maintained genetic diversity in terms of?tness diversity.Fitness values are divided into several classes,and each class has an equal opportunity of survival and hence preserving diversity through selection.Chen et al.[2009]recently proposed several different selection schemes(e.g.,integrating power-law distribution and tournament selection)to enhance population diversity in EP.On the other hand,if the search needs to be more exploitative,elitist strategies are often employed[Gen and Cheng1997].
—Replacement restrictions.De Jong introduced crowding[1975],called standard crowding,to maintain diversity.Each newly generated individual replaces the most similar existing individual from a random subpopulation of size C F(the crowding factor).Lozano et al.[2008]proposed a hybrid replacement scheme where individuals of poor?tness and low contribution to diversity are replaced,thereby promoting exploitation(highly?t individuals)and exploration(high contribution to diversity).Both objectives,that is,optimizing?tness function and enhancing population diversity,are ful?lled in this manner.
—Mating restrictions.Individuals are allowed to mate if they ful?ll special conditions.
A typical example is incest prevention[Eshelman and Schaffer1991].Ronald [1995]introduced genders into mating,where selection of the second mate is based on a seduction function between the?rst and second mates.Deb and Goldberg’s [1989]mating restrictions,where individuals are allowed to mate only if they are suf?ciently distinct,also fall into this category.
35:18M.ˇCrepinˇs ek,et al.—Disruptive operators.Until now,several disruptive operators have been proposed which address diversity issues explicitly.A prime example is the hyper-mutation operator[Eshelman1991;Cobb and Grefenstette1993;Joan-Arinyo et al.2011]. However,De Jong and Spears[1992]pointed out that disruption does not necessarily imply useful exploration.
—Hybrid approaches.There are some other approaches that can not be easily classi?ed into the aforementioned classes.This is due to the use of unconventional concepts (e.g.,concepts of age and compact GA)or blending different approaches(e.g., ensembles[Mallipeddi et al.2011]).Inevitably,there may be some approaches we have missed.Gosh et al.[1996]developed an aging genetic algorithm(aGA),where the concept of age for an individual is included into the?tness function as well as into mating.As in nature,adult individuals are considered more?t for mating.On a given problem,Gosh et al.reported that aGA maintains more diversity in the population,whilst its performance has also been improved.Paenke et al.[2009] showed that longer individual lifetime slows down the genotypic diversity loss.The compact genetic algorithm(cGA)[Harik et al.1999]used a probability vector for current population in order to obtain offspring.An element of probability,vector p v i denotes a probability to assign1to the i th gene of an individual.Diversity is simply
achieved by increasing/decreasing p v i by1
pop size .Lee et al.[2011]extend cGA with
belief vectors,where each element has probability distribution with a mean and a variance.Diversity is adaptively controlled by calculating entropy and updating the variance of a belief vector.The SaDE algorithm[Qin et al.2009]attempted to maintain a good balance between exploitation and exploration by choosing different strategies in differential evolution(DE)[Storn and Price1997](e.g.,DE/rand/1/bin, DE/best/1/bin)for each individual.Authors have taken advantage of the fact that different strategies have different exploration/exploitation capabilities.
On the other hand,niching methods promote the formation and maintenance of sta-ble subpopulations within the neighborhood of optimal solutions,thereby achieving a population diversity.Niching methods have already been well studied,and readers are referred to Mahfoud[1995]and Sareni and Kr¨ahenb¨uhl[1998]for more information. We have classi?ed niching methods into the following.
—Fitness-based.Fitness sharing(explicit[Goldberg and Richardson1987;Holland 1975]and implicit[Smith et al.1993]),clearing[Petrowski1996],modi?ed clearing [Singh and Deb2006],clustering[Yin and Germay1993].
—Replacement-based.Deterministic crowding[Mahfoud1995],probabilistic crowding [Mengshoel and Goldberg1999],restricted tournament selection[Harik1995].—Preservation-based.Species conserving GA[Li et al.2002].
—Hybrid.Adaptive elitist-population based GA[Liang and Leung2011],ensemble of niching algorithms[Yu and Suganthan2010].
Although most work done using non-niching and niching methods simply expects an increase in diversity and hence better balance between exploration and exploitation, not all diversi?cation is useful.In this respect,niching methods can be regarded as stronger diversi?cation methods[Friedrich et al.2008].There are only a few theoret-ical works on diversity mechanisms,and we would like to mention the following.De Jong and Spears[1992]provided the theoretical analysis of crossover operator(multi-point crossover vs.uniform crossover)with respect to disruptive effect,recombination potential,and exploratory power.Friedrich et al.[2007]provided a rigorous analysis of simple diversi?cation mechanisms(duplicate elimination at genotype and pheno-type levels)and analyzed it with respect to the runtime behaviour of an EA,whilst Storch[2004]analyzed duplicate elimination with respect to population size.Friedrich
Exploration and Exploitation in Evolutionary Algorithms35:19 et al.[2008]also provided the theoretical analysis of niching methods(?tness sharing and deterministic crowding)on simple bimodal functions.They rigorously proved that without any diversi?cation method or when only genotype/phenotype duplicate elimi-nation is used in(μ+1)EA,is the probability of being trapped into local optima almost
1 2,whilst the probability of?nding both optima using?tness sharing or deterministic
crowding is very high.
It is worth mentioning that diversity maintenance is very important to EMO[Smith et al.1993;Toffolo and Benini2003;Zitzler and Thiele1999].For example,in order to maintain the diversity among nondominated solutions,Zitzler et al.[2002]proposed the k-nearest neighbor clustering technique.Zitzler et al.noticed that not only the average distance between the nondominated solutions to the true Pareto front is important,but also the distribution of the nondominated solutions.
4.2.Achieving Exploration and Exploitation Balance through Diversity Control
The main difference between diversity maintenance and diversity control is that in the latter case,population diversity,individual?tness,and/or?tness improvements are measured and used as a feedback to steer an evolution process towards exploration or exploitation.We classify different approaches based on the process/operator responsible for diversi?cation.Another possibility would be to take into account how population diversity is measured(genotypic or phenotypic diversity measures,see Section3).—Diversity is controlled and preserved through selection.Survival probability can be computed based on population diversity,or diversity can be included within those ?tness functions that further drive the selection process.Several approaches fall into this category,and we mention the following.Mori et al.[1995]proposed a thermo-dynamical genetic algorithm(TDGA),which adopts the concept of temperature and entropy within the selection rule for better control of population diversity.Shimodaira [1997]proposed a diversity-control-oriented genetic algorithm(DCGA),where indi-viduals that are farther from the best individual,but which always survive,have higher survival probabilities.Chaiyaratana et al.[2007]proposed a modi?ed DCGA, where survival probability depends on similarity at the phenotype level.Wong et al. [2003]controlled population diversity by repelling population from the representa-tive one.This was achieved by including diversity within a?tness function.In such a manner,individuals with rare alleles would be?tter,and the survival probabilities of such individuals would be increased.Bersano-Begey[1997]also controlled diversity through a?tness function,which keeps track of how many individuals have solved a particular?tness case.In this manner,it is possible to detect when the population is locked in on a partial solution.This approach can be augmented by tracking over how many generations this situation has persisted.McGinley et al.[2011]introduced healthy population diversity as feedback to adaptively controlled selection pressure through tournament size,in order to avoid premature convergence or exploitation from the same cluster of highly?tted individuals continuously.Adra and Fleming [2011]employed the diversity indicator(I s)mentioned in Section3.1.2to activate a diversity mechanism for further improving the performance of NSGA-II in terms of convergence and diversity.Binary tournament selection with random tie breaking will be inactive if I s<1so that“the exploitation of diversity should not precede the exploitation of proximity”[Bosman and Thierens2003].
—Diversity is controlled through crossover and mutation.This is an easy and natural way to control diversity.Hence,the majority of approaches fall into this category. The idea is to increase/decrease the probability of crossover and/or mutation after population diversity,?tness,and/or?tness improvements are computed.Approaches differ from each other mainly on how diversity is computed:explicitly by different
35:20M.ˇCrepinˇs ek,et al. diversity measures(see Section3)and/or implicitly by?tness or?tness improve-ments.Selected approaches are described as follows.Whitley and Starkweather [1990]applied the adaptive probability of mutation based on Hamming distance in order to sustain population diversity.Srinivas and Patnaik[1994]proposed an adaptive genetic algorithm(AGA),where the adaptive probabilities of mutation and crossover are used to control the diversity of the population and to achieve good con-vergence.The probabilities of crossover and mutation are based on the?tness values of individuals,and in order to achieve balance between exploration and exploitation, they increase the probabilities of mutation and crossover when the population tends to get stuck at local optima,and decrease the probabilities when the population is scattered within the search space.The PRAM algorithm[Wong et al.2003]adapted the probabilities of crossover and mutation in order to determine an appropriate balance between exploration and exploitation.Based on?tness improvement,they used a set of greedy rules(e.g.,expand rule,stay rule,left move rule,and right move rule)to adapt control parameters.Another example is the diversity-guided microgenetic algorithm(DGμGA)[Jose-Revuelta2007],where a?tness-proportional entropy-based diversity measure is used to guide genetic algorithms.The authors correctly recognized that high entropy can be obtained when a population is diverse but far from global optima(usually at the beginning stage),and when a population is diverse but close to global optima(at the latest stage).This phenomenon is called entropy ambiguity.In order to eliminate such a phenomenon,the authors used an additional measure—how fast the convergence occurs—expressed as an average mean value of individuals’?tness over k successive generations.When convergence is unsatisfactory,the whole population is randomly reinitialized.Li et al.[2004]proposed the adaptive genetic algorithm with diversity-guided mutation and crossover(AGAD),where mutation and crossover probabilities are adaptively controlled by diversity measures based on entropy.Note that McGinley et al.[2011] (categorized in the previous group)also utilized Euclidean distance to adaptively control mutation and crossover rates,respectively,for exploration and exploitation.—Diversity is controlled through a changing population.After measuring population diversity,either the population size or the population alone is changed.Not many approaches fall into this category.Liu et al.[2009]presented an entropy-based exploration and exploitation approach for controlling an evolution process.It tends toward exploration when entropy is low and tends toward exploitation when entropy is high.Linear,Gaussian,?tness proportional,and cluster entropies were introduced by extending Rosca’s entropy[Rosca1995].The extension was done by rede?ning how individuals are classi?ed into different entropy classes,and whether the class boundaries are changed adaptively or self-adaptively.Despite the fact that this approach mainly adapts the probabilities of mutation and crossover,some experiments also adaptively changed population size.Tsujimura and Gen proposed an entropy-based genetic algorithm(EBGA)[1998],where the diversity of loci is measured by entropy.When the population diversity is too low,the diversity is improved by swapping loci with low entropy values.
4.3.Achieving Exploration and Exploitation Balance through Diversity Learning
The main difference between diversity control and diversity learning is that,in the former case,short-term history(e.g.,current population)is often used during diversity computation,whilst,in the latter case,long-term history is used in combination with different machine learning techniques to learn(un)explored search areas.The history of a population has also been an important criterion for the classi?cation of EAs in Calegary et al.[1999].Nevertheless,diversity learning approaches are rarely proposed, and currently researchers are using cultural learning,self-organizing maps,binary