动态凸包引导的偏优规划蚁群算法求解TSP问题

马学森; 宫帅; 朱建; 唐昊

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

您当前的位置：

首页 >

文章列表页 >

动态凸包引导的偏优规划蚁群算法求解TSP问题

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

- 动态凸包引导的偏优规划蚁群算法求解TSP问题
- Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem
- 通信学报 2018年39卷第10期页码：59-71
- 作者机构：
  
  1. 合肥工业大学计算机与信息学院，安徽合肥 230009
  2. 广东三水合肥工业大学研究院，广东佛山 528000
  3. 合肥工业大学电气与自动化工程学院，安徽合肥 230009
- 作者简介：
  
  [ "马学森（1976-），男，安徽庐江人，合肥工业大学副教授、硕士生导师，主要研究方向为无线传感器网络、嵌入式系统、大数据处理、网络与信息安全。" ]
  [ "宫帅（1993-），男，安徽滁州人，合肥工业大学硕士生，主要研究方向为无线传感器网络、物联网、网络与信息安全。" ]
  [ "朱建（1992-），男，安徽五河人，合肥工业大学硕士生，主要研究方向为高可靠性嵌入式系统、无线传感器网络、物联网。" ]
  [ "唐昊（1972-），男，安徽庐江人，合肥工业大学教授、博士生导师，主要研究方向为离散事件动态系统、随机决策与优化理论、强化学习等智能优化与控制方法、自动化生产线、物联网和微网等系统优化设计与控制技术。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61573126);广东省科技发展专项基金资助项目(2017A010101001);中央高校基本科研业务费专项基金资助项目(JZ2016HGBZ1032);国家留学基金资助项目
- DOI：10.11959/j.issn.1000-436x.2018218
  中图分类号： TP18
- 网络出版日期：2018-10，
  
  纸质出版日期：2018-10-25
- 稿件说明：
移动端阅览
马学森, 宫帅, 朱建, 等. 动态凸包引导的偏优规划蚁群算法求解TSP问题[J]. 通信学报, 2018,39(10):59-71.

Xuesen MA, Shuai GONG, Jian ZHU, et al. Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem[J]. Journal on communications, 2018, 39(10): 59-71.
马学森, 宫帅, 朱建, 等. 动态凸包引导的偏优规划蚁群算法求解TSP问题[J]. 通信学报, 2018,39(10):59-71. DOI： 10.11959/j.issn.1000-436x.2018218.

Xuesen MA, Shuai GONG, Jian ZHU, et al. Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem[J]. Journal on communications, 2018, 39(10): 59-71. DOI： 10.11959/j.issn.1000-436x.2018218.

摘要

针对蚁群算法搜索空间大、收敛速度慢、容易陷入局部最优等缺陷，提出一种基于动态凸包引导的偏优规划蚁群算法。改进后的算法动态控制蚂蚁的待选城市范围，有助于在跳出局部最优并向全局最优逼近的基础上减少蚂蚁搜索空间；同时，引入延陷漂流因子和基于待选城市构建的凸包来干预当前蚂蚁的城市选择，增加算法前期解的多样性并提高蚂蚁的偏优规划能力；再利用局部与整体相结合的完整路径信息、凸包的构建信息来协调信息素的更新，引导后继蚂蚁路径偏优规划，提高算法的求解精度；设计具有收敛性的信息素最大最小值限制策略，既加快算法的求解速度又避免算法过早停滞；最后在4种经典TSP模型上应用改进后的算法。仿真结果表明，所提算法在求解精度和收敛速度等方面均有显著提高，且具有较好的适用性。

Abstract

To solve basic ant colony algorithm’s drawbacks of large search space

low convergence rate and easiness of trapping in local optimal solution

an ant colony algorithm of partially optimal programming based on dynamic convex hull guidance was proposed.The improved algorithm dynamically controlled the urban selection range of the ants

which could reduce the search space of ants on basis of helping the algorithm to jump out of local optimal solution to global optimal solution.Meanwhile

the delayed drift factor and the convex hull constructed by the cities to be chosen were introduced to intervene the current ants’ urban choice

it could increase the diversity of the early solution of the algorithm and improve the ability of ants’ partially optimal programming.Then the pheromone updating was coordinated by using construction information of convex hull and the complete path information that combined local with whole

it could improve the accuracy of the algorithm by guiding the subsequent ants to partially optimal programming.The pheromone maximum and minimum limit strategy with convergence was designed to avoid the algorithm’s premature stagnation and accelerate the solving speed of the algorithm.Finally

the proposed algorithm was applied to four classic TSP models.Simulation results show that the algorithm has better optimal solution

higher convergence rate and better applicability.

关键词

Keywords

references

DORIGO M , GAMBARDELL L M . Ant colonies for the travelling salesman problem [J ] . Bio Systems , 1997 , 43 ( 2 ): 73 - 81 .

MAEKAWA K , TAMAKI H , KITA H , et al . A method for the traveling salesman problem based on the genetic algorithm [J ] . Transactions of the Society of Instrument ＆ Control Engineers , 1995 , 31 ( 5 ): 598 - 605 .

WANG J , ERSOY O K , HE M , et al . Multi-offspring genetic algorithm and its application to the traveling salesman problem [J ] . Applied Soft Computing , 2016 , 43 ( 3 ): 415 - 423 .

MURRAY A T , CHURCH R L . Applying simulated annealing to location-planning models [J ] . Journal of Heuristics , 1996 , 2 ( 1 ): 31 - 53 .

YU D , JIA J . A neural network algorithm with optimized parameters and used to solve the TSP [J ] . Acta Electronica Sinica , 1993 , 21 ( 7 ): 16 - 22 .

LIN Y , BIAZ Z , LIU X . Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing – tabu search algorithm to solve the symmetrical traveling salesman problem [J ] . Applied Soft Computing , 2016 , 49 ( 9 ): 937 - 952 .

LIU Z , LI X , WANG H . Improvement of self-adaptive ant colony algorithm based on cloud model [J ] . Computer Engineering and Applications , 2016 , 52 ( 19 ): 68 - 71 .

PAN G , LI K , OUYANG A , et al . Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP [J ] . Soft Computing , 2016 , 20 ( 2 ): 555 - 566 .

DORIGO M , MANIEZZO V , COLORNI A , et al . Ant system:optimization by a colony of cooperating agents [J ] . IEEE Transactions on Systems Man and Cybernetics-Part B , 1996 , 26 ( 1 ): 29 - 41 .

DORIGO M , GAMBARDELLA L M . Ant colony system:a cooperative learning approach to the traveling salesman problem [J ] . IEEE Transactions on Evolutionary Computation , 1997 , 1 ( 1 ): 53 - 66 .

孟祥萍 , 片兆宇 , 沈中玉 , 等 . 基于方向信息素协调的蚁群算法 [J ] . 控制与决策 , 2013 , 28 ( 5 ): 782 - 786 .

MENG X P , PIAN Z Y , SHEN Z Y , et al . Ant algorithm based on di-rection-coordinating [J ] . Control and Decision , 2013 ( 5 ): 782 - 786 .

吴华锋 , 陈信强 , 毛奇凰 , 等 . 基于自然选择策略的蚁群算法求解TSP问题 [J ] . 通信学报 , 2013 , 34 ( 4 ): 165 - 170 .

WU H F , CHEN X Q , MAO Q F , et al . Improved ant colony algorithm based on natural selection strategy for solving TSP problem [J ] . Journal on Communications , 2013 ( 4 ): 165 - 170 .

林建兵 , 陈智雄 , 姚国祥 . 一种基于域密度的蚁群系统(AS)改进算法及结果解析 [J ] . 武汉大学学报(工学版) , 2016 , 49 ( 4 ): 627 - 634 .

LIN J B , CHEN Z X , YAO G X . An improved AS algorithm and re-sult analyzing based on domain and its density [J ] . Engineering Journal of Wuhan University , 2016 , 49 ( 4 ): 627 - 634 .

马学森 , 曹政 , 韩江洪 , 等 . 改进蚁群算法的无线传感器网络路由优化与路径恢复算法 [J ] . 电子测量与仪器学报 , 2015 , 29 ( 9 ): 1320 - 1327 .

MA X S , CAO Z , HAN J H , et al . Routing optimization and path re-covery algorithm in wireless sensor network based on improved ant colony algorithm [J ] . Journal of Electronic Measurement and Instru-ment , 2015 , 29 ( 9 ): 1320 - 1327 .

孙力娟 , 王良俊 , 王汝传 . 改进的蚁群算法及其在TSP中的应用研究 [J ] . 通信学报 , 2004 , 25 ( 10 ): 111 - 116 .

SUN L J , WANG L J , WANG R C , et al . Research of using an improved ant colony algorithm to solve TSP [J ] . Journal on Communications , 2004 , 25 ( 10 ): 111 - 116 .

BU Y , LI T Q , ZHANG Q . A weighted max-min ant colony algorithm for TSP instances [J ] . IEICE Transactions on Fundamentals of Electronics Communications ＆ Computer Sciences , 2015 ( 3 ): 894 - 897 .

耿志强 , 邱大洪 , 韩永明 . 基于混沌的 MMAS 算法及其在旅行商问题中的应用 [J ] . 计算机工程 , 2016 , 42 ( 3 ): 192 - 197 .

GENG Z Q , QIU D H , HAN Y M . Max-min ant system algorithm based on chaos and its application in TSP [J ] . Computer Engineering , 2016 , 42 ( 3 ): 192 - 197 .

WANG Y . Hybrid max-min ant system with four vertices and three lines inequality for traveling salesman problem [J ] . Soft Computing , 2015 , 19 ( 3 ): 585 - 596 .

张层 . 基于二维凸包的改进蚁群算法求解 TSP 问题 [D ] . 广州:华南理工大学 , 2013 .

ZHANG C . An improved ant colony algorithm based on two-dimensional convex hull for TSP [D ] . Guangzhou:South China University of Technology , 2013 .

党小超 , 李小艳 . 基于图论的 WSN 节点定位路径规划 [J ] . 计算机工程 , 2012 , 38 ( 11 ): 100 - 103 .

DANG X C , LI X Y . WSN node localization path planning based on graph theory [J ] . Computer Engineering , 2012 , 38 ( 11 ): 100 - 103 .

PRAGYA , DUTTA M , PRATYUSH , . TSP solution using dimensional ant colony optimization [C ] // International Conference on Advanced Computing ＆ Communication Technologies . 2015 : 506 - 512 .

QIN H , ZHOU S , HUO L , et al . A new ant colony algorithm based on dynamic local search for TSP [C ] // International Conference on Communication Systems and Network Technologies . 2015 : 913 - 917 .

GU S , ZHANG X . An improved ant colony algorithm with soldier ants [C ] // 2015 11th International Conference on Natural Computation (ICNC) . 2016 : 205 - 209 .

LUO W , LIN D , FENG X X . An improved ant colony optimization and its application on TSP problem [C ] // 2016 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber,Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) . 2017 : 136 - 141 .

盛国军 , 温涛 , 郭权 , 等 . 基于改进蚁群算法的可信服务发现 [J ] . 通信学报 , 2013 , 34 ( 10 ): 37 - 48 .

SHENG G J , WEN T , GUO Q , et al . Trustworthy service discovery based on a modified ant colony algorithm [J ] . Journal on Communica-tions , 2013 , 34 ( 10 ): 37 - 48 .

詹士昌 , 徐婕 , 吴俊 . 蚁群算法中有关算法参数的最优选择 [J ] . 科技通报 , 2003 , 19 ( 5 ): 381 - 386 .

ZHAN S C , XU J , WU J . The optimal selection on the parameters of the ant colony algorithm [J ] . Bulletin of Science and Technology , 2003 , 19 ( 5 ): 381 - 386 .

浏览量

946

下载量

CSCD

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

提交

工具集

关联资源

基于自然选择策略的蚁群算法求解TSP问题

基于蚁群算法的骨干网络发现

基于蚁群算法的区域覆盖卫星星座优化设计