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 algorithm.

Keywords:Route Optimization, The Genetic Algorithm, Crossover Possibility, Mutation Probability, Dominant Individual

基于改进遗传算法的快递路径优化问题的研究

郑丽娜，王岩焱，罗融宇，童旭，梁欢

东北大学秦皇岛分校数学与统计学院，河北 秦皇岛

收稿日期：2016年8月9日；录用日期：2016年8月24日；发布日期：2016年8月31日

摘 要

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

关键词 :路径优化，遗传算法，交叉概率，变异概率，优势个体

1. 引言

随着电子商务的快速发展，网购逐渐成为人们生活的一部分，与之紧密相关的快递行业也随之发展起来。在快递配送过程中，合理的配送路径不仅能减少公司经济负担，增加利润，提升客户体验，缓解交通拥堵 [1] 。因此，如何找到合理的快递配送路径，是一个值得考虑的问题。

快递路径优化问题可以归类为旅行商问(Traveling Salesman Problem, TSP)。该问题的求解算法主要分为两类：与问题特征相关的启发式搜索算法和独立于问题的智能优化算法 [2] 。与问题本身相关的启发式算法，过于依赖问题本身，易陷入局部最优解。而随着人工智能的发展，一些独立于问题之外的智能算法被广泛采用，例如蚁群算法、模拟退火算法、遗传算法、神经网络等 [3] 。

遗传算法是根据种群优胜劣汰的进化理论而设计的一种智能算法，求解速度快，结果准确，实用性广，对求解路径优化问题，比传统算法有很大的优势。标准的遗传算法中，交叉概率Pc和变异概率Pm在整个进化过程中保持不变，是导致算法性能下降的重要原因 [4] ，并且在进化过程中，种群中的优势个体可能出现退化。本文针对标准遗传算法的缺陷，对算法进行改进，并通过一个快递路径优化问题的实例，对改进算法的可行性进行了验证。

2. 快递路径优化问题的数学模型

快递路径优化问题是现实生活中常见的一类优化问题。给定n个快递需求点，一个快递员从其中一个点出发，给每个需求点派送快件，要求经过每个点一次，且仅能经过一次，最后再回到出发点，如何安排使得路径最短。这个问题可以用如下数学模型表示。

(1)

(2)

(3)

(4)

(5)

为1表示需求点i和需求点j之间有路径，为0则表示没有路径，表示需求点i和需求点j之间的距离，目标函数(1)式表示路径的长度最短，(2)式和(3)式分别表示每个城市之前和之后仅有一个需求点。

所求的最短路径只有一个回路，(4)式中(和为实数)避免一次遍历中产生多余一个回路的情况。例如顶点构成一条回路，则，从而，，，，，所以，导致矛盾 [5] 。

该模型为带有线性约束条件的优化模型，理论上可以用穷举法列举所有可能的路径，比较路径长度得到最优解，但是当问题规模n较大时，穷举法难以通过计算机编程实现。相比较穷举法，遗传算法不依赖于问题本身，可以快速有效地求解这类问题。

3. 遗传算法的求解步骤和算法的改进

1962年Holland首次提出遗传算法的思想，吸引了大批的学者研究，迅速推广到优化、搜索、机器学习等方面，并奠定了坚实的理论基础 [6] ，形成了遗传算法的基本框架。

3.1. 遗传算法的求解步骤

对于一个需要采用遗传算法优化的问题，一般可以采用如下步骤进行求解。

Step1：生成初始种群。确定编码方式，常用的编码方式有二进制编码、实数编码等。随机生成M个个体作为初始种群P(0)，设置进化代数计数器t = 0，最大进化代数T；

Step2：计算个体适应度值、选择概率和累积概率；

Step3：选择与复制。随机产生M个0-1的随机数，根据累积概率，计算出每个个体被选中的次数，然后进行选择与复制；

Step4：交叉；

Step5：变异；

Step6：终止条件判断。若，则，返回Step2；否则，以进化过程中得到的具有最大适应度的个体作为最优解输出，算法终止 [7] 。

3.2. 改进的自适应遗传算法

标准的遗传算法保持交叉和变异概率不变，一般情况下，交叉概率取值在0.5~1.0之间，变异概率取值在0.00001~0.1之间，具体取值要根据具体问题进行多次实验测试得到，确定交叉和变异概率有一定的盲目性。如果选择不合适的交叉和变异概率会导致算法出现无法收敛、早熟和局部收敛等问题。在交叉和变异过程中，优势个体也会发生改变，可能导致个体退化。针对上述问题，本文对标准遗传算法进行相应改进。

3.2.1. 自适应交叉和变异概率

