求解旅行商问题的改进蚁群算法研究

计算机工程与科学

• 论文 • 上一篇

求解旅行商问题的改进蚁群算法研究

张于贤，丁修坤，薛殿春，王晓婷

（桂林电子科技大学商学院，广西桂林 541004）

收稿日期:2015-11-04 修回日期:2016-04-29 出版日期:2017-08-25 发布日期:2017-08-25
基金资助:
广西高等学校科技研究重点资助项目（SK13ZD016）；广西研究生科研创新项目（YCSW2015155，YCSW2012066）

An improved ant colony algorithm

for traveling salesman problem

ZHANG Yu-xian,DING Xiu-kun,XUE Dian-chun，WANG Xiao-ting

(School of Business,Guilin University of Electronic Technology,Guilin 541004，China)

Received:2015-11-04 Revised:2016-04-29 Online:2017-08-25 Published:2017-08-25

摘要/Abstract

摘要：

针对蚁群算法收敛速度慢的问题，对蚁群算法信息素更新规则进行研究，提出一个基于迭代思想的信息素更新规则。对信息残留因子进行实验，确定在新的信息素更新规则下信息素挥发系数的最佳合理值。最后针对eil51问题和dantzig42问题两个例子的仿真实验对比基本蚁群算法。实验结果表明，改进的蚁群算法在收敛性和求得最优解方面都明显优于基本蚁群算法和其它人工智能算法。

关键词: TSP问题, 蚁群算法, 信息素

Abstract:

In order to solve the slow convergence speed problem of the ant colony algorithm, we study ant colony algorithm pheromone updating rules and propose a pheromone updating rule based on the thought of iteration. We identify the best reasonable value of the pheromone volatilization coefficient under the new pheromone updating rules through information residual factor experiments. Finally, experimental results on the two examples of eil51 and dantzig42 problems show that the improved ant colony algorithm outperforms the traditional ant colony algorithm and other artificial intelligence algorithms in terms of optimal solution and convergence.

Key words: TSP problem, ant colony algorithm, pheromone

张于贤，丁修坤，薛殿春，王晓婷. 求解旅行商问题的改进蚁群算法研究[J]. 计算机工程与科学.

ZHANG Yu-xian,DING Xiu-kun,XUE Dian-chun，WANG Xiao-ting.

An improved ant colony algorithm

for traveling salesman problem

[J]. Computer Engineering & Science.

[1]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(01): 85-94.
[2]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(05): 910-915.
[3]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[4]	胡平志, 李泽滔. 基于改进蚁群算法的四足机器人步态规划[J]. 计算机工程与科学, 2021, 43(12): 2253-2262.
[5]	宋阿妮, 包贤哲. 精英扩散蚁群优化算法求解运输无人机三维路径规划[J]. 计算机工程与科学, 2021, 43(10): 1891-1900.
[6]	吴俊斌, 吴晟, 吴兴蛟. 一种用于求解TSP问题的随机最佳插入烟花算法[J]. 计算机工程与科学, 2020, 42(11): 2080-2087.
[7]	马贵平, 潘峰. 基于改进蚁群算法的物流运输路径研究[J]. 计算机工程与科学, 2020, 42(03): 523-528.
[8]	曹新亮, 王智文, 冯晶, 查敏, 王宇航. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学, 2020, 42(03): 564-570.
[9]	张卫祥，齐玉华，魏波，张敏，窦朝晖. 基于蚁群算法的测试用例优先排序[J]. 计算机工程与科学, 2020, 42(02): 241-249.
[10]	杨衡亮. 深化计算机课程教学改革,提高军校大学生信息素养[J]. 计算机工程与科学, 2019, 41(增刊S1): 21-25.
[11]	喻小惠1，张晶1,2，陶涛3，龚力波4，黄云明1，傅铁威1. 基于蚁群策略的无线传感器网络能耗均衡分簇算法[J]. 计算机工程与科学, 2019, 41(07): 1197-1202.
[12]	郑延斌1,2，王林林1，席鹏雪1，樊文鑫1，韩梦云1. 动态环境下改进蚁群算法的多Agent路径规划[J]. 计算机工程与科学, 2019, 41(06): 1078-1085.
[13]	吴尚智1，张文超2，佘志用1，张霞1，段超1. 利用蚁群优化算法的粗糙集属性约简方法[J]. 计算机工程与科学, 2019, 41(03): 538-544.
[14]	覃远年，梁仲华. 蚁群算法研究与应用的新进展[J]. 计算机工程与科学, 2019, 41(01): 173-184.
[15]	张瑾1，毕国通2，李丽丽1. 一种求解TSP问题的离散蝙蝠算法[J]. 计算机工程与科学, 2018, 40(11): 2085-2091.

求解旅行商问题的改进蚁群算法研究

An improved ant colony algorithm

for traveling salesman problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价