Evolving neural networks

ABSTRACT

Neuroevolution, i.e. evolution of artificial neural networks, has recently emerged as a powerful technique for solving challenging reinforcement learning problems. Compared to traditional(e.g. value-function based) methods, neuroevolution is especially strong in domains where the state of the world is not fully known: the state can be disambiguated through recurrency, and novel situations handled through pattern matching. In this tutorial, we will review (1)neuroevolution methods that evolve fixed-topology networks, network topologies, and network construction processes, (2) ways of combining traditional neural network learning algorithms with evolutionary methods, and (3) applications of neuroevolution to game playing, robot control, resource optimization, and cognitive science.

REFERENCES

• 1: Adrian Agogino , Kagan Tumer , Risto Miikkulainen, Efficient credit assignment through evaluation function decomposition, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068221]
• 2: Ranit Aharonov-barki , Tuvik Beker , Eytan Ruppin, Emergence of Memory-Driven Command Neurons in Evolved Artificial Agents, Neural Computation, v.13 n.3, p.691-716, March 2001 [doi>10.1162/089976601300014529]
• 3: P. J. Angeline, G. M. Saunders, and J. B. Pollack, An evolutionary algorithm that constructs recurrent neural networks, IEEE Transactions on Neural Networks, 5:54--65 (1994).
• 4: J. M. Baldwin, A new factor in evolution, The American Naturalist, 30:441--451, 536--553 (1896).
• 5: R. K. Belew, Evolution, learning and culture: Computational metaphors for adaptive algorithms, Complex Systems, 4:11--49 (1990).
• 6: B. D. Bryant and R. Miikkulainen, Neuroevolution for adaptive teams {http://nn.cs.utexas.edu/keyword?bryant:cec03}, in: Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), volume 3, 2194--2201, IEEE, Piscataway, NJ (2003).
• 7: B. D. Bryant and R. Miikkulainen, Acquiring visibly intelligent behavior with example-guided neuroevolution {http://nn.cs.utexas.edu/keyword?bryant:aaai07}, in: Proceedings of the Twenty-Second National Conference on Artificial Intelligence (2007).
• 8: D. J. Chalmers, The evolution of learning: An experiment in genetic connectionism, in: Connectionist Models: Proceedings of the 1990 Summer School, DS. Touretzky, JL. Elman, TJ. Sejnowski, and GE. Hinton, eds., 81--90, San Francisco: Kaufmann (1990).
• 9: K. Chellapilla and D. B. Fogel, Evolution, neual networks, games, and intelligence, Proceedings of the IEEE, 87:1471--1496 (1999).
• 10: C.-C. Chen and R. Miikkulainen, Creating melodies with evolving recurrent neural networks {http://nn.cs.utexas.edu/keyword?chen:ijcnn01}, in: Proceedings of the INNS-IEEE International Joint Conference on Neural Networks, 2241--2246, IEEE, Piscataway, NJ (2001).
• 11: Dave Cliff , Phil Husbands , Inman Harvey, Explorations in evolutionary robotics, Adaptive Behavior, v.2 n.1, p.73-110, Summer 1993 [doi>10.1177/105971239300200104]
• 12: R. Cornelius, K. O. Stanley, and R. Miikkulainen, Constructing adaptive AI using knowledge-based neuroevolution {http://nn.cs.utexas.edu/keyword?cornelius:wisdom06}, in: AI Game Programming Wisdom 3, SRabin, ed., 693--708, Charles River Media, Revere, MA (2006).
• 13: David B. D'Ambrosio , Kenneth O. Stanley, A novel generative encoding for exploiting neural network sensor and output geometry, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277155]
• 14: N. S. Desai and R. Miikkulainen, Neuro-evolution and natural deduction{http://nn.cs.utexas.edu/keyword?desai:ecnn00}, in: Proceedings of The First IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks}, 64--69, IEEE, Piscataway, NJ (2000).
• 15: J. Fan, R. Lau, and R. Miikkulainen, Utilizing domain knowledge in neuroevolution{http://nn.cs.utexas.edu/keyword?fan:icml03}, in: Machine Learning: Proceedings of the 20th Annual Conference (2003).
• 16: D. Floreano , F. Mondada, Evolutionary neurocontrollers for autonomous mobile robots, Neural Networks, v.11 n.7-8, p.1461-1478, Oct./Nov. 1998 [doi>10.1016/S0893-6080(98)00082-3]
• 17: D. Floreano , J. Urzelai, Evolutionary robots with on-line self-organization and behavioral fitness, Neural Networks, v.13 n.4-5, p.431-443, May-June 2000 [doi>10.1016/S0893-6080(00)00032-0]
• 18: David B. Fogel, Blondie24: playing at the edge of AI, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 19: D. B. Fogel, T. J. Hays, S. L. Hahn, and J. Quon, Further evolution of a self-learning chess program, in: Proceedings of the IEEE Symposium on Computational Intelligence and Games, IEEE, Piscataway, NJ (2005).
• 20: B. Fullmer and R. Miikkulainen, Using marker-based genetic encoding of neural networks to evolve finite-state behaviour {http://nn.cs.utexas.edu/keyword?fullmer:evolving}, in: Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, FJ. Varela and PBourgine, eds., 255--262, MIT Press, Cambridge, MA (1992).
• 21: Faustino John Gomez , Risto Miikkulainen, Robust non-linear control through neuroevolution, The University of Texas at Austin, 2003
• 22: F. Gomez, D. Burger, and R. Miikkulainen, A neuroevolution method for dynamic resource allocation on a chip multiprocessor http://nn.cs.utexas.edu/keyword?gomez:ijcnn01, in: Proceedings of the INNS-IEEE International Joint Conference on Neural Networks, 2355--2361, IEEE, Piscataway, NJ (2001).
• 23: Faustino Gomez , Risto Mikkulainen, Incremental evolution of complex general behavior, Adaptive Behavior, v.5 n.3-4, p.317-342, Winter/Spring 1997 [doi>10.1177/105971239700500305]
• 24: F. Gomez and R. Miikkulainen, Active guidance for a finless rocket using neuroevolution http://nn.cs.utexas.edu/keyword?gomez:gecco03, in: Proceedings of the Genetic and Evolutionary Computation Conference, 2084--2095, Kaufmann, San Francisco (2003).
• 25: F. Gomez, J. Schmidhuber, and R. Miikkulainen, Efficient non-linear control through neuroevolution http://nn.cs.utexas.edu/keyword?gomez:ecml06, in: Proceedings of the European Conference on Machine Learning}, 654--662, Springer, Berlin (2006).
• 26: B. Greer, H. Hakonen, R. Lahdelma, and R. Miikkulainen, Numerical optimization with neuroevolution http://nn.cs.utexas.edu/keyword?greer:cec02, in: Proceedings of the 2002 Congress on Evolutionary Computation, 361--401, IEEE, Piscataway, NJ (2002).
• 27: Frédéric Gruau , Darrell Whitley, Adding learning to the cellular development of neural networks: evolution and the Baldwin effect, Evolutionary Computation, v.1 n.3, p.213-233, Fall 1993
• 28: G. E. Hinton and S. J. Nowlan, How learning can guide evolution, Complex Systems, 1:495--502 (1987).
• 29: Greg Hornby , S. Takamura , O. Hanagata , M. Fujita , Jordan B. Pollack, Evolution of Controllers from a High-Level Simulator to a High DOF Robot, Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware, p.80-89, April 17-19, 2000
• 30: C. Igel, Neuroevolution for reinforcement learning using evolution strategies http://www.neuroinformatik.ruhr-uni-bochum.de/ini/PEOPLE/igel/NfRLUES.pdf, in: Proceedings of the 2003 Congress on Evolutionary Computation, R. Sarker, R. Reynolds, H. Abbass, K. C. Tan, B. McKay, D. Essam, and T. Gedeon, eds., 2588--2595, IEEE Press, Piscataway, NJ (2003).
• 31: Alon Keinan , Ben Sandbank , Claus C. Hilgetag , Isaac Meilijson , Eytan Ruppin, Axiomatic Scalable Neurocontroller Analysis via the Shapley Value, Artificial Life, v.12 n.3, p.333-352, July 2006 [doi>10.1162/artl.2006.12.3.333]
• 32: Nate Kohl , Kenneth Stanley , Risto Miikkulainen , Michael Samples , Rini Sherony, Evolving a real-world vehicle warning system, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144273]
• 33: Y. Liu, X. Yao, and T. Higuchi, Evolutionary ensembles with negative correlation learning, IEEE Transactions on Evolutionary Computation, 4:380--387 (2000).
• 34: Alan J. Lockett , Charles L. Chen , Risto Miikkulainen, Evolving explicit opponent models in game playing, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277367]
• 35: Richard Maclin , Jude W. Shavlik, Creating advice-taking reinforcement learners, Machine Learning, v.22 n.1-3, p.251-281, Jan./Feb./March 1996 [doi>10.1007/BF00114730]
• 36: J. R. McDonnell and D. Waagen, Evolving recurrent perceptrons for time-series modeling, IEEE Transactions on Evolutionary Computation, 5:24--38 (1994).
• 37: Paul Herbert Mcquesten , Risto Miikkulainen, Cultural enhancement of neuroevolution, The University of Texas at Austin, 2002
• 38: R. Miikkulainen, B. D. Bryant, R. Cornelius, I. V. Karpov, K. O. Stanley, and C. H. Yong, Computational intelligence in games http://nn.cs.utexas.edu/keyword?miikkulainen:cigames06, in: Computational Intelligence: Principles and Practice, GY. Yen and DB. Fogel, eds., IEEE Computational Intelligence Society, Piscataway, NJ (2006).
• 39: E. Mjolsness , D. H. Sharp , B. K. Alpert, Scaling, machine learning, and genetic neural nets, Advances in Applied Mathematics, v.10 n.2, p.137-163, June 1989 [doi>10.1016/0196-8858(89)90008-0]
• 40: German A. Monroy , Kenneth O. Stanley , Risto Miikkulainen, Coevolution of neural networks using a layered pareto archive, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144058]
• 41: D. J. Montana and L. Davis, Training feedforward neural networks using genetic algorithms, in: Proceedings of the 11th International Joint Conference on Artificial Intelligence, 762--767, San Francisco: Kaufmann (1989).
• 42: David E. Moriarty, Symbiotic Evolution of Neural Networks in Sequential Decision Tasks, University of Texas at Austin, Austin, TX, 1997
• 43: D. E. Moriarty and R. Miikkulainen, Discovering complex Othello strategies through evolutionary neural networks http://nn.cs.utexas.edu/keyword?moriarty:discovering, Connection Science, 7(3):195--209 (1995).
• 44: D. E. Moriarty and R. Miikkulainen, Evolving obstacle avoidance behavior in a robot arm http://nn.cs.utexas.edu/keyword?moriarty:sab96, in: From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior, PMaes, MJ. Mataric, J.-A. Meyer, JPollack, and SW. Wilson, eds., 468--475, Cambridge, MA: MIT Press (1996).
• 45: D. E. Moriarty and R. Miikkulainen, Forming neural networks through efficient and adaptive co-evolution http://nn.cs.utexas.edu/keyword?moriarty:ec97, Evolutionary Computation, 5:373--399 (1997).
• 46: D. E. Moriarty, A. C. Schultz, and J. J. Grefenstette, Evolutionary algorithms for reinforcement learning, Journal of Artificial Intelligence Research, 11:199--229 (1999).
• 47: Stefano Nolfi , Domenico Parisi , Jeffrey L. Elman, Learning and evolution in neural networks, Adaptive Behavior, v.3 n.1, p.5-28, Summer 1994 [doi>10.1177/105971239400300102]
• 48: S. Nolfi and D. Floreano, Evolutionary Robotics, MIT Press, Cambridge (2000).
• 49: S. Nolfi and D. Parisi, Good teaching inputs do not correspond to desired responses in ecological neural networks http://kant.irmkant.rm.cnr.it/econets/nolfi.evo--teach.ps.Z, Neural Processing Letters, 1(2):1--4 (1994).
• 50: David Pardoe , Michael Ryoo , Risto Miikkulainen, Evolving neural network ensembles for control problems, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068230]
• 51: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 52: Joseph Reisinger , Risto Miikkulainen, Acquiring evolvability through adaptive representations, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277164]
• 53: J. Reisinger, K. O. Stanley, and R. Miikkulainen, Evolving reusable neural moduleshttp://nn.cs.utexas.edu/keyword?reisinger:gecco04, in: Proceedings of the Genetic and Evolutionary Computation Conference (2004).
• 54: C. D. Rosin and R. K. Belew, New methods for competitive evolution, Evolutionary Computation, 5 (1997).
• 55: T. P. Runarsson and M. T. Jonsson, Evolution and design of distributed learning rules, in: Proceedings of The First IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks, 59--63, IEEE, Piscataway, NJ (2000).
• 56: E. Ruppin, Evolutionary autonomous agents: A neuroscience perspective http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=retrieve&db=pubmed&dopt=%abstract&list_uids=11836521, Nature Reviews Neuroscience (2002).
• 57: J. D. Schaffer, D. Whitley, and L. J. Eshelman, Combinations of genetic algorithms and neural networks: A survey of the state of the art, in: Proceedings of the International Workshop on Combinations of Genetic Algorithms and Neural Networks, DWhitley and J. Schaffer, eds., 1--37, IEEE Computer Society Press, Los Alamitos, CA (1992).
• 58: C. W. Seys and R. D. Beer, Evolving walking: The anatomy of an evolutionary search, in: From Animals to Animats 8: Proceedings of the Eight International Conference on Simulation of Adaptive Behavior, SSchaal, A. Ijspeert, A. Billard, S. Vijayakumar, J. Hallam, and J.-A. Meyer, eds., 357--363, MIT Press, Cambridge, MA (2004).
• 59: A. A. Siddiqi and SM. Lucas, A comparison of matrix rewriting versus direct encoding for evolving neural networks, in: Proceedings of IEEE International Conference on Evolutionary Computation, 392--397, IEEE, Piscataway, NJ (1998).
• 60: Yiu Fai Sit , Risto Miikkulainen, Learning basic navigation for personal satellite assistant using neuroevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068332]
• 61: Kenneth Owen Stanley , Risto P. Miikkulainen, Efficient evolution of neural networks through complexification, The University of Texas at Austin, 2004
• 62: K. O. Stanley, B. D. Bryant, and R. Miikkulainen, Evolving adaptive neural networks with and without adaptive synapses http://nn.cs.utexas.edu/keyword?stanley:cec03, in: Proceedings of the 2003 Congress on Evolutionary Computation, IEEE, Piscataway, NJ (2003).
• 63: K. O. Stanley, B. D. Bryant, and R. Miikkulainen, Real-time neuroevolution in the NERO video game http://nn.cs.utexas.edu/keyword?stanley:ieeetec05, IEEE Transactions on volutionary Computation Special Issue on Evolutionary Computation and Games, 9(6):653--668 (2005).
• 64: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 65: Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 [doi>10.1162/106454603322221487]
• 66: K. O. Stanley and R. Miikkulainen, Competitive coevolution through evolutionary complexification http://nn.cs.utexas.edu/keyword?stanley:jair04, Journal of Artificial Intelligence Research, 21:63--100 (2004).
• 67: K. O. Stanley and R. Miikkulainen, Evolving a roving eye for Go http://nn.cs.utexas.edu/keyword?stanley:gecco04, in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Springer Verlag, Berlin (2004).
• 68: D. G. Stork, S. Walker, M. Burns, and B. Jackson, Preadaptation in neural circuits, in: International Joint Conference on Neural Networks Washington, DC, 202--205, IEEE, Piscataway, NJ (1990).
• 69: Matthew E. Taylor , Shimon Whiteson , Peter Stone, Comparing evolutionary and temporal difference methods in a reinforcement learning domain, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144202]
• 70: J. Togelius and S. M. Lucas, Evolving robust and specialized car racing skills http://algoval.essex.ac.uk/rep/games/Togelius2006Evolving.pdf, in: IEEE Congress on Evolutionary Computation, 1187--1194, IEEE, Piscataway, NJ (2006).
• 71: J. Urzelai, D. Floreano, M. Dorigo, and M. Colombetti, Incremental robot shaping, Connection Science, 10:341--360 (1998).
• 72: Alex Conradie , Risto Miikkulainen , Christiaan Aldrich, Adaptive Control Utilising Neural Swarming, Proceedings of the Genetic and Evolutionary Computation Conference, p.60-67, July 09-13, 2002
• 73: Av E. Conradie, R. Miikkulainen, and C. Aldrich, Intelligent process control utilizing symbiotic memetic neuro-evolution http://nn.cs.utexas.edu/keyword?conradie:cec02, in: Proceedings of the 2002 Congress on Evolutionary Computation (2002).
• 74: Vinod Valsalam , James Bednar , Risto Miikkulainen, Constructing good learners using evolved pattern generators, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068012]
• 75: G. M. Werner and M. G. Dyer, Evolution of communication in artificial organisms, in: Proceedings of the Workshop on Artificial Life ALIFE '90), C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, eds., 659----687, Reading, MA: Addison--Wesley (1991).
• 76: Gregory M. Werner , Michael G. Dyer, Evolution of herding behavior in artificial animals, Proceedings of the second international conference on From animals to animats 2 : simulation of adaptive behavior: simulation of adaptive behavior, p.393-399, August 1993, Honolulu, Hawai, United States
• 77: Shimon Whiteson , Nate Kohl , Risto Miikkulainen , Peter Stone, Evolving Soccer Keepaway Players Through Task Decomposition, Machine Learning, v.59 n.1-2, p.5-30, May 2005 [doi>10.1007/s10994-005-0460-9]
• 78: Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006
• 79: Shimon Whiteson , Peter Stone , Kenneth O. Stanley , Risto Miikkulainen , Nate Kohl, Automatic feature selection in neuroevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068210]
• 80: S. Whiteson and D. Whiteson, Stochastic optimization for collision selection in high energy physics http://www.cs.utexas.edu/~shimon/pubs/b2hd-whitesoniaai07.html, in: Proceedings of the Nineteenth Annual Innovative Applications of Artificial Intelligence Conference (2007).
• 81: Darrell Whitley , Stephen Dominic , Rajarshi Das , Charles W. Anderson, Genetic Reinforcement Learning for Neurocontrol Problems, Machine Learning, v.13 n.2-3, p.259-284, Nov./Dec. 1993 [doi>10.1007/BF00993045]
• 82: A. P. Wieland, Evolving controls for unstable systems, in: Connectionist Models: Proceedings of the 1990 Summer School, D. S. Touretzky, J. L. Elman, T. J. Sejnowski, and G. E. Hinton, eds., 91--102. Kaufmann (1990).
• 83: X. Yao, Evolving artificial neural networks, Proceedings of the IEEE, 87(9):1423--1447 (1999).
• 84: Chern H Yong , Risto Miikkulainen, COOPERATIVE COEVOLUTION OF MULTI-AGENT SYSTEMS, University of Texas at Austin, Austin, TX, 2001
• 85: Chern H Yong , Risto Miikkulainen, COOPERATIVE COEVOLUTION OF MULTI-AGENT SYSTEMS, University of Texas at Austin, Austin, TX, 2001
• 86: C. H. Yong, K. O. Stanley, R. Miikkulainen, and I. Karpov, Incorporating advice into evolution of neural networks http://nn.cs.utexas.edu/keyword?yong:aiide06, in: Proceedings of the Second Artificial Intelligence and Interactive Digital Entertainment Conference, AAAI Press, Menlo Park, CA (2006).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Algorithms, Design, Experimentation

Keywords:
artificial life, control, evolutionary computation, games, learning, neural networks, reinforcement learning, robotics