固定的交叉和变异概率难以满足进化过程中的需要，交叉概率大，产生具有新性状的个体速度越快，数量也越多。交叉概率过大，可能使优良个体遭到破坏，交叉概率过小，产生新个体速度慢，可能导致算法过早收敛。变异概率在进化过程中决定算法是否能跳出局部最优解。变异概率过小，难以产生新个体，变异概率过大，算法就成为随机的搜索算法 [8] 。因此，为适应进化环境，可以将交叉和变异概率设置为动态变化的，随着种群的进化而适当调整，在本文的改进算法中，交叉概率Pc和变异概率Pm按照如下公式进行自适应调整。

(6)

(7)

其中，为种群中最优个体适应度值，为种群的平均适应度值，和为待定参数，根据实际问题而选取。在进化过程中，Pc和Pm的取值动态地变化。算法初期，当种群个体差异较大时，变大，Pc变大，Pm变小，保证更快的产生新的个体，避免算法过早收敛。算法后期，当种群个体差异较小，变小，Pc变小，Pm变大，有利于算法跳出局部最优解 [9] 。

3.2.2. 保留优势个体

在每一代的进化过程中，如果每个个体都有机会进行交叉和变异，虽然符合生物进化的原理，但是有可能使优势个体在交叉变异之后出现退化，会降低算法的效率。因此，可以在每一代的交叉和变异过程中，保留一定比例的优秀个体，不进行交叉变异，直接作为子代进入下一代中。

在算法迭代过程中，每一代会有多对个体进行交叉，多个个体进行变异，在每一次交叉和变异之前，计算个体适应度值，将个体按照适应度值从大到小排序，保持前5% (比例可以根据具体问题进行调整，但不宜过大)的个体不变，在交叉和变异中，只对后95%进行交叉和变异。这种保留优势个体的策略可以有效地避免上一代到下一代以及交叉变异过程中的退化，提高算法性能，并且保留的只是一小部分优势个体，不会使算法成为随机搜索算法。

4. 案例分析

秦皇岛市留守营镇拟在某处拟建立一个快递代收点，方便周边村民收发快递，拟建立的快递代收点及其周围的12个村落位置信息见表1。

为提高快递员的配送效率，现要为快递员设计一条最短的配送路径，从快递代收点出发，经过每个村庄一次，然后回到出发点。该问题可用遗传算法进行求解。为方便处理数据，将各点坐标[x,y]简化为，具体求解过程如下

① 编码。针对本问题，采用实数编码，种群个体X的染色体编码为1-13的一个排列，代表一条路径，路径长度是的函数，记。

② 设置适应度函数。个体X的路径长度越短，适应度值大，所以可以将适应度函数设置为路径的

负相关函数，根据问题的具体数据，将适应度函数设置为。

③ 交叉。由于交叉之后要保证个体仍然为一个排列，所以采用两点交叉。例如，两个个体的染色体分别为X和Y，对应位置的基因如图1所示，通过MATLAB中的unidrnd()函数产生1~13之间的一个随机整数作为X与Y的随机交叉点，如该随机交叉点为3，即X的基因7和Y的基因2的位置，找到Y中基因7的位置和X中基因2的位置，将X的基因7与Y的基因2互换，X的基因2与Y的基因7互换。

④ 变异。针对个体X的变异，随机产生两个不同的变异点，将两点的基因互换。

用MATLAB软件编写相应程序，设置种群规模M = 100，进化代数为G = 300。采用标准遗传算法，即确定的交叉概率和变异概率，经过多次实验也难以找到适合的交叉和变异概率求出最优解。采用本文改进的遗传算法，通过几次实验，确定(6)式交叉概率和(7)式变异概率中的系数分别为。经过300次的迭代，得到的最优路径为：1→13→9→8→7→6→11→10→12→2→5→3→4→1。随着种群的进化，最优路径变化过程如图2所示。

最大路径长度和平均路径长度随迭代次数的变化如图3所示，上方为最大长度，下方为平均长度。可以看出，最长路径和平均路径变化趋势接近一致，最终逐渐趋于稳定。实验表明，改进的遗传算法可以较好地解决过早收敛、局部收敛等问题，从而得到全局最优解。

表1. 快递代收点及村落位置信息表

图1. 染色体交叉示意图

图2. 各代的最优路径图

图3. 最大/平均路径长度变化图

5. 结语

本文建立了快递路径优化问题的数学模型，介绍了遗传算法的一般步骤，针对标准遗传算法的缺陷进行改进，并结合实例对改进算法的可行性进行验证，为以后路径优化问题及遗传算法的研究提供了借鉴。改进的算法虽能避免过早收敛或局部收敛等问题，但设计的算法求解速度有待提高，这将是下一步研究的重要内容。

基金项目

东北大学秦皇岛分校大学生科创基金项目，项目编号CX16505。

文章引用

郑丽娜,王岩焱,罗融宇,童旭,梁欢. 基于改进遗传算法的快递路径优化问题的研究
Study on Delivery Route Optimization Based on Improved Genetic Algorithm[J]. 应用数学进展, 2016, 05(03): 516-522. http://dx.doi.org/10.12677/AAM.2016.53062

参考文献 (References)