基于演化算法的资源包投放优化

邓海鑫，艾丽蓉

(西北工业大学计算机学院，陕西 西安 710129)

0 引言

现实世界的优化问题往往属于多目标优化问题，与单目标优化不同，多个相互竞争目标的优化结果得到的是一组可行解，被称作Pareto最优解集。由于缺少喜好信息，Pareto最优解集中找不到一个解比另一个解更好［1］。传统的方法，例如分支定界法、分治法会得到全局优化［2］，但是需要大量的运行时间，或者不能解决实际问题。如果为了避免这样的情况而使用传统的局部搜索方法［3］，则很容易陷入局部优化。由于不能改变NP-hard问题的时间复杂度，现代启发式方法把重点放在避免局部优化这样的问题上，其另一个特点是推广性、鲁棒性很高。因此，对于资源包投放优化问题这种NP-hard问题，应该设计更为高效的启发式算法来解决它。

资源包投放优化问题即如何用最少的资源包满足更多区域对于资源包的需求。资源包投放优化问题在现实活动中有着重大的实际应用意义。例如:2008年以来，我国陆续遭遇百年不遇的冰雪灾害和惨绝人寰的5·12汶川大地震之后，冰雪灾害和大地震中，救援包的及时高效的投放，可以为抗震救灾的胜利奠定坚实的基础。通过资源包投放优化问题的研究，设计合理的优化算法，以最快的反应能力在灾害影响的范围内发放救援包，并使发放的救援包可以覆盖最大的区域。在军事上资源包的投放优化问题也有着重要的应用。例如:战斗机轰炸目标时，如何用最少的弹药打击更多的目标是衡量一次战斗行动成功与否的重要标准。通过设计高效的优化算法，计算出合理的炸弹投放点，实现用最少的弹药完成打击目标的目的，这对提高国家的国防实力也有极大的意义。

1 算法设计及实现

为了更高效地运用演化算法解决资源包的投放问题，本文方法首先对目标区域进行区域分类，然后应用演化算法，最后对落点的结果进行线性规划求解。区域分类的目的是将各个目标区域进行划分从而剔除大部分空白区域，这样在各个小区域类中应用算法求解资源包的落点将更加高效，最后因为各个小区域类中的落点相互影响着最优落点，所以通过线性规划再将各个区域类中的落点整合成整体的最优落点。下面是算法的具体实现步骤。

1.1 区域分类

(1)区域Di和Dj具有关系R指这2个区域属于同一类，则可用图G表示这些区域和区域间的关系，计算图G的邻接矩阵W=(wij)n×n。如果dis(a，b)＜CP(CP在此例中为10)，则 wij=min{dis(a，b)|a∈Di，b∈Dj}，否则 wij=0;其中 dis(a，b)表示 a 和 b两点间的距离。

(2)利用深度优先或宽度优先算法，遍历图G，求G的连通分量。

(3)每个连通分量的顶点集合，作为一类区域。

通过对区域进行分类，可以对每个区域类分别使用演化算法，这样可以极大地缩短实验程序运行的时间，同时也可以减少实验误差。

1.2 应用演化算法

演化算法［7］是基于生物演化思想发展起来的一类随机搜索技术，它们是模拟由个体组成群体的学习过程，其中每个个体表示给定问题搜索空间的一点。演化算法从一个初始的群体出发，通过随机选择、变异和重组过程，使群体演化到搜索空间中越来越好的区域。选择过程是群体中适应性好的个体比适应性差的个体有更多的复制机会，交叉算子将父辈信息结合在一起并将它们遗传到子代个体，变异保证在群体中产生新的个体。演化算法这种以生物智能或自然现象为基础的随机搜索算法具有比数学规划方法更大的优越性，使得演化算法已经成为人工智能领域的研究热点。

1.2.1 演化算法的描述

首先用演化算法的数学形式描述资源包投放优化问题:

