Backward-chaining Evolutionary Algorithms

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  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
  URL =          "",
  URL =          "",
  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