一种求解旅行商问题的离散状态转移算法(英文)  

A discrete state transition algorithm for traveling salesman problem

作　　者：阳春华[1] 唐小林[1] 周晓君[1,2] 桂卫华[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083 [2]巴拉瑞特大学科学与信息技术及工程学院,澳大利亚维多利亚巴拉瑞特3350

出　　处：《控制理论与应用》2013年第8期1040-1046,共7页Control Theory & Applications

基　　金：supported by the the National Science Found for Distinguished Young Scholars of China(No.61025015);the China Scholarship Council

摘　　要：本文提出了一种求解旅行商问题的离散状态转移算法,设计了交换、平移、对称等3种转移算子,讨论了算法的收敛性和时间复杂度等问题,研究了参数对算法的影响.实验结果表明,与模拟退火算法及蚁群算法等经典组合优化算法相比,该算法具有耗时短、寻优能力强等优点,这也表明了状态转移算法的适应性很好.A discrete version of state transition algorithm is proposed to solve the traveling salesman problem. Three special operators named swap, shift and symmetry transformations are presented for discrete optimization problem. Convergence analysis and time complexity of the algorithm are also considered. To make the algorithm efficient, a parametric study is investigated. Experiments are carried out to test its performance, and comparisons with simulated annealing and ant colony optimization have demonstrated the effectiveness of the proposed algorithm. The results also show that the discrete state transition algorithm consumes much less time and has better search ability than other traditional combinatorial optimization methods, indicating that state transition algorithm has strong adaptability.

关 键 词：状态转移算法 旅行商问题 参数学习 组合优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]