research-article

Revising the evolutionary computation abstraction: minimal criteria novelty search

Authors:

Kenneth O. StanleyAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 103 - 110

https://doi.org/10.1145/1830483.1830503

Published: 07 July 2010 Publication History

Abstract

Though 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 capture how natural evolution discovers complexity. Alternatively, this paper proposes that natural evolution can be abstracted as a process that discovers many ways to express the same functionality. That is, all successful organisms must meet the same minimal criteria of survival and reproduction. This abstraction leads to the key idea in this paper: Searching for novel ways of meeting the same minimal criteria, which is an accelerated model of this new abstraction, may be an effective search algorithm. Thus the existing novelty search method, which rewards any new behavior, is extended to enforce minimal criteria. Such minimal criteria novelty search prunes the space of viable behaviors and may often be more efficient than the search for novelty alone. In fact, when compared to the raw search for novelty and traditional fitness-based search in the two maze navigation experiments in this paper, minimal criteria novelty search evolves solutions more consistently. It is possible that refining the evolutionary computation abstraction in this way may lead to solving more ambitious problems and evolving more complex artificial organisms.

References

[1]

T. Aaltonen et al. Measurement of the top quark mass with dilepton events selected using neuroevolution at CDF. Physical Review Letters, 2009.

[2]

Christoph Adami, Charles Ofria, and Travis C. Collier. Evolution of biological complexity. Proc. of the Natl. Academy of Sciences, USA, 97: 4463--4468, 2000.

[3]

Brian Allen and Petros Faloutsos. Complex networks of simple neurons for bipedal locomotion. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2009.

Digital Library

[4]

W. B. Arthur. On the evolution of complexity. In G. Cownan, D. Pines, and D. Meltzer, editors, Complexity: Metaphors, Models and Reality, pages 65--81. Addison-Wesley, Reading, MA, 1994.

Digital Library

[5]

Mark Bedau. Four puzzles about life. Artificial Life, 4: 125--140, 1998.

Digital Library

[6]

A. D. Channon and R. I. Damper. Towards the evolutionary emergence of increasingly complex advantageous behaviours. International Journal of Systems Science, 31 (7): 843--860, 2000.

[7]

Charles Darwin. On the Origin of Species by Means of Natural Selection or the Preservation of Favored Races in the Struggle for Life. Murray, London, 1859.

[8]

R. Dawkins. Human chauvinism. Evolution, 51 (3): 1015--1020, 1997.

[9]

Richard Dawkins. The Selfish Gene. Oxford University Press, Oxford, UK, 3rd edition, 1989.

[10]

J. A. Endler and J. J. D. Greenwood. Frequency-Dependent Predation, Crypsis and Aposematic Coloration {and Discussion}. Philosophical Transactions of the Royal Society of London. B, Biological Sciences, 319 (1196): 505--523, 1988.

[11]

Sevan Ficici and Jordan B. Pollack. Challenges in coevolutionary learning: Arms-race dynamics, open-endedness, and mediocre stable states. In Proceedings of the Sixth International Conference on Artificial Life, pages 238--247. MIT Press, 1998.

Digital Library

[12]

Steven Jay Gould. Full House: The Spread of Excellence from Plato to Darwin. Harmony Books, 1996.

[13]

Inman Harvey. The Artificial Evolution of Adaptive Behavior. PhD thesis, School of Cognitive and Computing Sciences, University of Sussex, Sussex, 1993.

[14]

Kimberly A. Hughes, Linh Du, F. Helen Rodd, and David N. Reznick. Familiarity leads to female mate preference for novel males in the guppy, poecilia reticulata. Animal Behavior, 58 (4): 907--916, 1999.

[15]

George Kampis and László Gulyás. Full body: The importance of the phenotype in evolution. Artificial Life, 14 (3): 375--386, 2008.

Digital Library

[16]

Joel Lehman and Kenneth O. Stanley. Exploiting open-endedness to solve problems through the search for novelty. In Proc. of the Eleventh Intl. Conf. on Artificial Life (ALIFE XI), Cambridge, MA, 2008. MIT Press.

[17]

Michael Lynch. The evolution of genetic networks by non-adaptive processes. Nature Reviews Genetics, 8: 803--813, 2007a.

