Abandoning objectives: Evolution through the search for novelty alone
Inhaltsverzeichnis
Reference
Lehman, J., Stanley, K.O.: Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation 19(2), 189–223 (2011).
DOI
http://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
Used References
Aaltonen, T., et al. (2009). Measurement of the top quark mass with dilepton events selected using neuroevolution at CDF. Physical Review Letters.
Adami, C., Ofria, C., and Collier, T. C. (2000). Evolution of biological complexity. Proceedings of the National Academy of Sciences, USA, 97:4463–4468.
Allen, B., and Faloutsos, P. (2009). Complex networks of simple neurons for bipedal locomo- tion. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
Arthur, W. (1994). On the evolution of complexity. In Cownan, G., Pines, D., and Meltzer, D., editors, Complexity: Metaphors, Models and Reality, 65–81. Reading, MA: Addison-Wesley.
Barnett, L. (2001). Netcrawling - optimal evolutionary search with neutral networks. In Pro- ceedings of the 2001 IEEE International Conference on Evolutionary Computation, 30–37. IEEE Press.
Bedau, M. (1998). Four puzzles about life. Artificial Life, 4:125–140. http://citeseer.ist.psu.edu/215015.html
Bedau, M. A., and Packard, N. H. (1991). Measurement of evolutionary activity, teleology, and life. In Langton, C. G., Taylor, C., Farmer, J. D., and Rasmussen, S., editors, Proceedings of Artificial Life II, 431–461. Redwood City, CA: Addison-Wesley.
Bedau, M. A., Snyder, E., and Packard, N. H. (1998). A classification of longterm evolutionary dynamics. In Adami, C., Belew, R., Kitano, H., and Taylor, C., editors, Proceedings of Artificial Life VI, 228–237. Cambridge, MA: MIT Press.
Benbrahim, H. (1996). Biped dynamic walking using reinforcement learning. PhD thesis, Durham, NH, USA. Director-Miller,III, W. Thomas.
Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., and Zitzler, E. (2007). Do additional objectives make a problem harder? In GECCO ’07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, 765–772. New York, NY, USA: ACM.
Cartlidge, J., and Bullock, S. (2004a). Combating coevolutionary disengagement by reducing parasite virulence. Evolutionary Computation, 12(2):193–222. http://www.mitpressjournals.org/doi/abs/10.1162/106365604773955148
Cartlidge, J., and Bullock, S. (2004b). Unpicking tartan CIAO plots: Understanding irregular coevolutionary cycling. Adaptive Behavior, 12(2):69–92. http://adb.sagepub.com/cgi/content/abstract/12/2/69
Channon, A. (2001). Passing the alife test: Activity statistics classify evolution in geb as un- bounded. In Proceedings of the European Conference on Artificial Life(ECAL-2001). Springer. http://www.springerlink.com/content/9x0k07vdy5mcp5xr/
Channon, A. D., and Damper, R. I. (2000). Towards the evolutionary emergence of increasingly complex advantageous behaviours. International Journal of Systems Science, 31(7):843–860. http://eprints.ecs.soton.ac.uk/398/
Chellapilla, K., and Fogel, D. B. (1999). Evolving neural networks to play checkers without relying on expert knowledge. IEEE Transactions on Neural Networks, 10(6):1382–1391.
Cliff, D., and Miller, G. (1995). Tracking the red queen: Measurements of adaptive progress in co-evolutionary simulations. 200–218. http://dx.doi.org/10.1007/3-540-59496-5_300
Davidor, Y. (1990). Epistasis variance: A viewpoint on GA-hardness. In Proceedings of the First Workshop on Foundations of Genetic Algorithms., 23–35. Morgan Kaufmann.
De Jong, E. D. (2004). The incremental pareto-coevolution archive. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004). Berlin: Springer Verlag. http://www.cs.uu.nl/~dejong/publications/gecco04coev.pdf
De Jong, E. D., and Pollack, J. B. (2003). Multi-objective methods for tree size control. Genetic Programming and Evolvable Machines, 4(3):211–233. http://www.cs.uu.nl/~dejong/publications/bloat.ps
De Jong, K. A. (2006). Evolutionary Computation: A Unified Approach. MIT Press.
Deb, K. (1999). Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7:205–230.
Elman, J. L. (1991). Incremental learning, or the importance of starting small. Technical Report 9101, CRL, La Jolla, CA.
Endler, J. A., and Greenwood, J. J. D. (1988). Frequency-Dependent Predation, Crypsis and Aposematic Coloration [and Discussion]. Philosophical Transactions of the Royal Society of London. B, Biological Sciences, 319(1196):505–523. http://rstb.royalsocietypublishing.org/content/319/1196/505.abstract
Ficici, S., and Pollack, J. B. (1998). Challenges in coevolutionary learning: Arms-race dynam- ics, open-endedness, and mediocre stable states. In Proceedings of the Sixth International Conference on Artificial Life, 238–247. MIT Press.
Fogel, L., Owens, A., and Walsh, M. (1966). Artificial intelligence through simulated evolution. John Wiley & Sons Inc.
Glover, F. (1989). Tabu search, part I. ORSA Journal on Computing, 1(3):190–206. Goldberg, D., Deb, K., and Korb, B. (1989). Messy genetic algorithms: motivation, analysis, and first results. Complex Systems, (3):493–530.
Goldberg, D. E. (1987). Simple genetic algorithms and the minimal deceptive problem. In Davis, L. D., editor, Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence. Morgan Kaufmann.
Goldberg, D. E., and Richardson, J. (1987). Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the Second International Conference on Genetic Al- gorithms, 41–49. Hillsdale, NJ, USA: L. Erlbaum Associates Inc.
Gomez, F. (2009). Sustaining diversity using behavioral information distance. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2009), 113–120. ACM.
Gomez, F., and Miikkulainen, R. (1997). Incremental evolution of complex general behavior. Adaptive Behavior, 5:317–342. http://nn.cs.utexas.edu/keyword?gomez:ab97
Gould, S. J. (1996). Full House: The Spread of Excellence from Plato to Darwin. Harmony Books. Grefenstette, J. J. (1992). Deception considered harmful. In Foundations of Genetic Algorithms 2, 75–91. Morgan Kaufmann.
Greiner, D., Emerador, J. M., Winter, G., and Galvan, B. (2007). Improving computational me- chanics optimum design using helper objectives: An application in frame bar structures. In Evolutionary Multi-Criterion Optimization, 575–589.
Handl, J., Lovell, S. C., and Knowles, J. (2008a). Investigations into the effect of multiobjec- tivization in protein structure prediction. In Proceedings of the 10th international conference on Parallel Problem Solving from Nature, 702–711. Berlin, Heidelberg: Springer-Verlag.
Handl, J., Lovell, S. C., and Knowles, J. (2008b). Multiobjectivization by decomposition of scalar cost functions. In Proceedings of the 10th international conference on Parallel Problem Solving from Nature, 31–40. Berlin, Heidelberg: Springer-Verlag.
Harvey, I. (1993). The Artificial Evolution of Adaptive Behavior. PhD thesis, School of Cognitive and Computing Sciences, University of Sussex, Sussex. http://www.cogs.susx.ac.uk/users/inmanh/inman_thesis.html (Verweis auf http://www.sussex.ac.uk/informatics/)
Harvey, I., and Thompson, A. (1996). Through the labyrinth evolution finds a way: A silicon ridge. In Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, 406–422. Springer-Verlag.
Hein, D., Hild, M., and Berger, R. (2007). Evolution of biped walking using neural oscillators and physical simulation. In RoboCup 2007: Proceedings of the International Symposium, LNAI. Springer.
Hillis, W. D. (1991). Co-evolving parasites improve simulated evolution as an optimization procedure. In Farmer, J. D., Langton, C., Rasmussen, S., and Taylor, C., editors, Artificial Life II. Reading, MA: Addison-Wesley.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. Ann Arbor, MI: University of Michigan Press.
Hordijk, W. (1995). A measure of landscapes. Evolutionary Computation, 4:335–360.
Hornby, G. S. (2006). ALPS: the age-layered population structure for reducing the problem of premature convergence. In Proceedings of the Genetic and Evolutionary Computation Confer- ence (GECCO-2006), 815–822. New York, NY, USA: ACM.
Hu, J., Goodman, E., Seo, K., Fan, Z., and Rosenberg, R. (2005). The hierarchical fair compe- tition (HFC) framework for sustainable evolutionary algorithms. Evolutionary Computa- tion, 13(2):241–277. http://www.mitpressjournals.org/doi/abs/10.1162/1063656054088530
Hughes, K. A., Du, L., Rodd, F. H., and Reznick, D. N. (1999). Familiarity leads to female mate preference for novel males in the guppy, poecilia reticulata. Animal Behavior, 58(4):907– 916.
Hutter, M., and Legg, S. (2006). Fitness uniform optimization. IEEE Transactions on Evolution- ary Computation, 10:568–589.
Huyen, M. (1995). Exploring phenotype space through neutral evolution. Working Papers 95-10-100, Santa Fe Institute. http://ideas.repec.org/p/wop/safiwp/95-10-100.html
Ishiguro, A., Fujii, A., and Hotz, P. E. (2003). Neuromodulated control of bipedal locomotion using a polymorphic CPG circuit. Adaptive Behavior, 11(1):7–17. http://adb.sagepub.com/cgi/content/abstract/11/1/7
Jones, T., and Forrest, S. (1995). Fitness distance correlation as a measure of problem diffi- culty for genetic algorithms. In Proceedings of the Sixth International Conference on Genetic Algorithms, 184–192. Morgan Kaufmann.
Kampis, G., and Guly ́as, L. (2008). Full body: The importance of the phenotype in evolution. Artificial Life, 14(3):375–386.
Kaplan, F., and Hafner, V. (2006). Information-theoretic framework for unsupervised activity classification. Advanced Robotics, 20(10):1087–1103.
Kati ́c, D., and Vukobratovi ́c, M. (2003). Survey of intelligent control techniques for humanoid robots. Journal of Intelligent Robotics Systems, 37(2):117–141.
Kauffman, S. A. (1993). The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, USA. First edition. http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/0195079515
Kimura, M. (1983). The neutral theory of molecular evolution. Cambridge University Press.
Kirkpatrick, S., Gelatt, C. D., Jr., and Vecchi, M. P. (1983). Optimization by simulated anneal- ing. Science, 220:671–680.
Knowles, J. D., Watson, R. A., and Corne, D. (2001). Reducing local optima in single-objective problems by multi-objectivization. In EMO ’01: Proceedings of the First International Confer- ence on Evolutionary Multi-Criterion Optimization, 269–283. London, UK: Springer-Verlag.
Lehman, J., and Stanley, K. O. (2008). Exploiting open-endedness to solve problems through the search for novelty. In Proceedings of the Eleventh International Conference on Artificial Life (ALIFE XI). Cambridge, MA: MIT Press.
Lehman, J., and Stanley, K. O. (2010a). Efficiently evolving programs through the search for novelty. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO- 2010). ACM. To appear.
Lehman, J., and Stanley, K. O. (2010b). Revising the evolutionary computation abstraction: Minimal criteria novelty search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2010). ACM. To appear.
Liepins, G. E., and Vose, M. D. (1990). Deceptiveness and genetic algorithm dynamics. In Rawlins, G. J. E., editor, FOGA, 36–50. Morgan Kaufmann.
Lynch, M. (2007a). The evolution of genetic networks by non-adaptive processes. Nature Reviews Genetics, 8:803–813. http://www.nature.com/nrg/journal/v8/n10/abs/nrg2192.html
Lynch, M. (2007b). The frailty of adaptive hypotheses for the origins of organismal complexity. In Proc Natl Acad Sci USA, vol. 104, 8597–8604. http://www.pnas.org/cgi/content/abstract/104/suppl_1/8597
Mahfoud, S. W. (1995). Niching methods for genetic algorithms. PhD thesis, Champaign, IL, USA.
Maley, C. C. (1999). Four steps toward open-ended evolution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), 1336–1343. San Francisco: Kauf- mann.
Manderick, B., de Weger, M. K., and Spiessens, P. (1991). The genetic algorithm and the struc- ture of the fitness landscape. In Belew, R. K., and Booker, L. B., editors, ICGA, 143–150. Morgan Kaufmann.
Martin, A. P. (1999). Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154(2):111–128.
McHale, G., and Husbands, P. (2004). Gasnets and other evolvable neural networks applied to bipedal locomotion. In From Animals to Animats 8.
McShea, D. W. (1991). Complexity and evolution: What everybody knows. Biology and Philos- ophy, 6(3):303–324. http://www.springerlink.com/content/k87536105j01g806/
Miconi, T. (2007). Evolution and complexity: The double-edged sword. Artificial Life: Special Issue on the Evolution of Complexity. http://www.cs.bham.ac.uk/~txm/complexfinal.pdf
Mitchell, M., Forrest, S., and Holland, J. H. (1992). The royal road for genetic algorithms: Fit- ness landscapes and ga performance. In Varela, F. J., and Bourgine, P., editors, Proceedings of the First European Conference on Artificial Life. Cambridge, MA: MIT Press.
Mitchell, T. M. (1997). Machine Learning. New York, NY: McGraw-Hill.
Mouret, J.-B. (2009). Novelty-based multiobjectivization. In Proceedings of the Workshop on Exploring New Horizons in Evolutionary Design of Robots,2009 IEEE/RSJ International Con- ference on Intelligent Robots and Systems.
Nehaniv, C. L., and Rhodes, J. L. (1999). On the manner in which biological complexity may grow. In Mathematical and Computational Biology, vol. 26 of Lectures on Mathematics in the Life Sciences, 93–102. American Mathematical Society.
Ok, S., and Kim, D. (2005). Evolution of the CPG with sensory feedback for bipedal locomo- tion. In Advances in Natural Computation. Springer Berlin / Heidelberg.
Oudeyer, P., Kaplan, F., and Hafner, V. (2007). Intrinsic motivation systems for autonomous mental development. IEEE Transactions on Evolutionary Computation, 11(2):265–286.
Oudeyer, P., Kaplan, F., Hafner, V., and Whyte, A. (2005). The playground experiment: Task- independent development of a curious robot. In Proceedings of the AAAI Spring Symposium on Developmental Robotics, 42–47.
Paul, C. (2003). Bilateral decoupling in the neural control of biped locomotion. In Proc. 2nd International Symposium on Adaptive Motion of Animals and Machines.
Pelikan, M., Pelikan, M., Goldberg, D. E., and Goldberg, D. E. (2001). Escaping hierarchical traps with competent genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), 511–518. Morgan Kaufmann.
Pollack, J., Blair, A. D., and Land, M. (1996). Coevolution of a backgammon player. In Proceed- ings of Artificial Life V, 92–98. MIT Press.
Ray, T. (1992). Evolution, ecology and optimization of digital organisms. Technical Report Working paper 92-08-042, Santa Fe Institute. http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.131.6840&rank=1
Reil, T., and Husbands, P. (2002). Evolution of central pattern generators for bipedal walk- ing in a real-time physics environment. IEEE Transactions on Evolutionary Computation, 6(2):159–168.
Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Trans- actions of the American Mathematical Society, 74(2):358–366. http://www.jstor.org/stable/1990888
Risi, S., Vanderbleek, S. D., Hughes, C. E., and Stanley, K. O. (2009). How novelty search es- capes the deceptive trap of learning to learn. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2009). New York, NY: ACM.
Rothlauf, F., and Goldberg, D. E. (2002). Representations for Genetic and Evolutionary Algorithms. Physica-Verlag.
Schmidhuber, J. (2003). Exploring the predictable. In Ghosh, S., and S., T., editors, Advances in Evolutionary Computing: theory and applications, 579–612. Springer-Verlag New York.
Schmidhuber, J. (2006). Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts. Connection Science, 18(2):173–187.
Sigmund, K. (1993). Games of Life: Explorations in Ecology, Evolution and Behaviour. New York, NY, USA: Oxford University Press, Inc.
Sims, K. (1994). Evolving 3D morphology and behavior by competition. In Brooks, R. A., and Maes, P., editors, Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems (Artificial Life IV), 28–39. Cambridge, MA: MIT Press.
Soltoggio, A., and Jones, B. (2009). Novelty of behaviour as a basis for the neuro-evolution of operant reward learning. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2009). New York, NY: ACM.
Standish, R. (2003). Open-ended artificial evolution. International Journal of Computational Intelligence and Applications, 3(167). http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.4072&rank=1
Stanley, K. O., Bryant, B. D., and Miikkulainen, R. (2005). Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation Special Issue on Evolu- tionary Computation and Games, 9(6):653–668.
Stanley, K. O., and Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10:99–127. http://nn.cs.utexas.edu/keyword?stanley:ec02
Stanley, K. O., and Miikkulainen, R. (2003). A taxonomy for artificial embryogeny. Artificial Life, 9(2):93–130. http://nn.cs.utexas.edu/keyword?stanley:alife03
Stanley, K. O., and Miikkulainen, R. (2004). Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21:63–100. http://nn.cs.utexas.edu/keyword?stanley:jair04
Stewart, T. C. (2001). Extrema selection: Accelerated evolution on neutral networks. In Pro- ceedings of the 2001 IEEE International Conference on Evolutionary Computation. IEEE Press.
Taylor, T., and Hallam, J. (1997). Studying evolution with self-replicating computer programs. In Fourth European Conference on Artificial Life, 550–559. MIT Press.
Van de Panne, M., and Lamouret, A. (1995). Guided optimization for balanced locomotion. In Terzopoulos, D., and Thalmann, D., editors, Sixth Eurographics Workshop on Animation and Simulation, 165–177. Springer Verlag. http://www.cs.ubc.ca/~van/papers/1995-egcas-guided.pdf
Veldhuizen, D. A. V., and Lamont, G. B. (2000). Multiobjective evolutionary algorithms: Ana- lyzing the state-of-the-art. Evolutionary Computation, 8(2):125–147. PMID: 10843518. http://www.mitpressjournals.org/doi/abs/10.1162/106365600568158
Watson, J. D., Hopkins, N. H., Roberts, J. W., Steitz, J. A., and Weiner, A. M. (1987). Molecular Biology of the Gene Fourth Edition. Menlo Park, CA: The Benjamin Cummings Publishing Company, Inc.
Watson, R., and Pollack, J. (2001). Coevolutionary dynamics in a minimal substrate. 702–709. Morgan Kaufmann.
Weinberger, E. (1990). Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics, 63(5):325–336. http://dx.doi.org/10.1007/BF00202749
Whiteson, S., and Stone, P. (2006). Evolutionary function approximation for reinforcement learning. Journal of Machine Learning Research, 7:877–917.
Whitley, L. D. (1991). Fundamental principles of deception in genetic search. In Foundations of Genetic Algorithms, 221–241. Morgan Kaufmann.
Yaeger, L. (1994). Computational genetics, physiology, metabolism, neural systems, learning, vision and behavior or polyworld: Life in a new context. In Langton, C. G., editor, Artificial Life III, Proceedings Volume XVII, 263–298. Addison-Wesley. http://citeseer.ist.psu.edu/yaeger94computational.html
Yao, X. (1993). An empirical study of genetic operators in genetic algorithms. Microprocessing and Microprogramming, 38(1-5):707–714.
Zaera, N., Cliff, D., and Bruten, J. (1996). (Not) evolving collective behaviours in synthetic fish. In From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior. MIT Press Bradford Books.
Links
Full Text
http://www.cs.swarthmore.edu/~meeden/DevelopmentalRobotics/lehman_ecj11.pdf
