Developing a Theory of Heuristics

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

Current theory does little to predict, explain or analyze the empirically observed success of search and optimization heuristics for some domains of NP-complete problem and their failure for others. Without such a theory, implementers of heuristics have no guidance as to whether a particular heuristic method is suitable for a particular problem domain, what kind of performance to expect, or how to set the various parameters for better performance. Implementation is often done in a haphazard way based on little more than guess-work or trial-and-error. The following inter-related lines of theoretical research will be explored to address this gap: (1) Extending average-case complexity to consider reductions to and between problem distributions that arise naturally ( in real-life, testing, cryptanalysis or combinatorics). (2) Extending average-case analysis techniques to a more general characterization of the relevant combinatorial properties of random problem instances from naturally arising distributions. In particular, the properties of associated search spaces for such problems. (3) For experimentally successful heuristic methods, identify the combinatorial characteristics of problem instances that determine their performance. (4) Investigate more efficient worst-case algorithms for NP complete problems, identify those NP complete problems with nontrivial worst-case algorithms, and explore the connection between lower and upper bounds. Although the techniques used are solely mathematical, the motivation and justification come from the experimental literature.