Abstract:
For this thesis, we propose to study how to automatically combine multiple neighborhood-based heuristics. For most computationally challenging problems, there exists 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. As a result, 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 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 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 view 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 patterns of collaboration can emerge, how do we recognize those patterns, and once we have those patterns, how frequently should we use one pattern versus another to compose the entire search process.

Thesis Proposal Document

Thesis Committee Members:
Stephen F. Smith, Chair
Katia Sycara
Zachary B. Rubinstein
Gabriela Ochoa, University of Stirling