More Web Proxy on the site http://driver.im/

research-article

Quantitative Analysis of Evolvability using Vertex Centralities in Phenotype Network

Authors:

Wolfgang BanzhafAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 733 - 740

https://doi.org/10.1145/2908812.2908940

Published: 20 July 2016 Publication History

Abstract

In an evolutionary system, robustness describes the resilience to mutational and environmental changes, whereas evolvability captures the capability of generating novel and adaptive phenotypes. The research literature has not seen an effective quantification of phenotypic evolvability able to predict the evolutionary potential of the search for novel phenotypes. In this study, we propose to characterize the mutational potential among different phenotypes using the phenotype network, where vertices are phenotypes and edges represent mutational connections between them. In the framework of such a network, we quantitatively analyze the evolvability of phenotypes by exploring a number of vertex centrality measures commonly used in complex networks. In our simulation studies we use a Linear Genetic Programming system and a population of random walkers. Our results suggest that the weighted eigenvector centrality serves as the best estimator of phenotypic evolvability.

References

[1]

W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone. Genetic Programming: An Introduction. Morgan Kaufmann, 1998.

Digital Library

[2]

A. Bavelas. Communication patterns in task-oriented groups. Journal of the Acoustical Society of America, 22:725--730, 1950.

[3]

P. Bonacich. Power and centrality: A family of measures. American Journal of Sociology, 92(5):1170--1182, 1987.

[4]

M. F. Brameier and W. Banzhaf. A comparison of linear genetic programming and neural networks in medical data mining. IEEE Transactions on Evolutionary Computation, 5(1):17--26, 2001.

Digital Library

[5]

M. F. Brameier and W. Banzhaf. Linear Genetic Programming. Springer, 2007.

Digital Library

[6]

S. Ciliberti, O. C. Martin, and A. Wagner. Innovation and robustness in complex regulatory gene networks. Proceedings of the National Academy of Sciences, 104(34):13591--13596, 2007.

[7]

M. C. Cowperthwaite, E. P. Economo, W. R. Harcombe, E. L. Miller, and L. A. Meyers. The ascent of the abundant: How mutational networks constrain evolution. PLoS Computational Biology, 4(7):e1000110, 2008.

[8]

B. C. Daniels, Y.-J. Chen, J. P. Sethna, R. N. Gutenkunst, and C. R. Myers. Sloppiness, robustness, and evolvability in systems biology. Current Opinion in Biotechnology, 19:389--395, 2008.

[9]

J. A. G. M. de Visser, J. Hermission, G. P. Wagner, L. A. Meyers, H. Bagheri-Chaichian, and et al. Evolution and detection of genetic robustness. Evolution, 57(9):1959--1972, 2003.

[10]

J. A. Draghi, T. L. Parsons, G. P. Wagner, and J. B. Plotkin. Mutational robustness can facilitate adaptation. Nature, 463:353--355, 2010.

[11]

E. Ferrada and A. Wagner. Protein robustness promotes evolutionary innovations on large evolutionary time-scales. Proceedings of The Royal Society B, 275:1595--1602, 2008.

[12]

L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35--41, 1977.

[13]

E. Galvan-Lopez and R. Poli. An empirical investigation of how and why neutrality affects evolutionary search. In M. Cattolico, editor, Proceedings of the Genetic and Evolutionary Computation Conference, pages 1149--1156, 2006.

Digital Library

[14]

A. Guven. Linear genetic programming for time-series modeling of daily flow rate. Journal of Earth System Science, 118(2):137--146, 2009.

[15]

T. Hu and W. Banzhaf. Neutrality and variability: Two sides of evolvability in linear genetic programming. In F. Rothlauf, editor, Proceedings of the Genetic and Evolutionary Computation Conference, pages 963--970, 2009.

Digital Library

[16]

