Carnegie Mellon University
chungyac_phd_robotics_2020.pdf (698.16 kB)
Download file

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

Download (698.16 kB)
posted on 2020-05-21, 22:19 authored by Chung-yao ChuangChung-yao Chuang
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.




Degree Type

  • Dissertation


  • Robotics Institute

Degree Name

  • Doctor of Philosophy (PhD)


Stephen F. Smith