Top

Published in:

2023 | OriginalPaper | Chapter

Phenotype Search Trajectory Networks for Linear Genetic Programming

Authors : Ting Hu, Gabriela Ochoa, Wolfgang Banzhaf

Published in: Genetic Programming

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this study, we visualise the search trajectories of a genetic programming system as graph-based models, where nodes are genotypes/phenotypes and edges represent their mutational transitions. We also quantitatively measure the characteristics of phenotypes including their genotypic abundance (the requirement for neutrality) and Kolmogorov complexity. We connect these quantified metrics with search trajectory visualisations, and find that more complex phenotypes are under-represented by fewer genotypes and are harder for evolution to discover. Less complex phenotypes, on the other hand, are over-represented by genotypes, are easier to find, and frequently serve as stepping-stones for evolution.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Graph Networks as Inductive Bias for Genetic Programming: Symbolic Models for Particle-Laden Flows

next chapter GPAM: Genetic Programming with Associative Memory

Note that multiple programs can contribute to the same phenotype as specified by its behavior.

Banzhaf, W.: Genotype-phenotype-mapping and neutral variation—a case study in genetic programming. In: Davidor, Y., Schwefel, H.-P., Männer, R. (eds.) PPSN 1994. LNCS, vol. 866, pp. 322–332. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-58484-6_276CrossRef

Banzhaf, W., Leier, A.: Evolution on neutral networks in genetic programming. In: Yu, T., Riolo, R., Worzel, B. (eds.) Genetic Programming – Theory and Practice III, pp. 207–221. Kluwer (2006)

Barrick, J.E.: Limits to predicting evolution: insights from a long-term experiment with Escherichia coli. In: Evolution in Action: Past, Present and Future. GEC, pp. 63–76. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-39831-6_7CrossRef

Brameier, M., Banzhaf, W.: Linear Genetic Programming. Springer, Heidelberg (2007). https://doi.org/10.1007/978-0-387-31030-5CrossRefMATH

Dingle, K., Camargo, C., Louis, A.: Input-output maps are strongly biased towards simple outputs. Nat. Commun. 9, 761 (2018)CrossRef

Dingle, K., Novev, J., Ahnert, S., Louis, A.: Predicting phenotype transition probabilities via conditional algorithmic probability approximations. J. Roy. Soc. Interface (2023)

Dingle, K., Valle Perez, G., Louis, A.: Generic predictions of output probability based on complexities of inputs and outputs. Sci. Rep. 10, 4415 (2020)CrossRef

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exp. 21(11), 1129–1164 (1991)CrossRef

Gao, J., Li, D., Havlin, S.: From a single network to a network of networks. Natl. Sci. Rev. 1, 346–356 (2014)CrossRef

10.

Hu, T., Banzhaf, W.: Neutrality and variability: two sides of evolvability in linear genetic programming. In: Rothlauf, F., et al. (eds.) Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 963–970 (2009)

11.

Hu, T., Payne, J.L., Banzhaf, W., Moore, J.H.: Robustness, evolvability, and accessibility in linear genetic programming. In: Silva, S., Foster, J.A., Nicolau, M., Machado, P., Giacobini, M. (eds.) EuroGP 2011. LNCS, vol. 6621, pp. 13–24. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20407-4_2CrossRef

12.

Hu, T., Payne, J.L., Banzhaf, W., Moore, J.H.: Evolutionary dynamics on multiple scales: a quantitative analysis of the interplay between genotype, phenotype, and fitness in linear genetic programming. Genet. Program. Evol. Mach. 13, 305–337 (2012)CrossRef

13.

Kimura, M.: The Neutral Theory of Molecular Evolution. Cambridge University Press, Cambridge (1983)CrossRef

14.

Lobkovsky, A.E., Wolf, Y.I., Koonin, E.V.: Predictability of evolutionary trajectories in fitness landscapes. PLoS Comput. Biol. 7(12), e1002302 (2011)CrossRef

15.

Ochoa, G., Malan, K.M., Blum, C.: Search trajectory networks of population-based algorithms in continuous spaces. In: Castillo, P.A., Jiménez Laredo, J.L., Fernández de Vega, F. (eds.) EvoApplications 2020. LNCS, vol. 12104, pp. 70–85. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43722-0_5CrossRef

16.

Ochoa, G., Malan, K.M., Blum, C.: Search trajectory networks: a tool for analysing and visualising the behaviour of metaheuristics. Appl. Soft Comput. 109, 107492 (2021)CrossRef

17.

Reidys, C., Stadler, P., Schuster, P.: Generic properties of combinatory maps: neutral networks of RNA secondary structures. Bull. Math. Biol. 59, 339–397 (1997)CrossRefMATH

18.

Sarti, S., Adair, J., Ochoa, G.: Neuroevolution trajectory networks of the behaviour space. In: Jiménez Laredo, J.L., Hidalgo, J.I., Babaagba, K.O. (eds.) EvoApplications 2022. LNCS, vol. 13224, pp. 685–703. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-02462-7_43CrossRef

19.

Wright, A.H., Laue, C.L.: Evolvability and complexity properties of the digital circuit genotype-phenotype map. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, pp. 840–848 (2021)

Title: Phenotype Search Trajectory Networks for Linear Genetic Programming
Authors: Ting Hu
Gabriela Ochoa
Wolfgang Banzhaf
Publisher: Springer Nature Switzerland
Book: Genetic Programming
Print ISBN: 978-3-031-29572-0

Electronic ISBN: 978-3-031-29573-7

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-29573-7_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner