Critical factors in the performance of novelty search

ABSTRACT

Novelty 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 novelty-based selection, where novelty is measured by comparing an individual's behavior to that of the current population and an archive of past novel individuals. Though there is substantial evidence that novelty search can overcome the problem of deception, the critical factors in its performance remain poorly understood. This paper helps to bridge this gap by analyzing how the behavior function, which maps each genotype to a behavior, affects performance. We propose the notion of descendant fitness probability (DFP), which describes how likely a genotype's descendants are to have a certain fitness, and formulate two hypotheses about when changes to the behavior function will improve novelty search's performance, based on the effect of those changes on behavior and DFP. Experiments in both artificial and deceptive maze domains provide substantial empirical support for these hypotheses.

References

1. P. Darwen and X. Yao. Every niching method has its niche: Fitness sharing and implicit sharing compared. In PPSN IV, volume 1141, pages 398--407, 1996.
2. K. A. De Jong. An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Ann Arbor, 1975.
3. F. Gomez and R. Mikkulainen. Incremental evolution of complex general behavior. In Adaptive Behavior, volume 5, pages 317--342. MIT Press, 1997.
4. F. J. Gomez. Sustaining diversity using behavioral information distance. In GECCO-09, pages 113--120, 2009.
5. G. R. Harik. Finding multimodal solutions using restricted tournament selection. In ICGA-95, pages 24--31, 1995.
6. J. Lehman and K. O. Stanley. Exploiting open-endedness to solve problems through the search for novelty. In ALIFE-XI, 2008.
7. J. Lehman and K. O. Stanley. Abandoning objectives evolution through the search for novelty alone. In Evolutionary Computation. 2010.
8. J. Lehman and K. O. Stanley. Efficiently evolving programs through the search for novelty. In GECCO-10, pages 837--844, 2010.
9. J. Lehman and K. O. Stanley. Revising the evolutionary computation abstraction: minimal criteria novelty search. In GECCO -10, pages 103--110, 2010.
10. M. Lynch. The frailty of adaptive hypotheses for the origins of organismal complexity. Proceedings of the National Academy of Sciences, 104(Suppl 1):8597--8604, 2007.
11. S. W. Mahfoud. Niching methods for genetic algorithms. PhD thesis, University of Illinois, Urbana-Champaign, 1995.
12. T. Miconi. Evolution and complexity: the double-edged sword. Artificial life, 14(3):325--344, 2008.
13. J.-B. Mouret and S. Doncieux. Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity. In CEC-09, pages 1161--1168, 2009.
14. A. Petrowski. A clearing procedure as a niching method for genetic algorithms. In IEEE IECC, pages 798--803, 1996.
15. S. Risi, C. Hughes, and K. Stanley. Evolving plastic neural networks with novelty search. Adaptive Behavior, 2010.
16. S. Risi, S. D. Vanderbleek, C. Hughes, and K. O. Stanley. How novelty search escapes the deceptive trap of learning to learn. In GECCO-09, pages 153--160, 2009.
17. B. Sareni and L. Krahenbuhl. Fitness sharing and niching methods revisited. Evolutionary Computation, IEEE Transactions on, 2(3):97--106, 1998.
18. K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2):99--127, 2002.
19. E. Uchibe, M. Yanase, and M. Asada. Behavior generation for a mobile robot based on the adaptive fitness function. Robotics and Autonomous Systems, 40:69--77(9), 2002.
20. J. Urzelai, D. Floreano, M. Dorigo, and M. Colombetti. Incremental robot shaping. Connection Science, 10:341--360(20), 1998.
21. D. L. Whitley. Fundamental principles of deception in genetic search. In Foundations of Genetic Algorithms, pages 221--241. Morgan Kaufmann, 1991.
22. A. P. Wieland. Evolving neural network controllers for unstable systems. In IJCNN-91, pages 667--673, 1991.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming