改进遗传算法在应急物资调运模型中的应用

宋树洋

（北京航空航天大学经济管理学院，中国 北京100000）

应急物资的运输与配送问题是应急物流主要研究的问题之一，它也是应急物流中最为关键的一个环节，而在一般情况下，应急物资调运问题就会转化成一般的车辆路径问题。车辆路径问题是一个典型的组合优化问题，求解十分困难，截至当下，仅有一些相对较小规模的问题能够保证被求解到精确的最优解。各国的学者通过大量的实践和理论证明得出结论，精确算法在求解大规模VRP问题时非常不适合，而启发式算法在求解这类问题时显示出非常大的优势，并成为近年来此领域应用最多的方法。其中遗传算法以其优秀的寻优能力为众多学者所青睐。

1 遗传算法

遗传算法(Genetic Algorithm，简称GA)是由Holland教授首先提出的，它是一种建立在群体遗传学基础和自然选择上的随机、并行搜索算法。求解车辆调度问题，使用GA搜索算法十分理想，但使用GA算法时面临的一个难以解决的问题就是如何防止其“早熟”收敛。

在遗传算法提出以来，来自世界各地的众多学者提出了多种方法提高GA的性能：Rudolhp G提出为保证算法的收敛性，使用精英选择策略保持群体中最好个体的方法[1]；马欣等提出了PEGA算法，即使用单亲进化的遗传算法，它提高算法收敛速度的方法，是利用来自父体有效边的信息，保留使用最小边，这样来进行个体的进化[2]；马均水等提出大变异策略，这个策略可以表述为，如果某一代里的大多数个体集中在了一起，此时使用一个较大的变异概率（远大于通常）执行一次变异操作，这样使之独立产生多个新个体，可以让整个群体脱离早熟[3]；以上方法只解决了算法部分问题，而且采取的改进方式比较复杂，一般以高运算量并降低算法效率为代价解决遗传算法过早收敛的问题。

遗传算法优化分析：

早熟收敛一直是遗传算法中存在的主要问题，算法一旦出现早熟收敛，将无法得到问题的最优解，这个问题主要原因是遗传算法自身的优化能力有限，不得不需要多次迭代才能够找到最优解，迭代过程中发生早熟将很难跳出。本文主要研究如何避免早熟收敛问题，下面将在交叉概率一定的(pc=0.8)的前提下进行研究讨论。

1）变异算子的改进

对于遗传算法易“早熟”的问题，其中主要原因之一是遗传算法中最重要的遗传算子——交叉算子使群体中的染色体具有局部相似性，从而会导致搜索停滞不前，因此变异算子的存在就变成克服算法早熟的最有效手段。

2）传统变异算子的缺陷

定义1 在优化问题求解过程中得到的最优解，其对应染色体上的每个基因称为这个染色体基因位上的有效基因。

定义2 种群中，染色体同一个基因位上的等位基因具有多样性，即染色体相同的基因位上既有“1”又有“0”，或者说在某一个基因位上，基因全为“1”(或“0”)的概率P(“1”)(或P(“0”))为：

P（“0”）或P（“1”）＝0 （1）

J.Craig Potts等人的研究得出结论，在GA搜索中，在遗传算法运行过程中发生早熟收敛的原因主要是有效等位基因缺失[4]。选择策略的目的是在于加快基因的收敛过程，但是交叉算子作用于个体却不可能产出新的基因，所以这无法避免地会使得在特定基因位上的某一类基因比例下降，最终会导致这个基因位上可能的有效基因的缺损。因此，为了预防早熟收敛，在不知道有效基因位的情形下，如果变异算子可以让染色体统一基因位上保持等位基因的高多样性，那么将极大地防止有效基因的缺失，进而在最大程度上避免遗传算法运行过程中的早熟收敛。

定理1 一般方法使用的变异算子没有办法保证保持染色体同一基因位上等位基因的多样性。

