article

Neutral genetic drift: an investigation using Cartesian Genetic Programming

Authors:

Andrew James Turner,

Julian Francis MillerAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 16, Issue 4

Pages 531 - 558

https://doi.org/10.1007/s10710-015-9244-6

Published: 01 December 2015 Publication History

Abstract

Neutral genetic drift is an evolutionary mechanism which can strongly aid the escape from local optima. This makes neutral genetic drift an increasingly important property of Evolutionary Computational methods as more challenging applications are approached. Cartesian Genetic Programming (CGP) is a Genetic Programming technique which contains explicit, as well as the more common implicit, genetic redundancy. As explicit genetic redundancy is easily identified and manipulated it represents a useful tool for investigating neutral genetic drift. The contributions of this paper are as follows. Firstly the paper presents a substantial evaluation of the role and benefits of neutral genetic drift in CGP. Here it is shown that the benefits of explicit genetic redundancy are additive to the benefits of implicit genetic redundancy. This is significant as it indicates that that levels of implicit genetic redundancy present in other Evolutionary Computational methods may be insufficient to fully utilise neutral genetic drift. It is also shown than the identification and manipulation of explicit genetic redundancy is far easier than for implicit genetic redundancy. This is significant as it makes the investigations here possible and leads to new possibilities for allowing more effective use of neutral genetic drift. This is the case not only for CGP, but many other Evolutionary Computational methods which contain explicit genetic redundancy. Finally, it is also shown that neutral genetic drift has additional benefits other than aiding the escape from local optima.

References

[1]

W. Banzhaf, Genotype---phenotype-mapping and neutral variation--a case study in genetic programming, in Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature (Springer, Berlin, 1994), pp. 322---332

Digital Library

[2]

L. Barnett, Ruggedness and neutrality: the nkp family of fitness landscapes, in Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life (1998), pp. 18---27

Digital Library

[3]

T. Blickle, L. Thiele, Genetic programming and redundancy. Choice 1000, 2 (1994)

[4]

M. Brameier, W. Banzhaf, Linear Genetic Programming (Springer, Berlin, 2007)

[5]

J. Clegg, J.A. Walker, J.F. Miller, A new crossover technique for Cartesian Genetic Programming, in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (ACM 2007), pp. 1580---1587

[6]

M. Collins, Finding needles in haystacks is harder with neutrality. Genet. Program. Evol. Mach. 7(2), 131---144 (2006)

Digital Library

[7]

M. Ebner, On the search space of genetic programming and its relation to nature's search space, in Proceedings of the 1999 Congress on Evolutionary Computation, 1999 (CEC 99), vol. 2 (IEEE, 1999)

[8]

M. Ebner, P. Langguth, J. Albert, M. Shackleton, R. Shipman, On neutral networks and evolvability, in Proceedings of the 2001 Congress on Evolutionary Computation, 2001, vol. 1 (IEEE, 2001), pp. 1---8

[9]

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

Digital Library

[10]

C.M. Fonseca, M.B. Correia, Developing redundant binary representations for genetic search, in The 2005 IEEE Congress on Evolutionary Computation, 2005, vol. 2 (IEEE, 2005), pp. 1675---1682

[11]

S. Forrest, M. Mitchell, Relative Building-block Fitness and the Building-block Hypothesis (1993)

[12]

E. Galván-López, S. Dignum, R. Poli, The effects of constant neutrality on performance and problem hardness in gp, in EuroGP 2008 (Springer, Berlin, 2008), pp. 312---324

[13]

E. Galván-López, R. Poli, A. Kattan, M. ONeill, A. Brabazon, Neutrality in evolutionary algorithms what do we know? Evol. Syst. 2(3), 145---163 (2011).

[14]

B. Goldman, W. Punch, Analysis of Cartesian Genetic Programmings evolutionary mechanisms. IEEE Trans. Evol. Comput. PP(99), 1---1 (2014). In press

[15]

B.W. Goldman, W.F. Punch, Length bias and search limitations in Cartesian Genetic Programming, in Proceeding of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference (ACM 2013), pp. 933---940

[16]

F. Gomez, J. Schmidhuber, R. Miikkulainen, Accelerated neural evolution through cooperatively coevolved synapses. J. Mach. Learn. Res. 9, 937---965 (2008)

Digital Library

[17]

M.A. Huynen, Exploring phenotype space through neutral evolution. J. Mol. Evol. 43(3), 165---169 (1996)

[18]

M.A. Huynen, P.F. Stadler, W. Fontana, Smoothness within ruggedness: the role of neutrality in adaptation. Proc. Natl. Acad. Sci. 93(1), 397---401 (1996)

[19]

M. Kimura et al., Evolutionary rate at the molecular level. Nature 217(5129), 624---626 (1968)

[20]

J.D. Knowles, R.A. Watson, On the utility of redundant encodings in mutation-based evolutionary search, in Parallel Problem Solving from Nature PPSN VII (Springer, Berlin, 2002), pp. 88---98

[21]

