Combining Multiple Heuristics: Studies on Neighborhood-based Heuristics and Sampling-based Heuristics

Abstract

This thesis centers on the topic of how to automatically combine multiple heuristics. For most computationally challenging problems, there exist multiple heuristics, and it is generally the case that any such heuristic exploits only a limited number of aspects among all the possible problem characteristics that we can think of, and by definition, is not infallible. Thus, if the situation encountered does not align well with the nature of the employed heuristic, the algorithm can progress very slowly or get trapped in a bad local optimum. In order to compensate for this, researchers have been investigating and experimenting with the idea of combining multiple heuristics. The development of this idea is also motivated by the fact that we have progressed to a point at which we started to consider more complex problems that have subproblems or facets similar to simpler and more-studied problems. In this case, it is very natural to attempt to reuse the heuristics that we developed for those more-studied problem domains. In this study, we intend to build on this approach of combining multiple heuristics. At the broadest level, we would like to explore possible ways to synthesize effective search processes for solving combinatorial optimization problems. The specific strategies we consider will be based on using existing heuristics as algorithmic components and combining them in an automatic fashion. Furthermore, this research will have an emphasis on creating and utilizing collaborations among heuristics as an underlying means. This leads to several research questions such as how to set up an environment so that collaborations among heuristics can emerge, how do we reuse the collaborated efforts, and how do we adjust the search process so that the benefit of collaboration can be amplified.

In this thesis, we develop two types of integration architectures, each of which is specific to a broad class of heuristics. The first part of this thesis focuses on studying possible ways of combining neighborhood-based heuristics, which operate based on the idea of iteratively searching for improvements in the neighborhood of the current solutions. We will first present a basic architecture that we use as a foundation for enabling cooperation among multiple neighborhood-based heuristics. The fundamental idea of this architecture is to chain multiple heuristics in a pipelined fashion so that we can utilize the interaction between heuristics. Based on that, we will proceed to examine some simple learning mechanisms that adjust the behavior of the search algorithm based on the collected data. Finally, we will explore how to learn more explicit collaboration patterns among the neighborhood-based heuristics, and we will evaluate the benefit of using these learned patterns in a more rigorous cross-validation assessment.

The second part of this thesis looks at how to combine multiple sampling-based heuristics, which compose a solution by sampling a probabilistic model that encodes the structures of potentially good candidate solutions. We will propose a method that uses a linear interpolation to combine multiple sampling-based heuristics. The weights associated with the participating heuristics are estimated automatically based on observed data and dynamically changed from iteration to iteration. Finally, by analyzing this approach, we will further distill a generalized framework for combining sampling-based heuristics.