通信学报 ›› 2018, Vol. 39 ›› Issue (12): 18-29.doi: 10.11959/j.issn.1000-436x.2018284

• 学术论文 • 上一篇    下一篇

改进蜂群算法求解大规模着色瓶颈旅行商问题

董文永,董学士(),王豫峰   

  1. 武汉大学计算机学院,湖北 武汉 430072
  • 修回日期:2018-06-24 出版日期:2018-12-01 发布日期:2019-01-21
  • 作者简介:董文永(1973?),男,河南南阳人,博士,武汉大学教授、博士生导师,主要研究方向为演化计算、智能仿真优化、系统控制、机器学习。|董学士(1985?),男,山东日照人,武汉大学博士生,主要研究方向为智能计算、仿真优化。|王豫峰(1982?),男,河南南阳人,武汉大学博士生,主要研究方向为演化计算、仿真优化。
  • 基金资助:
    国家自然科学基金资助项目(No.61672024);国家自然科学基金资助项目(No.61170305)

Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem

Wenyong DONG,Xueshi DONG(),Yufeng WANG   

  1. Computer School, Wuhan University, Wuhan 430072, China
  • Revised:2018-06-24 Online:2018-12-01 Published:2019-01-21
  • Supported by:
    The National Natural Science Foundation of China(No.61672024);The National Natural Science Foundation of China(No.61170305)

摘要:

在智能交通、多任务协作等领域,用着色瓶颈旅行商问题(CBTSP,colored bottleneck traveling salesman problem)所构建模型尺度易趋向于大规模,因此有必要研究大规模CBTSP及其求解算法。本文将一种改进蜂群算法(IABC,improved artificial bee colony algorithm)应用于求解大规模CBTSP。IABC首先运用m-tour编码方法生成问题的解,然后使用产生邻近解(GNS,generate neighboring solution)优化蜂群算法求解该问题,GNS通过采用删除和重插入操作来产生新的解,并在该过程中实现对已有解的优化。实验表明 IABC 求解大规模 CBTSP 问题的求解质量优于其他对比算法。

关键词: 改进蜂群算法, 着色瓶颈旅行商问题, 着色旅行商问题, 瓶颈旅行商问题, 大规模优化

Abstract:

In the fields such as intelligent transport and multiple tasks cooperation, the model scale constructed by colored bottleneck traveling salesman problem (CBTSP) tends to large scale, and therefore it is necessary to study the large scale CBTSP and its algorithms. An improved artificial bee colony algorithm (IABC) was applied to solve the large scale CBTSP. IABC employed generating neighboring solution (GNS) to improve artificial bee colony algorithm for CBTSP. GNS generated new solution by deletion and reinsertion operations, during this process, and it can optimized the existed solution for this problem. Experiments show that IABC can demonstrate better solution quality than other compared algorithms for large scale CBTSP.

Key words: improved artificial bee colony algorithm, colored bottleneck traveling salesman problem, colored traveling salesman problem, bottleneck traveling salesman problem, large scale optimization

中图分类号: 

No Suggested Reading articles found!