利用粒子滤波求解旅行商问题

Application of particle filter algorithm in traveling salesman problem

针对现有优化算法求解旅行商问题(TSP)时容易陷入局部极值的缺点,提出一种基于粒子滤波的优化搜索算法,该算法将TSP最优路径的搜索过程看成是一个动态时变系统。阐述了利用粒子滤波求解TSP最优路径的基本思想,给出了该方法的具体实现步骤。为了增强算法跳出局部极值的能力,在采样过程中引入了遗传算法的交叉和变异操作来丰富样本的多样性。最后为了验证新算法的有效性,进行了仿真实验,结果表明基于粒子滤波的优化算法能够找到比其他优化算法更好的解。

The existing optimization algorithm for solving the Traveling Salesman Problem （TSP） easily falls into local extremum. To overcome this shortcoming, a new optimization method based on the particle filter, which regarded the searching process of the best route of TSP as a dynamic time-varying system, was brought forward. The basic ideas using particle filter principle to search the best route of TSP were enunciated, and its implementation procedures were given. In order to reduce the possibility of sinking into local extreme, the crossover and mutation operator of Genetic Algorithm （GA） was introduced into the new optimization algorithm to enhance the variety of particles in the sampling process. Finally, the simulation experiments were performed to prove the validity of the new method. The new optimization method based on particle filter can find better solutions than those of other optimization algorithms.