The design of good heuristics is important in many engineering applications. Today, many application problems are too complex for users to find optimal algorithms analytically. Rather, users rely on heuristics designed by experts to find high-quality solutions. The effectiveness of these heuristics, however, depends on domain knowledge available to and past experience of these experts. When little domain knowledge is available, it is important to develop automated learning methods for generating improved heuristics systematically, evaluating their performance on realistic test cases, and generalizing their performance to test cases not seen in learning. Such learning and generalization methods will carry significant impact in many engineering applications.

The objective of the Teacher (TEchniques for the Automated Creation of HEuRistics) Project is to automate the learning and generalization of performance-related heuristics for knowledge-lean application problems. To find robust and better heuristics that perform well under a wide variety of conditions, issues on performance evaluation, generalization, generalizability, and resource scheduling must be studied.

• Overall System

• Generalizability: This involves finding heuristics that perform better than other competing heuristics across test cases of different statistical behavior in an application. Traditional statistical methods, which generally require performance data to be independent and identically distributed, cannot be applied. A new statistical measure called probability of win was developed to assess the performance of heuristics in a range-independent and distribution-independent manner. This generalization method has led to many new and robust heuristics that perform better than existing heuristics.

• Resource Scheduling: This involves scheduling (sequential and parallel) computing resources in genetics-based learning so that high-quality heuristics can be learned in a limited amount of time. This problem was largely ignored in the literature in the past but is extremely important in real applications in which tests of heuristics are expensive. A number of efficient resource scheduling algorithms have been developed to trade between the number of new heuristic methods considered and the amount of tests performed on each.

• Applications:
  • Process mapping in PostGame Analysis
  • Load balancing on a network of workstations in Condor
  • Circuit placement, routing, and testing in TimberWolf, Cris and GA Test
  • Automated design of feedforward neural networks
  • Branch-and-bound search
  • Range estimation in stereo vision
  • Channel equalization in signal processing

  Improvements in these problem solvers are very hard because they have been tuned extensively by their designers. In each application, Teacher was able to find improvements ranging from 5% to several orders of magnitude.

• Related research in learning