Design problems seldom exist in isolation. Any useful design system must expect to confront many related problems over its lifetime and we would like such a system to improve its performance with experience. Such a learning system requires memory; a place for storing past experiences to guide future operations. The storage area may be distributed or localized, but a system without a memory is forced to start from scratch in trying to solve every given problem. Genetic algorithms (GAs) are randomized parallel search algorithms that search from a population of points [Holland1975,Goldberg1989]. Current genetic algorithm based machine learning systems use rules to store past experience to improve their performance over time [Holland1975,Goldberg1989,Smith1985,Janikow1993,Grefenstette, Ramsey, & Shultz1990]. However, many application areas, especially in the design domain, are more suited to a case-based storage of past experience [Mostow, Barley, & Weinrich1992,Huhns & Acosta1992,Sycara & Navinchandra1992,Goel & Chandresekaran1992]. 1 We propose and describe a system that uses a case-base as a long term knowledge store in a new genetic algorithm based design system that learns from experience. Results from the design of parity checkers, applicable to problems from engineering design and architecture, show 1) that our system, with experience, takes less time to solve new problems and produces better quality solutions and 2) a simple syntactic similarity metric can result in this performance improvement thus avoiding the indexing problem endemic to purely case-based systems.
These performance gains imply that fewer evaluations are needed to reach a specified design solution quality and that the organization deploying this system builds a knowledge base of cases.
Typically, a genetic algorithm randomly initializes its starting population so that the GA can proceed from an unbiased sample of the search space. However, as pointed out earlier, problems do not usually exist in isolation and we often confront sets of similar problems. It makes little sense to start a problem solving search attempt from scratch when previous search attempts may have yielded useful information about the search space. Instead, periodically injecting a genetic algorithm's population with relevant (we describe what we mean by relevant later) solutions or partial solutions to similar previously solved problems can provide information (a search bias) that reduces the time taken to find a quality solution. Our approach borrows ideas from case-based reasoning (CBR) in which old problem and solution information, stored as cases in a case-base, helps solve a new problem [Riesbeck & Schank1989]. In our system, the data-base, or case-base, of problems and their solutions supplies the genetic problem solver with a long term memory. The system does not require a case-base to start with and can bootstrap itself by learning new cases from the genetic algorithm's attempts at solving a problem.
The case-base does what it is best at - memory organization; the genetic algorithm handles what it is best at - adaptation. The resulting combination takes advantage of both paradigms; the genetic algorithm component delivers robustness and adaptive learning while the case-based component speeds up the system.
The Case Injected Genetic AlgoRithm (CIGAR) system presented in this paper can be applied in a number of domains from computational science and engineering to operations research. We concentrate on configuration design problems, specifically the design of combinational logic circuits.
We define the CIGAR system in the next section. We then discusses related work and delineate the difference between problem and solution similarity and apply our system to two problems that highlight fundamental issues addressed by this work. The last section presents conclusions and directions for future work.