|
Abstract:
|
The effectiveness of any metaheuristic, e.g., genetic algorithms or simulated annealing, is dictated by the degree to which the algorithm is able to exploit the structure of the underlying search space or fitness landscape. This tutorial will begin with a formal definition of the concept of a fitness landscape, followed by an overview of the various structural features present in the fitness landscapes of many well-known NP-hard combinatorial optimization problems. Following the introductory material, I will discuss the relationship between fitness landscape structure and algorithm run-time behavior, explain why certain fitness landscape features often cause problems for various metaheuristics, and illustrate how metaheuristics can be designed to exploit the presence of specific fitness landscape features. The tutorial concludes with a brief survey of open, fundamental research questions in the area of metaheuristic analysis and design.
|
