引入梯度下降的蚁群算法求解多约束服务质量路由

doi:10.11772/j.issn.1001-9081.2017.03.722

计算机应用 ›› 2017, Vol. 37 ›› Issue (3): 722-729.DOI: 10.11772/j.issn.1001-9081.2017.03.722

引入梯度下降的蚁群算法求解多约束服务质量路由

梁本来¹, 杨忠明², 秦勇³, 蔡昭权⁴

1. 中山职业技术学院信息工程学院, 广东中山 528404;
2. 广东科学技术职业学院计算机工程技术学院, 广东珠海 519090;
3. 东莞理工大学计算机学院, 广东东莞 523808;
4. 惠州学院教育技术中心, 广东惠州 516007

收稿日期:2016-08-19 修回日期:2016-10-24 发布日期:2017-03-22 出版日期:2017-03-10
通讯作者: 梁本来
作者简介:梁本来(1983-),男,山东济宁人,讲师,硕士,主要研究方向:信息安全、网络路由;杨忠明(1980-),男,广东茂名人,副教授,硕士,CCF会员,主要研究方向:信息安全、智能算法;秦勇(1970-),男,湖南邵阳人,教授,博士,主要研究方向:网络路由优化;蔡昭权(1970-),男,广东陆丰人,教授,硕士,CCF会员,主要研究方向:计算机网络技术。
基金资助:
国家自然科学基金资助项目（61170193）；广东省工业高新技术领域科技计划项目（2013B010401036）；广东省自然科学基金资助项目（s2013010013432）；中山市社会公益科技研究项目（2016B2142）。

Ant colony algorithm with gradient descent for solving multi-constrained quality of service routing

LIANG Benlai¹, YANG Zhongming², QIN Yong³, CAI Zhaoquan⁴

1. College of Information Engineering, Zhongshan Polytechnic, Zhongshan Guangdong 528404, China;
2. Computer Engineering Technical College, Guangdong Polytechnic of Science and Technology, Zhuhai Guangdong 519090, China;
3. Computer Institute, Dongguan University of Technology, Dongguan Guangdong 523808, China;
4. Educational Technology Center, Huizhou University, Huizhou Guangdong 516007, China

Received:2016-08-19 Revised:2016-10-24 Online:2017-03-22 Published:2017-03-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61170193), the Science and the Technology Project in the Field of Industrial High and New Technology of Guangdong Province (2013B010401036), the Natural Science Foundation of Guangdong Province (S2013010013432) and the Science and Technology Project for Public Interest of Zhongshan City (2016B2142).

摘要/Abstract

摘要： 针对目前多数改进蚁群算法求解多约束服务质量路由（QoSR）存在收敛速度慢、易陷入局部最优从而效率不高的问题，提出一种引入梯度下降的蚁群算法（ACAGD）。该算法将梯度下降法引入到蚁群的局部搜索中，结合残余信息素，综合决定蚂蚁的下一跳选择策略。蚁群不仅以一定概率按照信息素浓度搜索下一跳，还将以一定概率按照梯度下降法搜索下一跳，从而降低传统蚁群算法容易陷入局部最优的可能性。利用Waxman网络模型随机生成不同路由节点数量的网络拓扑进行仿真实验。实验结果表明，ACAGD相比其他改进蚁群算法，能够在收敛速度不受影响的情况下，取得综合代价相对较低的路由，且算法的稳定性较好。

关键词: 服务质量路由, 蚁群算法, 梯度下降法, 信息素浓度, 收敛速度, 收敛结果, 算法稳定性

Abstract: To solve the problem that many improved ant colony algorithms are not efficient to solve the problem of multi-constrained Quality of Service Routing (QoSR), such as slow convergence and local optimization, an Ant Colony Algorithm with Gradient Descent (ACAGD) was proposed. The gradient descent method was introduced into the local search of ant colony, and combined with residual pheromone, the next-hop selection strategy of ants was synthetically determined. Ant colony not only search for the next hop according to the pheromone concentration with certain probability, but also search for the next hop according to the gradient descent method with certain probability, which reduced the possibility that the traditional ant colony algorithm was easy to fall into the local optimum. The Waxman network model was used to randomly generate the network topology with different number of routing nodes. The experimental results show that compared with other improved ACO algorithms, the ACAGD can obtain the route with relatively low comprehensive cost while the convergence rate is not affected, and the stability of the algorithm is better.

Key words: Quality of Service Routing (QoSR), ant colony algorithm, gradient descent algorithm, pheromone concentration, convergence speed, convergent result, algorithm stability

中图分类号:

TP393

梁本来, 杨忠明, 秦勇, 蔡昭权. 引入梯度下降的蚁群算法求解多约束服务质量路由[J]. 计算机应用, 2017, 37(3): 722-729.

LIANG Benlai, YANG Zhongming, QIN Yong, CAI Zhaoquan. Ant colony algorithm with gradient descent for solving multi-constrained quality of service routing[J]. Journal of Computer Applications, 2017, 37(3): 722-729.

参考文献

