A Strategy Adaptive Genetic Algorithm for Solving the Travelling Salesman Problem

摘要

This paper presents a Strategy adaptive Genetic Algorithm to address a wide range of sequencing discrete optimization problems. As for the performance analysis, we have applied our algorithm on the Travelling Salesman Problem(TSP).Here we present an innovative crossover scheme which selects a crossover strategy from a consortium of three such crossover strategies, the choice being decided partly by the ability of the strategy to produce fitter off springs and partly by chance. We have maintained an account of each such strategy in producing fit off springs by adopting a model similar to The Ant Colony Optimization. We also propose a new variant of the Order Crossover which retains some of the best edges during the inheritance process. Along with conventional mutation methods we have developed a greedy inversion mutation scheme which is incorporated only if the operation leads to a more economical traversal. This algorithm provides better results compared to other heuristics, which is evident from the experimental results and their comparisons with those obtained using other algorithms.