Adaptive genetic algorithm for GTSP

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (27): 41-43.

• 研究、探讨 • Previous Articles Next Articles

Adaptive genetic algorithm for GTSP

WANG Yuedong1，LI Wei2，YANG Weibo1

1.Oujiang College，Wenzhou University，Wenzhou，Zhejiang 325027，China
2.Wenzhou Entry-exit Inspection and Quarantine Bureau，Wenzhou，Zhejiang 325027，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-09-21 Published:2011-09-21

求解GTSP问题的自适应遗传算法

王跃东1，李卫2，杨卫波1

1.温州大学瓯江学院，浙江温州 325027
2.温州出入境检验检疫局，浙江温州 325027

Abstract

Abstract: Based on the basic concepts of traditional genetic algorithm，an improved adaptive genetic algorithm for solving GTSP is proposed.GTSP is changed into multi-segment map problem which is solved with dynamic programming algorithm by individual coding.Individual fitness function based on multi-segment map optimal sub-structure is designed to speed up algorithm calculation speed.Experimental test results show that the new algorithm has faster convergence and better solution than traditional genetic algorithm.

Key words: adaptive genetic algorithm, dynamic programming algorithm, Generalized Traveling Salesman Problem（GTSP）

摘要： 利用传统遗传算法的基本思想，针对GTSP问题，提出了一种改进的自适应遗传算法。通过个体编码方法，将GTSP转化为多段图最短路径问题，采用动态规划算法求解;根据多段图最优子结构性质设计了个体适应度评价函数，加快了算法的运行速度。实验测试的结果表明，新算法比传统的遗传算法具有更快的收敛速度和更优的解质量。

关键词: 自适应遗传算法, 动态规划算法, 广义旅行商问题

WANG Yuedong1，LI Wei2，YANG Weibo1. Adaptive genetic algorithm for GTSP[J]. Computer Engineering and Applications, 2011, 47(27): 41-43.

王跃东1，李卫2，杨卫波1. 求解GTSP问题的自适应遗传算法[J]. 计算机工程与应用, 2011, 47(27): 41-43.

[1]	CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(20): 164-171.
[2]	DAI Jiangtao, HAN Xiaolong. Coordinated Scheduling of Equipment in Container Terminals Considering Energy Consumption Under Different Job Status [J]. Computer Engineering and Applications, 2021, 57(19): 290-298.
[3]	QIU Yunfei, GAO Huacong. Hybrid Filter and Improved Adaptive GA for Feature Selection [J]. Computer Engineering and Applications, 2021, 57(11): 95-102.
[4]	XU Li, LIU Yunhua, WANG Qifu. Application of Adaptive Genetic Algorithm in Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(18): 36-41.
[5]	XIA Yichong, CHEN Qiulian, SONG Renkun. Packing of rectangles using adaptive genetic simulated annealing algorithm [J]. Computer Engineering and Applications, 2018, 54(22): 229-232.
[6]	HAN Xiaolong, LI Shang, YANG Quanye. Strategic supply chain integration research based on genetic algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 214-221.
[7]	YANG Weibo1，2, WANG Wanliang1, ZHANG Jingling3, ZHAO Yanwei3. Packing optimization of rectangles based on improved genetic annealing algorithm [J]. Computer Engineering and Applications, 2016, 52(7): 259-263.
[8]	CAO Jie1，2, ZHANG Ling1. Multi-Agent traffic signal control based on adaptive genetic algorithm [J]. Computer Engineering and Applications, 2016, 52(13): 265-270.
[9]	ZHANG Wei, FAN Nianbai, WANG Wenjia. Stock prediction model research based on improved adaptive genetic algorithm [J]. Computer Engineering and Applications, 2015, 51(4): 254-259.
[10]	LI Huaying, LIU Jianmin, QIAO Xinyong, LI Xiaolei. Method research of fault feature extraction based on AGA-RS [J]. Computer Engineering and Applications, 2014, 50(5): 257-260.
[11]	WANG Zhiliang. Customization module’s cost model and evaluation under supply chain [J]. Computer Engineering and Applications, 2012, 48(3): 205-208.
[12]	DING Shuai1，2, LI Tieke1，2, SHI Cantao1，2. Study of hybrid flow shop rescheduling with consideration of machine breakdown [J]. Computer Engineering and Applications, 2012, 48(23): 234-238.
[13]	REN Haiyan, CHEN Feixiang. Improvement of adaptive genetic algorithms and application in line simplification [J]. Computer Engineering and Applications, 2012, 48(11): 152-155.
[14]	LIU Wenyuan，LIU Bin. Adaptive genetic algorithm based on co-evolution [J]. Computer Engineering and Applications, 2011, 47(14): 31-33.
[15]	ZENG Qiang^1，2，YANG Yu¹，WANG Xiao-lei¹，LIANG Xue-dong¹. Optimal manufacturing tasks assignment method based on multi-objectives [J]. Computer Engineering and Applications, 2010, 46(5): 17-20.

Adaptive genetic algorithm for GTSP

求解GTSP问题的自适应遗传算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics