REDUCING INITIAL EDGE SET OF TRAVELING SALESMAN PROBLEMS
Traveling Salesman Problem is one of typical NP-hard problems of combinatorial optimization.It is because of the complexity of TSP that accurate computing algorithms couldnt find a global optimal solution in more short time or at all.By analyzing the relationship between global optimal solutions and local optimal solutions computed using heuristic algorithms for TSP, it is found that union set of edge sets of multi high-qualify local optimal solutions can include all of edges of a global optimal solution.The method, reducing initial edge set for TSP, is put forward based on probability statistic principle.The search space of original problem is cut down greatly by utilizing new method; the quantity of new initial edge set is about double times of problem scale.Accurate computing algorithms can find global optimal solution for small scale TSP based on new edge sets, and efficiency of stochastic search algorithms is improved greatly.
Traveling salesman problem Initial edge set Reducing Stochastic algorithms Accurate computation Intelligence algorithms
DONG WANG XIANG-BIN WU XIAN-CHENG MAO WEN-JIAN LIU
College of Geosciences and Environmental Engineering, Central South University, Changsha 410083, Chi College of Geosciences and Environmental Engineering, Central South University, Changsha 410083, Chi
国际会议
2007 International Conference on Machine Learning and Cybernetics(IEEE第六届机器学习与控制论国际会议)
香港
英文
2333-2338
2007-08-19（万方平台首次上网日期，不代表论文的发表时间）