An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP

Abstract EN

A new initial population strategy has been developedto improve the genetic algorithm for solving the well-known combinatorialoptimization problem, traveling salesman problem.

Based on the k-meansalgorithm, we propose a strategy to restructure the traveling route by reconnectingeach cluster.

The clusters, which randomly disconnect a link to connectits neighbors, have been ranked in advance according to the distance amongcluster centers, so that the initial population can be composed of the randomtraveling routes.

This process is k -means initial population strategy.

To test the performance of our strategy, a series of experiments on 14 differentTSP examples selected from TSPLIB have been carried out.

The results showthat KIP can decrease best error value of random initial population strategyand greedy initial population strategy with the ratio of approximately between29.15% and 37.87%, average error value between 25.16% and 34.39% in thesame running time.