[1] 夏小云.随机启发式搜索算法的性能分析[D].广州:华南理工大学,2015:11.(XIA X Y. On the performance analysis of randomized search heuristics[D]. Guangzhou:South China University of Technology, 2015:11.)
[2] STVTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(9):889-914.
[3] 杨洁,杨胜,曾庆光,等.基于信息素强度的蚁群算法[J].计算机应用,2009,29(3):865-867.(YANG J, YANG S, ZENG Q G, et al. Ant colony algorithm based on pheromone intensity[J]. Journal of Computer Applications, 2009, 29(3):865-867.)
[4] 段海滨,马冠军,王道波,等.一种求解连续空间优化问题的改进蚁群算法[J].系统仿真学报,2007,19(5):974-977.(DUAN H B, MA G J, WANG D B, et al. Improved ant colony algorithm for solving continuous space optimization problems[J]. Journal of System Simulation, 2007, 19(5):974-977.)
[5] 叶华乔.基于改进蚁群算法的计算机网络路由优化研究[J].计算机仿真,2015,32(4):265-268.(YE H Q. Research on routing optimization of computer network based on improved ant colony algorithm[J]. Computer Simulation, 2015, 32(4):265-268.)
[6] 王宏霞,李亚龙.求解QoS最佳路由选择问题的量子蚁群算法[J].计算机仿真,2014,31(3):295-298.(WANG H X, LI Y L. Quantum ant colony algorithm for QoS best routing problem[J]. Computer Simulation, 2014, 31(3):295-298.)
[7] 刘朝华,张英杰,章兢,等.蚁群算法与免疫算法的融合及其在TSP中的应用[J].控制与决策,2010,25(5):695-700.(LIU Z H, ZHANG Y J, ZHANG J, et al. Using combination of ant algorithm and immune algorithm to solve TSP[J]. Control and Decision, 2010, 25(5):695-700.)
[8] 刘朝华,张英杰,李小花,等.双态免疫优势蚁群算法及其在TSP中的应用研究[J].小型微型计算机系统,2010,31(5):937-941.(LIU Z H, ZHANG Y J, LI X H, et al. Research of using binary state ACA based on immunodominance to solve TSP[J]. Journal of Chinese Computer Systems, 2010, 31(5):937-941.)
[9] 邢志娟.多目标优化问题的蚁群算法研究[D].北京:中国地质大学,2010:5.(XING Z J. Study on multi-objective optimization problem based on ant colony optimization algorithm[D]. Beijing:China University of Geosciences, 2010:5.)
[10] 王永.多目标路由问题中的蚁群优化算法研究[D].长沙:湖南大学,2009:5.(WANG Y. The research on multi-objective routing problems based on ant colony optimization algorithm[D]. Changsha:Hunan University, 2009:5.)
[11] 王健安.基于蚁群优化算法的分布式多约束QoS路由算法研究[D].长春:长春理工大学,2014:3.(WANG J A. Research of multiple constrained distributed QoS routing based on improved ant colony algorithm[D]. Changchun:Changchun University of Science and Technology, 2014:3.)
[12] 宋悦.蚁群算法在路由优化中的应用研究[D].北京:北京交通大学,2015:4.(SONG Y. The study and application of ant colony algorithm in the field of routing optimization[D]. Beijing:Beijing Jiaotong University, 2015:4.)
[13] 胡朝明.几类谱共轭梯度方法理论及数值行为研究[D].长沙:中南大学,2012:9.(HU C M. Research on some types of spectral conjugate gradient methods from the viewpoints of theory and numerical performance[D]. Changsha:Central South University, 2012:9.)
[14] 黄翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1345-1353.(HUANG H, HAO Z F, WU C G, et al. The convergence speed of ant colony optimization[J]. Chinese Journal of Computers, 2007, 30(8):1345-1353.)

[1]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[2]	沙林秀, 聂凡, 高倩, 孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2139-2145.
[3]	韩舒宁, 徐敏, 董学士, 林青, 沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 695-700.
[4]	代荣荣, 李宏慧, 付学良. 基于差分进化融合蚁群算法的数据中心流量调度机制[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3863-3869.
[5]	刘志硕, 刘若思, 陈哲. 基于混合蚁群算法的冷链电动汽车车辆路径问题[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3244-3251.
[6]	王锦凯, 贾旭. 基于迁移孪生非负矩阵分解的静脉识别算法[J]. 计算机应用, 2021, 41(3): 898-903.
[7]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[8]	李二超, 齐款款. B样条曲线融合蚁群算法的机器人路径规划[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3558-3564.
[9]	王锦凯, 贾旭. 基于加权正交约束非负矩阵分解的车脸识别算法[J]. 计算机应用, 2020, 40(4): 1050-1055.
[10]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[11]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[12]	陈维兴, 刘清涛, 孙习习, 陈斌. 机坪感知网络的快速收敛平均一致性时间同步算法[J]. 计算机应用, 2020, 40(11): 3407-3412.
[13]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[14]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[15]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.

引入梯度下降的蚁群算法求解多约束服务质量路由

Ant colony algorithm with gradient descent for solving multi-constrained quality of service routing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics