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

作     者：乔屾 吕志民 张楠 QIAO Shen;LYU Zhimin;ZHANG Nan

作者机构：北京科技大学工程技术研究院北京100083 北京科技大学钢铁共性技术协同创新中心北京100083 

基　　金：国家自然科学基金资助项目(51274043) 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2017年第37卷第10期

页      码：2767-2772页

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

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.11772/j.issn.1001-9081.2017.10.2767

馆 藏 号：203274314...