Efficiently evolving programs through the search for novelty

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

@InProceedings{Lehman:2010:gecco,

• author = "Joel Lehman and Kenneth O. Stanley",
• title = "Efficiently evolving programs through the search for novelty",
• booktitle = "GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation",
• year = "2010",
• editor = "Juergen Branke and Martin Pelikan and Enrique Alba and Dirk V. Arnold and Josh Bongard and Anthony Brabazon and Juergen Branke and Martin V. Butz and Jeff Clune and Myra Cohen and Kalyanmoy Deb and Andries P Engelbrecht and Natalio Krasnogor and Julian F. Miller and Michael O'Neill and Kumara Sastry and Dirk Thierens and Jano {van Hemert} and Leonardo Vanneschi and Carsten Witt",
• isbn13 = "978-1-4503-0072-8",
• pages = "837--844",
• keywords = "genetic algorithms, genetic programming, premature convergence, program bloat, Artificial Intelligence, Learning, Novelty search",
• month = "7-11 " # jul,
• organisation = "SIGEVO",
• address = "Portland, Oregon, USA",
• DOI = "doi:10.1145/1830483.1830638",
• URL = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.365.4409",
• URL = "http://eplex.cs.ucf.edu/papers/lehman_gecco10b.pdf",
• publisher = "ACM",
• publisher_address = "New York, NY, USA",
• abstract = "A significant challenge in genetic programming is premature convergence to local optima, which often prevents evolution from solving problems. This paper introduces to genetic programming a method that originated in neuroevolution (i.e. the evolution of artificial neural networks) that circumvents the problem of deceptive local optima. The main idea is to search only for behavioural novelty instead of for higher fitness values. Although such novelty search abandons following the gradient of the fitness function, if such gradients are deceptive they may actually occlude paths through the search space towards the objective. Because there are only so many ways to behave, the search for behavioral novelty is often computationally feasible and differs significantly from random search. Counter intuitively, in both a deceptive maze navigation task and the artificial ant benchmark task, genetic programming with novelty search, which ignores the objective, outperforms traditional genetic programming that directly searches for optimal behaviour. Additionally, novelty search evolves smaller program trees in every variation of the test domains. Novelty search thus appears less susceptible to bloat, another significant problem in genetic programming. The conclusion is that novelty search is a viable new tool for efficiently solving some deceptive problems in genetic programming.",
• notes = "Maze, artificial ant (Santa Fe, Los Altos). LilGP. p838 'novelty search ... ignores the objective'. p839 'novelty needs to be measured'. k-nearest (k=25) phenotype clustering (cf fitness sharing, hall-of-fame coevolution archive, tabu) Mouret. Fitness = Euclidean distance between time sequences of food collection (fixed length vectors?) Pop=1000, 1000 generations, binary tournaments. Santa Fe Ant Wrong number of time steps. Performance similar to GP on Ant, much better on hardest maze.

  Also known as \cite{1830638} GECCO-2010 A joint meeting of the nineteenth international conference on genetic algorithms (ICGA-2010) and the fifteenth annual genetic programming conference (GP-2010)",

}

Genetic Programming entries for Joel Lehman Kenneth O Stanley

Citations