求解第二类GTSP 的距离矩阵重构遗传算法

doi:10.3969/j.issn.1000-565X.2013.03.005

华南理工大学学报（自然科学版） ›› 2013, Vol. 41 ›› Issue (3): 29-34.doi: 10.3969/j.issn.1000-565X.2013.03.005

求解第二类GTSP 的距离矩阵重构遗传算法

谭阳¹郝志峰^1,2 黄翰³ 赵森^1,4

1．华南理工大学计算机科学与工程学院，广东广州 510006; 2．广东工业大学计算机学院，广东广州 510006;3．华南理工大学软件学院，广东广州 510006; 4．暨南大学计算机科学系，广东广州 510632

收稿日期:2012-06-08 修回日期:2012-11-10 出版日期:2013-03-25 发布日期:2013-02-01
通信作者: 谭阳(1978-)，男，博士生，主要从事进化算法、机器学习、模式识别、人工智能研究． E-mail:tanyang26@126.com
作者简介:谭阳(1978-)，男，博士生，主要从事进化算法、机器学习、模式识别、人工智能研究．
基金资助:
国家自然科学基金资助项目( 61070033，61100148) ; 广东省自然科学基金资助项目( 9251009001000005，S2011040004804)

Genetic Algorithm of Distance Matrix Remodeling for Solving theSecond Kind of GTSP

Tan Yang¹ Hao Zhi-feng^1,2Huang Han³ Zhao Sen^1,4

1.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China;2.Faculty of Computer,Guangdong University of Technology,Guangzhou 510006,Guangdong,China;3.School of Software Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China;4.Department of Computer Science,Jinan University,Guangzhou 510632,Guangdong,China

Received:2012-06-08 Revised:2012-11-10 Online:2013-03-25 Published:2013-02-01
Contact: 谭阳(1978-)，男，博士生，主要从事进化算法、机器学习、模式识别、人工智能研究． E-mail:tanyang26@126.com
About author:谭阳(1978-)，男，博士生，主要从事进化算法、机器学习、模式识别、人工智能研究．
Supported by:
国家自然科学基金资助项目( 61070033，61100148) ; 广东省自然科学基金资助项目( 9251009001000005，S2011040004804)

摘要/Abstract

摘要： 目前第二类广义旅行商问题( GTSP) 求解方法少，仅有的一些方法也存在运算复杂度高等缺陷，为此，文中通过分析距离矩阵的性质，提出了一种重构距离矩阵的算法，将第二类GTSP 转化为第一类GTSP，然后利用混合染色体遗传算法求解转化后的第一类GTSP，从而间接求解了原问题( 第二类GTSP) ．通过转化，大大提高了求解的精度，降低了运算的复杂度．最后，采用文中提出的算法对TSP 问题库内的14 个基准问题构成的第二类GTSP 进行了测试，结果表明该算法可以有效地进行求解．

关键词: 广义旅行商问题, 第二类广义旅行商问题, 距离矩阵重构, 遗传算法

Abstract:

Considering the lack of solving methods and the high computation complexity of the existing methods ofthe second kind of GTSP ( Generalized Traveling Salesman Problem) ,an algorithm to remodel the distance matrix ispresented by analyzing the characters of distance matrix,which converts the second kind of GTSP into the firstkind,and then solves the converted first kind of GTSP by using the hybrid-chromosome genetic algorithm.Thus,the second kind of GTSP is successfully solved in an indirect mode.The results indicate that the conversion increasesthe solution accuracy and decreases the computation complexity significantly.Moreover,according to the testedresults of the second kind of GTSP composed of 14 benchmark problems from the TSPLIB,it is found that the proposedalgorithm is effective.

Key words: generalized traveling salesman problem, second kind of GTSP, distance matrix remodeling, geneticalgorithm

中图分类号:

TP301.6

谭阳郝志峰黄翰赵森. 求解第二类GTSP 的距离矩阵重构遗传算法[J]. 华南理工大学学报（自然科学版）, 2013, 41(3): 29-34.

Tan Yang Hao Zhi-feng Huang Han Zhao Sen. Genetic Algorithm of Distance Matrix Remodeling for Solving theSecond Kind of GTSP[J]. Journal of South China University of Technology (Natural Science Edition), 2013, 41(3): 29-34.

[1]	邱宇东, 王湛, 谢志燊. 基于混合算法的半刚性连接钢框架结构优化[J]. 华南理工大学学报(自然科学版), 2023, 51(6): 72-77.
[2]	翁剑成, 王茂林, 林鹏飞, 等. 基于客流特征鉴别的公交跨线组合调度优化方法[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 39-48.
[3]	秦雅琴, 钱正富, 谢济铭, 等. 基于社会力的交织区突发瓶颈段协同换道决策模型[J]. 华南理工大学学报(自然科学版), 2022, 50(7): 66-75.
[4]	郑亚晶, 李耀辉, 靳文舟. 考虑换乘客流的城市轨道交通网络末班车衔接优化研究[J]. 华南理工大学学报(自然科学版), 2022, 50(5): 32-39,72.
[5]	夏琴香, 李凯, 马骏, 等. 基于遗传算法的模具电极调度问题求解[J]. 华南理工大学学报(自然科学版), 2022, 50(3): 80-87.
[6]	周中, 邓卓湘, 陈云, 等. 基于GA-BP神经网络的泡沫轻质土强度预测[J]. 华南理工大学学报(自然科学版), 2022, 50(11): 125-132.
[7]	刘璇, 王子航, 张桐瑞, 等. 港口重载AGV横向稳定的优化控制策略[J]. 华南理工大学学报(自然科学版), 2021, 49(8): 113-121.
[8]	李静王晨张家旭. 基于UniTire轮胎模型的汽车行驶速度估计[J]. 华南理工大学学报（自然科学版）, 2021, 49(5): 47-55.
[9]	罗玉涛, 周天阳, 许晓通. 基于遗传算法的四轮转向－驱动汽车时变 LQR 控制[J]. 华南理工大学学报（自然科学版）, 2021, 49(3): 114-122.
[10]	晋刚何志豪王英俊. 基于遗传算法的5G频率选择表面形状优化方法[J]. 华南理工大学学报（自然科学版）, 2021, 49(11): 95-105.
[11]	李家乐刘真伯王雪菲. 智能电网下支持充放电策略的电动汽车配送路径优化[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 31-40.
[12]	靳文舟胡为洋邓嘉怡, 等. 基于混合算法的需求响应公交灵活调度模型 [J]. 华南理工大学学报（自然科学版）, 2021, 49(1): 123-133.
[13]	刘刚, 郭德明, 郑文成, 等. 基于轴向热路模型的架空地线与预绞丝接触端面接触电阻的计算[J]. 华南理工大学学报（自然科学版）, 2020, 48(7): 9-19.
[14]	马宏伟陈丰收. 基于粗粒度并行遗传算法的阻尼器优化布置[J]. 华南理工大学学报（自然科学版）, 2019, 47(11): 104-112.
[15]	张开升刘浩田王强张保成. 仿生鲔科机器鱼的多机体协同推进效率优化[J]. 华南理工大学学报（自然科学版）, 2018, 46(7): 109-115,122.

求解第二类GTSP 的距离矩阵重构遗传算法

Genetic Algorithm of Distance Matrix Remodeling for Solving theSecond Kind of GTSP

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价