求解超大规模旅行商问题的纵深遗传算法

doi:10.3778/j.issn.1002-8331.2009.04.016

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (4): 56-58.DOI: 10.3778/j.issn.1002-8331.2009.04.016

求解超大规模旅行商问题的纵深遗传算法

赵连朋^1,2,金喜子^2,3,王娜²,姚明海^1,2

1.渤海大学公共计算机教研部，辽宁锦州 121000
2.东北师范大学计算机学院，长春 130117
3.吉林大学计算机科学与技术学院，长春 130117

收稿日期:2008-09-02 修回日期:2008-12-12 出版日期:2009-02-01 发布日期:2009-02-01
通讯作者: 赵连朋

Depth genetic algorithm solve ultra-large-scale Traveling Salesman Problem

ZHAO Lian-peng^1,2,JIN Xi-zi^2,3,WANG Na²,YAO Ming-hai^1,2

1.Public Computer-Education Department，Bohai University，Jinzhou，Liaoning 121000，China
2.College of Computer，Northeast Normal University，Changchun 130117，China
3.School of Computer Science and Technology，Jilin University，Changchun 130117，China

Received:2008-09-02 Revised:2008-12-12 Online:2009-02-01 Published:2009-02-01
Contact: ZHAO Lian-peng

摘要/Abstract

摘要： 很多演化算法对初始参数设计都敏感，针对于不同的旅行商问题（Traveling Salesman Problem，TSP）实例需要进行相应的初始参数调整。并且，在求解超大规模TSP问题时容易陷于局部最优解。提出了一种纵深遗传算法的TSP问题求解方案，以及新的改良函数、变异函数和交叉函数。对pr1002（259 269.09）、pla85900（152 394 182.43）和brd14051（489 842.93）等实例都获得了比较好的优化解。实验表明该方案在求解TSP问题方面具有优势。

关键词: 旅行商问题, 演化算法, 纵深遗传算法, 最优解

Abstract: Many evolutionary algorithms are sensitive for initial parameters design，the different Traveling Salesman Problem（TSP） need for corresponding adjustment for the initial parameters.And the local optimal solution is easy when you solve the issue of ultra-large-scale TSP problem.Therefore，this paper presents a programme about depth genetic algorithms to solve TSP problems and improved function，variation function，cross-function in order to resolve the question.For example，pr1002（259 269.09），pla85900（152 394 182.43） and brd14051（489 842.93） have a relatively good optimal solution.Experimental results show that the algorithm has great advantages.

Key words: Traveling Salesman Problem（TSP）, evolutionary algorithm, Depth Genetic Algorithm（GDA）, optimal solution

赵连朋^1,2,金喜子^2,3,王娜²,姚明海^1,2. 求解超大规模旅行商问题的纵深遗传算法[J]. 计算机工程与应用, 2009, 45(4): 56-58.

ZHAO Lian-peng^1,2,JIN Xi-zi^2,3,WANG Na²,YAO Ming-hai^1,2. Depth genetic algorithm solve ultra-large-scale Traveling Salesman Problem[J]. Computer Engineering and Applications, 2009, 45(4): 56-58.

[1]	张波，徐黎明，黄志伟，要小鹏. 梯度策略的多目标GANs帕累托最优解算法[J]. 计算机工程与应用, 2021, 57(9): 89-95.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[4]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[5]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[6]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[7]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[8]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[9]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[10]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[11]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[12]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[13]	陈雷，张红梅，张向利. 自适应动态邻域布谷鸟混合算法求解TSP问题[J]. 计算机工程与应用, 2018, 54(23): 42-50.
[14]	白景波，李宏伟，陈亮，冯玉芳，刘建永. 双链量子蚁群系统及应用[J]. 计算机工程与应用, 2018, 54(21): 1-6.
[15]	徐小平，张东洁. 基于猴群算法求解旅行商问题[J]. 计算机工程与应用, 2018, 54(2): 144-148.

求解超大规模旅行商问题的纵深遗传算法

Depth genetic algorithm solve ultra-large-scale Traveling Salesman Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics