Performance Analysis of a New Genetic Crossover for the Traveling Salesman Problem(Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
In this paper, we propose an efficient and powerful crossover operator in the genetic algorithm for solving the traveling salesman problem(TSP). Our proposed crossover is called the complete subtour exchange crossover(CSEX), and inherits as many good subtours as possible because they are worth preserving for descendants. Before generating the descendants, a prerequisite for the CSEX is that it enumerates all common subtours, which consist of the same set in a pair of subtours on the given two tours of n cities. An algorithm to enumerate all common subtours in the CSEX consumes only O(n) time. In a fundamental experiment, we show the experimental number and length of the common subtours for two randomly generated tours with 5 to 500 thousand elements. In addition, we give the practical behavior of the CSEX and compare the CSEX with a hopeful crossover operator using the benchmark instances for the TSP. Moreover, in another experiment of parallel computing, in order to analyze the performance of the CSEX, we compare the CESX with hopeful crossovers for 25 benchmarks(48-2392 city)using a parallel supercomputer, Paragon. From these results, the CSEX shows an extremely bright performance.
社団法人電子情報通信学会の論文
1998-05-25