Learning and Utilizing Interaction Patterns among Neighborhood-Based Heuristics

Proceedings of the International Symposium on Combinatorial Search, 12

Volume

Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search

Long Papers

This paper proposes a method for learning and utilizing potentially useful interaction patterns among neighborhood-based heuristics. It is built upon a previously proposed framework designed for facilitating the task of combining multiple neighborhood-based heuristics. Basically, an algorithm derived from this framework will operate by chaining the heuristics in a pipelined fashion. Conceptually, we can view this framework as an algorithmic template that contains two user-defined components: 1) the policy H for selecting heuristics, and 2) the policy L for choosing the length of the pipeline that chains the selected heuristics. In this paper, we will develop a method that automatically derives a policy H by analyzing the experience collected from running a baseline algorithm. This analysis will distill potentially useful patterns of interactions among heuristics, and give an estimate for the frequency of using each pattern. The empirical results on three problem domains show the effectiveness of the proposed approach.

10.1609/socs.v10i1.18499