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

A discrete state transition algorithm for traveling salesman problem

本文提出了一种求解旅行商问题的离散状态转移算法,设计了交换、平移、对称等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.