On the efficiency of worst improvement for climbing NK-landscapes

Climbers are often used in metaheuristics in order to intensify the search and identify local optima with respect to a neighborhood structure. Even if they constitute a central component of modern heuristics, their design principally consists in choosing the pivoting rule, which is often reduced to two alternative strategies: first improvement or best improvement. The conception effort of most metaheuristics belongs in proposing techniques to escape from local optima, and not necessarily on how to climb toward better local optima. In this paper, we are interested in attaining good local optima with basic hill-climbing techniques. The NK model will be used to evaluate a set of climbers proposed in this paper. By focusing on the pivoting rule definition, we show that choosing the worst improving neighbor often leads to attain better local optima. Moreover, by slightly modifying the worst improvement strategy, one can design efficient climbers which outperform first and best improvement in terms of tradeoff between quality and computational effort.