[18]

Michael Lynch. The frailty of adaptive hypotheses for the origins of organismal complexity. In Proc. Natl. Acad. Sci. USA, volume 104, pages 8597--8604, 2007b.

[19]

Andrew P. Martin. Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154 (2): 111--128, 1999.

[20]

Daniel W. McShea. Complexity and evolution: What everybody knows. Biol. and Phil., 6 (3): 303--324, 1991.

[21]

Thomas Miconi. Evolution and complexity: The double-edged sword. Artificial Life: Special Issue on the Evolution of Complexity, 2007.

Digital Library

[22]

Tom M. Mitchell. Machine Learning. McGraw-Hill, New York, 1997.

Digital Library

[23]

Jean-Baptiste Mouret. Novelty-based multiobjectivization. In Proc. of the Workshop on Exploring New Horizons in Evolutionary Design of Robots,2009 IEEE/RSJ Intl Conf on Intelligent Robots and Systems, 2009.

[24]

C. L. Nehaniv and J. L. Rhodes. On the manner in which biological complexity may grow. In Mathematical and Computational Biology, volume 26 of Lectures on Mathematics in the Life Sciences, pages 93--102. American Mathematical Society, 1999.

[25]

Sebastian Risi, Sandy D. Vanderbleek, Charles E. Hughes, and Kenneth O. Stanley. How novelty search escapes the deceptive trap of learning to learn. In Proc. of the Genetic and Evolutionary Computation Conf. (GECCO-2009), New York, NY, 2009. ACM.

Digital Library

[26]

Michael Ruse. Evolution and progress. Tree, 8 (2): 55--60, 1993.

[27]

J. Schmidhuber. Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts. Connection Science, 18 (2): 173--187, 2006.

[28]

Karl Sigmund. Games of Life: Explorations in Ecology, Evolution and Behaviour. Oxford University Press, Inc., New York, NY, USA, 1993.

Digital Library

[29]

Andrea Soltoggio and Ben Jones. Novelty of behaviour as a basis for the neuro-evolution of operant reward learning. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-2009), New York, NY, 2009. ACM.

Digital Library

[30]

Russell Standish. Open-ended artificial evolution. Intl. Journal of Comp. Intell. and Applications, 3 (167), 2003.

[31]

Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Trans. on Evol. Comp. Special Issue on Evol. Comp. and Games, 9 (6): 653--668, 2005.

Digital Library

[32]

Kenneth O. Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10: 99--127, 2002.

Digital Library

[33]

Kenneth O. Stanley and Risto Miikkulainen. A taxonomy for artificial embryogeny. Artificial Life, 9 (2): 93--130, 2003.

Digital Library

[34]

Kenneth O. Stanley and Risto Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Art. Intell. Research, 21: 63--100, 2004a.

Digital Library

[35]

Kenneth O. Stanley and Risto Miikkulainen. Evolving a roving eye for Go. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Berlin, 2004b. Springer Verlag.

[36]

James D. Watson, Nancy H. Hopkins, Jeffrey W. Roberts, Joan A. Steitz, and Alan M. Weiner. Molecular Bio. of the Gene Fourth Edition. The Benjamin Cummings Publishing Company, Inc., 1987.

[37]

Shimon Whiteson and Peter Stone. Evolutionary function approximation for reinforcement learning. Journal of Machine Learning Research, 7: 877--917, May 2006.

Digital Library

[38]

N. Zaera, D. Cliff, and J. Bruten. (Not) evolving collective behaviours in synthetic fish. In From Animals to Animats 4: Proc. of the Fourth Intl. Conf. on Sim. of Adaptive Behavior. MIT Press Bradford Books., 1996.

Cited By

Höfling LSzatko KBehrens CDeng YQiu YKlindt DJessen ZSchwartz GBethge MBerens PFranke KEcker AEuler T(2024)A chromatic feature detector in the retina signals visual context changeseLife10.7554/eLife.8686013Online publication date: 4-Oct-2024
https://doi.org/10.7554/eLife.86860
Stock MGorochowski T(2024)Open-endedness in synthetic biology: A route to continual innovation for biological designScience Advances10.1126/sciadv.adi362110:3Online publication date: 19-Jan-2024
https://doi.org/10.1126/sciadv.adi3621
Anand DArulselvi GBalaji GGhantasala G(2024)Deep Convolutional Extreme Learning Machine with AlexNet-Based Bone Cancer Classification Using Whole-Body Scan ImagesDigital Transformation10.1007/978-981-99-8118-2_13(307-325)Online publication date: 30-Jan-2024
https://doi.org/10.1007/978-981-99-8118-2_13
Show More Cited By

