Genetic algorithms (GAs) are randomized parallel search algorithms that search from a population of points [Holland, 1975]. We typically randomly initialize the starting population so that a genetic algorithm can proceed from an unbiased sample of the search space. However in many application areas we confront sets of similar problems. It makes little sense to start a problem solving search attempt from scratch with a random initial population when previous search attempts may have yielded useful information about the search space. Instead, seeding a genetic algorithm's initial population with solutions to similar previously solved problems can provide information (a search bias) that, hopefully, increases the efficiency of the search. Our approach borrows ideas from case-based reasoning (CBR) in which old problem and solution information, stored as cases in a case-base, help solve a new problem [Riesbeck and Schank, 1989].
The approach outlined in this paper has many application areas in engineering design [Tong and Sriram, 1992] and we use example problems from open shop scheduling and re-scheduling as a test-bed for the work reported in this paper. Although we only consider genetic algorithms, the basic ideas can be extended to other evolutionary computation methods, and with some modifications, to other heuristic search methods.
The next two sub-sections provide short introductions to case-based reasoning and genetic algorithms. For researchers familiar with the topics these subsections may be skipped without loss of continuity. Section 2 outlines the issues in combining GAs and CBR and discusses previous work in this area. The open-shop scheduling and re-scheduling problems and our methodology and experimental results on the test problems are presented in subsequent sections. The last section presents conclusions and directions for future work.
Case-based reasoning (CBR) is based on the idea that reasoning and explanation can best be done with reference to prior experience, stored in memory as cases [Riesbeck and Schank, 1989, Bareiss, 1991]. When confronted with a problem to solve, a case-based reasoner extracts the most similar case in memory and uses information from the retrieved case and any available domain information to tackle the current problem. The strategy is first to collect and index a large and varied collection of examples, and then, when presented with a new situation, to fetch and possibly manipulate or adapt the stored example that most closely resembles the new situation.
Genetic algorithms are stochastic, parallel search algorithms based on the mechanics of natural selection, the process of evolution [Holland, 1975, Goldberg, 1989]. GAs were designed to search large, non-linear search spaces where expert knowledge is lacking or difficult to encode and where traditional optimization techniques fall short. They are flexible and robust, exhibiting the adaptiveness and graceful degradation of biological systems.
Genetic algorithms, like other search algorithms, balance the need for exploration -- to avoid local optima, with exploitation -- to converge on the optima. GAs dynamically balance exploration versus exploitation through the recombination (crossover and mutation) and selection operators respectively. When we seed a genetic algorithm's initial population with cases we alter this balance, subsequently affecting the search bias and thus the kind of solutions generated. We propose using a kind of associative memory -- organizing information based on ``similarity'' -- to help augment genetic algorithm search.