research-article

Neutrality and variability: two sides of evolvability in linear genetic programming

Authors:

Wolfgang BanzhafAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 963 - 970

https://doi.org/10.1145/1569901.1570033

Published: 08 July 2009 Publication History

Abstract

The notion of evolvability has been put forward to describe the "core mechanism" of natural and artificial evolution. Recently, studies have revealed the influence of the environment upon a system's evolvability. In this contribution, we study the evolvability of a system in various environmental situations. We consider neutrality and variability as two sides of evolvability. The former makes a system tolerant to mutations and provides a hidden staging ground for future phenotypic changes. The latter produces explorative variations yielding phenotypic improvements. Which of the two dominates is influenced by the environment. We adopt two tools for this study of evolvability: 1) the rate of adaptive evolution, which captures the observable adaptive variations driven by evolvability; and 2) the variability of individuals, which measures the potential of an individual to vary functionally. We apply these tools to a Linear Genetic Programming system and observe that evolvability is able to exploit its two sides in different environmental situations.

References

[1]

]]L. Altenberg. The evolution of evolvability in genetic programming. In Advances in Genetic Programming pages 47--74. MIT Press, Cambridge, MA, USA, 1994.

Digital Library

[2]

]]W. Banzhaf and A. Leier. Evolution on neutral networks in genetic programming. In Genetic Programming Theory and Practice III pages 207--221. Springer, 2006.

[3]

]]M. A. Bedau and N. H. Packard. Evolution of evolvability via adaptation of mutation rates. BioSystems 69(2):143--162, 2003.

[4]

]]T. V. Belle and D. H. Ackley. Code factoring and the evolution of evolvability. In GECCO '02: Proceedings of the Genetic and Evolutionary Computation Conference pages 1383--1390. ACM, 2002.

[5]

]]M. Brameier and W. Banzhaf. Linear Genetic Programming Number XVI in Genetic and Evolutionary Computation. Springer, 2007.

Digital Library

[6]

]]S. Collins, J. de Meaux, and C. Acquisti. Adaptive walks toward a moving optimum. Genetics 176(2):1089--1099, 2007.

[7]

]]M. Conrad. The geometry of evolution. BioSystems 24(11):61--81, 1990.

[8]

]]R. Dawkins. The evolution of evolvability. In Artificial Life: The Quest for a New Creation pages 201--220. Addison-Wesley, Reading, MA, USA, 1989.

[9]

]]D. J. Earl and M. W. Deem. Evolvability is a selectable trait. Proceedings of the National Academy of Sciences 101(32):11531--11536, 2004.

[10]

]]M. Ebner, M. Shackleton, and R. Shipman. How neutral networks in fluence evolvability. Complexity 7(2):19--33, 2002.

Digital Library

[11]

]]T. Hu and W. Banzhaf. Nonsynonymous to synonymous substitution ratio ka/ks Measurement for rate of evolution in evolutionary computation. In Proceedings of the 10th International Conference on Parallel Problem Solving from Nature (PPSN X) volume 5199 of LNCS pages 448--457. Springer, 2008.

[12]

]]Y. Jin, R. Gruna, I. Paenke, and B. Sendhoff. Multi-objective optimization of robustness and innovation in redundant genetic representations. In Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multicriteria Decision-Making pages 38--45. IEEE Press, 2009.

[13]

]]N. Kashtan, E. Noor, and U. Alon. Varying environments can speed up evolution. Proceedings of the National Academy of Sciences 104(34):13713--13716, 2007.

[14]

]]M. W. Kirschner and J. C. Gerhart. Evolvability. Proceedings of the National Academy of Sciences 95(15):8420--8427, 1998.

[15]

]]K. F. Liem. Key evolutionary innovations, differential diversity, and symecomorphosis. In Evolutioanry Innovations pages 147--170. University of Chicago Press, Chicago, IL, USA, 1990.

[16]

]]P. Marrow, M. Heath, and I. I. Re. Evolvability: Evolution, Computation, and Biology. In GECCO'99: Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop on Evolvability pages 30--33. Morgan Kaufmann, 1999.

[17]

]]L. A. Meyers, F. D. Ancel, and M. Lachmann. Evolution of genetic potential. PLoS Computational Biology 1(3):0236--0243, 2005.

[18]

]]C. L. Nehaniv. Measuring evolvability as the rate of complexity increase. In Proceedings of the Artificial Life VII Workshop pages 55--57. MIT Press, 2000.

[19]

]]H. A. Orr. The population genetics of adaptation:the distribution of factors fixed during adaptive evolution Evolution 52(4):935--949, 1998.

[20]

]]M. Parter, N. Kashtan, and U. Alon. Facilitated variation:How evolution learns from past environments to generalize to new environments. PLoS Computational Biology 4(11):e1000206, 2008.

[21]

]]R. A. Raff. The Shape of Life: Genes, Development, and the Evolution of Animal Form Universityof Chicago Press, Chicago, IL, USA, 1996.

[22]

]]J. Reisinger and R. Miikkulainen. Selecting for evolvable representations. In GECCO'06: Proceedings of the 2006 Genetic and Evolutionary Computation Conference pages 1297--1304. ACM, 2006.

