Fitness-probability cloud and a measure of problem hardness for evolutionary algorithms

Guanzhou LU, Jinlong LI, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

37 Citations (Scopus)

Abstract

Evolvability is an important feature directly related to problem hardness for Evolutionary Algorithms (EAs). A general relationship that holds for Evolvability and problem hardness is the higher the degree of evolvability, the easier the problem is for EAs. This paper presents, for the first time, the concept of Fitness-Probability Cloud (fpc) to characterise evolvability from the point of view of escape probability and fitness correlation. Furthermore, a numerical measure called Accumulated Escape Probability (aep) based on fpc is proposed to quantify this feature, and therefore problem difficulty. To illustrate the effectiveness of our approach, we apply it to four test problems: OneMax, Trap, OneMix and Subset Sum. We then contrast the predictions made by the aep to the actual performance measured using the number of fitness evaluations. The results suggest that the new measure can reliably indicate problem hardness for EAs. © 2011 Springer-Verlag.
Original languageEnglish
Title of host publicationEvolutionary Computation in Combinatorial Optimization : 11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011, Proceedings
EditorsPeter MERZ, Jin-Kao HAO
PublisherSpringer Berlin Heidelberg
Pages108-117
Number of pages10
ISBN (Electronic)9783642203640
ISBN (Print)9783642203633
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event11th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2011 - Torino, Italy
Duration: 27 Apr 201129 Apr 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
Volume6622
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2011
Country/TerritoryItaly
CityTorino
Period27/04/1129/04/11

Keywords

  • Search Space
  • Evolutionary Algorithm
  • Test Problem
  • Problem Instance
  • Actual Performance

Fingerprint

Dive into the research topics of 'Fitness-probability cloud and a measure of problem hardness for evolutionary algorithms'. Together they form a unique fingerprint.

Cite this