Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes

ABSTRACT

This study analyzes performance of several genetic and evolutionary algorithms on randomly generated NK fitness landscapes with various values of n and k. A large number of NK problem instances are first generated for each n and k, and the global optimum of each instance is obtained using the branch-and-bound algorithm. Next, the hierarchical Bayesian optimization algorithm (hBOA), the univariate marginal distribution algorithm (UMDA), and the simple genetic algorithm (GA) with uniform and two-point crossover operators are applied to all generated instances. Performance of all algorithms is then analyzed and compared, and the results are discussed.

REFERENCES

• 1: H. E. Aguirre and K. Tanaka. Genetic algorithms on nk-landscapes: Effects of selection, drift, mutation, and recombination. In G. R. Raidl et al., editors, Applications of Evolutionary Computing: EvoWorkshops 2003, pages 131--142, 2003.
• 2: L. Altenberg. NK landscapes. In T. Bäck, D. B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, pages B2.7:5--10. Institute of Physics Publishing and Oxford University Press, Bristol, New York, 1997.
• 3: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 4: P. A. N. Bosman and D. Thierens. Continuous iterated density estimation evolutionary algorithms within the IDEA framework. Workshop Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 197--200, 2000.
• 5: D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSR-TR-97-07, Microsoft Research, Redmond, WA, 1997.
• 6: Sung-Soon Choi , Kyomin Jung , Jeong Han Kim, Phase transition in a random NK landscape model, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068212]
• 7: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 8: Y. Gao and J. C. Culberson. An analysis of phase transition in NK landscapes. Journal of Artificial Intelligence Research (JAIR), 17:309--332, 2002.
• 9: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 10: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 11: D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research, Redmond, WA, 1994.
• 12: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 13: S. Kauffman. Adaptation on rugged fitness landscapes. In D. L. Stein, editor, Lecture Notes in the Sciences of Complexity, pages 527--618. Addison Wesley, 1989.
• 14: S. Kauffman. The origins of Order: Self-and selection in evolution. Oxford University Press, 1993.
• 15: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
• 16: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 17: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.
• 18: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, 2001.
• 19: M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and maxsat. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), II:1275--1286, 2003.
• 20: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 21: M. Pelikan, H. G. Katzgraber, and S. Kobe. Finding ground states of Sherrington-Kirkpatrick spin glasses with hierarchical BOA and genetic algorithms. MEDAL Report No. 2008004, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri-St. Louis, St. Louis, MO, 2008.
• 22: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Department of General Engineering, Urbana, IL, 2001.
• 23: A. H. Wright, R. K. Thompson, and J. Zhang. The computational complexity of N-K fitness functions. IEEE Transactions Evolutionary Computation, 4(4):373--379, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Performance

Keywords:
NK fitness landscape, branch and bound, crossover, genetic algorithm, hierarchical boa, local search, performance analysis, scalability