计算机应用 ›› 2012, Vol. 32 ›› Issue (08): 2219-2222.DOI: 10.3724/SP.J.1087.2012.02219

• 人工智能 • 上一篇    下一篇

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

吴新杰,黄国兴   

  1. 辽宁大学 物理学院,沈阳 110036
  • 收稿日期:2012-02-22 修回日期:2012-03-30 发布日期:2012-08-28 出版日期:2012-08-01
  • 通讯作者: 吴新杰
  • 作者简介:吴新杰(1964-),男,辽宁沈阳人,教授,博士,主要研究方向:层析成像、智能优化算法、盲源信号分离;
    黄国兴(1986-),男,江西上高人,硕士研究生,主要研究方向:智能优化算法。
  • 基金资助:
    辽宁省自然科学基金资助项目(20102082)

Application of particle filter algorithm in traveling salesman problem

WU Xin-jie,HUANG Guo-xing   

  1. School of Physics, Liaoning University, Shenyang Liaoning 110036,China
  • Received:2012-02-22 Revised:2012-03-30 Online:2012-08-28 Published:2012-08-01
  • Contact: WU Xin-jie

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

关键词: 粒子滤波, 旅行商问题, 局部极值, 优化算法, 遗传算法

Abstract: 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.

Key words: particle filter, Traveling Salesman Problem (TSP), local extremum, optimization algorithm, Genetic Algorithm (GA)

中图分类号: