One early attempt at reuse can be found in Ackley's work with SIGH [Ackley1987]. Ackley periodically restarts a search in an attempt to avoid local optima and increase the quality of solutions. Eshelman's CHC algorithm, a genetic algorithm with elitist selection and cataclysmic mutation, also restarts search when the population diversity drops below a threshold [Eshelman1991]. Other related work includes Koza's automatically defined functions [Koza1993] and Schoenauer's constraint satisfaction method [Schoenauer & Xanthakis1993]. More recently, Ramsey and Grefenstette come closest to our approach and use previously stored solutions to initialize a genetic algorithm's initial population and thus increase a genetic algorithm's performance in an anytime learning environment that changes with time [Ramsey & Grefensttete1993,Grefensttete & Ramsey1992]. Automatic injection of the best solutions to previously encountered problems biases the search toward relevant areas of the search space and results in the reported consistent performance improvements. Sheppard and Salzburg combined memory-based learning with genetic algorithms in finding better plans for the pursuer-evader game within a reinforcement learning framework [Sheppard & Salzburg1995]. Their experiments indicate that the combined approach performed better than either approach alone. To our knowledge, the earliest work in combining genetic algorithms and case-based reasoning was done by Louis, McGraw, and Wyckoff who used case-based reasoning principles to explain solutions found by genetic algorithm search [Louis, McGraw, & Wyckoff1993]. Preliminary work in this area solved pairs of similar problems with a clear performance advantage for the combined system [Louis & Johnson1997a]. These approaches only attack a single problem not a related class of problems. Moreover, these approaches do not relate problem/solution similarity to the quality of injected solutions and performance - a fundamental result of this paper.
Work on multitask learning suggests, as we do, that it is easier to learn many tasks at once, rather than to learn these same tasks separately [Caruana1997b,Caruana, Baluja, & Mitchell1996,Caruana1997a]. Multitask learning can be applied to clusters of related tasks in parallel or in sequence and provides an inductive bias that often leads to better generalization performance on the tasks. While MTL addresses generalization, we lean towards improving search performance - in design domains, a mapping from function to structure - for sequential (design) tasks. Parallel genetic algorithms using the island model, provide one possible avenue towards information exchange on related tasks in parallel for genetic based machine learning systems.
Lifelong learning seeks to address the problem of knowledge transfer between related tasks in the context of learning control algorithms for robotics [Thrun1996a,Thrun1996b]. The authors believe that knowledge transfer is essential for scaling robot learning algorithms to more realistic and complex domains. Lifelong learning differs from our approach in that they are interested in an incremental learning situation seeking to build behavioral complexity with experience. Work by Louis provides strong support for the CIGAR approach to control problems in robotics thus indirectly and independently providing more evidence for the utility of lifelong learning [Louis & Li1997].
What do we mean by problem similarity? What is the difference between problem similarity and solution similarity? The next section provides concrete answers to these questions in the context of combinational logic design.