Our results demonstrate the feasibility of combining genetic algorithms with case-based reasoning principles to augment search. 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 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 obtained consistently better performance in terms of both speed and quality on the the open-shop re-scheduling problem.
Injecting a large number of high fitness individuals into the population usually does not produce good quality solutions over the long run as there is too much exploitation in the area defined by these injected individuals. Injecting too few, low fitness individuals also does not produce an advantage versus running the GA with a randomly initialized population. The ``right'' quality and quantity of individuals must be injected to realize performance gains. We find that the fitness of individuals to be injected depends on the distance between the old problem, to which we have solutions, and the current one. Problem size and the structure of the search space also play an important part in this issue. The results indicate an inverse relationship between problem distance and the fitness of injected individuals. Finally, although we can inject a larger number of individuals for larger problems, injecting a number of individuals between 5 to 15 percent of the population size provides good results over our problem sets. In the absence of information, these results suggest injection of a small percentage (depending on how quickly we want results) of cases of different fitnesses to cover the various possibilities in problem distance, solution distance, and search space structure.
We are currently working on implementing a pilot system that will gradually decrease the time taken to solve problems within a domain using genetic search and an expanding case base. As the system adds to the case base while attempting to solve problems the probability of finding similar solutions in the case base will increase and lead to a decrease in the time taken to solve a new problem. We will be forced to confront problems in indexing, storage, and retrieval of cases; important issues in designing CBR systems.
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 different search algorithms. Deriving more refined estimates on the quality and quantity of individuals to inject will broaden applicability. 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.