T. Hu, W. Banzhaf, and J. H. Moore. Robustness and evolvability of recombination in linear genetic programming. In Proceedings of the European Conference on Genetic Programming, volume 7831 of Lecture Notes in Computer Science, pages 97--108, 2013.

Digital Library

[17]

T. Hu, J. H. Moore, and W. Banzhaf. The effects of recombination on phenotypic exploration and robustness in evolution. Artificial Life, 20(4):457--470, 2014.

Digital Library

[18]

T. Hu, J. L. Payne, W. Banzhaf, and J. H. Moore. Robustness, evolvability, and accessibility in linear genetic programming. In S. Silva, J. A. Foster, M. Nicolau, P. Machado, and M. Giacobini, editors, Proceedings of the European Conference on Genetic Programming, volume 6621 of Lecture Notes in Computer Science, pages 13--24, 2011.

Digital Library

[19]

T. Hu, J. L. Payne, W. Banzhaf, and J. H. Moore. Evolutionary dynamics on multiple scales: A quantitative analysis of the interplay between genotype, phenotype, and fitness in linear genetic programming. Genetic Programming and Evolvable Machines, 13:305--337, 2012.

Digital Library

[20]

M. A. Huynen, P. F. Stadler, and W. Fontana. Smoothness within ruggedness: The role of neutrality in adaptation. Proceedings of the National Academy of Sciences, 93:397--401, 1996.

[21]

H. Jeong, S. P. Mason, A. L. Barabasi, and Z. N. Oltvai. Lethality and centrality in protein networks. Nature, 411:41--42, 2001.

[22]

M. Kirschner and J. Gerhart. Evolvability. Proceedings of the National Academy of Sciences, 95:8420--8427, 1998.

[23]

C. R. Landry, B. Lemos, S. A. Rifkin, W. J. Dickinson, and D. L. Hartl. Genetic properties influcing the evolvability of gene expression. Science, 317:118--121, 2007.

[24]

R. E. Lenski, J. E. Barrick, and C. Ofria. Balancing robustness and evolvability. PLoS Biology, 4(12):e428, 2006.

[25]

M. Li, J. Wang, H. Wang, and Y. Pan. Identification of essential proteins from weighted protein-protein interaction networks. Journal of Bioinformatics and Computational Biology, 11(3):1341002, 2013.

[26]

J. Masel and M. V. Trotter. Robustness and evolvability. Trends in Genetics, 26:406--414, 2010.

[27]

R. C. McBride, C. B. Ogbunugafor, and P. E. Turner. Robustness promotes evolvability of thermotolerance in an RNA virus. BMC Evolutionary Biology, 8:231, 2008.

[28]

J. F. Miller, editor. Cartesian genetic programming. Springer, 2011.

[29]

J. F. Miller and P. Thomson. Cartesian genetic programming. In Prodeedings of the 3rd European Conference on Genetic Programming, volume 1802 of Lecture Notes in Computer Science, pages 121--132. Springer, 2000.

Digital Library

[30]

C. L. Nehaniv. Measuring evolvability as the rate of complexity increase. In C. C. Maley and E. Boudreau, editors, Artificial Life VII Workshop Proceedings, pages 55--57, 2000.

[31]

M. E. J. Newman. Analysis of weighted networks. Physical Review E, 70(5):56--131, 2004.

[32]

M. E. J. Newman. Networks: An Introduction. Oxford University Press, 2010.

Digital Library

[33]

M. Pigliucci. Is evolvability evolvable? Nature Review Genetics, 9:75--82, 2008.

[34]

C. Reidys, P. F. Stadler, and P. Schuster. Generic properties of combinatory maps: neutral networks of RNA secondary structures. Bulletin of Mathematical Biology, 59(2):339--397, 1997.

[35]

J. Reisinger and R. Miikkulainen. Acquring evolvability through adaptive representation. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1045--1052, 2007.

Digital Library

[36]

J. Reisinger, K. O. Stanley, and R. Miikkulainen. Towards an empirical measure of evolvability. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 257--264, 2005.

