Climbing Combinatorial Fitness Landscapes

International audience

<p>Hill-climbing constitutes one of the simplest way to produce approximate solutions of a combinatorial optimization problem, and is a central component of most advanced metaheuristics. This paper focuses on evaluating climbing techniques in a context where deteriorating moves are not allowed, in order to isolate the intensification aspect of metaheuristics. We aim at providing guidelines to choose the most adequate method for climbing efficiently fitness landscapes with respect to their size and some ruggedness and neutrality measures. To achieve this, we compare best and first improvement strategies, as well as different neutral move policies, on a large set of combinatorial fitness landscapes derived from academic optimization problems, including NK landscapes. The conclusions highlight that first-improvement is globally more efficient to explore most landscapes, while best-improvement superiority is observed only on smooth landscapes and on some particular structured landscapes. The empirical analysis realized on neutral move policies shows that a stochastic hill-climbing reaches in average better configurations and requires fewer evaluations than other climbing techniques. Results indicate that accepting neutral moves at each step of the search should be useful on all landscapes, especially those having a significant rate of neutrality. Last, we point out that reducing adequately the precision of a fitness function makes the climbing more efficient and helps to solve combinatorial optimization problems.</p>