Beyond open-endedness: quantifying impressiveness
Lehman, J., Stanley, K.: Beyond open-endedness: quantifying impressiveness. In: Adami, C., et al. (eds.) Proceedings of the Thirteenth International Conference on Artificial Life (ALIFE XIII). MIT Press (2012)
This paper seeks to illuminate and quantify a feature of natu- ral evolution that correlates to our sense of its intuitive great- ness: Natural evolution evolves impressive artifacts. Within artificial life, abstractions aiming to capture what makes nat- ural evolution so powerful often focus on the idea of open- endedness, which relates to boundless diversity, complex- ity, or adaptation. However, creative systems that have passed tests of open-endedness raise the possibility that open- endedness does not always correlate to impressiveness in ar- tificial life simulations. In other words, while natural evo- lution is both open-ended and demonstrates a drive towards evolving impressive artifacts, it may be a mistake to assume the two properties are always linked. Thus to begin to in- vestigate impressiveness independently in artificial systems, a novel definition is proposed: Impressive artifacts readily exhibit significant design effort. That is, the difficulty of cre- ating them is easy to recognize. Two heuristics, rarity and re-creation effort, are derived from this definition and applied to the products of an open-ended image evolution system. An important result is that that the heuristics intuitively separate different reward schemes and provide evidence for why each evolved picture is or is not impressive. The conclusion is that impressiveness may help to distinguish open-ended systems and their products, and potentially untangles an aspect of nat- ural evolution’s mystique that is masked by its co-occurrence with open-endedness.
Bedau, M., Snyder, E., Brown, C. T., and Packard, N. H. (1997). A comparison of evolutionary activity in artificial evolving systems and in the biosphere. In Husbands, P. and Harvey, I., editors, Proceedings Of The Fourth European Conference on Artificial Life, pages 125–134. MIT Press.
Bedau, M. A., Snyder, E., and Packard, N. H. (1998). A classi- fication of longterm evolutionary dynamics. In Adami, C., Belew, R., Kitano, H., and Taylor, C., editors, Proceedings of Artificial Life VI, pages 228–237, Cambridge, MA. MIT Press.
Channon, A. (2001). Passing the alife test: Activity statistics clas- sify evolution in geb as unbounded. In Proceedings of the Eu- ropean Conference on Artificial Life(ECAL-2001). Springer.
Channon, A. D. and Damper, R. I. (2000). Towards the evo- lutionary emergence of increasingly complex advantageous behaviours. International Journal of Systems Science, 31(7):843–860.
Darwin, C. (1859). On the Origin of Species by Means of Natural Selection or the Preservation of Favored Races in the Strug- gle for Life. Murray, London. Gasarch, W. (2002). The P =? NP poll. Sigact News, 33(2):34–47. Geng, L. and Hamilton, H. (2006). Interestingness measures for data mining: A survey. ACM Computing Surveys (CSUR), 38(3):9.
Kelly, K. (2010). What technology wants. Viking Press. 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, Proceed- ings of the Eleventh International Conference on Artificial Life (ALIFE XI), Cambridge, MA. MIT Press.
Lehman, J. and Stanley, K. O. (2011a). Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation.
Lehman, J. and Stanley, K. O. (2011b). Novelty seach and the prob- lem with objectives. In Genetic Programming in Theory and Practice IX (GPTP 2011), chapter 3, pages 37–56. Springer.
Maley, C. C. (1999). Four steps toward open-ended evolution. In Proceedings of the Genetic and Evolutionary Computation Conference(GECCO-1999), volume 2, pages 1336–1343, Or- lando, Florida, USA. IEEE Press.
Nehaniv, C. (2000). Measuring evolvability as the rate of complex- ity increase. In Maley, C. and Boudreau, E., editors, Artificial Life VII Workshop Proceedings, pages 55–57.
Neill, A. and Ridley, A. (1995). The philosophy of art: readings ancient and modern, pages 98–239. McGraw-Hill.
Reeves, C. (2000). Fitness landscapes and evolutionary algorithms. In Artificial Evolution, pages 3–20. Springer.
Schmidhuber, J. (2009). Driven by compression progress: A sim- ple principle explains essential aspects of subjective beauty, novelty, surprise, interestingness, attention, curiosity, creativ- ity, art, science, music, jokes. Anticipatory Behavior in Adap- tive Learning Systems, pages 48–76.
Secretan, J., Beato, N., D’Ambrosio, D., Rodriguez, A., Campbell, A., Folsom-Kovarik, J., and Stanley, K. (2011). Picbreeder: A case study in collaborative evolutionary exploration of design space. Evolutionary Computation, 19(3):373–403.
Standish, R. (2003). Open-ended artificial evolution. Interna- tional Journal of Computational Intelligence and Applica- tions, 3(167).
Stanley, K. (2007). Compositional pattern producing networks: A novel abstraction of development. Genetic Programming and Evolvable Machines, 8(2):131–162.
Stanley, K. O. and Miikkulainen, R. (2002). Evolving neural net- works through augmenting topologies. Evolutionary Compu- tation, 10:99–127.
Stanley, K. O. and Miikkulainen, R. (2004). Competitive coevolu- tion through evolutionary complexification. 21:63–100.
Taylor, T. and Hallam, J. (1998). Replaying the tape: An investiga- tion into the role of contingency in evolution. In Taylor, C., Langton, C., and Kitano, H., editors, Proceedings of Artificial Life VI, pages 256–265.
Woolley, B. G. and Stanley, K. O. (2011). On the deleterious ef- fects of a priori objectives on evolution and representation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2011). ACM.