The “Extended Reach” method: exploring the neighbors of the neighbors to escape from local optima

Abstract

[EN] Local search is a widely used meta-heuristic due to its simple yet effective approach for solving computationally hard optimization problems. Despite their popularity, hill-climbing algorithms get stuck in local optima, solutions with out improving neighbors form where the local search could continue. Trying to avoid this stagnant behaviour, most modern local search based algorithms have been designed to escape from local optima. Thanks to recently discovered properties of the landscapes formed by combinatorial optimization problems and neighborhood systems, a novel procedure to escape from local optima is proposed. This method, named “Extended Reach”, also considers the neighbors of the neighbors of the local optima it encounters as candidate solutions to proceed to and continue the search. The “Extended Reach” method is applied to well-known permutation based combinatorial optimization problems and neighborhoods, discussing along the way the numerous developments that went into its design. The conducted experiments show promising results, successfully escaping from local optima and notably outperforming the Multi-Start heuristic, specially with instances containing a reduced number of plateaus.