基于改进遗传算法的快递路径优化问题的研究
Study on Delivery Route Optimization Based on Improved Genetic Algorithm

作者: 郑丽娜 , 王岩焱 , 罗融宇 , 童旭 , 梁欢 :东北大学秦皇岛分校数学与统计学院,河北 秦皇岛;

关键词: 路径优化遗传算法交叉概率变异概率优势个体Route Optimization The Genetic Algorithm Crossover Possibility Mutation Probability Dominant Individual

摘要: 本文概述了快递路径优化问题的理论基础及其求解算法,建立了对应问题的数学模型。论述了遗传算法的一般步骤,并分析标准遗传算法在求解该问题中的缺陷及原因。针对标准遗传算法的过早收敛、局部收敛和优势个体退化等缺点,采用自适应交叉和变异概率及保留优势个体的方法改进算法,并结合具体实例介绍其实现方法,验证了改进算法的可行性。

Abstract: This passage reviewed the basic theory and algorithm of the delivery route optimization problem and established a mathematical model of the corresponding problem. This passage discussed the general steps of Genetic Algorithm and analyzed the defects and their reasons of Standard Genetic Algorithm in solving the problem. Aiming at the defects such as premature convergence, local convergence and dominant individual degradation, this passage improved the algorithm by using adaptive crossover probability and mutation probability and reserving dominant individuals. This passage combined a specific problem with its solution to verify the feasibility of the improved al-gorithm.

文章引用: 郑丽娜 , 王岩焱 , 罗融宇 , 童旭 , 梁欢 (2016) 基于改进遗传算法的快递路径优化问题的研究。 应用数学进展, 5, 516-522. doi: 10.12677/AAM.2016.53062

参考文献

[1] 张强, 安大翔. 快递业城市配送路径优化研究[J]. 经营管理者, 2016(11): 183.

[2] 赖志柱, 戈冬梅, 张云艳. 求解TSP问题的改进最邻近法[J]. 贵州工程应用技术学院学报, 2016, 34(1): 139-142.

[3] 高海昌, 冯博琴, 朱利. 智能优化算法求解TSP问题[J]. 控制与决策, 2006, 21(3): 241-247, 252.

[4] 王岚. 基于自适应交叉和变异概率的遗传算法收敛性研究[J]. 云南师范大学学报(自然科学版), 2010, 30(3): 32-37.

[5] 肖华勇. 大学生数学建模竞赛指南[M]. 北京: 电子工业出版社, 2015.

[6] 唐世浩, 朱启疆. 遗传算法中初始种群与交叉、变异率对解的影响及其解决方案[J]. 科技通报, 2001, 17(3): 1-7.

[7] 刘世清, 杨孔雨. 求解TSP问题的遗传算法改进研究[J]. 北京信息科技大学学报(自然科学版), 2014(2): 46-50.

[8] 金晶, 苏勇. 一种改进的自适应遗传算法[J]. 计算机工程与应用, 2005, 41(18): 64-69.

[9] 刘帅, 马志强, 刘清雪, 陆林英. 基于自适应免疫遗传算法的多序列比对[J]. 信息技术, 2007(2): 15-17, 111.

分享
Top