A Sequence Based Genetic Algorithm with Local （基于遗传算法与当地的一个序列）.pdfVIP

A Sequence Based Genetic Algorithm with Local Search for the Travelling Salesman Problem Shakeel Arshad, Shengxiang Yang, and Changhe Li Department of Computer Science University of Leicester Leicester LE1 7RH, UK { saa29, s.yang, ch160 } @mcs.le.ac.uk Abstract TSPs can be classified into different classes according to the properties of the cost matrix. The standard Genetic Algorithm often A TSP is called symmetric if we have cij = suffers from slow convergence for solv- cji ,∀i, j ; otherwise, it is referred to as asymmet- ing combinatorial optimization problems. ric. If the cities of a TSP lie in a metric space, In this study, we present a sequence i.e., satisfying the triangle inequality, the TSP is based genetic algorithm (SBGA) for the referred to as a metric TSP. Assuming that a city symmetric travelling salesman problem i in a tour is marked by its position (x , y ) in the (TSP). In our proposed method, a set i i plane, and the cost matrix C contains the Eu- of sequences are extracted from the best