Digital Library

[37]

F. Rothlauf and D. E. Goldberg. Redundant representations in evolutionary computation. Evolutionary Computation, 11(4):381--415, 2003.

Digital Library

[38]

G. Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581--603, 1966.

[39]

P. Schuster, W. Fontana, P. F. Stadler, and I. L. Hofacker. From sequences to shapes and back: A case study in RNA secondary structures. Proceedings of The Royal Society B, 255:279--284, 1994.

[40]

P. Shannon, A. Markiel, O. Ozier, N. S. Baliga, J. T. Wang, D. Ramage, N. Amin, B. Schwikowski, and T. Ideker. Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Research, 13:2498--2504, 2003.

[41]

D. Song, M. I. Heywood, and A. Zincir-Heywod. A linear genetic programming approch to intrusion detection. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 2724 of Lecture Notes in Computer Science, pages 2325--2336. Springer-Verlag, 2001.

Digital Library

[42]

T. Soule. Resilient individuals improve evolutionary search. Artificial Life, 12:17--34, 2006.

Digital Library

[43]

Y. Tang, M. Li, J. Wang, Y. Pan, and F.-X. Wu. CytoNCA: A cytoscape plugin for centrality analysis and evaluation of protein interaction networks. BioSystems, 127:67--72, 2015.

[44]

E. van Nimwegen, J. P. Crutchfield, and M. A. Huynen. Neutral evolution of mutational robustness. Proceedings of the National Academy of Sciences, 96(17):9716--9720, 1999.

[45]

V. K. Vassilev and J. F. Miller. The advantage of landscape neutrality in digital circuit evolution. In Proceedings of the 3rd International Conference on Evolvable Systems: From Biology to Hardware, volume 1801 of Lecture Notes in Computer Science, pages 252--263. Springer, 2002.

Digital Library

[46]

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

[47]

A. Wagner. Neutralism and selectionism: A network-based reconciliation. Nature Review Genetics, 9:965--974, 2008.

[48]

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

[49]

J. Whitacre and A. Bender. Degeneracy: A design principle for achieving robustness and evolvability. Journal of Theoretical Biology, 263:143--153, 2010.

[50]

C. O. Wilke. Adaptive evolution on neutral networks. Bulletin of Mathematical Biology, 63:715--730, 2001.

[51]

T. Yu and J. F. Miller. Through the interaction of neutral and adaptive mutations, evolutionary search finds a way. Artificial Life, 12:525--551, 2006.

Digital Library

Cited By

Burlacu BAffenzeller MKronberger GKommenda M(2019)Online Diversity Control in Symbolic Regression via a Fast Hash-based Tree Similarity Measure2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790162(2175-2182)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790162
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
Nickerson KChen YWang FHu TTakadama K(2018)Measuring evolvability and accessibility using the hyperlink-induced topic search algorithmProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205633(1175-1182)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205633

Index Terms

Quantitative Analysis of Evolvability using Vertex Centralities in Phenotype Network
1. Computing methodologies
  1. Artificial intelligence
  2. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Artificial life
        Genetic algorithms
        Genetic programming

Recommendations

The effects of recombination on phenotypic exploration and robustness in evolution

Recombination is a commonly used genetic operator in artificial and computational evolutionary systems. It has been empirically shown to be essential for evolutionary processes. However, little has been done to analyze the effects of recombination on ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 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: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ignite Grant from the Research and Development Corporation of Newfoundland and Labrador
Discovery Grant from the Natural Sciences and Engineering Research of Canada

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
106
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Burlacu BAffenzeller MKronberger GKommenda M(2019)Online Diversity Control in Symbolic Regression via a Fast Hash-based Tree Similarity Measure2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790162(2175-2182)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790162
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
Nickerson KChen YWang FHu TTakadama K(2018)Measuring evolvability and accessibility using the hyperlink-induced topic search algorithmProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205633(1175-1182)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205633

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