Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms

ABSTRACT

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue, at best by delaying the premature convergence of an evolving population. Analytical models in biology show that resiliently diverse populations evolve on high-dimensional fitness landscapes with "holey" rather than "rugged" topographies, but the implications for artificial evolutionary systems remain largely unexplored. Here I show how holey fitness landscapes (HFLs) can be incorporated in an evolutionary algorithm and use this approach to investigate the ability of HFLs to maintain genetic diversity in an evolving population. The results indicate that an underlying HFL can counteract premature genetic convergence and sustain diversity. They also suggest that HFL may provide a flexible mechanism for dynamic creation and maintenance of subpopulations that concentrate their evolutionary search in different regions of the solution space. Finally, I discuss on-going work on using the HFL model in optimisation problems.

REFERENCES

• 1: Samir W. Mahfoud, Niching methods for genetic algorithms, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
• 2: Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., University of Michigan, Ann Arbor, MI, 1975
• 3: David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, United States
• 4: D. Whitley, S. Rana and R. B. Heckendorn (1999). The Island Model Genetic Algorithm: On Separability, Population Size and Convergence. J. of Computing and IT. 7 (1): pp. 33--47.
• 5: J. Liu, Z. Cai and J. Liu (2000). Premature convergence in genetic algorithm: Analysis and prevention based on chaos operator, Procs 3rd W. Congr. Intell. Ctrl and Automation.
• 6: N. Kashtan, E. Noor and U. Alon (2007). Varying environments can speed up evolution. PNAS. 104 (34).
• 7: G. Paperin, S. Sadedin, D. G. Green and A. Dorin (2008). Holey Fitness Landscapes and the Maintenance of Evolutionary Diversity Submitted to 11th International Conference on Simulation and Synthesis of Living Systems (ALife XI).
• 8: S. Gavrilets (2004). Fitness Landscapes and the Origin of Species. Princeton University Press, Princeton / Oxford.
• 9: S. Gavrilets and J. Gravner (1997). Percolation on the Fitness Hypercube and the Evolution of Reproductive Isolation. J. of Th. Bio. 184 (1): pp. 51--64.
• 10: G. Paperin, D. G. Green and A. Dorin (2007). Fitness Landscapes in Individual-Based Simulation Models of Adaptive Radiation. In T. D. Pham and X. Zhou (eds.), 2007 Int. Symposium on Computational Models for Life Science .
• 11: G. Paperin, D. G. Green, S. Sadedin and T. G. Leishman (2007). A Dual Phase Evolution model of adaptive radiation in landscapes. In M. Randall, H. A. Abbass and J. Wiles (eds.), The 3rd Australian Conference on Artificial Life (ACAL'07), Springer.
• 12: S. Gavrilets (2003). Models of Speciation: What have we learned in 40 years? Evolution. 57 (10): pp. 2197--2215.
• 13: M. E. J. Newman and R. M. Ziff (2000). Efficient Monte Carlo Algorithm and High-Precision Results for Percolation. Physical Review Letters. 85 (19): pp. 4104--4107.
• 14: G. R. Grimmett (1999). Percolation. Springer.
• 15: S. Gavrilets and A. Vose (2005). Dynamic patterns of adaptive radiation. PNAS. 102 (50): pp. 18040--18045.
• 16: T. Ohta and M. Kimura (1973). A model of mutation appropriate to estimate the number of electrophoretically detectable alleles in a population. Gen. Res. 22 (2): pp. 201--204.
• 17: S. Van Dongen (2000). Graph Clustering by Flow Simulation. PhD thesis University of Utrecht. Utrecht.
• 18: R. R. Hudson, M. Slatkin and W. P. Maddison (1992). Estimation of Levels of Gene Flow From DNA Sequence Data. Genetics. 132 (2): pp. 583--589.
• 19: LiveGraph - a framework for real-time data visualisation, analysis and logging. Retrieved on 01.03.2008 from: http://www.live-graph.org.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

General Terms:
Algorithms, Performance, Theory

Keywords:
evolutionary algorithm, gene flow, genetic algorithm, holey fitness landscape, premature convergence, reproductive isolation.