This paper demonstrates the feasibility of combining genetic algorithms with case-based reasoning principles to augment search and shows that the combined system learns with experience. Instead of discarding information gleaned from previous problem solving attempts through search, we save and inject solutions to similar problems into the initial population of a genetic algorithm to increase performance. Our preliminary results, using pairs of problems, indicate the feasibility and usefulness of this approach and show that choosing the right quantity and quality of cases plays a large part in determining performance. We also developed a robust methodology that works in the absence of precise information on problem distance. Defining a class of about 50 similar problems, we show that the time taken by our prototype GA-CBR system to find a quality solution decreases as the number of problems attempted by the combined system increases.
Although the approach has promise, much work remains to be done. We need to consider the effect of different selection schemes, recombination operators, and niching operators, for genetic search as well other search algorithms and associative memory models. Individuals need not be injected solely into the initial population. We can keep track of the performance of injected individuals and their progeny and use this information to design and inject individuals in intermediate generations. Finally, the tradeoffs between speed and solution quality needs to be explored in more detail.
This material is based upon work supported by the National Science Foundation under Grant No. 9624130.