Innocent Until Proven Guilty: Reducing Robot Shaping from Polynomial to Linear Time

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

  author =       "Josh C. Bongard",
  title =        "Innocent Until Proven Guilty: Reducing Robot Shaping
                 from Polynomial to Linear Time",
  journal =      "IEEE Transactions on Evolutionary Computation",
  year =         "2011",
  volume =       "15",
  number =       "4",
  pages =        "571--585",
  month =        aug,
  keywords =     "genetic algorithms, genetic programming, Early
                 stopping, Evolutionary computation, Joints,
                 Manipulators, Neurons, Robot sensing systems,
                 evolutionary robotics",
  ISSN =         "1089-778X",
  DOI =          "doi:10.1109/TEVC.2010.2096540",
  abstract =     "In evolutionary algorithms, much time is spent
                 evaluating inferior phenotypes that produce no
                 offspring. A common heuristic to address this
                 inefficiency is to stop evaluations early if they hold
                 little promise of attaining high fitness. However, the
                 form of this heuristic is typically dependent on the
                 fitness function used, and there is a danger of
                 prematurely stopping evaluation of a phenotype that may
                 have recovered in the remainder of the evaluation
                 period. Here a stopping method is introduced that
                 gradually reduces fitness over the phenotype's
                 evaluation, rather than accumulating fitness. This
                 method is independent of the fitness function used,
                 only stops those phenotypes that are guaranteed to
                 become inferior to the current offspring-producing
                 phenotypes, and realises significant time savings
                 across several evolutionary robotics tasks. It was
                 found that for many tasks, time complexity was reduced
                 from polynomial to sublinear time, and time savings
                 increased with the number of training instances used to
                 evaluate a phenotype as well as with task difficulty.",
  notes =        "Also known as \cite{5703121}",

Genetic Programming entries for Josh C Bongard