A. Kordon, Tower Problem (2015). http://www.symbolicregression.com/

[22]

J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, Cambridge, 1992)

Digital Library

[23]

W.B. Langdon, R. Poli, Foundations of Genetic Programming (Springer, Berlin, 2002)

[24]

J. McDermott, D.R. White, S. Luke, L. Manzoni, M. Castelli, L. Vanneschi, W. Jaskowski, K. Krawiec, R. Harper, K. DeJong, et al., Genetic Programming needs better benchmarks, in Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference (ACM 2012), pp. 791---798

[25]

J.F. Miller, What bloat? Cartesian Genetic Programming on Boolean problems, in 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers (2001), pp. 295---302

[26]

J.F. Miller (ed.), Cartesian Genetic Programming (Springer, Berlin, 2011)

[27]

J.F. Miller, S. Smith, Redundancy and computational efficiency in Cartesian Genetic Programming. IEEE Trans. Evol. Comput. 10(2), 167---174 (2006)

Digital Library

[28]

J.F. Miller, P. Thomson, Cartesian Genetic Programming, in Proceedings of the Third European Conference on Genetic Programming (EuroGP), vol. 1820 (Springer, Berlin, 2000), pp. 121---132

[29]

P. Nordin, F. Francone, W. Banzhaf, Explicitly defined introns and destructive crossover in genetic programming, in Advances in Genetic Programming, ed. by P.J. Angeline, K.E. Kinnear Jr (MIT Press, Cambridge, 1996), pp. 111---134. http://dl.acm.org/citation.cfm?id=270195.270205

[30]

M. O'Neill, C. Ryan, Grammatical evolution. IEEE Trans. Evol. Comput. 5(4), 349---358 (2001)

Digital Library

[31]

M. O'Neill, C. Ryan, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language (Springer, Berlin, 2003)

[32]

L. Pagie, P. Hogeweg, Evolutionary consequences of coevolving targets. Evol. Comput. 5(4), 401---418 (1997)

Digital Library

[33]

R. Poli, W.W.B. Langdon, N.F. McPhee, J.R. Koza, A Field Guide to Genetic Programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk (2008)

[34]

F. Rothlauf, D.E. Goldberg, Redundant representations in evolutionary computation. Evol. Comput. 11(4), 381---415 (2003)

Digital Library

[35]

C. Ryan, J. Collins, M. Neill, Grammatical evolution: Evolving programs for an arbitrary language, in Genetic Programming, Lecture Notes in Computer Science, vol. 1391, ed. by W. Banzhaf, R. Poli, M. Schoenauer, T. Fogarty (Springer, Berlin, 1998), pp. 83---96

[36]

S. Silva, E. Costa, Dynamic limits for bloat control in Genetic Programming and a review of past and current bloat theories. Genet. Program. Evol. Mach. 10(2), 141---179 (2009)

Digital Library

[37]

L. Spector, A. Robinson, Genetic Programming and autoconstructive evolution with the push programming language. Genet. Program. Evol. Mach. 3(1), 7---40 (2002)

[38]

A.J. Turner, J.F. Miller, Cartesian Genetic Programming: Why no bloat?, in Genetic Programming: 17th European Conference (EuroGP-2014), LNCS, vol. 8599 (Springer, Berlin, 2014), pp. 193---204

[39]

A.J. Turner, J.F. Miller, Introducing a cross platform open source Cartesian Genetic Programming library. Genet. Program. Evol. Mach. 16(1), 83---91 (2014).

[40]

A.J. Turner, J.F. Miller, Recurrent Cartesian Genetic Programming, in 13th International Conference on Parallel Problem Solving from Nature (PPSN 2014), LNCS, vol. 8672 (2014), pp. 476---486

[41]

A.J. Turner, J.F. Miller, Recurrent Cartesian Genetic Programming applied to famous mathematical sequences, in Proceedings of the Seventh York Doctoral Symposium on Computer Science & Electronics (2014), pp. 37---46

[42]

A.J. Turner, J.F. Miller, Recurrent Cartesian Genetic Programming applied to series forecasting, in Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO-15) (2015), to appear

[43]

N.Q. Uy, N.X. Hoai, M. ONeill, R.I. McKay, E. Galván-López, Semantically-based crossover in genetic programming: application to real-valued symbolic regression. Genet. Program. Evol. Mach. 12(2), 91---119 (2011)

Digital Library

[44]

E. Van Nimwegen, J.P. Crutchfield, M. Huynen, Neutral evolution of mutational robustness. Proc. Natl. Acad. Sci. 96(17), 9716---9720 (1999)

[45]

A. Vargha, H.D. Delaney, A critique and improvement of the CL common language effect size statistics of McGraw and Wong. J. Educ. Behav. Stat. 25(2), 101---132 (2000)

[46]

Z. Vasicek, Cartesian gp in optimization of combinational circuits with hundreds of inputs and thousands of gates, in Genetic Programming (Springer, Berlin, 2015), pp. 139---150

[47]

