Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap

ABSTRACT

This paper presents a class of NK landscapes with nearest-neighbor interactions and tunable overlap. The considered class of NK landscapes is solvable in polynomial time using dynamic programming; this allows us to generate a large number of random problem instances with known optima. Several genetic and evolutionary algorithms are then applied to the generated problem instances. The results are analyzed and related to scalability theory for genetic algorithms and estimation of distribution algorithms.

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, 1997.
• 3: J. W. Barnes, B. Dimova, S. P. Dokov, and A. Solomon. The theory of elementary landscapes. Appl. Math. Lett., 16(3):337--343, 2003.
• 4: 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.
• 5: 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]
• 6: David Jonathan Coffin , Robert Elliott Smith, Why is parity hard for estimation of distribution algorithms?, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277084]
• 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: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 11: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992.
• 12: D. E. Goldberg and M. Rudnick. Genetic algorithms and the variance of fitness. Complex Systems, 5(3):265--278, 1991.
• 13: 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
• 14: G. R. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Int. Conf. on Evolutionary Computation (ICEC-97), pages 7--12, 1997.
• 15: G. R. Harik and D. E. Goldberg. Learning linkage. Foundations of Genetic Algorithms, 4:247--262, 1996.
• 16: 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.
• 17: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 18: 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.
• 19: S. Kauffman. The origins of Order: Self-organization and selection in evolution. Oxford University Press, 1993.
• 20: H. Mühlenbein and T. Mahnig. Convergence theory and applications of the factorized distribution algorithm. Journal of Computing and Information Technology, 7(1):19--32, 1998.
• 21: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.
• 22: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Genetic and Evolutionary Computation Conf. (GECCO-2001), pages 511--518, 2001.
• 23: M. Pelikan, K. Sastry, M. V. Butz, and D. E. Goldberg. Performance of evolutionary algorithms on random decomposable problems. Parallel Problem Solving from Nature, pages 788--797, 2006.
• 24: Martin Pelikan, Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389287]
• 25: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning, 31(3):221--258, 2002.
• 26: M. Pelikan, K. Sastry, D. E. Goldberg, M. V. Butz, and M. Hauschild. Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap. MEDAL Report No. 2009002, Missouri Estimation of Distribution Algorithms Laboratory, 2009.
• 27: Franz Rothlauf, Representations for Genetic and Evolutionary Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 28: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, Univ. of Illinois at Urbana-Champaign, Urbana, IL, 2001.
• 29: Kumara Sastry , Martin Pelikan , David E. Goldberg, Empirical analysis of ideal recombination on random decomposable problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277216]
• 30: D. Thierens. Analysis and design of genetic algorithms. PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium, 1995.
• 31: Dirk Thierens, Scalability problems of simple genetic algorithms, Evolutionary Computation, v.7 n.4, p.331-352, Winter 1999 [doi>10.1162/evco.1999.7.4.331]
• 32: D. Thierens and D. Goldberg. Convergence models of genetic algorithm selection schemes. Parallel Problem Solving from Nature, pages 116--121, 1994.
• 33: Dirk Thierens , David E. Goldberg, Mixing in Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.38-47, June 01, 1993
• 34: D. Thierens, D. E. Goldberg, and A. G. Pereira. Domino convergence, drift, and the temporal-salience structure of problems. Int. Conf. on Evolutionary Computation (ICEC-98), pages 535--540, 1998.
• 35: A. H. Wright, R. K. Thompson, and J. Zhang. The computational complexity of N-K fitness functions. IEEE Trans. on Evolutionary Computation, 4(4):373--379, 2000.
• 36: Tian-Li Yu , Kumara Sastry , David E. Goldberg , Martin Pelikan, Population sizing for entropy-based model building in discrete estimation of distribution algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277080]

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:
crossover, fitness landscape, genetic algorithm, hboa, hierarchical boa, hybridization, nk fitness landscape, performance analysis, problem difficulty, scalability