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

• 作者: 乔屾 吕志民 张楠
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 粒子群优化算法 汉明距离 随机贪婪规则 2-opt算子 3-opt算子 旅行商问题
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 先进计算
• 页码范围: 2767-2772
• 页数: 6页
• 分类号: TP301.6
• 字数: 6092字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017.10.2767

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吕志民	北京科技大学钢铁共性技术协同创新中心	32	397	9.0	19.0
2	张楠	北京科技大学工程技术研究院	8	54	4.0	7.0
3	乔屾	北京科技大学工程技术研究院	1	9	1.0	1.0