NM landscapes: beyond NK

ABSTRACT

For the past 25 years, NK landscapes have been the classic benchmarks for modeling combinatorial fitness landscapes with epistatic interactions between up to K+1 of N binary features. However, the ruggedness of NK landscapes grows in large discrete jumps as K increases, and computing the global optimum of unrestricted NK landscapes is an NP-complete problem. Walsh polynomials are a superset of NK landscapes that solve some of the problems. In this paper, we propose a new class of benchmarks called NM landscapes, where M refers to the Maximum order of epistatic interactions between N features. NM landscapes are much more smoothly tunable in ruggedness than NK landscapes and the location and value of the global optima are trivially known. For a subset of NM landscapes the location and magnitude of global minima are also easily computed, enabling proper normalization of fitnesses. NM landscapes are simpler than Walsh polynomials and can be used with alphabets of any arity, from binary to real-valued. We discuss several advantages of NM landscapes over NK landscapes and Walsh polynomials as benchmark problems for evaluating search strategies.

References

1. J. Buzas and J. Dinitz. An analysis of NK landscapes: Interaction structure, statistical properties and expected number of local optima. IEEE Transactions on Evolutionary Computation, in press, DOI 10.1109/TEVC.2013.2286352, 2014.
2. S. Kauffman. The origins of order: Self organization and selection in evolution. Oxford University Press, 1993.
3. S. A. Kauffman and E. D. Weinberger. The NK model of rugged fitness landscapes and its application to maturation of the immune response. Journal of theoretical biology, 141(2):211--245, 1989.
4. R. Tanese. Distributed genetic algorithms for Function Optimization. PhD thesis, The University of Michigan, Ann Arbor, MI, 1989.
5. A. H. Wright, R. K. Thompson, and J. Zhang. The computational complexity of NK fitness functions. IEEE Transactions on Evolutionary Computation, 4(4):373--379, 2000.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Computations on polynomials