设NP为种群大小，在整个求解过程中保持不变，不妨设可行域:D={(x1，x2，…，xn)|xl≤xi≤xh，i=1，2，…，n}，其中 xl与 xh代表每个个体可取的分量的范围，而xi代表种群中某个个体的一个分量。例如:在资源包的投放优化问题中每个分量都是一个落点的坐标。设x(i)(k)表示第k代种群中第i个个体，xj(i)(k)表示这个个体的第j个分量。

第k代种群集合可以表示为:

演化算法的主要操作如下:

(1)建立初始种群。

一般选可行域D上具有统一分布的NP个伪随机数构成初始种群。例如，取:

其中r(i)为［0，1］上均匀分布的随机数。

(2)变异操作。

对第k代种群中的每一个个体，从种群中随机抽取3个不同的个体x(r)(k)、x(s)(k)、x(t)(k)，通过如下变异操作产生试验向量u(i)(k+1):

其中F∈［0，1］为缩放因子，且一般为固定的，用于控制向量x(r)(k)－x(s)(k)的缩放，从而确定在距点x(t)(k)多远位置生成试验向量u(i)(k+1)。

(3)交叉操作。

对第k代种群G(k)中的每一个向量x(i)(k)及其变异得到的试验向量u(i)(k+1)做交叉操作，得到第k+1代向量v(i)(k+1)。

如果r≤CR，则 v(i)(k+1)=xi(k)，否则 v(i)jjjj(k+1)=uj(i)(k+1)，其中CR为预先给定的交叉概率，rj为随机生成的［0，1］上的随机数(j=1，2，…，n)。

最后检查向量v(i)(k+1)是否在可行域D中，即xl≤vj(i)(k+1)≤xh，用［xl，xh］中的随机值代替这个分量，即vj(i)(k+1)=xl+r*(xh－xl)，r为［0，1］上均匀分布的随机数。

(4)选择操作。

演化算法按照贪婪准则将当前种群中的目标向量与由它所产生的试验向量比较，选择目标函数值较优的放入下一代种群，函数f()为计算适应度的目标函数，如果f(v(i)(k+1))≤f(x(i)(k))，则 x(i)(k+1)=v(i)(k+1)，否则使 x(i)(k+1)=x(i)(k)。

这种选择方法保证了下一代中所有个体都不次于当前代中对应的个体。

1.2.2 应用演化算法进行资源包落点计算

1.对演化算法中的各个参数进行定值，如种群数目 NP=8，交叉概率 CR=0.6。

2.适应度函数。整个演化迭代过程总的来说就是搜索最优适应度个体的过程，种群个体为在这个区域类中所有资源包投放点的坐标，而且投点与落点存在误差，假设某个个体即染色体内的资源包个数为m，这个区域类中的区域个数为t，采用如下方法计算出个体适应度。

(1)通过蒙特卡洛算法得出每个资源包落入区域类中第 j个区域的概率为 p1j、p2j、…、pmj。

(2)计算不符合要求的概率值(假设满足区域需求的资源包数目为3)。

①没有资源包落入区域的概率为:

②当求只有一个资源包落入该区域时的概率可以通过公式表示为:

③当求有两个资源包落入该区域时的概率可以通过公式表示为:

(3)计算区域类中某个区域满足资源包落入需求的概率为:pj=1 －v1j－v2j－v3j，其中 j=1，2，…，t。

(4)设一个变量count的初值为0，依次比较pj与应用中要求的概率P，其中j=1，2，…，t。如果pj大于P，则count自加;最后若count等于t，则此个体的适应度为1，否则适应度为count/t。

3.对每个区域类分别使用所描述的演化算法。

1.3 线性规划求解

(1)生成各个区域类规划信息，假设某个区域类中有区域个数k个，则规划信息如表1所示。表1中为在第k个区域类中，满足投放要求的区域数为i时的资源包个数。

表1 规划信息

(2)对各个区域类进行线性规划求解，求出当满足从各个区域类中取出满足投放要求的区域数之和为6时，资源包个数最少的情况即为实例的结果。如共有d个区域类，从每个区域类中取出的区域数的要求为a1+a2+…+ad=value时(其中a1为从第一个区域类中取出的满足要求的区域数，value为总的要求的区域个数)的值为最小时即为所求结果。

