Learning and Utilizing Interaction Patterns Among Neighborhood-Based Heuristics

July 2019

Learning and Utilizing Interaction Patterns Among Neighborhood-Based Heuristics

Authors:

C-Y. Chuang and S. F. Smith

Abstract:

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.
@conference{Chuang-2019-120473,
author = {C-Y. Chuang And S. F. Smith},
title = {Learning and Utilizing Interaction Patterns Among Neighborhood-Based Heuristics},
booktitle = {Proceedings 12th International Symposium on Combinatorial Search (SoCS '19)},
year = {2019},
month = {July},
pages = {26 - 34},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.