Improving local-search metaheuristics through look-ahead policies

Abstract

As a basic principle, look-ahead approaches investigate the outcomes of potential future steps to evaluate the quality of alternative search directions. Different policies exist to set up look-ahead methods differing in the object of inspection and in the extensiveness of the search. In this work, two original look-ahead strategies are developed and tested through numerical experiments. The first method introduces a look-ahead mechanism that acts as a hyper-heuristic for comparing and selecting local-search operators. The second method uses a look-ahead strategy on a lower level in order to guide a local-search metaheuristic. The proposed approaches are implemented using a hyper-heuristic framework. They are tested against alternative methods using two different competition benchmarks, including a comparison with results given in literature. Furthermore, in a second set of experiments, a detailed investigation regarding the influence of particular parameter values is executed for one method. The experiments reveal that the inclusion of a simple look-ahead principle into an iterated local-search procedure significantly improves the outcome regarding the considered benchmarks.