一种求解旅行商问题的信息传播算法

An Information Propagation Algorithm for Solving Traveling Salesman Problem

针对旅行商问题求解精度较差、容易陷入局部最优等缺点,提出一种新的求解旅行商问题的信息传播算法。根据旅行商问题的特征,将线性方程嵌入信息传播算法方程中得到旅行商问题的势函数,进而将其转换为因子图,在因子图上利用信息传播算法的迭代方程进行迭代计算。在迭代过程中选择边际信念的最小值,从而得到旅行商问题的初始解,在算法达到设定的迭代次数后,引入局部搜索算法进行求解。在若干数据集上的实验结果表明,新算法能够有效求解旅行商问题。

Aiming at the shortcomings of traveling salesman problem such as poor accuracy and easy to falling into local optimum,a new information propagation algorithm for solving traveling salesman problem was proposed.According to the characteristics of traveling salesman problem,the linear equation was embedded into the information dissemination algorithm equation to obtain the potential function,which was then converted into factor graph,and the iterative equation of the information dissemination algorithm was used on the factor graph.In the process of iteration,the minimum value of marginal belief was selected to obtain the initial solution of travelling salesman problem.After the algorithm reached the set number of iterations,the local search algorithm was introduced to solve the problem.Experimental results on several data sets showed that the new algorithm could effectively solve the traveling salesman problem.