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

《改进遗传算法在应急物资调运模型中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进遗传算法在应急物资调运模型中的应用宋树洋（北京航空航天大学经济管理学院，中国北京100000）【摘　要】在考虑了应急物资调运的特殊性后，改进了VRP问题求解的遗传算法，并将其应用于应急物资调运问题的求解。通过仿真计算表明改进后的算法在收敛速度等方面有很大改善。.jyqk，简称GA)是由Holland教授首先提出的，它是一种建立在群体遗传学基础和自然选择上的随机、并行搜索算法。求解车辆调度问题，使用GA搜索算法十分理想，但使用GA算法时面临的一个难以解决的问题就是如何防止其“早熟”收敛。在遗传算法提出以来，来自世界各地的众多学者提出了多种方法提高GA的性能：RudolhpG提

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

3、的主要问题，算法一旦出现早熟收敛，将无法得到问题的最优解，这个问题主要原因是遗传算法自身的优化能力有限，不得不需要多次迭代才能够找到最优解，迭代过程中发生早熟将很难跳出。本文主要研究如何避免早熟收敛问题，下面将在交叉概率一定的(pc=0.8)的前提下进行研究讨论。1）变异算子的改进对于遗传算法易“早熟”的问题，其中主要原因之一是遗传算法中最重要的遗传算子——交叉算子使群体中的染色体具有局部相似性，从而会导致搜索停滞不前，因此变异算子的存在就变成克服算法早熟的最有效手段。2）传统变异算子的缺陷定义1　在优化问题求解过程中得到的最优解，其对应染色体上的每个基因称为这个染色体基因位上

4、的有效基因。定义2　种群中，染色体同一个基因位上的等位基因具有多样性，即染色体相同的基因位上既有“1”又有“0”，或者说在某一个基因位上，基因全为“1”(或“0”)的概率P(“1”)(或P(“0”))为：P（“0”）或Ｐ（“１”）＝０（1）J.CraigPotts等人的研究得出结论，在GA搜索中，在遗传算法运行过程中发生早熟收敛的原因主要是有效等位基因缺失[4]。选择策略的目的是在于加快基因的收敛过程，但是交叉算子作用于个体却不可能产出新的基因，所以这无法避免地会使得在特定基因位上的某一类基因比例下降，最终会导致这个基因位上可能的有效基因的缺损。因此，为了预防早熟收敛，在不知道

5、有效基因位的情形下，如果变异算子可以让染色体统一基因位上保持等位基因的高多样性，那么将极大地防止有效基因的缺失，进而在最大程度上避免遗传算法运行过程中的早熟收敛。定理１　一般方法使用的变异算子没有办法保证保持染色体同一基因位上等位基因的多样性。证明：在一个种群规模为N的种群中，如果假设在染色体的第j个基因位上有n1个“0”和n2(n2=N-n1)个“1”，那么这个基因位上的全部基因经过变异操作（取反操作）后变为同一个基因的概率为：（2）此式与式（1）矛盾。３）二元变异算子一般来说，一般的变异算子作用是进行的是一元操作（取反操作），即是操作数需要且仅需要一个基因。如果染色体是由二

6、进制字符串组成的，对于此类染色体，我们可以在遗传算法搜索中引入数字技术里的二元逻辑算子，优化传统的变异方式，即产生了二元的变异算子：同或/异或。此种变异操作与传统的取反变异有所不同，这种变异操作中需要两个个体（染色体）参与，例如：从逻辑上容易知道，在这个运算之后得到的两种逻辑状态是互补关系，即如果一个为“0”，另一个一定为“1”。换句话说在一个基因位上的基因经过变异操作之后，这个基因位上至少有一个“0”和一个“1”同时存在，但是并不会出现都是“0”或者都是“1”的情况。基于二元变异算子的遗传算法流程与原遗传算法流程相同，只在变异操作时有所区别。2　应急物资调度模型2.1　问题的

7、提出应急资源的调度需要考虑的问题有很多，其中包括运输工具的调度、运输路线的设计，还有资源调度的速度和效率。突发事件发生后，如果造成了大面积的受灾，救灾物资需求点的数量很多，那么在短时间内制定出合理的物资配送计划将会十分困难。应急资源调度问题可以抽象为图１所示：2.2　问题情景描述假设中国西南部某地发生了一定强度的地震，地震地带处于山地丘陵地形内，震后造成交通线路阻断，围绕震中形成了几个受灾较为严重的区域，区域内交通能力恢复迅速，区域与区域之间处于半隔离状态。处于各受灾区域的政府救助力量迅速组