一种改进的遗传算法在TSP问题中的应用
|
摘要
物流业作为国家经济体系的重要组成部分,费用居高不下,特别是运输费用达到物流费用的一半以上,是导致物流成本过高的重要因素。旅行商问题是车辆路径问题的特例,是实现车辆路径优化的关键。对遗传算法的交叉和变异算子进行改进,在边集合重组交叉的基础上结合近旁构造的启发式思想,多阶段展开的边集合重组交叉算子,在2-opt算法的基础上提出了基于2-opt启发式算法的不断变异算子,并在实例中进行应用,达到缩短距离、降低物流费用的目的。
The logistics industry has become an important part of the national economic system,high cost of logistics, especially transportation costs, reaching more than half the cost of logistics is an important factor. Travelling salesman problem is not just an exception to vehicle routing problem, but also the key to get the vehicle routing optimized. To achieve the aim of shortening distance and lowering the logistics expenses, firstly, it is crucial to ameliorate the crossover operator and mutation operator in Genetic Algorithm. Then, we are supposed to combine the heuristic thought of proximal structure and edge set recombination crossover operated by multistage steps with the foundation of Edge Set Recombination Crossover, so we can propose continuous mutation operator which is based on the2-opt heuristic algorithm and finally apply it to practice.
The logistics industry has become an important part of the national economic system,high cost of logistics, especially transportation costs, reaching more than half the cost of logistics is an important factor. Travelling salesman problem is not just an exception to vehicle routing problem, but also the key to get the vehicle routing optimized. To achieve the aim of shortening distance and lowering the logistics expenses, firstly, it is crucial to ameliorate the crossover operator and mutation operator in Genetic Algorithm. Then, we are supposed to combine the heuristic thought of proximal structure and edge set recombination crossover operated by multistage steps with the foundation of Edge Set Recombination Crossover, so we can propose continuous mutation operator which is based on the2-opt heuristic algorithm and finally apply it to practice.
引文
[1]李明海,邢桂华.用MATLAB实现中国旅行商问题求解[J].微计算机应用,2004(2):218-222.
[2]赖志柱,戈冬梅,张云燕.求解TSP问题的改进最邻近法[J].贵州应用技术学院学报,2016,34(1):139-140.
[3]吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015(10):1861-1862.
[4]许智宏,赵嘉伟,黄永峰,等.基于Spark的并行遗传算法在旅行商问题中的应用[J].计算机应用研究,2016(8):1-2.
[5]李军民,林淑飞,高让礼.用混合遗传算法求解多目标TSP问题[J].西安科技人学学报,2006,26(4):515-518.
[6]杨新武,杨丽军.基于交叉模型的改进遗传算法[J].控制与决策,2016(10):1837-1838.
[7]钱武文,钱军瑞.基于复合形的聚类遗传算法[J].计算机工程与应用,2017,53(3):87-88.
[8]孙文彬,王江.一种基于遗传算法的TSP问题多策略优化求解方法[J].地理与地理信息科学,2016,32(4):1-3.
[9]王小平,曹立明.遗传算法[M].西安:西安交通大学出版社,2002.
[10]天野恵美子,加藤友彦.巡回セールスマン問題に対するマルチカノニカル法の適用[A].福岡工業大学研究論集.2004(37):14.
[11]李军民,林淑飞,高让礼.用混合遗传算法求解多目标TSP问题[J].西安科技大学学报,2006,26(4):515-518.
[12]仙石,吉原.遺伝的アルゴリズムによるTSPの高速解法[A].情報処理学会第46回全国大会.1993(8):4-8.
[13]樋口,筒井,山村.実数値GAにおけるシンプレクス交叉の提案[J].人工知能学会誌,2001(16):147-155.
[2]赖志柱,戈冬梅,张云燕.求解TSP问题的改进最邻近法[J].贵州应用技术学院学报,2016,34(1):139-140.
[3]吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015(10):1861-1862.
[4]许智宏,赵嘉伟,黄永峰,等.基于Spark的并行遗传算法在旅行商问题中的应用[J].计算机应用研究,2016(8):1-2.
[5]李军民,林淑飞,高让礼.用混合遗传算法求解多目标TSP问题[J].西安科技人学学报,2006,26(4):515-518.
[6]杨新武,杨丽军.基于交叉模型的改进遗传算法[J].控制与决策,2016(10):1837-1838.
[7]钱武文,钱军瑞.基于复合形的聚类遗传算法[J].计算机工程与应用,2017,53(3):87-88.
[8]孙文彬,王江.一种基于遗传算法的TSP问题多策略优化求解方法[J].地理与地理信息科学,2016,32(4):1-3.
[9]王小平,曹立明.遗传算法[M].西安:西安交通大学出版社,2002.
[10]天野恵美子,加藤友彦.巡回セールスマン問題に対するマルチカノニカル法の適用[A].福岡工業大学研究論集.2004(37):14.
[11]李军民,林淑飞,高让礼.用混合遗传算法求解多目标TSP问题[J].西安科技大学学报,2006,26(4):515-518.
[12]仙石,吉原.遺伝的アルゴリズムによるTSPの高速解法[A].情報処理学会第46回全国大会.1993(8):4-8.
[13]樋口,筒井,山村.実数値GAにおけるシンプレクス交叉の提案[J].人工知能学会誌,2001(16):147-155.