Sebastian Risi
Charles E. Hughes
ABSTRACT
A major goal for researchers in neuroevolution is to evolve artificial neural networks (ANNs) that can learn during their lifetime. Such networks can adapt to changes in their environment that evolution on its own cannot anticipate. However, a profound problem with evolving adaptive systems is that if the impact of learning on the fitness of the agent is only marginal, then evolution is likely to produce individuals that do not exhibit the desired adaptive behavior. Instead, because it is easier at first to improve fitness without evolving the ability to learn, they are likely to exploit domain-dependent static (i.e. non-adaptive) heuristics. This paper proposes a way to escape the deceptive trap of static policies based on the novelty search algorithm, which opens up a new avenue in the evolution of adaptive systems because it can exploit the behavioral difference between learning and non-learning individuals. The main idea in novelty search is to abandon objective-based fitness and instead simply search only for novel behavior, which avoids deception entirely and has shown prior promising results in other domains. This paper shows that novelty search significantly outperforms fitness-based search in a tunably deceptive T-Maze navigation domain because it fosters the emergence of adaptive behavior.
- T. Aaltonen et al. Measurement of the top quark mass with dilepton events selected using neuroevolution at CDF. Physical Review Letters, 2009. To appear.Google Scholar
Cross Ref
- J. Blynel and D. Floreano. Exploring the T-Maze: Evolving Learning-Like Robot Behaviors using CTRNNs. In 2nd European Workshop on Evolutionary Robotics (EvoRob'2003), Lecture Notes in Computer Science, 2003.Google ScholarDigital Library
- T. Carew, E. Walters, and E. Kandel. Classical conditioning in a simple withdrawal reflex in Aplysia californica. The Journal of Neuroscience, 1(12):1426--1437, 1981.Google ScholarCross Ref
- P. Darwen and Y. Yao. Every niching method has its niche: Fitness sharing and implicit sharing compared. Parallel Problem Solving from Nature (PPSN IV), pages 398--407, 1996. Google ScholarDigital Library
- D. Floreano and J. Urzelai. Evolutionary robots with online self-organization and behavioral fitness. Neural Networks, 13:431--443, 2000. Google ScholarDigital Library
- D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, pages 41--49, Hillsdale, NJ, USA, 1987. L. Erlbaum Associates Inc. Google ScholarDigital Library
- G. E. Hinton and S. J. Nowlan. How learning can guide evolution. Complex Systems, 1, 1987.Google Scholar
- G. S. Hornby. Alps: the age-layered population structure for reducing the problem of premature convergence. In GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 815--822, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- J. Hu, E. Goodman, K. Seo, Z. Fan, and R. Rosenberg. The hierarchical fair competition (hfc) framework for sustainable evolutionary algorithms. Evolutionary Computation, 13(2):241--277, 2005. PMID: 15969902. Google ScholarDigital Library
- M. Hutter and S. Legg. Fitness uniform optimization. IEEE Transactions on Evolutionary Computation, 10:568--589, 2006. Google ScholarDigital Library
- E. D. Jong. The incremental pareto-coevolution archive. In Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO--2004), Berlin, 2004. Springer.Google ScholarCross Ref
- J. Lehman and K. O. Stanley. Exploiting open endedness to solve problems through the search for novelty. In Proceedings of the Eleventh International Conference on Artificial Life, Cambridge, MA, 2008. MIT Press.Google Scholar
- S. W. Mahfoud. Niching methods for genetic algorithms. PhD thesis, Champaign, IL, USA, 1995. Google ScholarDigital Library
- G. Mayley. Guiding or hiding: Explorations into the effects of learning on the rate of evolution. In Fourth European Conference on Artificial Life, pages 135--144. MIT Press, 1997.Google Scholar
- Y. Niv, D. Joel, I. Meilijson, and E. Ruppin. Evolution of reinforcement learning in uncertain environments: A simple explanation for complex foraging behaviors. Adaptive Behavior, 10(1):5--24, 2002. Google ScholarDigital Library
- S. Nolfi and D. Floreano. Learning and evolution. Autonomous Robots, 7(1):89--113, July 1999. Google ScholarDigital Library
- S. Nolfi, D. Parisi, and J. L. Elman. Learning and evolution in neural networks. Adaptive Behavior, 3:5--28, 1994. Google ScholarDigital Library
- A. Soltoggio, J. A. Bullinaria, C. Mattiussi, P. Dürr, and D. Floreano. Evolutionary Advantages of Neuromodulated Plasticity in Dynamic, Reward-based Scenarios. In Artificial Life XI, pages 569--576, Cambridge, MA, 2008. MIT Press.Google Scholar
- A. Soltoggio, P. Dürr, C. Mattiussi, and D. Floreano. Evolving neuromodulatory topologies for reinforcement learning-like problems. In Proceedings of the IEEE Congress on Evolutionary Computation, 2007.Google ScholarCross Ref
- K. O. Stanley. rtNEAT C++ software homepage: www.cs.utexas.edu/users/nn/keyword?rtneat. 2006--2008.Google Scholar
- K. O. Stanley, B. D. Bryant, and R. Miikkulainen. Evolving adaptive neural networks with and without adaptive synapses. In Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC--2003). Canberra, Australia: IEEE Press, 2003.Google ScholarCross Ref
- K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10:99--127, 2002. Google ScholarDigital Library
Index Terms
- How novelty search escapes the deceptive trap of learning to learn
Recommendations
Devising Effective Novelty Search Algorithms: A Comprehensive Empirical Study
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationNovelty search is a state-of-the-art evolutionary approach that promotes behavioural novelty instead of pursuing a static objective. Along with a large number of successful applications, many different variants of novelty search have been proposed. It ...
Critical factors in the performance of novelty search
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationNovelty search is a recently proposed method for evolutionary computation designed to avoid the problem of deception, in which the fitness function guides the search process away from global optima. Novelty search replaces fitness-based selection with ...
Evolving plastic neural networks with novelty search
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 ...
Comments