Fitness Uniform Selection to Preserve Genetic Diversity
Keywords: Evolutionary algorithms, fitness uniform selection strategy,
preserve diversity, local optima, evolution, correlated recombination, crossover.
Abstract: In evolutionary algorithms, the fitness of a population increases
with time by mutating and recombining individuals and by a biased
selection of more fit individuals. The right selection pressure is
critical in ensuring sufficient optimization progress on the one
hand and in preserving genetic diversity to be able to escape from
local optima on the other. We propose a new selection scheme,
which is uniform in the fitness values. It generates selection
pressure towards sparsely populated fitness regions, not
necessarily towards higher fitness, as is the case for all other
selection schemes. We show that the new selection scheme can be
much more effective than standard selection schemes.
Table of Contents
- Introduction
- Evolutionary algorithms (EA)
- Standard selection schemes (STD)
- The problem of the right selection pressure
- The main idea
- Contents
- Fitness Uniform Selection Strategy (FUSS)
- The problem of local optima
- The fitness uniform selection scheme (FUSS)
- Asymptotically fitness uniform population
- Fitness gaps and continuous fitness
- Mutation and recombination
- Properties of Fuss
- FUSS effectively favors fit individuals
- No takeover in FUSS
- FUSS may also favor unfit individuals
- Distribution within a fitness level
- Steady creation of individuals from every fitness level
- Transformation properties of FUSS
- A Simple Example
- Simple 2D example
- Random search
- Random search with crossover
- Mutation
- Standard selection with crossover
- FUSS
- FUSS with crossover
- Simple 3D example
- Numerical results
- Recombination
- Worst case analysis without recombination
- Quadratic slowdown due to recombination
- Scale independent pair selection
- Properties of $p(f,f')$
- Continuous Fitness Functions
- Effective discretization scale
- FUSS
- Discussion
- Summary & Conclusions
BibTeX Entry
@Article{Hutter:01fuss,
author = "Marcus Hutter",
number = "IDSIA-01-01",
institution = "Istituto Dalle Molle di Studi sull'Intelligenza Artificiale",
title = "Fitness Uniform Selection to Preserve Genetic Diversity",
month = jan,
year = "2001",
pages = "13 pages",
address = "Manno(Lugano), CH",
journal = "Submitted to IEEE Transactions Evolutionary Computation",
keywords = "Evolutionary algorithms, fitness uniform selection strategy,
preserve diversity, local optima, evolution,
correlated recombination, crossover.",
url = "http://www.hutter1.net/ai/pfuss.htm",
url2 = "http://arxiv.org/abs/cs.AI/0103015",
ftp = "ftp://ftp.idsia.ch/pub/techrep/IDSIA-01-01.ps.gz",
abstract = "In evolutionary algorithms, the fitness of a population increases
with time by mutating and recombining individuals and by a biased
selection of more fit individuals. The right selection pressure is
critical in ensuring sufficient optimization progress on the one
hand and in preserving genetic diversity to be able to escape from
local optima on the other. We propose a new selection scheme,
which is uniform in the fitness values. It generates selection
pressure towards sparsely populated fitness regions, not
necessarily towards higher fitness, as is the case for all other
selection schemes. We show that the new selection scheme can be
much more effective than standard selection schemes.",
}