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

董文永; 董学士; 王豫峰

doi:10.11959/j.issn.1000-436x.2018284

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 改进蜂群算法求解大规模着色瓶颈旅行商问题
- Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem
- 通信学报 2018年39卷第12期页码：18-29
- 作者机构：
  
  武汉大学计算机学院，湖北武汉 430072
- 作者简介：
  
  [ "董文永（1973−），男，河南南阳人，博士，武汉大学教授、博士生导师，主要研究方向为演化计算、智能仿真优化、系统控制、机器学习。" ]
  [ "董学士（1985−），男，山东日照人，武汉大学博士生，主要研究方向为智能计算、仿真优化。" ]
  [ "王豫峰（1982−），男，河南南阳人，武汉大学博士生，主要研究方向为演化计算、仿真优化。" ]
- 基金信息：
  
  国家自然科学基金资助项目(No.61672024);国家自然科学基金资助项目(No.61170305)
- DOI：10.11959/j.issn.1000-436x.2018284
  中图分类号： TP301
- 网络出版日期：2018-12，
  
  纸质出版日期：2018-12-25
- 稿件说明：
移动端阅览
董文永, 董学士, 王豫峰. 改进蜂群算法求解大规模着色瓶颈旅行商问题[J]. 通信学报, 2018,39(12):18-29.

Wenyong DONG, Xueshi DONG, Yufeng WANG. Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem[J]. Journal on communications, 2018, 39(12): 18-29.
董文永, 董学士, 王豫峰. 改进蜂群算法求解大规模着色瓶颈旅行商问题[J]. 通信学报, 2018,39(12):18-29. DOI： 10.11959/j.issn.1000-436x.2018284.

Wenyong DONG, Xueshi DONG, Yufeng WANG. Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem[J]. Journal on communications, 2018, 39(12): 18-29. DOI： 10.11959/j.issn.1000-436x.2018284.

摘要

在智能交通、多任务协作等领域，用着色瓶颈旅行商问题(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.

关键词

Keywords

references

LI J , ZHOU M C , SUN Q , et al . Colored traveling salesman problem [J ] . IEEE Transactions on Cybernetics , 2015 , 45 ( 11 ): 2390 - 2401 .

LI J , QIRU S , ZHOU M C , et al . A new multiple traveling salesman problem and its genetic algorithm-based solution [C ] // The 2013 IEEE International Conference on Systems Man and Cybernetics , 2013 : 1 - 6 .

MENG X H , LI J , DAI X Z , et al . Variable neighborhood search for a colored traveling salesman problem [J ] . IEEE Transactions on Intelligent Transport Systems , 2018 , 19 ( 4 ): 1018 - 1025 .

DONG X S , DONG W Y , CAI Y L . Ant colony optimization for colored traveling salesman problem by multi-task learning [J ] . IET Intelligent Transport Systems , 2018 , 12 ( 8 ): 774 - 782 .

KAO M Y , SANGHI M . An approximation algorithm for a bottleneck traveling salesman problem [J ] . Journal of Discrete Algorithms , 2009 , 7 ( 3 ): 315 - 326 .

LARUSIC J , PUNNEN A P . The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis [J ] . Computer & Operation Research , 2014 , 43 : 20 - 35 .

AHMED Z H . A hybrid genetic algorithm for the bottleneck traveling salesman problem [J ] . ACM Transactions on Embedded Computing Systems , 2013 , 12 ( 1 ): 9:1 - 9:10 .

VAIRAKTARAKIS G . VAIRAKTARAKIS L . On Gilmore-Gomorys open question for the bottleneck TSP [J ] . Operations Research Letters , 2003 , 31 : 483 - 491 .

KABADI S N . Polynomial solvable cases of the TSP [M ] . Traveling Salesman Problem and its Variants , 2007 , 12 : 489 - 583 .

董学士，董文永，蔡永乐 . 混合算法求解着色瓶颈旅行商问题 [J ] . 计算机研究与发展， 2018 , 55 ( 11 ): 2372 - 2385 .

DONG X S , DONG W Y , CAI Y L . Hybrid algorithm for colored bot-tleneck traveling salesman problem [J ] . Journal of Computer Research and Development , 2018 , 55 ( 11 ): 2372 - 2385 .

CHENG R , JIN Y C . A competitive swarm optimizer for large scale optimization [J ] . IEEE Transaction on Cybernetics , 2015 , 45 ( 2 ): 191 - 204 .

YE B L , WU W M , LI L X , et al . A hierarchical model predictive control approach for signal splits optimization in large-scale urban road networks [J ] . IEEE Transaction on Intelligent Transport Systems , 2016 , 17 ( 8 ): 2182 - 2192 .

OMIDVAR M N , YANG M , MEI Y , et al . DG2: a faster and more accurate differential grouping for large-scale black-box optimization [J ] . IEEE Transaction on Evolutionary Computation , 2017 , 21 ( 6 ): 929 - 942 .

ZHANG X Y , TIAN Y , CHENG R , et al . A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization [J ] . IEEE Transaction on Evolutionary Computation , 2018 , 22 ( 1 ): 97 - 112 .

HU X M , HE F L , CHEN W N , et al . Cooperation coevolution with fast interdependency identification for large scale optimization [J ] . Information Science , 2017 , 381 : 142 - 160 .

GAO W F , HUANG L L , LIU S Y , et al . Artificial bee colony algorithm based on information learning [J ] . IEEE Transactions on Cybernetics , 2015 , 45 ( 12 ): 2827 - 2838 .

KARABOGA D . An idea based on honey bee swarm for numerical optimization [R ] . Computers Engineering Department, Engineering Faculty, Erciyes University , 2015 .

LI J Q , PAN Q K , DUAN P Y . An improved artificial bee colony algorithm for solving hybrid flexible flowshop with dynamic operation skipping [J ] . IEEE Transactions on Cybernetics , 2016 , 46 ( 6 ): 1311 - 1323 .

MANUEL L , CARLOS G M , FRANCISCO , , et al . Optimizing network attacks by artificial bee colony [J ] . Information Sciences , 2017 , 377 : 30 - 50 .

VENKATESH P , SINGH A . Two metaheuristic approaches for the multiple traveling salesperson problem [J ] . Applied Soft Computing , 2015 , 26 : 74 - 89 .

ZHANG H G , ZHOU J . Dynamic multicale region search algorithm using vitality selection for traveling salesman problem [J ] . Expert Systems with Applications , 2016 , 60 : 81 - 95 .

浏览量

819

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据