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

research-article

Measuring evolvability and accessibility using the hyperlink-induced topic search algorithm

Authors:

Kyle L. Nickerson,

Ting HuAuthors Info & Claims

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

Pages 1175 - 1182

https://doi.org/10.1145/3205455.3205633

Published: 02 July 2018 Publication History

Abstract

The redundant mapping from genotype to phenotype is common in evolutionary algorithms, where multiple genotypes can map to the same phenotype. Such a redundancy has been suggested to make an evolutionary system robust as well as evolvable. However, the impact of the redundant genotype-to-phenotype mapping and its resulted robustness and evolvability have not been well characterized quantitatively. In this article, we used a Boolean linear genetic programming system to construct a weighted and directed phenotype network, where vertices are phenotypes and a weighted link represents the number of possible point mutations that can transition genotypes from one phenotype to another. The direction of the links ensures moving from less fit phenotypes to fitter or equally fit ones. We used two fitness functions to investigate how it influences the network structure. Then we employed the Hyperlink-Induced Topic Search (HITS) algorithm to quantitatively characterize the evolvability and accessibility of phenotypes in the network. We found more robust phenotypes are both more evolvable and accessible. Our results help elucidate the effects of redundant mapping and the relationship of robustness, evolvability, and accessibility.

References

[1]

Wolfgang Banzhaf. 1994. Genotype-phenotype mapping and neutral variation - a case study in genetic programming. In Parallel Problem Solving from Nature (Lecture Notes in Computer Science), Y. Davidor, H.-P. Schwefel, and R. Manner (Eds.), Vol. 866. Springer, Berlin, 322--332.

Digital Library

[2]

Wolfgang Banzhaf, Guillaume Beslon, Steffen Christensen, James A Foster, François Képès, Virginie Lefort, Julian F Miller, Miroslav Radman, and Jeremy J Ramsden. 2006. From artificial evolution to computational evolution: a research agenda. Nature Reviews Genetics 7 (2006), 729--735.

[3]

Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, and Frank D. Francone. 1998. Genetic programming: An introduction. Morgan Kaufmann, San Francisco, CA.

Digital Library

[4]

Markus F. Brameier and Wolfgang Banzhaf. 2007. Linear Genetic Programming. Springer.

Digital Library

[5]

Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual web search engine. Computer Networks 30 (1998), 107--117.

Digital Library

[6]

Matthew C. Cowperthwaite, Evan P. Economo, William R. Harcombe, Eric L. Miller, and Lauren Ancel Meyers. 2008. The ascent of the abundant: How mutational networks constrain evolution. PLoS Computational Biology 4, 7 (2008), e1000110.

[7]

Kenneth A De Jong. 2006. Evolutioanry Computation: A Unified Approach. MIT Press, Cambridge, MA.

Digital Library

[8]

Jeremy A. Draghi, Todd L. Parsons, Gunter P. Wagner, and Joshua B. Plotkin. 2010. Mutational robustness can facilitate adaptation. Nature 463 (2010), 353--355.

[9]

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

[10]

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

Digital Library

[11]

Agoston E Eiben and Jim Smith. 2015. From evolutionary computation to the evolution of things. Nature 521 (2015), 476--482.

[12]

Agoston E Eiben and Jim E Smith. 2015. Introduction to Evolutionary Computing (second ed.). Springer, Berlin, Germany.

Digital Library

[13]

Miguel A. Fortuna, Luis Zaman, Charles Ofria, and Andreas Wagner. 2017. The genotype-phenotype map of an evolving digital organism. PLoS Computational Biology 13, 2 (2017), e1005414.

[14]

Pedram Ghamisi and Jon Atli Benediktsson. 2015. Feature Selection Based on Hybridization of Genetic Algorithm and Particle Swarm Optimization. IEEE Geoscience and Remote Sensing Letters 12, 2 (2015), 309--313.

[15]

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

[16]

John Holland. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.

Digital Library

[17]

Ting Hu and Wolfgang Banzhaf. 2010. Evolvability and speed of evolutionary algorithms in light of recent developments in biology. Journal of Artificial Evolution and Applications 2010 (2010), 568375.

Digital Library

[18]

Ting Hu and Wolfgang Banzhaf. 2016. Quantitative analysis of evolvability using vertex centralities in phenotype networks. In Proceedings of the 25th Genetic and Evolutionary Computation Conference (GECCO). 733--740.

Digital Library

[19]

Ting Hu, Wolfgang Banzhaf, and Jason H. Moore. 2013. Robustness and evolvability of recombination in linear genetic programming. In Proceedings of the 16th European Conference on Genetic Programming (EuroGP) (Lecture Notes in Computer Science), Vol. 7831. 97--108.

Digital Library

[20]

Ting Hu, Wolfgang Banzhaf, and Jason H Moore. 2014. The effect of recombination on phenotypic exploration and robustness in evolution. Artificial Life 20, 4 (2014), 457--470.

Digital Library

[21]

Ting Hu, Wolfgang Banzhaf, and Jason H. Moore. 2014. Population exploration on genotype networks in genetic programming. In Proceedings of the 13th International Conference on Parallel Problem Solving from Nature (PPSN) (Lecture Notes in Computer Science), Vol. 8672. 424--433.

[22]

