A Novel Human-Computer Collaboration: Combining Novelty Search with Interactive Evolution
Brian G. Woolley and Kenneth O. Stanley (2014): A Novel Human-Computer Collaboration: Combining Novelty Search with Interactive Evolution. In:Proceedings of the Genetic and Evolutionary Computation Conference(GECCO-2014). New York, NY: ACM.
Recent work on novelty and behavioral diversity in evolutionary computation has highlighted the potential disadvantage of driving search purely through objective means. This paper suggests that leveraging human insight during search can complement such novelty-driven approaches. In particular, a new approach called novelty-assisted interactive evolutionary computation (NA-IEC) combines human intuition with novelty search to facilitate the serendipitous discovery of agent behaviors in a deceptive maze. 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 not only finds solutions significantly faster and at lower genomic complexities than fully-automated processes guided purely by fitness or novelty, but it also finds solutions faster than the traditional IEC approach. Such results add to the evidence that combining human users and automated processes creates a synergistic effect in the search for solutions.
Josh C. Bongard , Gregory S. Hornby, Combining fitness-based search and user modeling in evolutionary robotics, Proceedings of the 15th annual conference on Genetic and evolutionary computation, July 06-10, 2013, Amsterdam, The Netherlands http://doi.acm.org/10.1145/2463372.2500097
Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991 http://dl.acm.org/citation.cfm?id=129837&CFID=588525319&CFTOKEN=29804931
R. Dawkins. The Blind Watchmaker. Longman, Essex, U.K., 1986.
Kenneth A. DeJong: The incremental pareto-coevolution archive. In Proceedings of the 6th annual conference on Genetic and evolutionary computation, GECCO '04, pages 525--536. Springer Berlin Heidelberg, 2004. ACM.
Kenneth A. DeJong , Kenneth A. De Jong, Evolutionary Computation, The MIT Press, 2002 http://dl.acm.org/citation.cfm?id=1137808&CFID=588525319&CFTOKEN=29804931
Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003 http://dl.acm.org/citation.cfm?id=954563&CFID=588525319&CFTOKEN=29804931
David B. Fogel, Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (IEEE Press Series on Computational Intelligence), Wiley-IEEE Press, 2006 http://dl.acm.org/citation.cfm?id=1202305&CFID=588525319&CFTOKEN=29804931
David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989 http://dl.acm.org/citation.cfm?id=534133&CFID=588525319&CFTOKEN=29804931
David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, USA http://dl.acm.org/citation.cfm?id=42519&CFID=588525319&CFTOKEN=29804931
J. Gomes, P. Urbano, and A. Christensen. Evolution of swarm robotics systems with novelty search. Swarm Intelligence, pages 1--30, 2013.
Gregory S. Hornby , Josh C. Bongard, Accelerating human-computer collaborative search through learning comparative and predictive user models, Proceedings of the 14th annual conference on Genetic and evolutionary computation, July 07-11, 2012, Philadelphia, Pennsylvania, USA http://doi.acm.org/10.1145/2330163.2330196
Steijn Kistemaker , Shimon Whiteson, Critical factors in the performance of novelty search, Proceedings of the 13th annual conference on Genetic and evolutionary computation, July 12-16, 2011, Dublin, Ireland http://doi.acm.org/10.1145/2001576.2001708
J. Lehman and K. O. Stanley. 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, 2008. MIT Press.
Joel Lehman , Kenneth O. Stanley, Efficiently evolving programs through the search for novelty, Proceedings of the 12th annual conference on Genetic and evolutionary computation, July 07-11, 2010, Portland, Oregon, USA http://doi.acm.org/10.1145/1830483.1830638
Joel Lehman , Kenneth O. Stanley, Revising the evolutionary computation abstraction: minimal criteria novelty search, Proceedings of the 12th annual conference on Genetic and evolutionary computation, July 07-11, 2010, Portland, Oregon, USA http://doi.acm.org/10.1145/1830483.1830503
Joel Lehman , Kenneth O. Stanley, Abandoning objectives: Evolution through the search for novelty alone, Evolutionary Computation, v.19 n.2, p.189-223, Summer 2011 http://dx.doi.org/10.1162/EVCO_a_00025
Joel Lehman and K. O. Stanley. Novelty search and the problem with objectives. In Genetic Programming Theory and Practice IX (GPTP 2011), New York, NY, 2011. Springer.
G. E. Liepins and M. D. Vose. Deceptiveness and genetic algorithm dynamics. Technical Report CONF-9007175--1, Oak Ridge National Lab., TN (USA); Tennessee Univ., Knoxville, TN (USA), 1990.
J.-B. Mouret. Novelty-based multiobjectivization. In New Horizons in Evolutionary Robotics, volume 341 of Studies in Computational Intelligence, pages 139--154. Springer Berlin / Heidelberg, 2011.
Enrique Naredo , Leonardo Trujillo, Searching for novel clustering programs, Proceedings of the 15th annual conference on Genetic and evolutionary computation, July 06-10, 2013, Amsterdam, The Netherlands http://doi.acm.org/10.1145/2463372.2463505
G. Newman, A. Wiggins, A. Crall, E. Graham, S. Newman, and K. Crowston. The future of citizen science: emerging technologies and shifting paradigms. Frontiers in Ecology and the Environment, 10 (6): 298--304, 2012.
M. Pelikan and D. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Technical Report 2001003, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 2001.
T. Reil , P. Husbands, Evolution of central pattern generators for bipedal walking in a real-time physics environment, IEEE Transactions on Evolutionary Computation, v.6 n.2, p.159-168, April 2002 http://dx.doi.org/10.1109/4235.996015
Sebastian Risi , Kenneth O. Stanley, Enhancing es-hyperneat to evolve more complex regular neural networks, Proceedings of the 13th annual conference on Genetic and evolutionary computation, July 12-16, 2011, Dublin, Ireland http://doi.acm.org/10.1145/2001576.2001783
Juan Romero , Penousal Machado, The Art of Artificial Evolution: A Handbook on Evolutionary Art and Music (Natural Computing Series), 2007
Jimmy Secretan , Nicholas Beato , David B. D'Ambrosio , Adelein Rodriguez , Adam Campbell , Jeremiah T. Folsom-Kovarik , Kenneth O. Stanley, Picbreeder: A case study in collaborative evolutionary exploration of design space, Evolutionary Computation, v.19 n.3, p.373-403, Fall 2011 http://dx.doi.org/10.1162/EVCO_a_00030
Jimmy Secretan , Nicholas Beato , David B. D Ambrosio , Adelein Rodriguez , Adam Campbell , Kenneth O. Stanley, Picbreeder: evolving pictures collaboratively online, Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, April 05-10, 2008, Florence, Italy http://doi.acm.org/10.1145/1357054.1357328
K. O. Stanley. Searching without objectives. Speech presented at SPLASH 2010, Reno, Nevada. October 21, 2010. http://www.infoq.com/presentations/Searching-Without-Objectives.
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
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=588525319&CFTOKEN=29804931
Sean R. Szumlanski , Annie S. Wu , Charles E. Hughes, Conflict resolution and a framework for collaborative interactive evolution, Proceedings of the 21st national conference on Artificial intelligence, p.512-517, July 16-20, 2006, Boston, Massachusetts http://dl.acm.org/citation.cfm?id=1597621&CFID=588525319&CFTOKEN=29804931
Takagi, H.: Interactive evolutionary computation: Fusion of the capabilities of EC optimization and human evaluation. Proceedings of the IEEE 89, 1275–1296 (2001) DOI: http://dx.doi.org/10.1109/5.949485 http://candy.yonsei.ac.kr/courses/2003/03TAI/ch02-3.pdf
M. van de Panne and A. Lamouret. Guided optimization for balanced locomotion. In Sixth Eurographics Workshop on Animation and Simulation, volume 95, pages 165--177. Springer-Verlag, 1995.
L. D. Whitley. Fundamental principles of deception in genetic search. Foundations of genetic algorithms, 1 (3): 221--241, 1991.
Brian G. Woolley , Kenneth O. Stanley, On the deleterious effects of a priori objectives on evolution and representation, Proceedings of the 13th annual conference on Genetic and evolutionary computation, July 12-16, 2011, Dublin, Ireland http://doi.acm.org/10.1145/2001576.2001707