Revising the evolutionary computation abstraction: minimal criteria novelty search
Inhaltsverzeichnis
Referenz
Lehman, J., Stanley, K.O.: Revising the evolutionary computation abstraction: minimal criteria novelty search. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 103–110. ACM (2010)
DOI
http://dx.doi.org/10.1145/1830483.1830503
Abstract
Though based on abstractions of nature, current evolutionary algorithms and artificial life models lack the drive to complexity characteristic of natural evolution. Thus this paper argues that the prevalent fitness-pressure-based abstraction does not capture how natural evolution discovers complexity. Alternatively, this paper proposes that natural evolution can be abstracted as a process that discovers many ways to express the same functionality. That is, all successful organisms must meet the same minimal criteria of survival and reproduction. This abstraction leads to the key idea in this paper: Searching for novel ways of meeting the same minimal criteria, which is an accelerated model of this new abstraction, may be an effective search algorithm. Thus the existing novelty search method, which rewards any new behavior, is extended to enforce minimal criteria. Such minimal criteria novelty search prunes the space of viable behaviors and may often be more efficient than the search for novelty alone. In fact, when compared to the raw search for novelty and traditional fitness-based search in the two maze navigation experiments in this paper, minimal criteria novelty search evolves solutions more consistently. It is possible that refining the evolutionary computation abstraction in this way may lead to solving more ambitious problems and evolving more complex artificial organisms.
Extended Abstract
Bibtex
@inproceedings{Lehman:2010:REC:1830483.1830503,
author = {Lehman, Joel and Stanley, Kenneth O.},
title = {Revising the Evolutionary Computation Abstraction: Minimal Criteria Novelty Search},
booktitle = {Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation},
series = {GECCO '10},
year = {2010},
isbn = {978-1-4503-0072-8},
location = {Portland, Oregon, USA},
pages = {103--110},
numpages = {8},
url = {http://doi.acm.org/10.1145/1830483.1830503 http://de.evo-art.org/index.php?title=Revising_the_evolutionary_computation_abstraction:_minimal_criteria_novelty_search},
doi = {10.1145/1830483.1830503},
acmid = {1830503},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {artificial life, evolution of complexity, neat, novelty search},
}
Used References
1 T. Aaltonen et al. Measurement of the top quark mass with dilepton events selected using neuroevolution at CDF. Physical Review Letters, 2009.
2 Christoph Adami, Charles Ofria, and Travis C. Collier. Evolution of biological complexity. Proc. of the Natl. Academy of Sciences, USA, 97: 4463--4468, 2000.
3 Brian Allen , Petros Faloutsos, Complex networks of simple neurons for bipedal locomotion, Proceedings of the 2009 IEEE/RSJ international conference on Intelligent robots and systems, p.4457-4462, October 10-15, 2009, St. Louis, MO, USA http://dl.acm.org/citation.cfm?id=1732776&CFID=558819604&CFTOKEN=68186175
4 W. Brian Arthur, On the evolution of complexity, Complexity: metaphors, models, and reality, Perseus Books, Cambridge, MA, 1999 http://dl.acm.org/citation.cfm?id=336626&CFID=558819604&CFTOKEN=68186175
5 Mark A. Bedau, Four puzzles about life, Artificial Life, v.4 n.2, p.125-140, Spring 1998 http://dx.doi.org/10.1162/106454698568486
6 A. D. Channon and R. I. Damper. Towards the evolutionary emergence of increasingly complex advantageous behaviours. International Journal of Systems Science, 31 (7): 843--860, 2000.
7 Charles Darwin. On the Origin of Species by Means of Natural Selection or the Preservation of Favored Races in the Struggle for Life. Murray, London, 1859.
8 R. Dawkins. Human chauvinism. Evolution, 51 (3): 1015--1020, 1997.
9 Richard Dawkins. The Selfish Gene. Oxford University Press, Oxford, UK, 3rd edition, 1989.
10 J. A. Endler and J. J. D. Greenwood. Frequency-Dependent Predation, Crypsis and Aposematic Coloration {and Discussion}. Philosophical Transactions of the Royal Society of London. B, Biological Sciences, 319 (1196): 505--523, 1988.
11 Sevan G. Ficici , Jordan B. Pollack, Challenges in coevolutionary learning: arms-race dynamics, open-endedness, and medicocre stable states, Proceedings of the sixth international conference on Artificial life, p.238-247, August 1998, Madison, Wisconsin, USA http://dl.acm.org/citation.cfm?id=286166&CFID=558819604&CFTOKEN=68186175
12 Steven Jay Gould. Full House: The Spread of Excellence from Plato to Darwin. Harmony Books, 1996.
13 Inman Harvey. The Artificial Evolution of Adaptive Behavior. PhD thesis, School of Cognitive and Computing Sciences, University of Sussex, Sussex, 1993.
14 Kimberly A. Hughes, Linh Du, F. Helen Rodd, and David N. Reznick. Familiarity leads to female mate preference for novel males in the guppy, poecilia reticulata. Animal Behavior, 58 (4): 907--916, 1999.
15 George Kampis , László Gulyás, Full body: The importance of the phenotype in evolution, Artificial Life, v.14 n.3, p.375-386, Summer 2008 http://dx.doi.org/10.1162/artl.2008.14.3.14310
16 Joel Lehman and Kenneth O. Stanley. Exploiting open-endedness to solve problems through the search for novelty. In Proc. of the Eleventh Intl. Conf. on Artificial Life (ALIFE XI), Cambridge, MA, 2008. MIT Press.
17 Michael Lynch. The evolution of genetic networks by non-adaptive processes. Nature Reviews Genetics, 8: 803--813, 2007a.
18 Michael Lynch. The frailty of adaptive hypotheses for the origins of organismal complexity. In Proc. Natl. Acad. Sci. USA, volume 104, pages 8597--8604, 2007b.
19 Andrew P. Martin. Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154 (2): 111--128, 1999.
20 Daniel W. McShea. Complexity and evolution: What everybody knows. Biol. and Phil., 6 (3): 303--324, 1991.
21 Thomas Miconi, Evolution and complexity: The double-edged sword, Artificial Life, v.14 n.3, p.325-344, Summer 2008 http://dx.doi.org/10.1162/artl.2008.14.3.14307
22 Thomas M. Mitchell, Machine Learning, McGraw-Hill, Inc., New York, NY, 1997 http://dl.acm.org/citation.cfm?id=541177&CFID=558819604&CFTOKEN=68186175
23 Jean-Baptiste Mouret. Novelty-based multiobjectivization. In Proc. of the Workshop on Exploring New Horizons in Evolutionary Design of Robots,2009 IEEE/RSJ Intl Conf on Intelligent Robots and Systems, 2009.
24 C. L. Nehaniv and J. L. Rhodes. On the manner in which biological complexity may grow. In Mathematical and Computational Biology, volume 26 of Lectures on Mathematics in the Life Sciences, pages 93--102. American Mathematical Society, 1999.
25 Sebastian Risi , Sandy D. Vanderbleek , Charles E. Hughes , Kenneth O. Stanley, How novelty search escapes the deceptive trap of learning to learn, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada http://doi.acm.org/10.1145/1569901.1569923
26 Michael Ruse. Evolution and progress. Tree, 8 (2): 55--60, 1993.
27 J. Schmidhuber. Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts. Connection Science, 18 (2): 173--187, 2006.
28 Karl Sigmund, Games of Life: Explorations in Ecology, Evolution and Behaviour, Oxford University Press, Inc., New York, NY, 1993 http://dl.acm.org/citation.cfm?id=529311&CFID=558819604&CFTOKEN=68186175
29 Andrea Soltoggio , Ben Jones, Novelty of behaviour as a basis for the neuro-evolution of operant reward learning, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada http://doi.acm.org/10.1145/1569901.1569925
30 Russell Standish. Open-ended artificial evolution. Intl. Journal of Comp. Intell. and Applications, 3 (167), 2003.
31 K. O. Stanley , B. D. Bryant , R. Miikkulainen, Real-time neuroevolution in the NERO video game, IEEE Transactions on Evolutionary Computation, v.9 n.6, p.653-668, December 2005 http://dx.doi.org/10.1109/TEVC.2005.856210
32 Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 http://dx.doi.org/10.1162/106365602320169811
33 Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 http://dx.doi.org/10.1162/106454603322221487
34 Kenneth O. Stanley , Risto Miikkulainen, Competitive coevolution through evolutionary complexification, Journal of Artificial Intelligence Research, v.21 n.1, p.63-100, January 2004 http://dl.acm.org/citation.cfm?id=1622471&CFID=558819604&CFTOKEN=68186175
35 Kenneth O. Stanley and Risto Miikkulainen. Evolving a roving eye for Go. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Berlin, 2004b. Springer Verlag.
36 James D. Watson, Nancy H. Hopkins, Jeffrey W. Roberts, Joan A. Steitz, and Alan M. Weiner. Molecular Bio. of the Gene Fourth Edition. The Benjamin Cummings Publishing Company, Inc., 1987.
37 Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006 http://dl.acm.org/citation.cfm?id=1248578&CFID=558819604&CFTOKEN=68186175
38 N. Zaera, D. Cliff, and J. Bruten. (Not) evolving collective behaviours in synthetic fish. In From Animals to Animats 4: Proc. of the Fourth Intl. Conf. on Sim. of Adaptive Behavior. MIT Press Bradford Books., 1996.
Links
Full Text
http://eplex.cs.ucf.edu/papers/lehman_gecco10a.pdf
