Exploring promising stepping stones by combining novelty search with interactive evolution
Inhaltsverzeichnis
Reference
Woolley, B.G., Stanley, K.O.: Exploring promising stepping stones by combining novelty search with interactive evolution. CoRR abs/1207.6682 (2012)
DOI
Abstract
The field of evolutionary computation is inspired by the achievements of natural evolution, in which there is no final objective. Yet the pursuit of objectives is ubiquitous in simulated evolution. A significant problem is that objective approaches assume that intermediate stepping stones will increasingly resemble the final objective when in fact they often do not. The consequence is that while solutions may exist, searching for such objectives may not discover them. This paper highlights the importance of leveraging human insight during search as an alternative to articulating explicit objectives. In particular, a new approach called novelty-assisted interactive evolutionary computation (NA-IEC) combines human intuition with novelty search for the first time to facilitate the serendipitous discovery of agent behaviors. In this approach, the human user directs evolution by selecting what is interesting from the on-screen population of behaviors. However, unlike in typical IEC, the user can now request that the next generation be filled with novel descendants. The experimental results demonstrate that combining human insight with novelty search finds solutions significantly faster and at lower genomic complexities than fully-automated processes, including pure novelty search, suggesting an important role for human users in the search for solutions.
Extended Abstract
Bibtex
Used References
[1] Bongard, J. C. (2002). Evolving modular genetic regulatory networks. In Proceedings of the 2002 Congress on Evolutionary Computation.
[2] Cover, T. M. and Thomas, J. (1991). Elements of Information Theory. Wiley, Hoboken, NJ.
[3] Dawkins, R. (1986). The Blind Watchmaker. Longman, Essex, U.K.
[4] De Jong, E. D. (2004). The incremental pareto-coevolution archive. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Berlin. Springer Verlag.
[5] De Jong, K. A. (2002). Evolutionary Computation: A Unified Perspective. MIT Press, Cambridge, MA.
[6] Eiben, A. and Smith, J. (2003). Introduction to evolutionary computing. Springer-Verlag.
[7] Ficici, S. and Pollack, J. (1998). Challenges in coevolutionary learning: Arms-race dynamics, open-endedness, and mediocre stable states. Artificial life VI, page 238.
[8] Fogel, D. B. (2006). Evolutionary computation: toward a new philosophy of machine intelligence, third edition. Wiley-IEEE Press.
[9] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA.
[10] Goldberg, D. E. and Richardson, J. (1987). Genetic algorithms with sharing for multimodal function optimization. In Grefenstette, J. J., editor, Proceedings of the Second International Conference on Genetic Algorithms, pages 148– 154. San Francisco: Kaufmann.
[11] Gruau, F., Whitley, D., and Pyeatt, L. (1996). A comparison between cellular encoding and direct encoding for genetic neural networks. In Koza, J. R., Goldberg, D. E., Fogel, D. B., and Riolo, R. L., editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 81–89, Cambridge, MA. MIT Press.
[12] Hornby, G. S. and Pollack, J. B. (2001). The advantages of generative grammatical encodings for physical design. In Proceedings of the 2002 Congress on Evolutionary Computation.
[13] James, D. and Tucker, P. (2005–2010). Anji homepage. http://anji.sourceforge.net/.
[14] Kistemaker, S. and Whiteson, S. (2011). Critical factors in the performance of novelty search. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO ’11, pages 965–972, New York, NY, USA. ACM.
[15] Lehman, J. and Stanley, K. O. (2008). Exploiting open-endedness to solve problems through the search for novelty. In Bullock, S., Noble, J., Watson, R., and Bedau, M., editors, Proceedings of the Eleventh International Conference on Artificial Life (Alife XI), Cambridge, MA. MIT Press.
[16] Lehman, J. and Stanley, K. O. (2010a). Efficiently evolving programs through the search for novelty. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, GECCO ’10, pages 837–844, New York, NY, USA. ACM.
[17] Lehman, J. and Stanley, K. O. (2010b). Revising the evolutionary computation abstraction: minimal criteria novelty search. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, GECCO ’10, pages 103–110, New York, NY, USA. ACM.
[18] Lehman, J. and Stanley, K. O. (2011). Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189–223.
[19] Liepins, G. E. and Vose, M. D. (1990). Deceptiveness and genetic algorithm dynamics. Technical Report CONF- 9007175-1, Oak Ridge National Lab., TN (USA); Tennessee Univ., Knoxville, TN (USA).
[20] Miller, J. F. (2004). Evolving a self-repairing, self-regulating, French flag organism. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Berlin. Springer Verlag.
[21] Mouret, J.-B. (2011). Novelty-based multiobjectivization. In Doncieux, S., Bred`eche, N., and Mouret, J.-B., editors, New Horizons in Evolutionary Robotics, volume 341 of Studies in Computational Intelligence, pages 139– 154. Springer Berlin / Heidelberg.
[22] Pelikan, M. and Goldberg, D. (2001). Escaping hierarchical traps with competent genetic algorithms. Technical Report 2001003, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL.
[23] Reil, T. and Husbands, P. (2002). Evolution of central pattern generators for bipedal walking in a real-time physics environment. IEEE Transactions on Evolutionary Computation, 6(2):159–168.
[24] Risi, S. and Stanley, K. O. (2011). Enhancing es-hyperneat to evolve more complex regular neural networks. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO ’11, pages 1539–1546, New York, NY, USA. ACM.
[25] Romero, J. and Machado, P., editors (2008). The art of artificial evolution: A handbook on evolutionary art and music. Springer-Verlag, New York, NY.
[26] Secretan, J., Beato, N., D.Ambrosio, D. B., Rodriguez, A., Campbell, A., Folsom-Kovarik, J. T., and Stanley, K. O. (2011). Picbreeder: A case study in collaborative evolutionary exploration of design space. Evolutionary Computation, 19(3):373–403.
[27] Secretan, J., Beato, N., D’Ambrosio, D. B., Rodriguez, A., Campbell, A., and Stanley, K. O. (2008). Picbreeder: Evolving pictures collaboratively online. In CHI ’08: Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, pages 1759–1768, New York, NY, USA. ACM.
[28] Stanley, K. O. (2010). Searching without objectives. Speech presented at SPLASH 2010, Reno/Tahoe, Nevada. http://www.infoq.com/presentations/Searching-Without-Objectives.
[29] Stanley, K. O. and Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10:99–127.
[30] Stanley, K. O. and Miikkulainen, R. (2003). A taxonomy for artificial embryogeny. Artificial Life, 9(2):93–130.
[31] Stanley, K. O. and Miikkulainen, R. (2004). Competitive coevolution through evolutionary complexification. Jour- nal of Artificial Intelligence Research, 21:63–100.
[32] Szumlanski, S. R., Wu, A. S., and Hughes, C. E. (2006). Conflict resolution and a framework for collaborative interactive evolution. In Proceedings of the 21st national conference on Artificial intelligence - Volume 1, pages 512–517. AAAI Press.
[33] Takagi, H. (2001). Interactive evolutionary computation: Fusion of the capacities of EC optimization and human evaluation. Proceedings of the IEEE, 89(9):1275–1296.
[34] 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, volume 95, pages 165–177. Springer-Verlag.
[35] Ventrella, J. J. (1994). Disney meets Darwin: an evolution-based interface for exploration and design of expressive animated behavior. Master’s thesis, Massachusetts Institute of Technology.
[36] Whitley, L. D. (1991). Fundamental principles of deception in genetic search. Foundations of genetic algorithms, 1(3):221–241.
[37] Woolley, B. G. and Stanley, K. O. (2011). On the deleterious effects of a priori objectives on evolution and rep- resentation. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’11, New York, NY, USA. ACM.
[38] Zaera, N., Cliff, D., and Bruten, J. (1996). (Not) evolving collective behaviours in synthetic fish. In Maes, P., Mataric, M. J., Meyer, J.-A., Pollack, J., and Wilson, S. W., editors, From animals to animats 4: proceedings of the Fourth International Conference on Simulation of Adaptive Behavior (SAB’96), pages 635–642, Cambridge, Mass. MIT Press.
Links
Full Text
http://arxiv.org/pdf/1207.6682v1
