Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (10): 2767-2772.DOI: 10.11772/j.issn.1001-9081.2017.10.2767

Previous Articles     Next Articles

Improved particle swarm optimization algorithm based on Hamming distance for traveling salesman problem

QIAO Shen1, LYU Zhimin2, ZHANG Nan1   

  1. 1. Institute of Engineering Technology, University of Science and Technology Beijing, Beijing 100083, China;
    2. Collaborative Innovation Center of Steel Technology, University of Science and Technology Beijing, Beijing 100083, China
  • Received:2017-05-11 Revised:2017-08-01 Online:2017-10-10 Published:2017-10-16
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51274043).

基于汉明距离的改进粒子群算法求解旅行商问题

乔屾1, 吕志民2, 张楠1   

  1. 1. 北京科技大学 工程技术研究院, 北京 100083;
    2. 北京科技大学 钢铁共性技术协同创新中心, 北京, 100083
  • 通讯作者: 乔屾(1985-),男,河北保定人,硕士研究生,主要研究方向:智能算法、生产计划与调度,E-mail:xiaoqiao_0412@126.com
  • 作者简介:乔屾(1985-),男,河北保定人,硕士研究生,主要研究方向:智能算法、生产计划与调度;吕志民(1971-),男,河北邯郸人,研究员,博士生导师,博士,主要研究方向:工业大数据、智能制造、生产计划与调度;张楠(1990-),女(满族),吉林四平人,博士研究生,主要研究方向:智能算法、生产计划与调度.
  • 基金资助:
    国家自然科学基金资助项目(51274043)。

Abstract: An improved Particle Swarm Optimization (PSO) algorithm based on Hamming distance was proposed to solve the discrete problems. The basic idea and process of traditional PSO was retained, and a new speed representation based on Hamming distance was defined. Meanwhile, in order to make the algorithm be more efficient and avoid the iterative process falling into the local optimum, new operators named 2-opt and 3-opt were designed, and the random greedy rule was also used to improve the quality of the solution and speed up the convergence. At the later period of the algorithm, in order to increase the global search ability of the particles in the whole solution space, a part of particles was regenerated to re-explore the solution space. Finally, a number of TSP standard examples were used to verify the effectiveness of the proposed algorithm. The experimental results show that the proposed algorithm can find the historical optimal solution for small scale TSP; for large-scale TSP, for example, the city number is more than 100, satisfactory solutions can also be found, and the deviations between the known and the optimal solutions are small, usually within 5%.

Key words: Particle Swarm Optimization (PSO) algorithm, Hamming distance, random greedy rule, 2-opt operator, 3-opt operator, Traveling Salesman Problem (TSP)

摘要: 针对传统粒子群算法不适合求解离散型问题,提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程,并基于汉明距离为粒子定义了一种新型的速度表示。同时,为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出,设计了2-opt和3-opt算子,结合随机贪婪规则,使求解质量更高、收敛更快。在算法后期,为了提高粒子在整体解空间中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性,采用了众多旅行商问题(TSP)标准算例进行测试。实验结果表明,对于小规模TSP,该算法可以找到历史最优解;对于大规模TSP,如城市数在100以上的问题,也可以找到满意解,与已知最优解之间偏差度较小,通常在5%以内。

关键词: 粒子群优化算法, 汉明距离, 随机贪婪规则, 2-opt算子, 3-opt算子, 旅行商问题

CLC Number: