Local search heuristics (metaheuristics, evolutionary algorithms, etc.) are stochastic optimization methods which split a global optimization problem into a succession of local optimization problems. Although it can not be guaranteed to find global optimum by local search, they have been applied to number of real-world problems due to their efficiency and robustness. However, one fundamental issue is to understand why such local search strategies are efficient, and another difficulty in practice is to design a relevant local search according to the structure of the optimization problem.

Fitness landscape is one of the powerful metaphor which depicts the local search dynamic on a landscape based on peaks, valleys, plateaus, etc. Beside the picture which helps to understand the problem structure and to intuitively design better algorithms, the fitness landscapes analysis is a way to characterize problem structure, and to be able to predict algorithm performance, or to select a relevant local search.

This talk will give an overview of the fitness landscape analysis for single- multi-objective optimization problems. In particular, we will highlight the Local Optima Networks (LONs) which is a model combinatorial landscapes as graphs, where nodes are local optima and edges transitions among them according to given move operators; and also we will give a sound and concise summary of features characterizing the structure of multi-objective problems.