2 实验结果及分析

将以上算法应用于资源包投放问题的一个特定的实例中，实例如图1所示。

图1 实例图

在图1中11个平面区域内(即目标区域)投放资源包，使得其中6个平面区域以不小于概率P获得所需的资源包数量，同时使得所需的资源包数量尽可能地少(大圆的半径为30 m，小圆半径为20 m)。假设P为0.8，每个区域满足需求的资源包数目为3，求出满足条件的最少投放资源包的数目和其落点。

应用前面所设计的算法得到的投放信息如图2所示。

图2 演化算法投放信息结果图

若将上述方法中的演化算法改成传统的遗传算法，得到投放信息如图3所示。

图3 遗传算法投放信息结果图

通过实验结果分析可知，使6个平面区域以不小于0.8的概率获得3个资源包时应用演化算法后只需要16个资源包投放点。如果使用遗传算法得到的结果将差于演化算法的结果，大概需要17个资源包投放点，而且算出结果的速度也会非常慢。这是因为演化算法利用种群中个体间的差分向量对个体进行扰动，实现个体变异，而遗传算法则是直接对个体进行变异，其运算时间较长且收敛较慢，使结果非常容易向不好的方向变化。

演化算法所具有的内含并行性使它能以较少的计算量获得较大的收益，而且与传统搜索算法一般要使用导数等其它辅助信息相比，演化算法只使用目标函数，并在增加效率和减小开销之间进行权衡，因此演化算法在处理资源包投放优化这类NP-hard问题中非常高效。而区域分类和线性规划更高效地运用了演化算法，使资源包投放问题得到了很好的解决。

3 结束语

本文详细介绍了如何运用演化算法实现对资源包投放的优化，使用演化算法处理该问题可以解决使用传统遗传算法时运算时间长和收敛较慢的缺陷。实验表明该算法在处理资源包投放问题中是非常高效的，但是演化算法自身存在参数敏感问题，选用合适的参数范围可能要经过多次实验分析，因此设计参数自适应的演化算法来处理资源包投放优化问题将是下一步的研究重点。

［1］张利彪，周春光，马铭，等.基于极大极小距离密度的多目标微分进化算法［J］.计算机研究与发展，2007，44(1):177-184.

［2］刘立英.分支定界法的推广应用［D］.青岛:青岛农业大学，2011.

［3］Hakimi S L.Optimum locations of switching centers and the absolute centers and medians of a graph［J］.Operations Research，1964，12(3):450-459.

［4］Mark S Daskin，Edmund H Stern.A hierarchical objective set covering model for emergency medical service vehicle deployment［J］.Transportation Science，1981，15(2):137-152.

［5］Richard Church，Charles ReVelle.The maximal covering location problem［J］.Papers of the Regional Science Association，1974，32(1):101-l18.

［6］张文修，梁怡.遗传算法的数学基础(第2版)［M］.西安:西安交通大学出版社，2003.

［7］刘波，王凌，金以慧.差分进化算法研究进展［J］.控制与决策，2007，22(7):721-729.

［8］汪彤，李云强.基于近邻策略的旅行商问题求解［J］.计算机工程与应用，2009，45(28):67-68，71.

［9］孟红云，张小华，刘三阳.用于约束多目标优化问题的双群体差分进化算法［J］.计算机学报，2008，31(2):228-235.

［10］吴亮红，王耀南，周少武，等.双群体伪并行差分进化算法研究及应用［J］.控制理论与应用，2007，24(3):453-458.

［11］江雷，陈贤富.一种衡量TSP问题种群多样性的新方法［J］.微电子学与计算机，2004，21(8):10-12.

［12］陶利民，郭俊恩.改进遗传算法在求解TSP问题上的应用研究［J］.计算机工程与应用，2009，45(33):45-47.

［13］张启义，邱国庆，寇学智，等.两阶段遗传算法在求解TSP问题中的应用［J］.解放军理工大学学报:自然科学版，2011，12(1):79-83.