Fitness Uniform Deletion: A Simple Way to Preserve Diversity
Keywords: Evolutionary algorithm, deletion schemes, fitness evaluation,
optimization, fitness landscapes, (self)adaptation.
Abstract: A commonly experienced problem with population based optimisation
methods is the gradual decline in population diversity that tends
to occur over time. This can slow a system's progress or even
halt it completely if the population converges on a local optimum
from which it cannot escape. In this paper we present the Fitness
Uniform Deletion Scheme (FUDS), a simple but somewhat
unconventional approach to this problem. Under FUDS the deletion
operation is modified to only delete those individuals which are
"common" in the sense that there exist many other individuals of
similar fitness in the population. This makes it impossible for
the population to collapse to a collection of highly related
individuals with similar fitness. Our experimental results on a
range of optimisation problems confirm this, in particular for
deceptive optimisation problems the performance is significantly
more robust to variation in the selection intensity.
BibTeX Entry
@InProceedings{Hutter:05fuds,
author = "S. Legg and M. Hutter",
title = "Fitness Uniform Deletion for Robust Optimization",
booktitle = "Proc. Genetic and Evolutionary Computation Conference ({GECCO-2005})",
address = "Washington, OR",
year = "2005",
keywords = "Evolutionary algorithm, deletion schemes, fitness evaluation,
optimization, fitness landscapes, (self)adaptation.",
http = "http://www.hutter1.net/ai/fuds.htm",
url = "http://arxiv.org/abs/cs.NE/0504035",
ftp = "ftp://ftp.idsia.ch/pub/techrep/IDSIA-11-04.pdf",
abstract = "A commonly experienced problem with population based optimisation
methods is the gradual decline in population diversity that tends
to occur over time. This can slow a system's progress or even
halt it completely if the population converges on a local optimum
from which it cannot escape. In this paper we present the Fitness
Uniform Deletion Scheme (FUDS), a simple but somewhat
unconventional approach to this problem. Under FUDS the deletion
operation is modified to only delete those individuals which are
``common'' in the sense that there exist many other individuals of
similar fitness in the population. This makes it impossible for
the population to collapse to a collection of highly related
individuals with similar fitness. Our experimental results on a
range of optimisation problems confirm this, in particular for
deceptive optimisation problems the performance is significantly
more robust to variation in the selection intensity.",
}