An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP

Yong Deng, Yang Liu and Deyun Zhou

Mathematical Problems in Engineering, 2015, vol. 2015, 1-6

Abstract:

A new initial population strategy has been developed to improve the genetic algorithm for solving the well-known combinatorial optimization problem, traveling salesman problem. Based on the k -means algorithm, we propose a strategy to restructure the traveling route by reconnecting each cluster. The clusters, which randomly disconnect a link to connect its neighbors, have been ranked in advance according to the distance among cluster centers, so that the initial population can be composed of the random traveling routes. This process is -means initial population strategy. To test the performance of our strategy, a series of experiments on 14 different TSP examples selected from TSPLIB have been carried out. The results show that KIP can decrease best error value of random initial population strategy and greedy initial population strategy with the ratio of approximately between 29.15% and 37.87%, average error value between 25.16% and 34.39% in the same running time.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2015/212794.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2015/212794.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:212794

DOI: 10.1155/2015/212794

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().