Backward-chaining Evolutionary Algorithms
Created by W.Langdon from
gp-bibliography.bib Revision:1.7954
- @Article{poli_2006_AIJ,
-
author = "Riccardo Poli and William B. Langdon",
-
title = "Backward-chaining Evolutionary Algorithms",
-
journal = "Artificial Intelligence",
-
year = "2006",
-
volume = "170",
-
number = "11",
-
pages = "953--982",
-
month = aug,
-
keywords = "genetic algorithms, genetic programming, Evolutionary
Algorithms, Selection, Theory, Backward-chaining,
Rule-based Systems, Efficient Algorithms, Tournament
selection",
-
URL = "http://www.cs.essex.ac.uk/staff/poli/papers/aijournal2006.pdf",
-
URL = "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/poli_2006_AIJ.pdf",
-
DOI = "doi:10.1016/j.artint.2006.04.003",
-
size = "49 pages",
-
abstract = "Starting from some simple observations on a popular
selection method in Evolutionary Algorithms (EAs) --
tournament selection -- we highlight a common source of
inefficiency. We propose the iterated coupon collection
problem and describe its connection to tournament
selection. We use Markov chain theory to solve the
iterated coupon collection problem and show how this
enables us to evaluate the savings that could be
achieved in EAs. This leads us to rethink the order in
which operations are performed within EAs, and to
suggest an algorithm -- the EA with efficient
macro-selection -- that avoids the inefficiencies
associated with tournament selection. This algorithm
has the same expected behaviour as the standard EA but
yields considerable savings in terms of fitness
evaluations. Since fitness evaluations typically
dominates the resources needed to solve any non-trivial
problem, these savings translate into a reduction in
computer time. Noting the connection between the
algorithm and rule-based systems, we then further
modify the order of operations in the EA, effectively
turning the evolutionary search into an inference
process operating in backward-chaining mode. The
resulting backward-chaining EA, creates and evaluates
individuals recursively, backward from the last
generation to the first, using depth-first search and
backtracking. It is even more powerful than the EA with
efficient macro-selection in that it shares all its
benefits, but it also provably finds fitter solutions
sooner, i.e., it is a faster algorithm. These
algorithms can be applied to any form of population
based search, any representation, fitness function,
crossover and mutation, provided they use tournament
selection. We have applied them to genetic algorithms
and genetic programming. This is one of the rare cases
where EA theory precedes implementation.",
- }
Genetic Programming entries for
Riccardo Poli
William B Langdon
Citations