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

doi:10.3778/j.issn.1002-8331.2009.04.016

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (4): 56-58.DOI: 10.3778/j.issn.1002-8331.2009.04.016

• 研究、探讨 • Previous Articles Next Articles

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

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

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

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

通讯作者: 赵连朋

Abstract

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

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

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

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

[1]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[2]	QIAN Zhengyuan, ZENG Guosun. Differential Evolution Algorithm Guided by Elite Island Population [J]. Computer Engineering and Applications, 2021, 57(20): 73-81.
[3]	JI Xunsheng, CAI Yiqing. Solving Multi-Objective FJSP Using Historical Information and Restriction Operator [J]. Computer Engineering and Applications, 2020, 56(2): 272-278.
[4]	CAI Yanguang, CHEN Houren, QI Yuanhang. Variable Neighborhood Quantum Fireworks Algorithm for Solving CVRP [J]. Computer Engineering and Applications, 2019, 55(9): 230-236.
[5]	GENG Huantong, ZHOU Lifa, DING Yangyang, ZHOU Shansheng. Improved MOEA/D Algorithm Based on New Differential Evolution Model [J]. Computer Engineering and Applications, 2019, 55(8): 138-146.
[6]	ZHOU Lin. Integrated Optimization Research on Vehicle Routing and Scheduling in City Logistics with Time-Dependent and CO2 Emissions Considerations [J]. Computer Engineering and Applications, 2019, 55(8): 264-270.
[7]	XIAO Junming, GAO Hongyang, ZHU Yongsheng, QU Boyang. Multi-Objective Power Dispatching Considering New Energy Access [J]. Computer Engineering and Applications, 2019, 55(23): 241-247.
[8]	CHEN Jia, YOU Xiaoming, LIU Sheng, LI Juan. Entropy-Game Based Multi-Population Ant Colony Optimization [J]. Computer Engineering and Applications, 2019, 55(16): 170-178.
[9]	ZHAO Yawen, XIONG Ruiping, QIAO Zhi, LIANG Qiqi, LUO Yong. Improved Polymorphic Ant Colony Algorithm with Predatory Search Strategy [J]. Computer Engineering and Applications, 2019, 55(14): 115-121.
[10]	DENG Ye, ZHU Wanhong, WANG Fengshan, LIU Huali. Research on Multi-Objective Robust Vehicle Routing Problem in Emergency Logistics [J]. Computer Engineering and Applications, 2019, 55(1): 248-255.
[11]	BAI Jingbo, LI Hongwei, CHEN Liang, FENG Yufang, LIU Jianyong. Double-chain quantum-inspired ant colony system and its application [J]. Computer Engineering and Applications, 2018, 54(21): 1-6.
[12]	GU Chunhua, LIU Xinping, LUO Fei, DING Weichao. Improved NSGA-II algorithm based on synchronous update of external archive [J]. Computer Engineering and Applications, 2018, 54(20): 28-34.
[13]	LI Hongya1, PENG Yuzhong1，2, DENG Chuyan1, GONG Daoqing1. Review of hybrids of GA and PSO [J]. Computer Engineering and Applications, 2018, 54(2): 20-28.
[14]	XU Xiaoping, ZHANG Dongjie. Solving traveling salesman problem based on monkey algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 144-148.
[15]	DENG Ye, ZHU Wanhong, TANG Jian. Study on vehicle routing problem with stochastic demands and time windows combining with new remediation strategies [J]. Computer Engineering and Applications, 2018, 54(11): 241-248.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics