Biological brains can adapt and learn from past experience. Yet neuroevolution, that is, automatically creating artificial neural networks (ANNs) through evolutionary algorithms, has sometimes focused on static ANNs that cannot change their weights during their lifetime. A profound problem with evolving adaptive systems is that learning to learn is highly deceptive. Because it is easier at first to improve fitness without evolving the ability to learn, evolution is likely to exploit domain-dependent static (i.e., nonadaptive) heuristics. This article analyzes this inherent deceptiveness in a variety of different dynamic, reward-based learning tasks, and proposes a way to escape the deceptive trap of static policies based on the novelty search algorithm. The main idea in novelty search is to abandon objective-based fitness and instead simply search only for novel behavior, which avoids deception entirely. A series of experiments and an in-depth analysis show how behaviors that could potentially serve as a stepping stone to finding adaptive solutions are discovered by novelty search yet are missed by fitness-based search. The conclusion is that novelty search has the potential to foster the emergence of adaptive behavior in reward-based learning tasks, thereby opening a new direction for research in evolving plastic ANNs.
Aaltonen, T., Adelman, J., Akimoto, T., Albrow, M.G., Alvarez González, B., Amerio, S., et al. (2009). Measurement of the top quark mass with dilepton events selected using neuroevolution at CDF. Physical Review Letters, 102(15), 152001.
2.
Angeline, P.J., Saunders, G.M., & Pollack, J.B. ( 1994). An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 5(1), 54-65.
3.
Barlow, M., Galloway, J., & Abbass, H.A. ( 2002). Mining evolution through visualization. In E. Bilotta et al (Eds.), A Life VIII Workshops (pp. 103-112). UNSW Press.
4.
Barnett, L. ( 2001). Netcrawling-optimal evolutionary search with neutral networks. In B. Moon (Ed.), Proceedings of the 2001 Congress on Evolutionary Computation (Vol. 1, pp. 30-37). Piscataway, NJ: IEEE Press.
5.
Baxter, J. ( 1992). The evolution of learning algorithms for artificial neural networks. In D. Green, & T. Bossomaier (Eds.), Complex systems (pp. 313-326). Amsterdam, The Netherlands: IOS Press.
6.
Blynel, J., & Floreano, D. ( 2002). Levels of dynamics and adaptive behavior in evolutionary neural controllers. In B. Hallam, D. Floreano, J. Hallam, G. Hayes, & J.-A. Meyer (Eds.), From Animals to Animats 7 (pp. 272-281). The MIT Press.
7.
Blynel, J., & Floreano, D. ( 2003). Exploring the T-maze: Evolving learning-like robot behaviors using CTRNNs. In G. Raidle (Ed.), 2nd European Workshop on Evolutionary Robotics (EvoRob 2003). Springer.
8.
Bongard, J.C., & Paul, C. ( 2001). Making evolution an offer it can’t refuse: Morphology and the extradimensional bypass. In J. Kelemen , & P. Sosik (Eds.), Proceedings of the 6th European Conference on Advances in Artificial Life (ECAL 2001), (pp. 401-412). London, UK: Springer-Verlag.
9.
Carew, T., Walters, E., & Kandel, E. ( 1981). Classical conditioning in a simple withdrawal reflex in Aplysia californica. The Journal of Neuroscience , 1(12), 1426-1437.
10.
Chalmers, D.J. ( 1990). The evolution of learning: An experiment in genetic connectionism . In D. S. Touretzky, & S. L. Elman (Eds.), In Proceedings of the 1990 Connectionist Models Summer School, (pp. 81-90). San Mateo, CA: Morgan Kaufmann.
11.
Darwen, P., & Yao, Y. ( 1996). Every niching method has its niche: Fitness sharing and implicit sharing compared. In W. Ebeling , I Rechenberg, H.-P. Schwefel , & H.-M. Voigt (Eds.), Parallel Problem Solving from Nature (PPSN IV) (pp. 398-407).
12.
De Jong, E.D. ( 2004). The incremental pareto-coevolution archive. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), (pp. 525-536). Berlin: Springer .
13.
Dürr, P., Mattiussi, C., Soltoggio, A., & Floreano, D. ( 2008). Evolvability of neuromodulated learning for robots . In A. O. El-Rayis, A. Stoica, E. Tunstel, T. Huntsberger, T. Arslan , & S. Vijayakumar (Eds.), The 2008 ECSIS Symposium on Learning and Adaptive Behavior in Robotic Systems (pp. 41-46). Los Alamitos, CA: IEEE Computer Society.
14.
Dybowski, R., Collins, T.D., Hall, W., & Weller, P.R. ( 1996). Visualization of binary string convergence by sammon mapping. In L. J. Fogel, P. J. Angeline, & T. Back (Eds.), Proceedings of The 5th Annual Conference on Evolutionary Programming (pp. 377-383). Cambridge, MA: MIT Press.
15.
Floreano, D., Dürr, P., & Mattiussi, C. ( 2008). Neuroevolution: from architectures to learning . Evolutionary Intelligence, 1, 47-62.
16.
Floreano, D., & Urzelai, J. ( 2000). Evolutionary robots with online self-organization and behavioral fitness. Neural Networks, 13, 431-443.
Goldberg, D.E. ( 1987). Simple genetic algorithms and the minimal deceptive problem . In L. D. Davis (Ed.), Genetic algorithms and simulated annealing, research notes in artificial intelligence (pp. 74-88). San Mateo, CA: Morgan Kaufmann.
19.
Goldberg, D.E., & Richardson, J. (1987). Genetic algorithms with sharing for multimodal function optimization. In J. J. Grefenstette (Ed.), Proceedings of the 2nd International Conference on Genetic Algorithms and their Application, (pp. 41-49). Hillsdale, NJ: L. Erlbaum Associates Inc .
20.
Gomez, F.J., & Miikkulainen, R. (1999). Solving non-Markovian control tasks with neuroevolution. In T. Dean (Ed.), Proceedings of the 16th International Joint Conference on Artificial Intelligence (pp. 1356-1361). Denver, CO: Morgan Kaufman.
21.
Gruau, F., Whitley, D., & Pyeatt, L. ( 1996). A comparison between cellular encoding and direct encoding for genetic neural networks. In J. R. Koza, D. E. Goldberg, D. B. Fogel, & R. L. Riolo (Eds.), Proceedings of the 1st Annual Conference on Genetic Programming, (pp. 81-89). Cambridge, MA : MIT Press.
22.
Harvey, I.( 1993). The artificial evolution of adaptive behavior, Unpublished doctoral dissertation, School of Cognitive and Computing Sciences . University of Sussex.
23.
Hase, K., & Yamazaki, N. ( 1999). Computational evolution of human bipedal walking by a neuro-musculo-skeletal model. Artificial Life and Robotics , 3, 133-138.
24.
Hinton, G.E., & Nowlan, S.J. ( 1987). How learning can guide evolution. Complex Systems, 1, 495-502.
25.
Hornby, G.S. ( 2006). ALPS: The age-layered population structure for reducing the problem of premature convergence. In M. Keijzer, M. Cattolico, D. Arnold, V. Babovic, C. Blum, P. Bosman, et al. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006), (pp. 815-822). New York: ACM.
26.
Hu, J., Goodman, E., Seo, K., Fan, Z., & Rosenberg, R. ( 2005). The hierarchical fair competition (HFC) framework for sustainable evolutionary algorithms. Evolutionary Computation , 13(2), 241-277 (PMID: 15969902).
27.
Hutter, M., & Legg, S. ( 2006). Fitness uniform optimization. IEEE Transactions on Evolutionary Computation, 10, 568-589. Ishiguro, A., Fujii, A., & Hotz, P.E. ( 2003). Neuromodulated control of bipedal locomotion using a polymorphic CPG circuit . Adaptive Behavior, 11(1), 7-17.
28.
Kim, Y.-H., & Moon, B.-R. ( 2003). New usage of Sammon’s mapping for genetic visualization . In Proceedings Genetic and Evolutionary Computation (GECCO 2003), LNCS (Vol. 2723, pp. 1136-1147). Berlin: Springer-Verlag.
29.
Kittler, J., & Young, P.C. ( 1973). A new approach to feature selection based on the Karhunen-Loeve expansion. Pattern Recognition, 5, 335-352.
30.
Lehman, J., & Stanley, K.O. ( 2008). Exploiting open-ended-ness to solve problems through the search for novelty. In S. Bullock, J. Noble, R. Watson, & M. A. Bedau (Eds.), Proceedings of the 11th International Conference on Artificial Life, Cambridge, MA: MIT Press .
31.
Lehman, J., & Stanley, K.O. ( 2010a). Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation (in press).
32.
Lehman, J., & Stanley, K.O. ( 2010b). Efficiently evolving programs through the search for novelty. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), New York : ACM (in press).
33.
Lehman, J., & Stanley, K.O. ( 2010c). Revising the evolutionary computation abstraction: Minimal criteria novelty search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), New York: ACM (in press).
34.
Mahfoud, S.W. ( 1995). Niching methods for genetic algorithms. Unpublished doctoral dissertation. Champaign, IL, USA.
35.
Martin, A.P. ( 1999). Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154(2), 111-128.
36.
Mayley, G. ( 1997). Guiding or hiding: Explorations into the effects of learning on the rate of evolution. In P. Husbands & I. Harvey (Eds.), 4th European Conference on Artificial Life, (pp. 135-144). Cambridge, MA : MIT Press.
37.
McHale, G., & Husbands, P. ( 2004). GasNets and other evolvable neural networks applied to bipedal locomotion. In S. Schaal, A. J. Ijspeert, A. Billard , S. Vijaykumar, J. Hallam, & J.-A. Meyer (Eds.), From Animals to Animats (Vol 8, pp. 163-172). The MIT Press.
38.
McQuesten, P., & Miikkulainen, R. (1997). Culling and teaching in neuro-evolution. In Proceedings of the 7th International Conference on Genetic Algorithms, San Francisco: Kaufmann.
39.
Mitchell, M., Forrest, S., & Holland, J.H. ( 1991). The royal road for genetic algorithms: fitness landscapes and GA performance. In Proceedings of the 1st European Conference on Artificial Life, (pp. 245-254). Cambridge, MA : MIT Press.
40.
Mouret, J. ( 2009). Novelty-based multiobjectivization. In N. Papanikolopoulos, S. Sugano , S. Chiaverini, & M. Meng (Eds.), Proceedings of IROS Workshop on Exploring New Horizons in the Evolutionary Design of Robots .
41.
Niv, Y., Joel, D., Meilijson, I., & Ruppin, E. ( 2002). Evolution of reinforcement learning in uncertain environments: A simple explanation for complex foraging behaviors. Adaptive Behavior, 10(1), 5-24.
42.
Nolfi, S., & Floreano, D. ( 1999). Learning and evolution. Autonomous Robots , 7(1), 89-113.
43.
Nolfi, S., & Parisi, D. ( 1993). Auto-teaching: Networks that develop their own teaching input. In J. L. Deneubourg, H. Bersini, S. Goss, G. Nicolis, & R. Dagonnier (Eds.), In Proceedings of the 2nd European Conference on Artificial Life, (pp. 845-862). MIT Press.
44.
Nolfi, S., & Parisi, D. ( 1996). Learning to adapt to changing environments in evolving neural networks. Adaptive Behavior, 5, 75-98.
45.
Nolfi, S., Parisi, D., & Elman, J.L. ( 1994). Learning and evolution in neural networks. Adaptive Behavior, 3, 5-28.
46.
Panne, M., van de, & Lamouret, A. ( 1995). Guided optimization for balanced locomotion. In D. Terzopoulos & D. Thalmann (Eds.), 6th Eurographics Workshop on Animation and Simulation, (pp. 165-177). Springer.
47.
Reil, T., & Husbands, P. ( 2002). Evolution of central pattern generators for bipedal walking in a real-time physics environment. IEEE Transactions on Evolutionary Computation, 6(2), 159-168.
48.
Sammon, J.W. ( 1969). A nonlinear mapping for data structure analysis . IEEE Transactions on Computers, 18(5), 401-409.
49.
Saravanan, N., & Fogel, D.B. ( 1995). Evolving neural control systems. IEEE Expert: Intelligent Systems and Their Applications, 10(3), 23-27.
50.
Schmidhuber, J. ( 2003). Exploring the predictable. In S. Ghosh, & S. Tsutsui (Eds.), Advances in evolutionary computing: theory and applications (pp. 579-612). New York: Springer-Verlag .
51.
Schmidhuber, J. ( 2006). Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts. Connection Science, 18(2), 173-187.
52.
Soltoggio, A., Bullinaria, J.A., Mattiussi, C., Dürr, P., & Floreano, D. ( 2008). Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios. In S. Bullock, J. Noble, R. Watson, & M. A. Bedau (Eds.), Artificial Life XI (pp. 569-576). Cambridge, MA: MIT Press.
53.
Soltoggio, A., Dürr, P., Mattiussi, C., & Floreano, D. ( 2007). Evolving neuromodulatory topologies for reinforcement learning-like problems. In P. Angeline, M. Michaelewicz, G. Schonauer , X. Yao, & Z. Zalzala (Eds.), Proceedings of the IEEE Congress on Evolutionary Computation (pp. 2471-2478). IEEE press .
54.
Stanley, K.O. ( 2006-2008). rtNEAT C++ software home-page: www.cs.utexas.edu/users/nn/keyword?rtneat.
55.
Stanley, K.O., Bryant, B.D., & Miikkulainen, R. (2003). Evolving adaptive neural networks with and without adaptive synapses. In H. Abbass & B. Verma (Eds.), Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC-2003) (pp. 2557-2564). Piscataway, NJ: IEEE Press.
56.
Stanley, K.O., Bryant, B.D., & Miikkulainen, R. (2005). Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation, 9(6), 653-668.
57.
Stanley, K.O., & Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10, 99-127.
58.
Stanley, K.O., & Miikkulainen, R. (2004). Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21, 63-100.
59.
Stewart, T. ( 2001). Extrema selection: Accelerated evolution on neutral networks . In Proceedings of the 2001 IEEE International Conference on Evolutionary Computation (Vol 1). Piscataway, NJ: IEEE Press.
60.
Taylor, M.E., Whiteson, S., & Stone, P. ( 2006). Comparing evolutionary and temporal difference methods in a reinforcement learning domain. In M. Keijzer, M. Cattolico, D. Arnold, V. Babovic, C. Blum, & P. Bosman (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006) (pp. 1321-1328). New York : ACM.
61.
Vassilev, V.K., Fogarty, T.C., & Miller, J.F. ( 2000). Information characteristics and the structure of landscapes . Evolutionary Computation, 8(1), 31-60.
62.
Watson, J.D., Hopkins, N.H., Roberts, J.W., Steitz, J.A., & Weiner, A.M. ( 1987). Molecular biology of the gene (4th ed.). Menlo Park, CA: The Benjamin Cummings Publishing Company, Inc.
63.
Whiteson, S., & Stone, P. ( 2006). Evolutionary function approximation for reinforcement learning. Journal of Machine Learning Research, 7, 877-917.
64.
Yao, X. ( 1999). Evolving artificial neural networks. In Proceedings of the IEEE, 87(9), 1423-1447.
