Using genetical and cultural search to design unorganised machines
Tóm tắt
In 1948 Turing presented a general representation scheme by which to achieve artificial intelligence—his unorganised machines. Significantly, these were a form of discrete dynamical system and yet dynamical representations remain almost unexplored within evolutionary computation. Further, at the same time as also suggesting that natural evolution may provide inspiration for search mechanisms to design machines, he noted that mechanisms inspired by the social aspects of learning may prove useful. This paper presents results from an investigation into using Turing’s dynamical representation designed by Evolutionary Programming and a new imitation-based, i.e., cultural, approach. Moreover, the original synchronous and an asynchronous form of unorganised machines are considered.
Tài liệu tham khảo
Abbeel P, Ng A (2004) Apprenticeship learning via inverse reinforcement learning. In: Proceedings of the 21st international conference on machine learning, ACM Press, pp 1–8
Andre D, Koza JR, Bennett FH, Keane M (1999) Genetic programming III. MIT Press, Cambridge
Angeline P (1998) Evolutionary optimization versus particle swarm optimization. In: Porto VW et al (eds) Proceedings of evolutionary programming 7. Springer, Berlin, pp 601–610
Angeline P, Saunders G, Pollock J (1994) An evolutionary algorithm that constructs recurrent neural networks. IEEE Trans Neural Netw 5:54–65
Atkeson CG, Schaal S (1997) Robot learning from demonstration. In: Proceedings of the fourteenth international conference on machine learning, Morgan Kaufmann, pp 12–20
Billard A, Dautenhahn K (1999) Experiments in learning by imitation—grounding and use of communication in robotic agents. Adapt Behav 7(3/4):415–438
Blackmore S (1999) The meme machine. Oxford
Brave S (1996) Evolving deterministic finite automata using cellular encoding. In: Koza JR et al (eds) Proceedings of the first annual conference on genetic programming. MIT Press, Cambridge, pp 39–44
Bull L (2008) Toward artificial creativity with evolution strategies. In: Parmee I (ed) Adaptive computing in design and manufacture VIII, IPCC (CD)
Bull L (2009) On dynamical genetic programming: simple boolean networks in learning classifier systems. Int J Parallel Emergent Distribut Syst 24(5):421–442
Chellapilla K (1997) Evolving computer programs without subtree crossover. IEEE Trans Evol Comput 1(1):209–216
Cramer N (1985) A representation for the adaptive generation of simple sequential programs. In: Grefenstette JJ (ed) Proceedings of an international conference on genetic algorithms and their application, Lawrence Erlbaum, pp 183–187
Copeland J, Proudfoot D (1996) On Alan Turing’s anticipation of connectionism. Synthese 108:361–377
Dawkins R (1976) The selfish gene. Oxford
Di J, Lala P (2007) Cellular array-based delay insensitive asynchronous circuits design and test for nanocomputing systems. J Elect Testing 23:175–192
Dolan C, Dyer M (1987) Toward the evolution of symbols. In: Grefenstette JJ (ed) Proceedings of the second international conference on genetic algorithms, Lawrence Erlbaum, pp 123–131
Friedberg RM (1958) A learning machine: part I. IBM J Res Dev 2(1):2–13
Fogel LJ, Owens AJ, Walsh MJ (1965) Artificial intelligence through a simulation of evolution. In: Maxfield M et al (eds) Biophysics and cybernetic systems: proceedings of the 2nd cybernetic sciences symposium, Spartan Books, pp 131–155
Forsyth R (1981) BEAGLE: a Darwinian approach to pattern recognition. Kybernetes 10:159–166
Galvan-Lopez E (2008) Efficient graph-based genetic programming representation with multiple outputs. Int J Autom Comput 5(1):81–89
Gorman B, Humphreys M (2006) Towards integrated imitation of strategic planning and motion modeling in interactive computer games. Computers in Entertainment 4(4) Article 10
Gruau F, Whitley D (1993) Adding learning to the cellular development process. Evol Comput 1(3):213–233
Harvey I (1992) Species adaptation genetic algorithms: a basis for a continuing SAGA. In: Varela F, Bourgine P (eds) Proceedings of 1st European conference on artificial life. MIT Press, Cambridge, pp 346–354
Hassdijk E, Vogt P, Eiben A (2008) Social learning in population-based adaptive systems. In: Proceedings of the 2008 IEEE congress on evolutionary computation, IEEE Press, New York, pp 1276–1282
Hirasawa K, Okubo M, Katagari H, Hu J, Murata J (2001) Comparison between genetic network programming (GNP) and genetic programming (GP). In: Proceedings of the 2001 congress on evolutionary computation, IEEE Press, New York, pp 1276–1282
Holland JH (1975) Adaptation in natural and artificial systems. Univ. of Mich. Press, Michigan
Hutchins E, Hazelhurst B (1990) Learning in the cultural process. In: Langton CG et al (eds) Artificial life II. Addison Wesley, Boston, pp 689–706
Kauffman SA (1993) The origins of order. Oxford
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, IEEE Press, pp 1942–1948
Kennedy J, Eberhart R (1997) A discrete binary version of the particle swarm algorithm. In: Proceedings of the IEEE international conference on systems, man and cybernetics, IEEE Press, pp 4104–4108
Koza JR (1992) Genetic programming. MIT Press, Cambridge
Luerssen M, Powers D (2005) Graph composition in a graph grammar-based method for automata network evolution. In: Proceedings of the 2005 IEEE congress on evolutionary computation, IEEE Press, pp 1653–1660
Luke S, Spector L (1996) Evolving graphs and networks with edge encoding: preliminary report. In: Koza JR (ed) Late breaking papers at the genetic programming 1996 conference, Stanford University, pp 117–124
McCulloch WS, Pitts W (1943) A logical calculus of the ideas immanent in nervous activity. Bull Math Biophys 5:115–133
Metivier M, Lattaud L (2009) Imitation guided learning in learning classifier systems. Nat Comput 8(1):29–56
Miller J (1999) An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In: Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, Smith RE (eds) Proceedings of the genetic and evolutionary computation conference—GECCO-99. Morgan Kaufmann, Massachusetts, pp 1135–1142
Mitchell M, Hraber P, Crutchfield J (1993) Revisiting the edge of chaos: evolving cellular automata to perform computations. Complex Syst 7:83–130
Nakamura K (1974) Asynchronous cellular automata and their computational ability. Syst Comput Controls 5(5):58–66
Niehaus J, Banzhaf W (2001) Adaption of operator probabilities in genetic programming. In: Miller J, Tomassini M, Lanzi P-L, Ryan C, Tettamanzi A, Langdon W (eds) Proceedings of Euro GP. Springer, Berlin, pp 325–336
Packard N (1988) Adaptation toward the edge of chaos. In: Kelso J, Mandell A, Shlesinger M (eds) Dynamic patterns in complex systems. World Scientific, New Jersey, pp 293–301
Parisi D (1997) Cultural evolution in neural networks. IEEE Expert Intell Syst Appl 12(4):9–11
Poli R (1997) Evolution of graph-like programs with parallel distributed programming. In: Back T (ed) Proceedings of the seventh international conference on genetic algorithms. Morgan Kaufmann, Massachusetts, pp 346–353
Poli R (1999) Parallel distributed genetic programming. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimisation. McGraw-Hill, New York, pp 403–431
Price B, Boutilier C (1999) Implicit imitation in multi-agent reinforcement learning. In: Proceedings of the sixteenth international conference on machine learning. Morgan Kaufmann, pp 325–334
Reynolds R (1994) An Introduction to Cultural Algorithms. In: Sebald AV, Fogel LJ (eds) Proceedings of the 3rd annual conference on evolutionary programming. World Scientific Publishing, New Jersey, pp 131–139
Rivero D, Dorado J, Rabunal J, Pazos A, Pereira J (2006) Artificial neural network development by means of genetic programming with graph codification. Proc World Acad Sci Eng Technol 15:209–214
Sapin E, Bailleux O, Chabrier J (2003) Research of a cellular automaton simulating logic gates by evolutionary algorithms. In: Proceedings of Euro GP, Springer, pp 414–423
Schmidt M, Lipson H (2007) Comparison of tree and graph encodings as function of problem complexity. In: Proceedings of the genetic and evolutionary computation conference—GECCO-07, ACM Press, pp 1674–1679
Sipper M (1997) Evolution of parallel cellular machines. Springer, Berlin
Sipper M, Tomassini M, Capcarrere S (1997) Evolving asynchronous and scalable non-uniform cellular automata. In: Proceedings of the third international conference on artificial neural networks and genetic algorithms, Springer, Berlin, pp 66–70
Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341–359
Strukov DB, Snider GS, Stewart DR, Williams RS (2008) The missing memristor found. Nature 453:80–83
Sylvain C, Billard A (2009) Statistical learning by imitation of competing constraints in joint space and task space. Adv Robot 23(15):2059–2076
Teller A, Veloso M (1996) Neural programming and an internal reinforcement policy. In: Koza JR (ed) Late breaking papers at the genetic programming 1996 conference. Stanford University, Stanford, pp 186–192
Teuscher C (2002) Turing’s connectionism. Springer, Berlin
Toth R, Stone C, De Lacy Costello B, Adamatzky A, Bull L (2008) Dynamic control and information processing in the Belousov-Zhabotinsky reaction using a co-evolutionary algorithm. J Chem Phys 129:184708
Turing A (1948) Intelligent machinery. See pages 395–432 in [13]
Turing A (1968) Intelligent machinery. In: Evans CR, Robertson A (eds) Key papers: cybernetics. Butterworths, London, pp 91–102
Von Neumann J (1966) The theory of self-reproducing automata. University of Illinois, Illinois
Werner T, Akella V (1997) Asynchronous processor survey. Computing 30(11):67–76