Tunably Rugged Landscapes With Known Maximum and Minimum.

Area of Science:

• Computational intelligence
• Optimization algorithms
• Benchmark problem generation

Background:

• Existing benchmark problems like NK landscapes and Walsh polynomials have limitations in tunability and transparency of epistasis.
• There is a need for robust benchmark problems that accurately model search difficulty and possess known global optima.

Purpose of the Study:

• To introduce and define a new class of benchmark problems called NM landscapes.
• To demonstrate the tunable ruggedness and desirable properties of NM landscapes for optimization research.

Main Methods:

• Definition of NM landscapes applicable to discrete and real-valued alphabets.
• Incorporation of epistasis in a natural and transparent manner.
• Empirical studies to validate tunable ruggedness and correlation with search difficulty measures.

Main Results:

• NM landscapes are well-defined and include epistasis transparently.
• The global maximum's value and location are known; the global minimum can also be known under certain constraints.
• Empirical results show smoothly tunable ruggedness correlating with search difficulty.

Conclusions:

• NM landscapes offer a superior alternative to NK landscapes and Walsh polynomials for benchmark modeling.
• Their tunable epistasis and known optima make them ideal for rigorous testing of optimization algorithms.