A sequential similarity metric for case injected genetic algorithms applied to TSPs

Abstract

We present and use a sequence similarity metric to solve sets of similar problems with case injected genetic algorithms. Rather than starting anew on each problem, we periodically inject a genetic algorithm's population with appropriate intermediate solutions to similar, previously solved problems. Using simple syntactic similarity measures, our experimental results from optimizing a series of traveling salesman problems demonstrates the robustness of our approach. Results show that compared to a randomly initialized genetic algorithm, our system learns to take decreasing time to provide better solutions to a new problem as it gains experience from solving other similar problems. 1 INTRODUCTION Problems seldom exist in isolation. Any useful 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 operati...