证明：在一个种群规模为N的种群中，如果假设在染色体的第j个基因位上有n1个“0”和n2(n2=N-n1)个“1”，那么这个基因位上的全部基因经过变异操作（取反操作）后变为同一个基因的概率为：

此式与式（1）矛盾。

3）二元变异算子

一般来说，一般的变异算子作用是进行的是一元操作（取反操作），即是操作数需要且仅需要一个基因。如果染色体是由二进制字符串组成的，对于此类染色体，我们可以在遗传算法搜索中引入数字技术里的二元逻辑算子，优化传统的变异方式，即产生了二元的变异算子：同或/异或。

此种变异操作与传统的取反变异有所不同，这种变异操作中需要两个个体（染色体）参与，例如：

从逻辑上容易知道，在这个运算之后得到的两种逻辑状态是互补关系，即如果一个为“0”，另一个一定为“1”。换句话说在一个基因位上的基因经过变异操作之后，这个基因位上至少有一个“0”和一个“1”同时存在，但是并不会出现都是“0”或者都是“1”的情况。

基于二元变异算子的遗传算法流程与原遗传算法流程相同，只在变异操作时有所区别。

2 应急物资调度模型

2.1 问题的提出

应急资源的调度需要考虑的问题有很多，其中包括运输工具的调度、运输路线的设计，还有资源调度的速度和效率。突发事件发生后，如果造成了大面积的受灾，救灾物资需求点的数量很多，那么在短时间内制定出合理的物资配送计划将会十分困难。

应急资源调度问题可以抽象为图1所示：

图1 震后应急资源调度问题抽象模型

2.2 问题情景描述

假设中国西南部某地发生了一定强度的地震，地震地带处于山地丘陵地形内，震后造成交通线路阻断，围绕震中形成了几个受灾较为严重的区域，区域内交通能力恢复迅速，区域与区域之间处于半隔离状态。处于各受灾区域的政府救助力量迅速组织人员和工具分别进行难民的搜寻和治疗，并以最快的速度恢复通信能力，与上一级政府组织取得联系并发出求救信息。上级地震灾害救助领导组织汇集各区域需求，利用空中设备(直升机)将救灾物资空投至各区域，其中包括医药、食物、饮用水、救灾车辆及工具等具体物资，另各救灾区域内的救灾应急小组抓紧组织收集可利用的机动性运输工具，在各区域内形成配送中心，根据各需求点需求进行救灾物资配送和伤员运输。

2.3 模型的建立

2.3.1 模型的假设条件

假设一：应急资源调度中心与各物资需求点、各物资需求点之间的运输距离已知，可以作为常数。

假设二：受灾地点及各应急资源调度中心根据其地理位置及交通便利情况完成最优区域划分，形成局部地震救灾单元，单元区域内可以以最快速度进行物资分配及救灾响应。各单元地震灾区资源运输费用有限可加，总和为地震总灾区资源调度费用。

假设三：救灾物资运送车辆所在停车场与应急物资调度中心之间的距离可以忽略不计。

假设四：所有的需求点之间都可以相互通行，即此路径网络是完全路网。

假设五：所有的受灾地点的资源需求，在时间和数量方面都能够得到满足。

假设六：物资从调运车辆上卸载的时间忽略，不予计算。

2.3.2 问题的数学模型描述

应急资源车辆调度问题的数学模型可以概述如下：对于单一地震灾害救助单元，把各物资需求节点和应急资源调度中心组成一个图G(V,E)，其中V是图中所有节点的集合，Vo∈V是应急资源调度中心，其余节点为物资需求节点；E为图中所有边的集合，eij∈E为节点i，j之间的边，图G为无向图，即边eij是无方向的。有n个受灾地向救灾指挥中心请求物资配送，物资储备中心与受灾节点、受灾节点之间的广义运输费用(距离)为Cij(i，j=0，1，2，…，n)，物资储备中心编号为0，受灾节点编号为1到n，要求为各地震应急救助区域指派运输车辆k，并确定车辆运输路线，使得总运输费用最低。

对于模型图中的每条弧(i，j)(i≠j)和车辆k定义变量Xijk：

