research-article

Evolvability and complexity properties of the digital circuit genotype-phenotype map

Authors:

Alden H. Wright,

Cheyenne L. LaueAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 840 - 848

https://doi.org/10.1145/3449639.3459393

Published: 26 June 2021 Publication History

Abstract

Recent research on genotype-phenotype (G-P) maps in natural evolution has contributed significantly to our understanding of neutrality, redundancy, robustness, and evolvability. Here we investigate the properties of the digital logic gate G-P map and show that this map shares many of the common properties of natural G-P maps, with the exception of a positive relationship between evolvability and robustness. Our results show that in some cases robustness and evolvability may be negatively related as a result of the method used to approximate evolvability. We give two definitions of circuit complexity and empirically show that these two definitions are closely related. This study leads to a better understanding of the relationships between redundancy, robustness, and evolvability in genotype-phenotype maps. We further investigate these results in the context of complexity and show the relationships between phenotypic complexity and phenotypic redundancy, robustness and evolvability.

Supplementary Material

PDF File (p840-wright_suppl.pdf)

p840-wright_suppl.pdf

Download
420.83 KB

References

[1]

Adami, C. et al. 2000. Evolution of biological complexity. Proceedings of the National Academy of Sciences. 97, 9 (2000), 4463--4468.

[2]

Adami, C. 2002. What is complexity? BioEssays. 24, 12 (2002), 1085--1094.

[3]

Ahnert, S.E. 2017. Structural properties of genotype-phenotype maps. Journal of The Royal Society Interface. 14, 132 (2017), 20170275.

[4]

Barnett, L. 2001. Netcrawling-optimal evolutionary search with neutral networks. Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No. 01TH8546) (2001), 30--37.

[5]

Bedau, M.A. 2009. The evolution of complexity. Mapping the future of biology. Springer. 111--130.

[6]

Catalán, P. et al. 2018. Adding levels of complexity enhances robustness and evolvability in a multilevel genotype-phenotype map. Journal of The Royal Society Interface. 15, 138 (2018), 20170516.

[7]

Crutchfield, J. and van Nimwegen, E. 2002. The Evolutionary Unfolding of Complexity. L. Landweber and E. Winfree, eds. Springer Berlin Heidelberg. 67--94.

[8]

Gavrilets, S. 2003. Perspective: models of speciation: what have we learned in 40 years? Evolution. 57, 10 (2003), 2197--2215.

[9]

Gavrilets, S. and Gravner, J. 1997. Percolation on the Fitness Hypercube and the Evolution of Reproductive Isolation. Journal of Theoretical Biology. 184, 1 (Jan. 1997), 51--64.

[10]

Greenbury, S.F. et al. 2013. A tractable genotype-phenotype map for the self-assembly of protein quaternary structure. arXiv preprint arXiv:1311.0399. (2013).

[11]

Greenbury, S.F. and Ahnert, S.E. 2015. The organization of biological sequences into constrained and unconstrained parts determines fundamental properties of genotype-phenotype maps. Journal of The Royal Society Interface. 12, 113 (2015), 20150724.

[12]

Grünwald, P.D. and Vitányi, P.M.B. 2008. Algorithmic information theory. Handbook of the Philosophy of Information. (2008), 281--320.

[13]

Hosseini, S.-R. and Wagner, A. 2016. The potential for non-adaptive origins of evolutionary innovations in central carbon metabolism. BMC Systems Biology. 10, 1 (2016), 1--14.

[14]

Hu, T. et al. 2020. A network perspective on genotype-phenotype mapping in genetic programming. Genetic Programming and Evolvable Machines. (2020), 1--23.

[15]

Hu, T. and Banzhaf, W. 2018. Neutrality, robustness, and evolvability in genetic programming. Genetic Programming Theory and Practice XIV. Springer. 101--117.

[16]

Korb, K.B. and Dorin, A. 2011. Evolution unbound: releasing the arrow of complexity. Biology & philosophy. 26, 3 (2011), 317--338.

[17]

Laue, C.L. and Wright, A.H. 2019. Landscape revolutions for cultural evolution: Integrating advanced fitness landscapes into the study of cultural change. Handbook of Evolutionary Research in Archaeology. Springer. 127--147.

[18]

Lynch, M. and Walsh, B. 2007. The origins of genome architecture. Sinauer Associates Sunderland (MA).

[19]

Macia, J. and Solé, R. V 2009. Distributed robustness in cellular networks: insights from synthetic evolved circuits. Journal of the Royal Society Interface. 6, 33 (2009), 393--400.

[20]