Ting Hu, Josh L. Payne, Wolfgang Banzhaf, and Jason H. Moore. 2011. Robustness, evolvability, and accessibility in linear genetic programming. In Proceedings of the European Conference on Genetic Programming (Lecture Notes in Computer Science), Sara Silva, James A. Foster, Miguel Nicolau, Penousal Machado, and Mario Giacobini (Eds.), Vol. 6621. 13--24.

Digital Library

[23]

Ting Hu, Joshua L. Payne, Wolfgang Banzhaf, and Jason H. Moore. 2012. 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 (2012), 305--337.

Digital Library

[24]

Leo Katz. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 1 (1953), 39--43.

[25]

Junil Kim, Drieke Vandamme, Jeong-Rae Kim, Amaya Garcia Munoz, Walter Kolch, and Kwang-Hyun Cho. 2014. Robustness and evolvability of the human signaling network. PLOS Computational Biology 10, 7 (2014), e1003763.

[26]

Jon M Kleinberg. 1999. Authoritative Sources in a Hyperlinked Environment. J. ACM 46, 5 (1999), 604--632.

Digital Library

[27]

John R Koza. 1992. Genetic programming: On the programming of computers by means of natural selection. MIT Press, Cambridge, MA.

Digital Library

[28]

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

Digital Library

[29]

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

[30]

Stjepan Oreski and Goran Oreski. 2014. Genetic algorithm-based heuristic for feature selection in credit risk assessment. Expert Systems with Applications 41, 4 (2014), 2052--2064.

Digital Library

[31]

Joshua L. Payne and Andreas Wagner. 2014. The robustness and evolvability of transcription factor binding sites. Science 343, 6173 (2014), 875--877.

[32]

Massimo Pigliucci. 2008. Is evolvability evolvable? Nature Reviews Genetics 9 (2008), 75--82.

[33]

Meikang Qiu, Zhong Ming, Jiayin Li, Keke Gai, and Ziliang Zong. 2015. Phase-Change Memory Optimization for Green Cloud with Genetic Algorithm. IEEE Trans. Comput. 64, 12 (2015), 3528 -- 3540.

Digital Library

[34]

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

[35]

Joseph Reisinger, Kenneth O. Stanley, and Risto Miikkulainen. 2005. Towards an Empirical Measure of Evolvability. In Proceedings of the Genetic and Evolutionary Computation Conference. 257--264.

Digital Library

[36]

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

Digital Library

[37]

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

[38]

Tom Smith, Phil Husbands, Paul Layzell, and Michael O'Shea. 2002. Fitness landscapes and evolvability. Evolutionary Computation 10, 1 (2002), 1--34.

Digital Library

[39]

Leslie G. Valiant. 2006. Evolvability. Electronic Colloquium on Computational Complexity 120. Division of Engineering and Applied Sciences, Harvard University.

[40]

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

[41]

Andreas Wagner. 2008. Neutralism and selectionism: A network-based reconciliation. Nature Reviews Genetics 9 (2008), 965--974.

[42]

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

[43]

James West, Martin Widschwendter, and Andrew E. Teschendorff. 2013. Distinctive topology of age-associated epigenetic drift in the human interactome. Proceedings of the National Academy of Sciences 110, 35 (2013), 14138--14143.

Cited By

Forati AGhose RMohebbi FMantsch J(2023)The journey to overdose: Using spatial social network analysis as a novel framework to study geographic discordance in overdose deathsDrug and Alcohol Dependence10.1016/j.drugalcdep.2023.109827245(109827)Online publication date: Apr-2023
https://doi.org/10.1016/j.drugalcdep.2023.109827
Wright ALaue CKrawiec K(2021)Evolvability and complexity properties of the digital circuit genotype-phenotype mapProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459393(840-848)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459393
Manzoni LBartoli ACastelli MGoncalves IMedvet E(2020)Specializing Context-Free Grammars With a (1 + 1)-EAIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.298366424:5(960-973)Online publication date: Oct-2020
https://doi.org/10.1109/TEVC.2020.2983664
Show More Cited By

Index Terms

Measuring evolvability and accessibility using the hyperlink-induced topic search algorithm
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Quantitative Analysis of Evolvability using Vertex Centralities in Phenotype Network
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

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 ...
Regulatory genotype-to-phenotype mappings improve evolvability in genetic programming
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Most genotype-to-phenotype mappings in EAs are redundant, i.e., multiple genotypes can map to the same phenotype. Phenotypes are accessible from one to another through point mutations. However, these mutational connections can be unevenly distributed ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 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: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

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
115
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Forati AGhose RMohebbi FMantsch J(2023)The journey to overdose: Using spatial social network analysis as a novel framework to study geographic discordance in overdose deathsDrug and Alcohol Dependence10.1016/j.drugalcdep.2023.109827245(109827)Online publication date: Apr-2023
https://doi.org/10.1016/j.drugalcdep.2023.109827
Wright ALaue CKrawiec K(2021)Evolvability and complexity properties of the digital circuit genotype-phenotype mapProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459393(840-848)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459393
Manzoni LBartoli ACastelli MGoncalves IMedvet E(2020)Specializing Context-Free Grammars With a (1 + 1)-EAIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.298366424:5(960-973)Online publication date: Oct-2020
https://doi.org/10.1109/TEVC.2020.2983664
Xu SMariani MLü LMedo M(2020)Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation dataJournal of Informetrics10.1016/j.joi.2019.10100514:1(101005)Online publication date: Feb-2020
https://doi.org/10.1016/j.joi.2019.101005
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: 24-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-16670-0_4

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