Mapping non-conventional extensions of genetic programming | Natural Computing Skip to main content

Advertisement

Springer Nature Link
Log in

Mapping non-conventional extensions of genetic programming

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

Conventional genetic programming research excludes memory and iteration. We have begun an extensive analysis of the space through which GP or other unconventional AI approaches search and extend it to consider explicit program stop instructions (T8), including Markov analysis and any time models (T7). We report halting probability, run time and functionality (including entropy of binary functions) of both halting and anytime programs. Irreversible Turing complete program fitness landscapes, even with halt, scale poorly however loops lock-in variation allowing more interesting functions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. In Fig. 9 we include the entropy of those T8 programs which have stopped or HALTed. This leads to higher values than we reported in Langdon (2006). In Langdon (2006, Fig. 8) we also excluded from the average programs which had stopped on all test cases.

  2. It is this increase-fall-increase in the spread of run time which gives rise to the curious non-monotonic curve in the average minimum run time seen in Fig. 11.

  3. Rather than executing the same instructions at different times.

  4. The relationship is slightly non-linear. Due to returning the same value with different inputs, the entropy of random 8-bit functions is about 7.17, rather than 8. Therefore long random programs with high entropy implement functions of slightly less entropy than their total or PC entropy.

    Fig. 20
    figure 20

    Variation of some common functions implemented by T7 with program length. As Fig. 19 except we include only programs which are not suspected of looping indefinitely on any test case

    Full size image
    Fig. 21
    figure 21

    Comparison of the entropy of functions implemented by midsize T7 programs with total entropy

    Full size image

References

  • Banzhaf W, Nordin P, Keller RE, Francone FD (1998) Genetic programming—an introduction; On the automatic evolution of computer programs and its applications. Morgan Kaufmann, San Francisco, CA, USA

  • Daida JM, Bertram RR, Polito JA 2, Stanhope SA (1999) Analysis of single-node (building) blocks in genetic programming. In: Spector L, Langdon WB, O’Reilly U-M, Angeline PJ (eds) Advances in genetic programming 3, chapter 10. MIT Press, Cambridge, MA, USA, pp 217–241

  • Greene WA (2004) Greene. Schema disruption in chromosomes that are structured as binary trees. In: Deb K et al. (eds) Genetic and evolutionary computation—GECCO-2004, Part I, vol 3102 of Lecture Notes in Computer Science. Springer-Verlag, Seattle, WA, USA, pp 1197–1207

  • Langdon WB (2002) Convergence rates for the distribution of program outputs. In: Langdon WB et al. (eds) GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference. New York, July 2002, pp 812–819

  • Langdon WB (2003a) How many good programs are there? How long are they? In: De Jong KA, Poli R, Rowe JE (eds) Foundations of genetic algorithms VII. Torremolinos, Spain, 4–6 September 2002. Morgan Kaufmann, pp 183–202

  • Langdon WB (2003b) The distribution of reversible functions is Normal. In: Riolo RL, Worzel B (eds) Genetic programming theory and practice, chapter 11. Kluwer, pp 173–188

  • Langdon WB (2003c) Convergence of program fitness landscapes. In: Cantú-Paz E et al. (eds) Genetic and evolutionary computation—GECCO-2003, vol 2724 of LNCS, Chicago, 12–16 July 2003. Springer-Verlag, pp 1702–1714

  • Langdon WB (2006) Mapping non-conventional extensions of genetic programming. In: Calude CS, Dinneen MJ, Paun G, Rozenberg G, Stepney S (eds) Unconventional computing 2006, vol 4135 of LNCS, York. Springer-Verlag, pp 166–180

  • Langdon WB, Poli R (2002) Foundations of genetic programming. Springer-Verlag

  • Langdon WB, Poli R (2005) On turing complete T7 and MISC F-4 program fitness landscapes. Technical Report CSM-445, Computer Science, University of Essex, UK

  • Langdon WB, Poli R (2006) The halting probability in von Neumann architectures. In: Collet P et al. (eds) Proceedings of the 9th European Conference on Genetic Programming, vol 3905 of Lecture Notes in Computer Science, pp 225–237, Budapest, Hungary, 10–12 April 2006, Springer

  • Maxwell SR III (1994) Experiments with a coroutine model for genetic programming. In: Proceedings of the 1994 IEEE World Congress on Computational Intelligence. Orlando, Florida, USA, 27–29 June 1994. IEEE, pp 413a–417a

  • McPhee NF, Poli R (2002) Using schema theory to explore interactions of multiple operators. In: Langdon WB et al. (eds) GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, New York, July 2002. Morgan Kaufmann, pp 853, 860

  • Poli R, Langdon WB (2006) Efficient markov chain model of machine code program execution and halting. In: Riolo RL, Soule T, Worzel B (eds) Genetic programming theory and practice IV, vol 5 of Genetic and evolutionary computation. Springer, Ann Arbor

  • Rosca J (2003) A probabilistic model of size drift. In: Riolo RL, Worzel B (eds) Genetic programming theory and practice. Kluwer Academic Publishers, pp 119–136

  • Sastry K, O’Reilly U-M, Goldberg DE, Hill D (2003) Building block supply in genetic programming. In: Riolo RL, Worzel B (eds) Genetic programming theory and practice. Kluwer, pp 137–154

  • Shannon CE, Weaver W (1964) The mathematical theory of communication. The University of Illinois Press, Urbana

    Google Scholar 

  • Spector L, Klein J, Keijzer M (2005) The push3 execution stack and the evolution of control. In: Beyer H-G et al (eds) GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, vol 2, Washington DC, USA, 25–29 June 2005. ACM Press, pp 1689–1696

  • Teller A (1994) Genetic programming, indexed memory, the halting problem, and other curiosities. In Proceedings of the 7th annual Florida Artificial Intelligence Research Symposium, Pensacola, Florida, USA. IEEE, pp 270–274

Download references

Acknowledgements

We would like to thank Dagstuhl Seminar 06061.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Essex, Colchester, Essex, CO4 3SQ, UK

    William B. Langdon

  2. Department of Computer Science, University of Essex, Colchester, Essex, CO4 3SQ, UK

    Riccardo Poli

Authors
  1. William B. Langdon
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Riccardo Poli
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to William B. Langdon.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Langdon, W.B., Poli, R. Mapping non-conventional extensions of genetic programming. Nat Comput 7, 21–43 (2008). https://doi.org/10.1007/s11047-007-9044-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-007-9044-x

Keywords