Jonathan C. Brant
ABSTRACT
Recent studies have emphasized the merits of search processes that lack overarching objectives, instead promoting divergence by rewarding behavioral novelty. While this less objective search paradigm is more open-ended and divergent, it still differs significantly from nature's mechanism of divergence. Rather than measuring novelty explicitly nature is guided by a single, fundamental constraint: survive long enough to reproduce. Surprisingly, this simple constraint produces both complexity and diversity in a continual process unparalleled by any algorithm to date. Inspired by the relative simplicity of open-endedness in nature in comparison to recent non-objective algorithms, this paper investigates the extent to which interactions between two coevolving populations, both subject to their own constraint, or minimal criterion, can produce results that are both functional and diverse even without any behavior characterization or novelty archive. To test this new approach, a novel maze navigation domain is introduced wherein evolved agents must learn to navigate mazes whose structures are simultaneously coevolving and increasing in complexity. The result is a broad range of maze topologies and successful agent trajectories in a single run, thereby suggesting the viability of minimal criterion coevolution as a new approach to non-objective search and a step towards genuinely open-ended algorithms.
- Edwin D De Jong. 2004. The Incremental Pareto-Coevolution Archive. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004). Springer Verlag, Berlin.Google Scholar
Cross Ref
- Kenneth A De Jong. 2006. Evolutionary computation: a unified approach. MIT press. Google ScholarDigital Library
- Sevan G Ficici and Jordan B Pollack. 1998. Challenges in Coevolutionary Learning: Arms-Race Dynamics, Open-Endedness, and Mediocre Stable States. In Proceedings of the Sixth International Conference on Artificial Life, Adami et al (Ed.). MIT Press, Cambridge, MA, 238--247. Google ScholarDigital Library
- Martin Foltin. 2011. Automated Maze Generation and Human Interaction. Brno: Masaryk University Faculty Of Informatics (2011).Google Scholar
- Colin Green. 2016. SharpNEAT v3. URL: http://sharpneat.sourceforge.net (2016).Google Scholar
- Marc Kirschner and John Gerhart. 1998. Evolvability. Proceedings of the National Academy of Sciences 95, 15 (1998), 8420--8427.Google ScholarCross Ref
- Bakir Lacevic and Edoardo Amaldi. 2010. On population diversity measures in Euclidean space. In IEEE Congress on Evolutionary Computation. IEEE, 1--8.Google ScholarCross Ref
- Joel Lehman and Kenneth O Stanley. 2008. 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, 329--336.Google Scholar
- Joel Lehman and Kenneth O Stanley. 2010. Revising the evolutionary computation abstraction: minimal criteria novelty search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2010). ACM, 103--110. Google ScholarDigital Library
- Joel Lehman and Kenneth O Stanley. 2011. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation 19, 2 (2011), 189--223. Google ScholarDigital Library
- Joel Lehman and Kenneth O Stanley. 2011. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation. ACM, 211--218. Google ScholarDigital Library
- Joel Lehman and Kenneth O Stanley. 2013. Evolvability is inevitable: Increasing evolvability without the pressure to adapt. PloS one 8, 4 (2013), e62186.Google ScholarCross Ref
- Antonios Liapis, Héctor P. Martinez, Julian Togelius, and Georgios N. Yannakakis. 2013. Transforming Exploratory Creativity with DeLeNoX. In Proceedings of the Fourth International Conference on Computational Creativity.Google Scholar
- Andrea Maesani, Pradeep Ruben Fernando, and Dario Floreano. 2014. Artificial evolution by viability rather than competition. PloS one 9, 1 (2014), e86831.Google ScholarCross Ref
- Claudio Mattiussi and Dario Floreano. 2003. Viability Evolution: Elimination and Extinction in Evolutionary Computation. Technical Report. EPFL.Google Scholar
- Jean-Baptiste Mouret. 2011. Novelty-based multiobjectivization. In New Horizons in Evolutionary Robotics. Springer, 139--154.Google Scholar
- Jean-Baptiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015).Google Scholar
- Jean-Baptiste Mouret and Stéphane Doncieux. 2012. Encouraging behavioral diversity in evolutionary robotics: An empirical study. Evolutionary computation 20, 1 (2012), 91--133. Google ScholarDigital Library
- Charles Ofria and Claus O Wilke. 2004. Avida: A software platform for research in computational evolutionary biology. Artificial life 10, 2 (2004), 191--229. Google ScholarDigital Library
- Elena Popovici, Anthony Bucci, R Paul Wiegand, and Edwin D De Jong. 2012. Coevolutionary principles. In Handbook of Natural Computing. Springer, 987--1033.Google Scholar
- Mitchell A Potter and Kenneth A De Jong. 1995. Evolving Neural Networks with Collaborative Species. In Proceedings of the 1995 Summer Computer Simulation Conference. 340--345.Google Scholar
- Justin K Pugh, Lisa B Soros, and Kenneth O Stanley. 2016. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI 3 (2016), 40.Google ScholarCross Ref
- Thomas S Ray. 1991. An approach to the synthesis of life. In Artificial Life II. Addison-Wesley, 371--408.Google Scholar
- Sebastian Risi, Sandy D Vanderbleek, Charles E Hughes, and Kenneth O Stanley. 2009. How novelty search escapes the deceptive trap of learning to learn. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2009). ACM, 153--160. Google ScholarDigital Library
- Eivind Samuelsen and Kyrre Glette. 2014. Some distance measures for morphological diversification in generative evolutionary robotics. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2014). ACM, 721--728. Google ScholarDigital Library
- Lisa B Soros and Kenneth O Stanley. 2014. Identifying necessary conditions for open-ended evolution through the artificial life world of Chromaria. In Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems (ALife 14). Citeseer, 793--800.Google ScholarCross Ref
- Russell K Standish. 2003. Open-ended artificial evolution. International Journal of Computational Intelligence and Applications 3, 02 (2003), 167--175.Google ScholarCross Ref
- Kenneth O Stanley and Risto Miikkulainen. 2002. Evolving neural networks through augmenting topologies. Evolutionary computation 10, 2 (2002), 99--127. Google ScholarDigital Library
- Danesh Tarapore, Jeff Clune, Antoine Cully, and Jean-Baptiste Mouret. 2016. How do different encodings influence the performance of the MAP-Elites algorithm?. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2016). ACM, 173--180. Google ScholarDigital Library
- R Paul Wiegand, William C Liles, and Kenneth A De Jong. 2001. An empirical analysis of collaboration methods in cooperative coevolutionary algorithms. In Proceedings of the genetic and evolutionary computation conference (GECCO), Vol. 2611. 1235--1245. Google ScholarDigital Library
Index Terms
- Minimal criterion coevolution: a new approach to open-ended search
Recommendations
Benchmarking open-endedness in minimal criterion coevolution
GECCO '19: Proceedings of the Genetic and Evolutionary Computation ConferenceMinimal criterion coevolution (MCC) was recently introduced to show that a very simple criterion can lead to an open-ended expansion of two coevolving populations. Inspired by the simplicity of striving to survive and reproduce in nature, in MCC there ...
POET: open-ended coevolution of environments and their optimized solutions
GECCO '19: Proceedings of the Genetic and Evolutionary Computation ConferenceHow can progress in machine learning and reinforcement learning be automated to generate its own never-ending curriculum of challenges without human intervention? The recent emergence of quality diversity (QD) algorithms offers a glimpse of the ...
Revising the evolutionary computation abstraction: minimal criteria novelty search
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computationThough 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 ...
Comments