Improving Grammatical Evolution in Santa Fe Trail using Novelty Search

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

  author =       "Paulo Urbano and Loukas Georgiou",
  title =        "Improving Grammatical Evolution in {Santa Fe} Trail
                 using Novelty Search",
  booktitle =    "Advances in Artificial Life, ECAL 2013",
  year =         "2013",
  editor =       "Pietro Lio and Orazio Miglino and Giuseppe Nicosia and 
                 Stefano Nolfi and Mario Pavone",
  series =       "Complex Adaptive Systems",
  pages =        "917--924",
  address =      "Taormina, Italy",
  month =        sep # " 2-6",
  publisher =    "MIT Press",
  keywords =     "genetic algorithms, genetic programming, Grammatical
  isbn13 =       "978-0-262-31709-2",
  DOI =          "doi:10.7551/978-0-262-31709-2-ch137",
  size =         "8 pages",
  abstract =     "Grammatical Evolution is an evolutionary algorithm
                 that can evolve complete programs using a Backus Naur
                 form grammar as a plug-in component to describe the
                 output language. An important issue of Grammatical
                 Evolution, and evolutionary computation in general, is
                 the difficulty in dealing with deceptive problems and
                 avoid premature convergence to local optima. Novelty
                 search is a recent technique, which does not use the
                 standard fitness function of evolutionary algorithms
                 but follows the gradient of behavioural diversity. It
                 has been successfully used for solving deceptive
                 problems mainly in neuro-evolutionary robotics where it
                 was originated. This work presents the first
                 application of Novelty Search in Grammatical Evolution
                 (as the search component of the later) and benchmarks
                 this novel approach in a well known deceptive problem,
                 the Santa Fe Trail. For the experiments, two grammars
                 are used: one that defines a search space semantically
                 equivalent to the original Santa Fe Trail problem as
                 defined by Koza and a second one which were widely used
                 in the Grammatical Evolution literature, but which
                 defines a biased search space. The application of
                 novelty search requires to characterise behaviour,
                 using behaviour descriptors and compare descriptions
                 using behaviour similarity metrics. The conducted
                 experiments compare the performance of standard
                 Grammatical Evolution and its Novelty Search variation
                 using four intuitive behaviour descriptors. The
                 experimental results demonstrate that Grammatical
                 Evolution with Novelty Search outperforms the
                 traditional fitness based Grammatical Evolution
                 algorithm in the Santa Fe Trail problem demonstrating a
                 higher success rates and better solutions in terms of
                 the required steps.",
  notes =        "jGE Netlogo.

Genetic Programming entries for Paulo Urbano Loukas Georgiou