Tunably Rugged Landscapes With Known Maximum and Minimum

Abstract

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.

Keywords: Benchmark landscapes; NK landscapes; Walsh polynomials; fitness landscapes.

Fig. 1

Number of local peaks in NK landscapes with N = 10, as a function of the number of terms in the equivalent parametric interaction model (m, bottom x-axis) for K = {1, 2, …, 9} (top x-axis). The black dots show empirical results of ten random landscapes generated for each value of K; red lines show the expected number of peaks (L) of these same landscapes computed according to the formula given in [11]. The inset shows a magnification of the K = 3 results.

Fig. 2

Histograms of all 1024 fitnesses in NM landscapes for M = 2, N = 10, and coefficients drawn from (9) with σ as indicated above each panel.

Fig. 3

Histograms of all 1024 fitnesses in binary NM landscapes for M = 2, N = 10, and coefficients drawn from a uniform distribution in the range [0, 1].

Fig. 4

Number of local peaks as a function of the number of terms m (x-axis) and order of interactions M (labels near top), for (a)–(b) Type I and (c)–(d) Type II binary NM landscapes with N = 10 and σ = 10. The gray area shows one standard deviation and black lines show the means for 100 random NM landscapes. (a) and (c) show the number of local peaks, (b) and (d) show the lag 1 autocorrelation for the Types I and II NM landscapes, respectively.

Fig. 5

Number of local peaks as a function of the number of terms m (x-axis) and order of interactions M (labels near top), for Type II NM landscapes with N = 15 and σ ∈ {15, 30, 100}. The shaded areas show one standard deviation and the lines show the means for 100 random Type II NM landscapes.

Fig. 6

Visualization of fitnesses of all the points in representative Type I binary NM landscapes with N = 10, σ = 10 versus their distances from the global optimum in feature space for (a) M = 1, (b) M = 2, (c) M = 3, (d) M = 4, (e) M = 6, and (f) M = 10. In these models, all possible interactions for orders ≤ M were included.

Fig. 7

Visualization of fitnesses of all the points in representative Type II binary NM landscapes with N = 10, σ = 10 versus their distances from the global optimum in feature space for (a) M = 1, (b) M = 2, (c) M = 3, (d) M = 4, (e) M = 6, and (f) M = 10. In these models, all possible interactions for orders ≤ M were included.

Fig. 8

Size of the basin of attraction for the global optimum for NK, Types I and II NM landscapes as a function of the maximum order of the interactions (K = M − 1).

Fig. 9

Average of the best fitnesses in populations of 256 agents shown for 30 generations of a GA search performed on 32 random NM landscapes with M = 2, N = 32, and different proportions (P) of second-order interactions.

Fig. 10

Histograms of the distances between the best solution at generation 30 and the global maximum for 32 random Type I NM binary landscapes with M = 2 and N = 32, and with proportions (P) of second-order interactions from top to bottom, as indicated.

Fig. 11

Mean of the best fitnesses found by the GA over 30 generations (x-axis) for 32 random Type III NM landscapes with M ∈ [1, 3, 5] and N = 32 when (a) fitnesses are not normalized, (b) fitnesses are normalized by (14).

Fig. 12

Results of search with a GA on 32 random NM landscapes with M = [1, 3, 5] and N = 32. (a) Proportion of the times the search found the global maximum out of 32 runs. (b) Mean and the standard deviation of the distances between the best solution found by a GA and the global maximum, when the global maximum was not found. The dashed line indicates that at M = 1 all runs found the global maximum.

Fig. 13

Mean and the standard deviation of the best fitnesses found by a GA on NM landscapes with M = 3 and N = 32, when fitnesses are either normalized by (13) (red dashed lines) or by (14) (black lines).