Miller, J.F. et al. 2000. Principles in the evolutionary design of digital circuits---Part I. Genetic programming and evolvable machines. 1, 1--2 (2000), 7--35.

[21]

Miller, J.F. and Smith, S.L. 2006. Redundancy and computational efficiency in cartesian genetic programming. IEEE Transactions on Evolutionary Computation. 10, 2 (2006), 167--174.

Digital Library

[22]

Nickerson, K.L. et al. 2018. Measuring evolvability and accessibility using the Hyperlink-Induced Topic Search algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (2018), 1175--1182.

Digital Library

[23]

Raman, K. and Wagner, A. 2011. The evolvability of programmable hardware. Journal of The Royal Society Interface. 8, 55 (Feb. 2011), 269--281.

[24]

Rigato, E. and Fusco, G. 2020. Effects of phenotypic robustness on adaptive evolutionary dynamics. Evolutionary Biology. 47, 3 (2020), 233--239.

[25]

Rodrigues, J.F.M. and Wagner, A. 2009. Evolutionary plasticity and innovations in complex metabolic reaction networks. PLoS Comput Biol. 5, 12 (2009), e1000613.

[26]

Tononi, G. et al. 1994. A measure for brain complexity: relating functional segregation and integration in the nervous system. Proceedings of the National Academy of Sciences. 91, 11 (1994), 5033--5037.

[27]

Tononi, G. et al. 1998. Complexity and coherency: integrating information in the brain. Trends in cognitive sciences. 2, 12 (1998), 474--484.

[28]

Vassilev, V.K. and Miller, J.F. 2000. The Advantages of Landscape Neutrality in Digital Circuit Evolution. Ices'00. (2000), 252--263.

[29]

Wagner, A. 2017. Information theory, evolutionary innovations and evolvability. Philosophical Transactions of the Royal Society B: Biological Sciences. 372, 1735 (2017), 20160416.

[30]

Wagner, A. 2008. Robustness and evolvability: a paradox resolved. Proceedings of the Royal Society B: Biological Sciences. 275, 1630 (2008), 91--100.

[31]

Wagner, A. 2011. The molecular origins of evolutionary innovations. Trends in Genetics. 27, 10 (Oct. 2011), 397--410.

[32]

Wagner, A. 2012. The role of robustness in phenotypic adaptation and innovation. Proceedings of the Royal Society B: Biological Sciences. 279, 1732 (2012), 1249--1258.

[33]

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

Cited By

Martin NCamargo CLouis A(2024)Bias in the arrival of variation can dominate over natural selection in Richard Dawkins’s biomorphsPLOS Computational Biology10.1371/journal.pcbi.101189320:3(e1011893)Online publication date: 27-Mar-2024
https://doi.org/10.1371/journal.pcbi.1011893
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
Wright ALaue C(2023)Evolving Complexity is HardGenetic Programming Theory and Practice XIX10.1007/978-981-19-8460-0_10(233-253)Online publication date: 12-Mar-2023
https://doi.org/10.1007/978-981-19-8460-0_10
Show More Cited By

Index Terms

Evolvability and complexity properties of the digital circuit genotype-phenotype map
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Randomized search
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

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 ...
A network perspective on genotype–phenotype mapping in genetic programming
Abstract
Genotype–phenotype mapping plays an essential role in the design of an evolutionary algorithm. Variation occurs at the genotypic level but fitness is evaluated at the phenotypic level, therefore, this mapping determines if and how variations are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 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 the author(s) 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: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
144
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Martin NCamargo CLouis A(2024)Bias in the arrival of variation can dominate over natural selection in Richard Dawkins’s biomorphsPLOS Computational Biology10.1371/journal.pcbi.101189320:3(e1011893)Online publication date: 27-Mar-2024
https://doi.org/10.1371/journal.pcbi.1011893
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
Wright ALaue C(2023)Evolving Complexity is HardGenetic Programming Theory and Practice XIX10.1007/978-981-19-8460-0_10(233-253)Online publication date: 12-Mar-2023
https://doi.org/10.1007/978-981-19-8460-0_10
Langdon W(2022)Deep Genetic Programming Trees Are RobustACM Transactions on Evolutionary Learning and Optimization10.1145/35397382:2(1-34)Online publication date: 16-Aug-2022
https://dl.acm.org/doi/10.1145/3539738
Johnston IDingle KGreenbury SCamargo CDoye JAhnert SLouis A(2022)Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolutionProceedings of the National Academy of Sciences10.1073/pnas.2113883119119:11Online publication date: 11-Mar-2022
https://doi.org/10.1073/pnas.2113883119

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