In this paper, we discuss a new approach to generalize heuristic methods (HMs) to new test cases of an application, and conditions under which such generalization is possible. Generalization is difficult when performance values of HMs are characterized by multiple statistical distributions across subsets of test cases of an application. We define a new measure called probability of win and propose three methods to evaluate it: interval analysis, maximum likelihood estimate, and Bayesian analysis. We show experimental results on new HMs found for blind equalization and branch-and-bound search.

We present new results on the automated generalization of performance-related heuristics learned for knowledge-lean applications. We study methods to statistically generalize new heuristics learned for some small subsets of a problem space (using methods such as genetics-based learning) to unlearned problem subdomains. Our method uses a new statistical metric called probability of win. By assessing the performance of heuristics in a range-independent and distribution-independent manner, we can compare heuristics across problem subdomains in a consistent manner. To illustrate our approach, we show experimental results on generalizing heuristics learned for sequential circuit testing, VLSI cell placement and routing, and branch-and-bound search. We show that generalization can lead to new and robust heuristics that perform better than the original heuristics across problem instances of different characteristics.

We present new methods for the automated learning of heuristics in knowledge lean applications and for finding heuristics that can be generalized to unlearned domains. These applications lack domain knowledge for credit assignment; hence, operators for composing new heuristics are generally model free, domain independent, and syntactic in nature. The operators we have used are genetics based; examples of which include mutation and cross over. Learning is based on a generate and test paradigm that maintains a pool of competing heuristics, tests them to a limited extent, creates new ones from those that perform well in the past, and prunes poor ones from the pool. We have studied three important issues in learning better heuristics: anomalies in performance evaluation; rational scheduling of limited computational resources in testing candidate heuristics in single objective as well as multiobjective learning; and finding heuristics that can be generalized to unlearned domains. We show experimental results in learning better heuristics for: process placement for distributed memory multicomputers, node decomposition in a branch and bound search, generation of test patterns in VLSI circuit testing, and VLSI cell placement and routing.>

In this paper we present TEACHER 4.1, a system for designing automatically heuristics that map a set of cmnmunicating processes on a real-time distributed computing system.The problem of optimal promas mapping is NP-hard and involves the optimal placement of precesses on the distributed system and the optimaf routing of messages from one computer to another.The design of efficient and robust heuristics is often ad hoc and is guided by intuition and experience of the designers.In this paper we develop a statistical method to explore systematically the space of possible heuristics for process mapp.mg.The method operates under a specified time constraint and intends to get the best possible heuristics whale trading between the solution quality and the execution time of the process mapping heuristics.Our prototype for process mWPing is extended hom post-game analysis, a system that uses a set of user-specified roles for generating new mappings.It tunes pamneters of these rules and proposea new heuristics for process mapping.Simulations show that there is significant improvement m performance through systematic and automatic exploration of the spare of heuristics.