The Simulated Annealing Algorithm Based on Multi-Populations Application of TSP

Abstract:

Traveling salesman problem (TSP) is not only a combinatorial optimization problem but also a classical NP problem, which has has high application value. Simulated annealing algorithm is especially effective for solving TSP problems. Based on the deficiency of simulated annealing algorithm on avoiding local minima, this paper has improved the traditional simulated annealing algorithm, proposed simulated annealing algorithm of multiple populations to solve the classical TSP problem. This algorithm has introduced collateral mechanism of multiple populations and increased the initial populations so that it can include more solution set, avoid local minima, thus it has improved the optimization efficiency.This algorithm has very high use value in solving the TSP problem. Keywords: Traveling salesman problem, NP (Non-deterministic Polynomial) problem, simulated annealing algorithm, multiple populations

• Periodical: Applied Mechanics and Materials (Volumes 457-458)
• Pages: 1037-1041
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.457-458.1037
• Online since: October 2013
• Authors: Qin Hui Gong
• Keywords: Multiple Populations, NP (Non-Deterministic Polynomial) Problem, Simulated Annealing Algorithm, Traveling Salesman Problem

References

[1] Hui Miao, Tao Yang. The improved simulated annealing algorithm of TSP. Micro computer information, 2007, 23(11): 241.

[2] Huiling, Li. Application on GA based on SA for TSP[J]. Heat treatment technology and equipment, 2007, 28(6): 51-55.

[3] Metropolis N, Rosenbluth A. Rosenbluth Metal, Equation of state calculations by fast computing machines[J]. Journal of Chemical Physics, 1953, 56(21): 1087-1092.

DOI: 10.1063/1.1699114

[4] Ingber L, Rosen B. Genetic algorithms and very fast simulated annealing: A comparison[J]. Mathematical Computer Modeling. 1992, 16(11): 87-100.

DOI: 10.1016/0895-7177(92)90108-w

[5] Kirpatrick S, Jr Gelatt C D, Vecchi M P. Optinfization by simulated annealing[J]. Science, 1983, 220(11): 650—671.

[6] R. A. Rutenbar. Simulated Annealing Algorithm: An Overview [ J ]. IEEE CIRCU ITS AND DEVICES MAGAZINE, 1989: 19～26.

[7] Haojie Cao. Study on the simulated annealing algorithm for solving the TSP problem [J]. Journal of xiaogan university, 2007, 27(6): 65-67.

[8] Yanping Qiao, Jun Zhang. Traveling salesman problem solving based on improved genetic simulated annealing algorithm [J]. Computer simulation, 2009, 26(5): 205-208.

[9] Lixia Han, Yuping Wang. A Novel Genetic Algorithm for Traveling Salesman Problem[J]. Systems engineering theory & practice, 2007, 12: 145-150.