Index Terms

Revising the evolutionary computation abstraction: minimal criteria novelty search
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Neural networks

Recommendations

Surprise Search: Beyond Objectives and Novelty
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Grounded in the divergent search paradigm and inspired by the principle of surprise for unconventional discovery in computational creativity, this paper introduces surprise search as a new method of evolutionary divergent search. Surprise search is ...
Minimal criterion coevolution: a new approach to open-ended search
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

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 ...
Evolving a diversity of virtual creatures through novelty search and local competition
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

An ambitious challenge in artificial life is to craft an evolutionary process that discovers a wide diversity of well-adapted virtual creatures within a single run. Unlike in nature, evolving creatures in virtual worlds tend to converge to a single ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

120
Total Citations
View Citations
461
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)8

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Höfling LSzatko KBehrens CDeng YQiu YKlindt DJessen ZSchwartz GBethge MBerens PFranke KEcker AEuler T(2024)A chromatic feature detector in the retina signals visual context changeseLife10.7554/eLife.8686013Online publication date: 4-Oct-2024
https://doi.org/10.7554/eLife.86860
Stock MGorochowski T(2024)Open-endedness in synthetic biology: A route to continual innovation for biological designScience Advances10.1126/sciadv.adi362110:3Online publication date: 19-Jan-2024
https://doi.org/10.1126/sciadv.adi3621
Anand DArulselvi GBalaji GGhantasala G(2024)Deep Convolutional Extreme Learning Machine with AlexNet-Based Bone Cancer Classification Using Whole-Body Scan ImagesDigital Transformation10.1007/978-981-99-8118-2_13(307-325)Online publication date: 30-Jan-2024
https://doi.org/10.1007/978-981-99-8118-2_13
Zammit MLiapis AYannakakis G(2024)MAP-Elites with Transverse Assessment for Multimodal Problems in Creative DomainsArtificial Intelligence in Music, Sound, Art and Design10.1007/978-3-031-56992-0_26(401-417)Online publication date: 29-Mar-2024
https://doi.org/10.1007/978-3-031-56992-0_26
Omelianenko I(2023)Simulation of the autonomous maze navigation using the NEAT algorithmPROBLEMS IN PROGRAMMING10.15407/pp2023.04.076(76-89)Online publication date: Dec-2023
https://doi.org/10.15407/pp2023.04.076
Fontaine MNikolaidis SSilva SPaquete L(2023)Covariance Matrix Adaptation MAP-AnnealingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590389(456-465)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590389
Dharna AHoover ATogelius JSoros L(2023)Transfer Dynamics in Emergent Evolutionary CurriculaIEEE Transactions on Games10.1109/TG.2022.315102515:2(157-170)Online publication date: Jun-2023
https://doi.org/10.1109/TG.2022.3151025
Li XRoth CMohr D(2023)Neural network based rate- and temperature-dependent Hosford–Coulomb fracture initiation modelInternational Journal of Mechanical Sciences10.1016/j.ijmecsci.2023.108643260(108643)Online publication date: Dec-2023
https://doi.org/10.1016/j.ijmecsci.2023.108643
Heider MStegherr HPätzel DSraj RWurth JVolger BHähner J(2023)Discovering Rules for Rule-Based Machine Learning with the Help of Novelty SearchSN Computer Science10.1007/s42979-023-02198-x4:6Online publication date: 12-Oct-2023
https://doi.org/10.1007/s42979-023-02198-x
Taherkhani ACosma GMcGinnity T(2023)A Deep Convolutional Neural Network for Time Series Classification with Intermediate TargetsSN Computer Science10.1007/s42979-023-02159-44:6Online publication date: 28-Oct-2023
https://doi.org/10.1007/s42979-023-02159-4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents