Application of an Improved Genetic Algorithm with the Search Space Compression in TSP

Abstract:

The Traveling Salesman Problem is a combinatorial optimization problem, the problem has been shown to belong to the NPC problem, the possible solution of Traveling Salesman Problem and the scale of the cities have the exponential relation, so the more bigger of the scale. In this paper, improve the search process of the genetic algorithm by introducing the idea is to compress the search space. The simulation results show that for solving the TSP, the algorithm can quickly obtain multiple high-quality solutions. It can reduce the blindness of random search and accelerate convergence of the algorithm.

• Periodical: Advanced Materials Research (Volumes 765-767)
• Pages: 687-689
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.765-767.687
• Online since: September 2013
• Authors: Yi Song, Ni Ni Wei
• Keywords: Genetic Algorithm (GA), Incomplete Evolution, Search Space Compression, TSP

References

[1] M. Li, L. Wu, K .B. Zhang, Comparative study of several algorithms for traveling salesman problem, Journal of Chongqing University Of Posts And Telecommunications. No 5, (2008), pp.124-126.

[2] Y .C. Gao, L.M. Liu, X. Wei, Delomposing Algorithm Bsed on Space Partition, Journal of System Simulation. No 16, (2009), pp.113-117.

[3] S .Y. Zeng, L .S. Kang, L .X. Ding, A new method of evolutionary algorithm for mixed-integer Nonlinear optimization Problem, Journal of Wuhan University (Natural Science Edition), Vol. 46, No. 5, (2000) , pp.554-558.

[4] J. Zhang,Y. Liu, F. L . Lu, Parallel Research and Implementation of Ant Colony Algorithm to Solve Problem of TSP, Journal of Computer Technology and Development, Vol. 21, No. 5, (2011), pp.72-74.

[5] L .Y. Jia, C.H. ZHOU , Strategy for Generic Algorithms to Slove TSP Problem Quickly, Journal of Computer Engineering, Vol. 34, No. 5, (2008), pp.174-175.