  We propose NM landscapes as a new class of tunably rugged benchmark problems.
NM landscapes are well-defined on alphabets of any arity, including both
discrete and real-valued alphabets, include epistasis in a natural and
transparent manner, are proven to have known value and location of the global
maximum and, with some additional constraints, are proven to also have a known
global minimum. Empirical studies are used to illustrate that, when
coefficients are selected from a recommended distribution, the ruggedness of NM
landscapes is smoothly tunable and correlates with several measures of search
difficulty. We discuss why these properties make NM landscapes preferable to
both NK landscapes and Walsh polynomials as benchmark landscape models with
tunable epistasis.
