ABSTRACT
In this chapter, the authors study methods for developing general heuristics in order to solve problems in knowledge-lean application domains with a large and possibly infinite problem space. Genetics-based learning is a generate-and-test paradigm that maintains a pool of competing heuristic methods (HM), tests them to a limited extent, creates new ones from those that perform well in the past, and prunes poor ones from the pool. The authors discuss two types of problem domains: First, those with a large number of test cases and possibly an infinite number of deterministic HMs for solving them. Second, those with a small number of test cases but the HMs concerned have a nondeterministic component, such as a random initialization point, that allows different results to be generated for each test case. The authors show that generalization can lead to new and robust heuristics that perform well across problem instances of different characteristics in an application domain.