V.K. Vassilev, J.F. Miller, The advantages of landscape neutrality in digital circuit evolution, in Proceedings of the International Conference on Evolvable Systems, LNCS, vol. 1801 (Springer, Berlin, 2000), pp. 252---263

[48]

A. Wagner, Robustness, evolvability, and neutrality. FEBS Lett. 579(8), 1772---1778 (2005)

[49]

A. Wieland, Evolving neural network controllers for unstable systems, in International Joint Conference on Neural Networks, 1991 (IJCNN-91)-Seattle, vol. 2 (IEEE, 1991), pp. 667---673

[50]

D. Wilson, D. Kaur, Search, neutral evolution, and mapping in evolutionary computing: a case study of grammatical evolution. IEEE Trans. Evol. Comput. 13(3), 566---590 (2009)

Digital Library

[51]

S. Wright, The roles of mutation, inbreeding, crossbreeding, and selection in evolution, in Sixth International Congress of Genetics (Brooklyn Botanic Garden, 1932), pp. 356---366

[52]

T. Yu, J. Miller, Neutrality and the evolvability of boolean function landscape, in Genetic Programming, Lecture Notes in Computer Science, vol. 2038, ed. by J. Miller, M. Tomassini, P. Lanzi, C. Ryan, A. Tettamanzi, W. Langdon (Springer, Berlin, 2001), pp. 204---217

[53]

T. Yu, J. Miller, Finding needles in haystacks is not hard with neutrality, in Genetic Programming, Lecture Notes in Computer Science, vol. 2278, ed. by J. Foster, E. Lutton, J. Miller, C. Ryan, A. Tettamanzi (Springer, Berlin, 2002), pp. 13---25.

[54]

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

Digital Library

Cited By

Huang ZMei YZhang FZhang MBanzhaf W(2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
https://dl.acm.org/doi/10.1007/s10710-023-09478-8
Cui HHeider MHähner J(2024)Positional Bias Does Not Influence Cartesian Genetic Programming with CrossoverParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_10(151-167)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_10
Cui HPätzel DMargraf AHähner J(2023)Weighted Mutation of Connections To Mitigate Search Space Limitations in Cartesian Genetic ProgrammingProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607130(50-60)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607130
Show More Cited By

Neutral genetic drift: an investigation using Cartesian Genetic Programming
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Solving real-valued optimisation problems using cartesian genetic programming
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Classical Evolutionary Programming (CEP) and Fast Evolutionary Programming (FEP) have been applied to real-valued function optimisation. Both of these techniques directly evolve the real-values that are the arguments of the real-valued function. In this ...
A new crossover technique for Cartesian genetic programming
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Genetic Programming was first introduced by Koza using tree representation together with a crossover technique in which random sub-branches of the parents' trees are swapped to create the offspring. Later Miller and Thomson introduced Cartesian Genetic ...
Embedded cartesian genetic programming and the lawnmower and hierarchical-if-and-only-if problems
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Embedded Cartesian Genetic Programming (ECGP) is an extension of the directed graph based Cartesian Genetic Programming (CGP), which is capable of automatically acquiring, evolving and re-using partial solutions in the form of modules. In this paper, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 16, Issue 4

December 2015

162 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZMei YZhang FZhang MBanzhaf W(2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
https://dl.acm.org/doi/10.1007/s10710-023-09478-8
Cui HHeider MHähner J(2024)Positional Bias Does Not Influence Cartesian Genetic Programming with CrossoverParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_10(151-167)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_10
Cui HPätzel DMargraf AHähner J(2023)Weighted Mutation of Connections To Mitigate Search Space Limitations in Cartesian Genetic ProgrammingProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607130(50-60)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607130
Komosinski MMiazga KSilva SPaquete L(2023)Revealing the Inner Dynamics of Evolutionary Algorithms with Convection SelectionProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590708(491-494)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590708
Kalkreuth RSotto LVašíček ZWagner M(2022)Graph-based genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533657(958-982)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533657
Cui HMargraf AHähner J(2022)Refining Mutation Variants in Cartesian Genetic ProgrammingBioinspired Optimization Methods and Their Applications10.1007/978-3-031-21094-5_14(185-200)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21094-5_14
Atkinson TPlump DStepney S(2021)Evolving graphs with semantic neutral driftNatural Computing: an international journal10.1007/s11047-019-09772-420:1(127-143)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s11047-019-09772-4
Françoso Dal Piccol Sotto LKaufmann PAtkinson TKalkreuth RPorto Basgalupp M(2021)Graph representations in genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-021-09413-922:4(607-636)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10710-021-09413-9
Lalejini AMoreno MOfria C(2021)Tag-based regulation of modules in genetic programming improves context-dependent problem solvingGenetic Programming and Evolvable Machines10.1007/s10710-021-09406-822:3(325-355)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10710-021-09406-8
Sotto LKaufmann PAtkinson TKalkreuth RBasgalupp MCoello Coello C(2020)A study on graph representations for genetic programmingProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390234(931-939)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390234
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents