Loading ...
Sorry, an error occurred while loading the content.

Re: [GP] Turing Complete Genetic Programming.

Expand Messages
  • Michael Orlov
    Hi, Evolution of unrestricted Java bytecode is described in: Genetic Programming in the Wild: Evolving Unrestricted Bytecode, Michael Orlov and Moshe Sipper.
    Message 1 of 7 , Sep 28, 2009
    • 0 Attachment
      Hi,

      Evolution of unrestricted Java bytecode is described in:

      Genetic Programming in the Wild: Evolving Unrestricted Bytecode, Michael
      Orlov and Moshe Sipper. In Proceedings of the 11th Annual Conference on
      Genetic and Evolutionary Computation (GECCO 2009), pp. 1043–1050.
      Montréal Québec, Canada (July 8–12, 2009). ACM Press.
      http://dx.doi.org/10.1145/1569901.1570042

      Java is Turing-complete, so evolving arbitrary bytecode is clearly in
      the Turing-complete area. We are submitting an extensive follow-up paper
      very soon, with specific examples involving iteration and recursion.

      Best regards,
      Michael


      John Woodward wrote:
      > Dear All,
      >
      > I am interested in Genetic Programming with Turing Complete primitives (i.e.
      > which have memory and iteration).
      >
      > Some work has been done on this - see the list below.
      > If I have missed any references please could you let me have them *this
      > week*.
      > reply to "John Woodward" <john.r.woodward@...>,
      > I can send out a list of replies in a week if anyone is interested.
      >
      > I would like to use these references for a paper for the 10th anniversary of
      >
      > Genetic Programming and Evolvable Machines.
      >
      > Thank you in advance, and I look forward to your replies.
    • Julian Togelius
      I believe Alexandros Agapitos has done some experiments using Turing-complete GP, including loops and memory registers, e.g. for evolving sorting algorithms:
      Message 2 of 7 , Sep 30, 2009
      • 0 Attachment
        I believe Alexandros Agapitos has done some experiments using
        Turing-complete GP, including loops and memory registers, e.g. for evolving
        sorting algorithms:
        http://privatewww.essex.ac.uk/~aagapi/publications.html

        Julian

        2009/9/28 John Woodward <john.r.woodward@...>

        >
        >
        > Dear All,
        >
        > I am interested in Genetic Programming with Turing Complete primitives
        > (i.e.
        > which have memory and iteration).
        >
        > Some work has been done on this - see the list below.
        > If I have missed any references please could you let me have them *this
        > week*.
        > reply to "John Woodward" <john.r.woodward@...<john.r.woodward%40gmail.com>
        > >,
        > I can send out a list of replies in a week if anyone is interested.
        >
        > I would like to use these references for a paper for the 10th anniversary
        > of
        >
        > Genetic Programming and Evolvable Machines.
        >
        > Thank you in advance, and I look forward to your replies.
        >
        > --
        > Thanks, John
        > http://www.cs.nott.ac.uk/~jrw/ <http://www.cs.nott.ac.uk/%7Ejrw/>
        >
        > [1] Astro Teller. Turing completeness in the language of
        >
        > genetic programming with indexed memory. In
        >
        > Proceedings of the 1994 IEEE World Congress on
        >
        > Computational Intelligence, volume 1, pages 136{141,
        >
        > Orlando, Florida, USA, 27-29 June 1994. IEEE Press.
        >
        > [3] Wolfgang Banzhaf, Peter Nordin, Robert E. Keller,
        >
        > and Frank D. Francone. Genetic Programming { An
        >
        > Introduction; On the Automatic Evolution of
        >
        > Computer Programs and its Applications. Morgan
        >
        > Kaufmann, dpunkt.verlag, January 1998.
        >
        > [4] Peter J. Angeline. A historical perspective on the
        >
        > evolution of executable structures. Fundamenta
        >
        > Informaticae, 35(1{4):179{195, August 1998.
        >
        > [5] Astro Teller. Algorithm Evolution with Internal
        >
        > Reinforcement for Signal Understanding. PhD thesis,
        >
        > School of Computer Science, Carnegie Mellon
        >
        > University, Pittsburgh, USA, 5 December 1998.
        >
        > [6] A. E. Eiben. Evolutionary computing: The most
        >
        > powerful problem solver in the universe?
        >
        > [7] Julio Tanomaru and Akio Azuma. Automatic
        >
        > generation of turing machines by a genetic approach.
        >
        > In Daniel Borrajo and Pedro Isasi, editors, The First
        >
        > International Workshop on Machine Learning,
        >
        > Forecasting, and Optimization (MALFO96), pages
        >
        > 173{184, Gatafe, Spain, 10{12 July 1996.
        >
        > [8] Julio Tanomaru. Evolving turing machines from
        >
        > examples. In J.-K. Hao, E. Lutton, E. Ronald,
        >
        > M. Schoenauer, and D. Snyers, editors, Arti_cial
        >
        > Evolution, volume 1363 of LNCS, Nimes, France,
        >
        > October 1993. Springer-Verlag.
        >
        > [9] Edgar E. Vallejo and Fernando Ramos. Evolving
        >
        > turing machines for biosequences recognition and
        >
        > analysis. In Julian F. Miller, Marco Tomassini,
        >
        > Pier Luca Lanzi, Conor Ryan, Andrea G. B.
        >
        > Tettamanzi, and William B. Langdon, editors, Genetic
        >
        > Programming, Proceedings of EuroGP'2001, volume
        >
        > 2038 of LNCS, pages 192{203, Lake Como, Italy, 18-20
        >
        > April 2001. Springer-Verlag.
        >
        > [10] Nichael Lynn Cramer. A representation for the
        >
        > adaptive generation of simple sequential programs. In
        >
        > John J. Grefenstette, editor, Proceedings of an
        >
        > International Conference on Genetic Algorithms and
        >
        > the Applications, pages 183{187, Carnegie-Mellon
        >
        > University, Pittsburgh, PA, USA, 24-26 July 1985.
        >
        > [11] Lorenz Huelsbergen. Toward simulated evolution of
        >
        > machine language iteration. In Genetic Programming
        >
        > 1996: Proceedings of the First Annual Conference,
        >
        > pages 315{320, Stanford University, CA, USA, 28{31
        >
        > July 1996. MIT Press.
        >
        > [12] Lorenz Huelsbergen. Learning recursive sequences via
        >
        > evolution of machine-language programs. In Genetic
        >
        > Programming 1997: Proceedings of the Second Annual
        >
        > Conference, pages 186{194, Stanford University, CA,
        >
        > USA, 13-16 July 1997. Morgan Kaufmann.
        >
        > [13] Lorenz Huelsbergen. Finding general solutions to the
        >
        > parity problem by evolving machine-language
        >
        > representations. In Genetic Programming 1998:
        >
        > Proceedings of the Third Annual Conference, pages
        >
        > 158{166, University of Wisconsin, Madison,
        >
        > Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.
        >
        > [14] Jurgen Schmidhuber and Fakultat Fur Informatik. On
        >
        > learning how to learn learning strategies, February 01
        >
        > 1995.
        >
        > [15] Juergen Schmidhuber, Jieyu Zhao, and Marco
        >
        > Wiering. Simple principles of metalearning. Technical
        >
        > Report IDSIA-69-96, IDSIA, Lugano, Switzerland,
        >
        > Corso Elvezia 36, CH-6900, Switzerland, June 27 1996.
        >
        > [16] Jurgen Schmidhuber, Jieyu Zhao, and Marco Wiering.
        >
        > Shifting inductive bias with success-story algorithm,
        >
        > adaptive levin search, and incremental
        >
        > self-improvement. Machine Learning, 28:105, 1997.
        >
        > [17] Peter Nordin, Wolfgang Banzhaf, Fachbereich
        >
        > Informatik, Fachbereich Informatik, Lehrstuhl Fur
        >
        > Systemanalyse, and Lehrstuhl Fur Systemanalyse.
        >
        > Evolving turing-complete programs for a register
        >
        > machine with self-modifying code. In Genetic
        >
        > algorithms: proceedings of the sixth international
        >
        > conference (ICGA95, pages 318{325. Morgan
        >
        > Kaufmann, 1995.
        >
        > [18] Peter Nordin, Wolfgang Banzhaf, and Frank D.
        >
        > Francone. E_cient evolution of machine code for
        >
        > CISC architectures using instruction blocks and
        >
        > homologous crossover. In Lee Spector, William B.
        >
        > Langdon, Una-May O'Reilly, and Peter J. Angeline,
        >
        > editors, Advances in Genetic Programming 3,
        >
        > chapter 12, pages 275{299. MIT Press, Cambridge,
        >
        > MA, USA, June 1999.
        >
        > [19] Astro Teller. The evolution of mental models. In
        >
        > Kenneth E. Kinnear, Jr., editor, Advances in Genetic
        >
        > Programming, chapter 9, pages 199{219. MIT Press,
        >
        > 1994.
        >
        > [20] W. B. Langdon. Evolving data structures using
        >
        > genetic programming. In L. Eshelman, editor, Genetic
        >
        > Algorithms: Proceedings of the Sixth International
        >
        > Conference (ICGA95), pages 295{302, Pittsburgh, PA,
        >
        > USA, 15-19 July 1995. Morgan Kaufmann.
        >
        > [21] William B. Langdon. Data structures and genetic
        >
        > programming. In Peter J. Angeline and K. E. Kinnear,
        >
        > Jr., editors, Advances in Genetic Programming 2,
        >
        > chapter 20, pages 395{414. MIT Press, Cambridge,
        >
        > MA, USA, 1996.
        >
        > [28] William B. Langdon. Evolving data structures with
        >
        > genetic programming. In Proceedings of the Sixth
        >
        > International Conference on Genetic Algorithms,
        >
        > pages 295{302. Morgan Kaufmann, 1995.
        >
        > [29] W. B. Langdon. Data structures and genetic
        >
        > programming. Research Note RN/95/70, University
        >
        > College London, Gower Street, London WC1E 6BT,
        >
        > UK, September 1995.
        >
        > [Non-text portions of this message have been removed]
        >
        >
        >



        --
        Julian Togelius
        Assistant Professor
        IT University of Copenhagen
        Rued Langgaards Vej 7
        2300 Copenhagen S
        Denmark
        julian@...
        http://julian.togelius.com
        +46-705-192088


        [Non-text portions of this message have been removed]
      • Lucas, Simon M
        Thanks Julian, Perhaps the most relevant ones for this thread are: Alexandros Agapitos and Simon M.
        Message 3 of 7 , Sep 30, 2009
        • 0 Attachment
          Thanks Julian,

          Perhaps the most relevant ones for this thread are:

          Alexandros Agapitos<http://privatewww.essex.ac.uk/~aagapi/index.html> and Simon M. Lucas<http://cswww.essex.ac.uk/staff/sml/lucas.htm>, Evolving Efficient Recursive Sorting Algorithms, in 2006 IEEE Congress on Evolutionary Computation, Vancouver, Canada, July 16-21 2006, pp. 9227-9234 [PDF<http://privatewww.essex.ac.uk/~aagapi/papers/AgapitosLucasEvolvingSort.pdf>] [BibTex<http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Agapitos_2006_CEC.html>]
          Alexandros Agapitos<http://privatewww.essex.ac.uk/~aagapi/index.html> and Simon M. Lucas<http://cswww.essex.ac.uk/staff/sml/lucas.htm>, Learning Recursive Functions with Object Oriented Genetic Programming, in Proceedings of the 9th European Conference on Genetic Programming, Pierre Collet, Marco Tomassini, Marc Ebner, Steven Gustafson, and Aniko Ekart, Eds., Budapest, Hungary, 10-12 April 2006, vol. 3905 of Lecture Notes in Computer Science, pp. 166-177, Springer. (Nominated for best paper award) [PDF<http://privatewww.essex.ac.uk/~aagapi/papers/AgapitosLucasRecOOGP.pdf>] [BibTex<http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/eurogp06_AgapitosLucas.html>]

          In particular our CEC 2006 paper shows some conditions under which
          efficient algorithms similar to quicksort or mergesort can be evolved.

          Best wishes,

          Simon



          From: genetic_programming@yahoogroups.com [mailto:genetic_programming@yahoogroups.com] On Behalf Of Julian Togelius
          Sent: 30 September 2009 17:32
          To: genetic_programming@yahoogroups.com
          Subject: {Disarmed} Re: [GP] Turing Complete Genetic Programming.



          I believe Alexandros Agapitos has done some experiments using
          Turing-complete GP, including loops and memory registers, e.g. for evolving
          sorting algorithms:
          http://privatewww.essex.ac.uk/~aagapi/publications.html

          Julian

          2009/9/28 John Woodward <john.r.woodward@...<mailto:john.r.woodward%40gmail.com>>

          >
          >
          > Dear All,
          >
          > I am interested in Genetic Programming with Turing Complete primitives
          > (i.e.
          > which have memory and iteration).
          >
          > Some work has been done on this - see the list below.
          > If I have missed any references please could you let me have them *this
          > week*.
          > reply to "John Woodward" <john.r.woodward@...<mailto:john.r.woodward%40gmail.com><john.r.woodward%40gmail.com>
          > >,
          > I can send out a list of replies in a week if anyone is interested.
          >
          > I would like to use these references for a paper for the 10th anniversary
          > of
          >
          > Genetic Programming and Evolvable Machines.
          >
          > Thank you in advance, and I look forward to your replies.
          >
          > --
          > Thanks, John
          > http://www.cs.nott.ac.uk/~jrw/ <http://www.cs.nott.ac.uk/%7Ejrw/>
          >
          > [1] Astro Teller. Turing completeness in the language of
          >
          > genetic programming with indexed memory. In
          >
          > Proceedings of the 1994 IEEE World Congress on
          >
          > Computational Intelligence, volume 1, pages 136{141,
          >
          > Orlando, Florida, USA, 27-29 June 1994. IEEE Press.
          >
          > [3] Wolfgang Banzhaf, Peter Nordin, Robert E. Keller,
          >
          > and Frank D. Francone. Genetic Programming { An
          >
          > Introduction; On the Automatic Evolution of
          >
          > Computer Programs and its Applications. Morgan
          >
          > Kaufmann, dpunkt.verlag, January 1998.
          >
          > [4] Peter J. Angeline. A historical perspective on the
          >
          > evolution of executable structures. Fundamenta
          >
          > Informaticae, 35(1{4):179{195, August 1998.
          >
          > [5] Astro Teller. Algorithm Evolution with Internal
          >
          > Reinforcement for Signal Understanding. PhD thesis,
          >
          > School of Computer Science, Carnegie Mellon
          >
          > University, Pittsburgh, USA, 5 December 1998.
          >
          > [6] A. E. Eiben. Evolutionary computing: The most
          >
          > powerful problem solver in the universe?
          >
          > [7] Julio Tanomaru and Akio Azuma. Automatic
          >
          > generation of turing machines by a genetic approach.
          >
          > In Daniel Borrajo and Pedro Isasi, editors, The First
          >
          > International Workshop on Machine Learning,
          >
          > Forecasting, and Optimization (MALFO96), pages
          >
          > 173{184, Gatafe, Spain, 10{12 July 1996.
          >
          > [8] Julio Tanomaru. Evolving turing machines from
          >
          > examples. In J.-K. Hao, E. Lutton, E. Ronald,
          >
          > M. Schoenauer, and D. Snyers, editors, Arti_cial
          >
          > Evolution, volume 1363 of LNCS, Nimes, France,
          >
          > October 1993. Springer-Verlag.
          >
          > [9] Edgar E. Vallejo and Fernando Ramos. Evolving
          >
          > turing machines for biosequences recognition and
          >
          > analysis. In Julian F. Miller, Marco Tomassini,
          >
          > Pier Luca Lanzi, Conor Ryan, Andrea G. B.
          >
          > Tettamanzi, and William B. Langdon, editors, Genetic
          >
          > Programming, Proceedings of EuroGP'2001, volume
          >
          > 2038 of LNCS, pages 192{203, Lake Como, Italy, 18-20
          >
          > April 2001. Springer-Verlag.
          >
          > [10] Nichael Lynn Cramer. A representation for the
          >
          > adaptive generation of simple sequential programs. In
          >
          > John J. Grefenstette, editor, Proceedings of an
          >
          > International Conference on Genetic Algorithms and
          >
          > the Applications, pages 183{187, Carnegie-Mellon
          >
          > University, Pittsburgh, PA, USA, 24-26 July 1985.
          >
          > [11] Lorenz Huelsbergen. Toward simulated evolution of
          >
          > machine language iteration. In Genetic Programming
          >
          > 1996: Proceedings of the First Annual Conference,
          >
          > pages 315{320, Stanford University, CA, USA, 28{31
          >
          > July 1996. MIT Press.
          >
          > [12] Lorenz Huelsbergen. Learning recursive sequences via
          >
          > evolution of machine-language programs. In Genetic
          >
          > Programming 1997: Proceedings of the Second Annual
          >
          > Conference, pages 186{194, Stanford University, CA,
          >
          > USA, 13-16 July 1997. Morgan Kaufmann.
          >
          > [13] Lorenz Huelsbergen. Finding general solutions to the
          >
          > parity problem by evolving machine-language
          >
          > representations. In Genetic Programming 1998:
          >
          > Proceedings of the Third Annual Conference, pages
          >
          > 158{166, University of Wisconsin, Madison,
          >
          > Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.
          >
          > [14] Jurgen Schmidhuber and Fakultat Fur Informatik. On
          >
          > learning how to learn learning strategies, February 01
          >
          > 1995.
          >
          > [15] Juergen Schmidhuber, Jieyu Zhao, and Marco
          >
          > Wiering. Simple principles of metalearning. Technical
          >
          > Report IDSIA-69-96, IDSIA, Lugano, Switzerland,
          >
          > Corso Elvezia 36, CH-6900, Switzerland, June 27 1996.
          >
          > [16] Jurgen Schmidhuber, Jieyu Zhao, and Marco Wiering.
          >
          > Shifting inductive bias with success-story algorithm,
          >
          > adaptive levin search, and incremental
          >
          > self-improvement. Machine Learning, 28:105, 1997.
          >
          > [17] Peter Nordin, Wolfgang Banzhaf, Fachbereich
          >
          > Informatik, Fachbereich Informatik, Lehrstuhl Fur
          >
          > Systemanalyse, and Lehrstuhl Fur Systemanalyse.
          >
          > Evolving turing-complete programs for a register
          >
          > machine with self-modifying code. In Genetic
          >
          > algorithms: proceedings of the sixth international
          >
          > conference (ICGA95, pages 318{325. Morgan
          >
          > Kaufmann, 1995.
          >
          > [18] Peter Nordin, Wolfgang Banzhaf, and Frank D.
          >
          > Francone. E_cient evolution of machine code for
          >
          > CISC architectures using instruction blocks and
          >
          > homologous crossover. In Lee Spector, William B.
          >
          > Langdon, Una-May O'Reilly, and Peter J. Angeline,
          >
          > editors, Advances in Genetic Programming 3,
          >
          > chapter 12, pages 275{299. MIT Press, Cambridge,
          >
          > MA, USA, June 1999.
          >
          > [19] Astro Teller. The evolution of mental models. In
          >
          > Kenneth E. Kinnear, Jr., editor, Advances in Genetic
          >
          > Programming, chapter 9, pages 199{219. MIT Press,
          >
          > 1994.
          >
          > [20] W. B. Langdon. Evolving data structures using
          >
          > genetic programming. In L. Eshelman, editor, Genetic
          >
          > Algorithms: Proceedings of the Sixth International
          >
          > Conference (ICGA95), pages 295{302, Pittsburgh, PA,
          >
          > USA, 15-19 July 1995. Morgan Kaufmann.
          >
          > [21] William B. Langdon. Data structures and genetic
          >
          > programming. In Peter J. Angeline and K. E. Kinnear,
          >
          > Jr., editors, Advances in Genetic Programming 2,
          >
          > chapter 20, pages 395{414. MIT Press, Cambridge,
          >
          > MA, USA, 1996.
          >
          > [28] William B. Langdon. Evolving data structures with
          >
          > genetic programming. In Proceedings of the Sixth
          >
          > International Conference on Genetic Algorithms,
          >
          > pages 295{302. Morgan Kaufmann, 1995.
          >
          > [29] W. B. Langdon. Data structures and genetic
          >
          > programming. Research Note RN/95/70, University
          >
          > College London, Gower Street, London WC1E 6BT,
          >
          > UK, September 1995.
          >
          > [Non-text portions of this message have been removed]
          >
          >
          >

          --
          Julian Togelius
          Assistant Professor
          IT University of Copenhagen
          Rued Langgaards Vej 7
          2300 Copenhagen S
          Denmark
          julian@...<mailto:julian%40togelius.com>
          http://julian.togelius.com
          +46-705-192088

          [Non-text portions of this message have been removed]



          [Non-text portions of this message have been removed]
        Your message has been successfully submitted and would be delivered to recipients shortly.