Exploiting open-endedness to solve problems through the search for novelty
Inhaltsverzeichnis
Referenz
Lehman, J., Stanley, K.O.: Exploiting open-endedness to solve problems through the search for novelty. In: Proceedings of the Eleventh International Conference on Artificial Life (ALIFE XI). MIT Press, Cambridge (2008)
DOI
https://dx.doi.org/10.1162/EVCO_a_00025
Abstract
In evolutionary computation, the fitness function normally measures progress toward an objective in the search space, effectively acting as an objective function. Through deception, such objective functions may actually prevent the objective from being reached. While methods exist to mitigate deception, they leave the underlying pathology untreated: Objective functions themselves may actively misdirect search toward dead ends. This paper proposes an approach to circumventing deception that also yields a new perspective on open-ended evolution. Instead of either explicitly seeking an objective or modeling natural evolution to capture open-endedness, the idea is to simply search for behavioral novelty. Even in an objective-based problem, such novelty search ignores the objective. Because many points in the search space collapse to a single behavior, the search for novelty is often feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. By decoupling open-ended search from artificial life worlds, the search for novelty is applicable to real world problems. Counterintuitively, in the maze navigation and biped walking tasks in this paper, novelty search significantly outperforms objective-based search, suggesting the strange conclusion that some problems are best solved by methods that ignore the objective. The main lesson is the inherent limitation of the objective-based paradigm and the unexploited opportunity to guide search through other means.
Extended Abstract
Bibtex
TY - JOUR T1 - Abandoning Objectives: Evolution Through the Search for Novelty Alone AU - Lehman, Joel AU - Stanley, Kenneth O. Y1 - 2010/09/24 PY - 2010 DA - 2011/06/01 N1 - doi: 10.1162/EVCO_a_00025 DO - 10.1162/EVCO_a_00025 T2 - Evolutionary Computation JF - Evolutionary Computation JO - Evolutionary Computation SP - 189 EP - 223 VL - 19 IS - 2 PB - MIT Press SN - 1063-6560 M3 - doi: 10.1162/EVCO_a_00025 UR - http://dx.doi.org/10.1162/EVCO_a_00025 http://de.evo-art.org/index.php?title=Exploiting_open-endedness_to_solve_problems_through_the_search_for_novelty Y2 - 2016/06/12 ER -
Used References
[1] M. A. Bedau and N. H. Packard. Measurement of evolutionary activity, teleology, and life. In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, editors, Proc. of Art. Life II, pages 431–461, Redwood City, CA, 1991. Addison- Wesley.
[2] M. A. Bedau, E. Snyder, and N. H. Packard. A classification of longterm evolutionary dynamics. In C. Adami, R. Belew, H. Kitano, and C. Taylor, editors, Proc. of Art. Life VI, pages 228–237, Cambridge, MA, 1998. MIT Press.
[3] Mark Bedau. Four puzzles about life. Artificial Life, 4:125–140, 1998.
[4] A. Channon. Passing the alife test: Activity statistics classify evolution in geb as unbounded. In Proceedings of the European Conference on Artificial Life(ECAL-2001). Springer, 2001.
[5] Paul Darwen and Yin Yao. Every niching method has its niche: Fitness sharing and implicit sharing compared. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel, editors, Parallel Problem Solving from Nature – PPSN IV, pages 398–407, Berlin, 1996. Springer.
[6] Richard Dawkins. Genetic and evolutionary computation conference (GECCO- 2007) Keynote Debate, July 2007.
[7] E. D. De Jong. The incremental pareto-coevolution archive. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-2004), Berlin, 2004. Springer Verlag.
[8] Jeffrey L. Elman. Incremental learning, or the importance of starting small. Technical Report 9101, CRL, La Jolla, CA, 1991.
[9] David E. Goldberg. Simple genetic algorithms and the minimal deceptive problem. In L. D. Davis, editor, Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence. Morgan Kaufmann, 2007.
[10] Faustino Gomez and Risto Miikkulainen. Incremental evolution of complex general behavior. Adaptive Behavior, 5:317–342, 1997.
[11] Inman Harvey. The Artificial Evolution of Adaptive Behavior. PhD thesis, School of Cognitive and Computing Sciences, U. of Sussex, Sussex, 1993.
[12] 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.
[13] Marcus Hutter and Shane Legg. Fitness uniform optimization. IEEE Transactions on Evolutionary Computation, 10:568–589, 2006.
[14] Michael Lynch. The evolution of genetic networks by non-adaptive processes. Nature Reviews Genetics, 8:803–813, 2007.
[15] Michael Lynch. The frailty of adaptive hypotheses for the origins of organismal complexity. In Proc Natl Acad Sci USA, volume 104, pages 8597–8604, 2007.
[16] C. C. Maley. Four steps toward open-ended evolution. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-1999), pages 1336–1343, San Francisco, 1999. Kaufmann.
[17] Andrew P. Martin. Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154(2):111–128, 1999.
[18] DanielW. McShea. Complexity and evolution: What everybody knows. Biology and Philosophy, 6(3):303–324, 1991.
[19] Thomas Miconi. Evolution and complexity: The double-edged sword. Artificial Life: Special Issue on the Evolution of Complexity, 2007.
[20] Thomas Miconi. THE ROAD TO EVERYWHERE: Evolution, Complexity and Progress in Nature and in Computers. PhD thesis, U. of Birmingham, 2007.
[21] Melanie Mitchell, Stephanie Forrest, and John H. Holland. The royal road for genetic algorithms: Fitness landscapes and ga performance. In F. J. Varela and P. Bourgine, editors, Proceedings of the First European Conference on Artificial Life, Cambridge, MA, 1992. MIT Press.
[22] Tom M. Mitchell. Machine Learning. McGraw-Hill, New York, 1997.
[23] C. L. Nehaniv and J. L. Rhodes. On the manner in which biological complexity may grow. In Math. and Comp. Biology, volume 26 of Lectures on Mathematics in the Life Sciences, pages 93–102. American Mathematical Society, 1999.
[24] T. Ray. Evolution, ecology and optimization of digital organisms. Technical Report Working paper 92-08-042, Santa Fe Institute, 1992.
[25] Russell Standish. Open-ended artificial evolution. International Journal of Computational Intelligence and Applications, 3(167), 2003.
[26] Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Trans. on Evol. Comp. Special Issue on Evolutionary Computation and Games, 9(6):653–668, 2005.
[27] Kenneth O. Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10:99–127, 2002.
[28] Kenneth O. Stanley and Risto Miikkulainen. A taxonomy for artificial embryogeny. Artificial Life, 9(2):93–130, 2003.
[29] Kenneth O. Stanley and Risto Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Art. Int. Research, 21:63–100, 2004.
[30] Michiel Van de Panne and Alexis Lamouret. Guided optimization for balanced locomotion. In D. Terzopoulos and D. Thalmann, editors, Sixth Eurographics Workshop on Animation and Simulation, pages 165–177. Springer Verlag, 1995.
[31] James D. Watson, Nancy H. Hopkins, Jeffrey W. Roberts, Joan A. Steitz, and Alan M. Weiner. Molecular Biology of the Gene Fourth Edition. The Benjamin Cummings Publishing Company, Inc., Menlo Park, CA, 1987.
[32] Larry Yaeger. Computational genetics, physiology, metabolism, neural systems, learning, vision and behavior or polyworld: Life in a new context. In C. G. Langton, editor, Art. Life III, Proc. Vol. XVII, pages 263–298. Addison-Wesley, 1994.
Links
Full Text
http://eplex.cs.ucf.edu/papers/lehman_alife08.pdf
Sonstige Links
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.365.3998
