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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (27): 41-43.

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

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

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

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-09-21 发布日期:2011-09-21

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

摘要/Abstract

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

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

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）

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

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

[1]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[2]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[3]	邱云飞，高华聪. 混合Filter与改进自适应GA的特征选择方法[J]. 计算机工程与应用, 2021, 57(11): 95-102.
[4]	徐力，刘云华，王启富. 自适应遗传算法在机器人路径规划的应用[J]. 计算机工程与应用, 2020, 56(18): 36-41.
[5]	夏以冲，陈秋莲，宋仁坤. 基于自适应遗传模拟退火算法的矩形件排样[J]. 计算机工程与应用, 2018, 54(22): 229-232.
[6]	韩晓龙，李上，杨全业. 基于遗传算法的战略供应链集成研究[J]. 计算机工程与应用, 2018, 54(2): 214-221.
[7]	杨卫波1，2，王万良1，张景玲3，赵燕伟3. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7): 259-263.
[8]	方刚1，张社民2. 三元统计语言模型对基因表达载体设计的优化[J]. 计算机工程与应用, 2016, 52(15): 60-64.
[9]	曹洁1，2，张玲1. 自适应遗传算法的Multi-Agent交通信号优化控制[J]. 计算机工程与应用, 2016, 52(13): 265-270.
[10]	张炜，范年柏，汪文佳. 基于自适应遗传算法的股票预测模型研究[J]. 计算机工程与应用, 2015, 51(4): 254-259.
[11]	李华莹，刘建敏，乔新勇，李晓磊. 基于AGA-RS的故障特征参数提取方法研究[J]. 计算机工程与应用, 2014, 50(5): 257-260.
[12]	刘睿1，于波1，崔耀东2. 一维下料问题中提高计算效率方法的研究[J]. 计算机工程与应用, 2013, 49(9): 247-250.
[13]	王志亮. 供应链下产品族模块成本模型与评估[J]. 计算机工程与应用, 2012, 48(3): 205-208.
[14]	丁帅1，2，李铁克1，2，施灿涛1，2. 考虑机器故障的HFS重调度研究[J]. 计算机工程与应用, 2012, 48(23): 234-238.
[15]	任海艳，陈飞翔. 自适应遗传算法的改进及在曲线化简中的应用[J]. 计算机工程与应用, 2012, 48(11): 152-155.