Digital Library

[23]

]]A. Wagner. Robustness, evolvability, and neutrality. Federation of European Biochemical Societies Letters 579(8):1772--1778, 2005.

[24]

]]A. Wagner. Robustness and evolvability:A paradox resolved. Proceedings of The Royal Society B 275(1630):91--100, 2008.

[25]

]]G. P. Wagner and L. Altenberg. Complex adaptations and the evolution of evolvability. Evolution 50(3):967--976, 1996.

[26]

]]Z. Yang and J. P. Bielawski. Statistical methods for detecting molecular adaptation. Trends in Ecology and Evolution 15(12):496--503, 2000.

[27]

]]T. Yu. Program evolvability under environmental variations and neutrality. In Proceedings of the 9th European Conference on Advances in Artificial Life (ECAL07)pages 835--844. Springer, 2007.

Digital Library

Cited By

Banzhaf WHu TOchoa G(2024)How the Combinatorics of Neutral Spaces Leads Genetic Programming to Discover Simple SolutionsGenetic Programming Theory and Practice XX10.1007/978-981-99-8413-8_4(65-86)Online publication date: 18-Feb-2024
https://doi.org/10.1007/978-981-99-8413-8_4
Hu TOchoa GBanzhaf W(2023)Phenotype Search Trajectory Networks for Linear Genetic ProgrammingGenetic Programming10.1007/978-3-031-29573-7_4(52-67)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_4
Atkinson TPlump DStepney S(2019)Evolving graphs with semantic neutral driftNatural Computing10.1007/s11047-019-09772-4Online publication date: 29-Oct-2019
https://doi.org/10.1007/s11047-019-09772-4
Show More Cited By

Recommendations

Program evolvability under environmental variations and neutrality
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computation

Biological organisms employ various mechanisms to cope with the dynamic environments they live in. One recent research reported that depending on the rates of environmental variation, populations evolve toward genotypes in different regions of the ...
Robustness and evolvability of recombination in linear genetic programming
EuroGP'13: Proceedings of the 16th European conference on Genetic Programming

The effect of neutrality on evolutionary search is known to be crucially dependent on the distribution of genotypes over phenotypes. Quantitatively characterizing robustness and evolvability in genotype and phenotype spaces greatly helps to understand ...
Evolutionary dynamics on multiple scales: a quantitative analysis of the interplay between genotype, phenotype, and fitness in linear genetic programming

Redundancy is a ubiquitous feature of genetic programming (GP), with many-to-one mappings commonly observed between genotype and phenotype, and between phenotype and fitness. If a representation is redundant, then neutral mutations are possible. A ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
136
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Banzhaf WHu TOchoa G(2024)How the Combinatorics of Neutral Spaces Leads Genetic Programming to Discover Simple SolutionsGenetic Programming Theory and Practice XX10.1007/978-981-99-8413-8_4(65-86)Online publication date: 18-Feb-2024
https://doi.org/10.1007/978-981-99-8413-8_4
Hu TOchoa GBanzhaf W(2023)Phenotype Search Trajectory Networks for Linear Genetic ProgrammingGenetic Programming10.1007/978-3-031-29573-7_4(52-67)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_4
Atkinson TPlump DStepney S(2019)Evolving graphs with semantic neutral driftNatural Computing10.1007/s11047-019-09772-4Online publication date: 29-Oct-2019
https://doi.org/10.1007/s11047-019-09772-4
Hu TTomassini MBanzhaf W(2019)Complex Network Analysis of a Genetic Programming Phenotype NetworkGenetic Programming10.1007/978-3-030-16670-0_4(49-63)Online publication date: 27-Mar-2019
https://doi.org/10.1007/978-3-030-16670-0_4
Hu TBanzhaf W(2018)Neutrality, Robustness, and Evolvability in Genetic ProgrammingGenetic Programming Theory and Practice XIV10.1007/978-3-319-97088-2_7(101-117)Online publication date: 25-Oct-2018
https://doi.org/10.1007/978-3-319-97088-2_7
Hu TBanzhaf WNeumann FSutton A(2016)Quantitative Analysis of Evolvability using Vertex Centralities in Phenotype NetworkProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908940(733-740)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908940
Troiano LBirtolo CArmenise R(2015)Searching optimal menu layouts by linear genetic programmingJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-015-0322-77:2(239-256)Online publication date: 15-Sep-2015
https://doi.org/10.1007/s12652-015-0322-7
Hu TBanzhaf WMoore J(2014)The effects of recombination on phenotypic exploration and robustness in evolutionArtificial Life10.1162/ARTL_a_0014520:4(457-470)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1162/ARTL_a_00145
Hu TBanzhaf WMoore J(2014)Population Exploration on Genotype Networks in Genetic ProgrammingParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_42(424-433)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10762-2_42
Hu TBanzhaf WMoore J(2013)Robustness and evolvability of recombination in linear genetic programmingProceedings of the 16th European conference on Genetic Programming10.1007/978-3-642-37207-0_9(97-108)Online publication date: 3-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37207-0_9
Show More Cited By

View Options

Get Access

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