计算机工程 ›› 2010, Vol. 36 ›› Issue (11): 183-184,187.doi: 10.3969/j.issn.1000-3428.2010.11.066

• 人工智能及识别技术 • 上一篇    下一篇

基于混合粒子群优化算法的旅行商问题求解

俞靓亮,王万良,介 婧   

  1. (浙江工业大学软件学院,杭州 310023)
  • 出版日期:2010-06-05 发布日期:2010-06-05
  • 作者简介:俞靓亮(1985-),男,硕士研究生,主研方向:生产计划与调度;王万良,教授、博士、博士生导师;介 婧,博士后
  • 基金项目:

    国家“863”计划基金资助项目“流程工业企业生产过程的智能计划与动态优化调度技术”(2007AA04Z155);国家自然科学基金资助项目“面向节能减排的流程工业生产过程不确定动态调度方法及其应用”(60874074)

Solution of Travel Salesman Problem Based on Hybrid Particle Swarm Optimization Algorithm

YU Liang-liang, WANG Wan-liang, JIE Jing   

  1. (Software College, Zhejiang University of Technology, Hangzhou 310023)
  • Online:2010-06-05 Published:2010-06-05

摘要:

针对旅行商问题提出一种混合粒子群优化算法。为了增强算法的局部搜索能力,在粒子群优化算法中加入倒置、对换等局部搜索算法。利用遗传算法全局搜索能力强的特点对用粒子群优化算法求到的解进行优化,对全局最优路径通过消除交叉路径进行优化,以进一步提高混合算法的性能。仿真结果表明,中小规模旅行商问题能够在较少的代数内收敛到较满意解。

关键词: 旅行商问题, 粒子群优化算法, 遗传算法, 局部搜索

Abstract:

This paper researches a hybrid Particle Swarm Optimization(PSO) algorithm for solving travel salesman problem. In order to improve the capability of local searching, some local searching algorithms such as inversion and swapping are added. It takes advantage of strong global searching capability of Genetic Algorithm(GA) to further optimize the results got from PSO algorithm, which can further improve the performance of the hybrid algorithm. Besides, it adds an optimization to eliminate cross path of global optimum solution. Simulation result shows this hybrid algorithm can converge to a satisfactory result within a few generations for middle and small scale travel salesman problem.

Key words: travel salesman problem, Particle Swarm Optimization(PSO) algorithm, Genetic Algorithm(GA), local searching

中图分类号: