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

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

Abstract

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.

Key words: ant colony algorithm, convex hull, TSP, partially optimal programming

CLC Number:

TP18

Xuesen MA,Shuai GONG,Jian ZHU,Hao TANG. 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.

Figures/Tables 11

步骤	内容	时间复杂度
1)	初始化参数	O(n²+m)
2)	设置算法禁忌表	O(m)
3)	蚂蚁遍历解	$O ({⌈ λ n ⌉}^{2} m)$
4)	解的比较和路径更新量的计算	$O ({⌈ λ n ⌉}^{2} m)$
5)	路径上信息素浓度的更新	$O (⌈ λ n ⌉^{2})$
6)	判断算法是否达到停止条件若没有则转到步骤2)，	$O (⌈ λ n ⌉ m)$
7)	输出执行结果	O(1)

References 26

[1]	DORIGO M , GAMBARDELL L M . Ant colonies for the travelling salesman problem[J]. Bio Systems, 1997,43(2): 73-81.
[2]	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.
[3]	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.
[4]	MURRAY A T , CHURCH R L . Applying simulated annealing to location-planning models[J]. Journal of Heuristics, 1996,2(1): 31-53.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	孟祥萍, 片兆宇, 沈中玉 ,等. 基于方向信息素协调的蚁群算法[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.
[12]	吴华锋, 陈信强, 毛奇凰 ,等. 基于自然选择策略的蚁群算法求解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.
[13]	林建兵, 陈智雄, 姚国祥 . 一种基于域密度的蚁群系统(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.
[14]	马学森, 曹政, 韩江洪 ,等. 改进蚁群算法的无线传感器网络路由优化与路径恢复算法[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.
[15]	孙力娟, 王良俊, 王汝传 . 改进的蚁群算法及其在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.
[16]	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.
[17]	耿志强, 邱大洪, 韩永明 . 基于混沌的 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.
[18]	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.
[19]	张层 . 基于二维凸包的改进蚁群算法求解 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.
[20]	党小超, 李小艳 . 基于图论的 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.
[21]	PRAGYA , DUTTA M , PRATYUSH , . TSP solution using dimensional ant colony optimization[C]// International Conference on Advanced Computing ＆ Communication Technologies. 2015: 506-512.
[22]	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.
[23]	GU S , ZHANG X . An improved ant colony algorithm with soldier ants[C]// 2015 11th International Conference on Natural Computation (ICNC). 2016: 205-209.
[24]	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.
[25]	盛国军, 温涛, 郭权 ,等. 基于改进蚁群算法的可信服务发现[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.
[26]	詹士昌, 徐婕, 吴俊 . 蚁群算法中有关算法参数的最优选择[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.

Metrics

Recommended 0

No Suggested Reading articles found!

参数名称	参数值
信息素浓度权重值α	1
启发式函数权重值β	5
局部信息素挥发系数ρ₁	0.04
概率增量P	0.07
蚂蚁选择范围参数λ的初始值N	0.1
全局最优解连续N₁次迭代值	30
最大迭代次数N_max	1 000

TSP算例	参数名称	参数值
	全局信息素挥发系数ρ	0.7
Oliver30	蚂蚁个数m	30
	延陷漂流因子μ初始值N	1.4n
	权重因子λ₁、λ₂、λ₃	1.1、1.0、0.8
	全局信息素挥发系数ρ	0.8
Eil51	蚂蚁个数m	51
	延陷漂流因子μ初始值N	1.3n
	权重因子λ₁、λ₂、λ₃	1.2、1.1、0.9
	全局信息素挥发系数ρ	0.8
St70	蚂蚁个数m	70
	延陷漂流因子μ初始值N	1.2n
	权重因子λ₁、λ₂、λ₃	1.4、1.3、1.0
	全局信息素挥发系数ρ	0.8
Eil76	蚂蚁个数m	76
	延陷漂流因子μ初始值N	1.1n
	权重因子λ₁、λ₂、λ₃	1.5、1.4、1.1

	TSP问题	Oliver30	Eil51
	迭代最小值	612	897
ACS算法	迭代最大值	1502	1712
	迭代平均值	1011	1397
	平均解	429.16	441.23
	迭代最小值	407	781
MMAS算法	迭代最大值	1124	1501
	迭代平均值	712	1238
	平均解	427.18	439.81
	迭代最小值	191	450
AADC算法	迭代最大值	531	1703
	迭代平均值	306	1078
	平均解	424.64	437.20
	迭代最小值	187	446
ACADCG算法	迭代最大值	473	923
	迭代平均值	274	716
	平均解	423.89	437.03

TSP算例	算法名称	最优路径长度	误差	最差路径长度	平均路径长度	平均迭代次数/次
	ACS算法	425.52	1.3%	446.87	429.16	1 011
Oliver30	MMAS算法	424.86	1.2%	442.34	427.18	712
	AADC算法	423.91	0.9%	425.82	424.64	306
	ACADCG算法	423.14	0.8%	425.26	423.89	274
	ACS算法	438.74	3.0%	455.17	441.23	1 397
Eil51	MMAS算法	436.63	2.5%	453.12	439.81	1 238
	AADC算法	429.74	0.9%	449.82	437.20	1 078
	ACADCG算法	429.18	0.8%	450.39	437.03	716
	ACS算法	687.46	1.8%	700.95	697.37	1 276
St70	MMAS算法	685.13	1.5%	698.89	694.74	1 112
	AADC算法	682.31	1.1%	699.12	689.92	932
	ACADCG算法	681.25	0.9%	698.27	689.16	619
	ACS算法	555.61	3.3%	559.55	557.18	1 297
Eil76	MMAS算法	552.26	2.7%	558.11	555.84	1 142
	AADC算法	544.43	1.2%	557.43	550.21	970
	ACADCG算法	543.41	1.0%	557.52	549.39	658

Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 26

Related Articles 13

Metrics

Recommended 0

[1]	Tong WANG, Shan GAO, Huiwen GONG, Bo SUN. Research on forecast and recommendation technology of taxi passengers based on time-varying Markov decision process [J]. Journal on Communications, 2021, 42(2): 37-51.
[2]	Fang LYU,Jun BAI,Junheng HUANG,Bailing WANG. Discovering the backbone network with a novel designed ant colony algorithm [J]. Journal on Communications, 2020, 41(11): 74-85.
[3]	Zhong-an JIANG,Ming WANG,Ya CHEN. Path recommendation based on geographic coordinates and trajectory data [J]. Journal on Communications, 2017, 38(5): 165-171.
[4]	. Improved ant colony algorithm based on natural selection strategy for solving TSP problem [J]. Journal on Communications, 2013, 34(4): 20-170.
[5]	Hua-feng WU,Xin-qiang CHEN,Qi-huang MAO,Qian-nan ZHANG,Shou-chun ZHANG. Improved ant colony algorithm based on natural selection strategy for solving TSP problem [J]. Journal on Communications, 2013, 34(4): 165-170.
[6]	Mao-hua SUN,Shou-shan LUO,Yang XIN,Yi-xian YANG. Secure two-party line segments intersection scheme and its application in privacy-preserving convex hull intersection [J]. Journal on Communications, 2013, 34(1): 30-42.
[7]	Nyuan YUA,Yu-xing PENG,Shan-shan LI,Wen-sheng TANG. Efficient heuristic algorithm for the mobile sink routing problem [J]. Journal on Communications, 2011, 32(10): 107-117.
[8]	Jiang-qing WANG,Jun QIN,Zi-mao LI. Hybrid optimization algorithm for routing problem in dynamic networks [J]. Journal on Communications, 2008, 29(7): 135-140.
[9]	Yi-ling ZENG,Hong-bo XU. Research on Internet hotspot information detection [J]. Journal on Communications, 2007, 28(12): 141-146.
[10]	Qiu-yu ZHANG,Zhan-ting YUAN,Qi-kun ZHANG,Rui-fang WANG. Multi-domain authentication mechanism based on lattice and adaptive algorithm [J]. Journal on Communications, 2007, 28(11A): 82-86.
[11]	Jiao-long WEI,Zhao-hui CEN. Optimization of regional coverage satellite constellations based on ant colony algorithm [J]. Journal on Communications, 2006, 27(8): 62-66.
[12]	Gang WANG,Hua WANG,Ning LIAO. Modified ant colony algorithm based on orientation factor in solving the multi-constraint QoS routing problem [J]. Journal on Communications, 2006, 27(11A): 189-193.
[13]	Xue-hui LUO,Xia LI,Ji-hong ZHANG. Vector quantization codebook design algorithm based on hybrid ant colony algorithm [J]. Journal on Communications, 2005, 26(9): 135-139.