应急资源调度模型如下：

目标函数：

以上数学模型中各表达式含义如下：

式（3）此式为目标函数，其表示总的路径代价(运输费用、距离或时间)最低；

式（4）保证了有且仅有一辆物资配给车辆从物资配送中心出发；

式（5）保证了每个物资需求点净流量为0；

式（6）保证了有且只有一辆物资配给车辆最终回到调度中心。

2.4 模型求解

根据前面已经建立的应急物流车辆调度数学模型，可将此问题进一步描述如下：在各地震救灾单元区域内，从配送中心派出车辆进行救灾，每一辆车可为若干受灾点载送物资，车辆行驶路径应保证是距离最短的那条，最终要求出总消耗最低的路径线路和最低费用(距离)。

2.4.1 求解步骤描述

遗传算法优化算法(GA-plus)在求解应急资源调度问题时的基本步骤如下：

Step1：设定初始参数。主要是遗传迭代次数、初始种群大小、交叉和变异概率；

Step2：随机产生初始种群，利用适应度函数计算种群适应度；

Step3：根据适应度按轮盘赌方法和最佳个体复制选择下一代染色体；

Step4：根据交叉概率，对染色体（候选解）进行顺序交叉操作；

Step5：根据变异概率，对染色体（候选解）进行变异操作(二元变异)；

Step6：产生新的种群，利用适应度函数计算种群适应度，记录新种群中的最佳个体；

Step7：判断是否满足遗传算法迭代次数，若满足则停止并输出优化结果，否则转Step2对新种群继续操作。

2.4.2 案例分析

本文采用Matlab编程，对有30个节点、50个节点和75个节点三种情况进行试验分析。

（1）30节点时

各算法参数设置为：

GA迭代步数为2000，种群规模为100，交叉概率为0.8，变异概率为0.2；

GA-plus迭代步数为2000，种群规模为100，交叉概率为0.8，变异概率为0.2。

（2）50节点时

各算法参数设置为：

GA迭代步数为3000，种群规模为150，交叉概率为0.8，变异概率为0.2；

GA-plus迭代步数为3000，种群规模为150，交叉概率为0.8，变异概率为0.2。

（3）75节点时

各算法参数设置为：

GA迭代步数为7000，种群规模为200，交叉概率为0.8，变异概率为0.2；

GA-plus迭代步数为7000，种群规模为200，交叉概率为0.8，变异概率为0.2。

图2 GA搜索结果

图3 GA-plus搜索结果

图4 GA搜索结果

图5 GA-plus搜索结果

图6 GA搜索结果

图7 GA-plus搜索结果

3 结束语

通过实验过程以及以上图示结果，可以对GA-plus优化方法得出以下结论：

（1）GA-plus的全局优化度相对较高，最终解显示出更优水平，并且平均优化度也比较高；

（2）GA-plus的鲁棒性强，趋于优化解的概率较高；

（3）GA-plus的计算时间较长，在算法效率上有待提高，但在一定程度上克服了过早收敛的早熟问题。

本文针对应急物资调运问题建立了数学模型，对模型求解过程中使用的启发式算法进行了优化和改进，实验结果表明改进后的算法增强了对问题的求解能力，一定程度上克服了算法过早收敛的问题。本文对于应急物资调运问题的研究对于实际问题也具有借鉴意义

［1］Rudolph G. Convergence analysis of canonical genetic algorithms [J]. Neural Networks, IEEE Transactions on, 1994,5(1):96-101.

［2］马欣,朱双东,杨斐.旅行商问题(TSP)的一种改进遗传算法[J].计算机仿真,2003,4:36-37.

［3］马钧水,刘贵忠.改进遗传算法搜索性能的大变异操作[J].控制理论与应用,1998,15(3):404-408.

［4］Potts J C, Giddens T D, Yadav S B. The development and evaluation of an improved genetic algorithm based on migration and artificial selection [J]. Systems,Man and Cybernetics, IEEE Transactions on, 1994,24(1):73-86.