Using Case Retrieval to Seed Genetic Algorithms

Abstract

In this paper we evaluate the usefulness of seeding genetic algorithms (GAs) from a case-base. This is motivated by the expectation that the seeding will speed up the GA by starting the search in promising regions of the search space. We evaluate this case-based seeding on popular GA solutions to the Travelling Salesman Problem (TSP) and the Job-Shop Scheduling Problem (JSSP). We find that seeding works very well with the TSP but poorly with the JSSP. We have discovered that this discrepancy may be predicted by examining the correlation of parent and offspring fitness. In the TSP this correlation is strong and the seeding works well, the converse is true for the JSSP. This provides a simple mechanism to evaluate the potential for seeding in genetic algorithms in general.