Idealization-Based Discovery of Search Heuristics

点击翻译按钮获取中文摘要

Many computational problems can be solved by searching through a well-defined but huge space of candidates provided good heuristics are available to guide the search. Thus automated discovery of search heuristics would have both practical and scientific importance. In this approach, the generation of heuristics is modelled as the application of successive transformations to an initial problem specification. This research addresses a number of issues raised by the long-term goal of scaling up to more realistic application domains. To refine the model, studies of perturbation experiments aimed at understanding when and why it works will be carried out. To enrich the space of generated heuristics, extensions and integration of transformations so as to rederive known scheduling and routing heuristics and the discovery of new ones will be undertaken. To explore this space more efficiently, novel methods for evaluating potential heuristics will be employed. Expected outcomes of this work include engineering advances in automated methods for discovering heuristics, as well as scientific advances in understanding their underlying principles.