Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Exploration and exploitation in evolutionary algorithms: a survey
Črepinšek M., Liu S., Mernik M. ACM Computing Surveys45 (3):1-33,2013.Type:Article
Date Reviewed: Aug 21 2013

In this survey paper, the authors tackle an important issue concerning the solution of an optimization problem using search. The paper revisits almost 100 papers in connection with exploration and exploitation in evolutionary algorithms (EAs).

The paper addresses the following issues:

  • How exploration and exploitation can be achieved in EAs;
  • When and how to control exploration and exploitation; and
  • How to balance exploration and exploitation in situations driven by diversity.

It is commonly accepted that “exploration and exploitation in EAs is achieved by selection, mutation, and crossover,” but it is difficult to distinguish between exploration and exploitation within these processes. Until now, it seemed like achieving a good balance between exploration and exploitation required proper settings for control parameters and the effective representation of individuals.

Due to existing experimental studies, exploration and exploitation should be controlled online and balanced during the run. The authors classify different diversity measures at three levels: genotype, phenotype, and the composite measure. The surveyed genotype measures are based on difference, distance, entropy, probability, and history. The phenotypic diversity measures are based on difference, distance, entropy, and probability.

The authors also present different techniques for maintaining the diversity of the population: non-niching approaches (those based on population, selection, crossover, and mutation, as well as a hybrid method) and niching approaches (those based on fitness, replacement, and preservation, as well as a hybrid method). The paper identifies other techniques for achieving exploration and exploitation through diversity control, diversity learning, and direct approaches.

The paper ends with suggestions for important future research directions.

Reviewer:  Petrica Pop Review #: CR141490 (1311-1033)
Bookmark and Share
  Reviewer Selected
 
 
Heuristic Methods (I.2.8 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Heuristic Methods": Date
Embedding decision-analytic control in a learning architecture
Etzioni O. (ed) Artificial Intelligence 49(1-3): 129-159, 1991. Type: Article
Sep 1 1992
The complexity of the Lin-Kernighan heuristic for the traveling salesman problem
Papadimitriou C. SIAM Journal on Computing 21(3): 450-465, 1992. Type: Article
May 1 1993
Toward combining empirical and analytical methods for inferring heuristics
Mitchell T. (ed)  Artificial and human intelligence (, Lyon, France,1031984. Type: Proceedings
Aug 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy