基于Multi-Agent的应急物资储存点布局优化研究

田德红，何建敏，孙海信

引 言

地震、海啸、食物中毒以及传染病等灾难发生的时间、地点及程度等都是无法预测的，尽管我国在减灾防灾方面做了巨大的努力，但是重大突发事件仍然时有发生，如何加强对突发事件的应急处理能力，是需要迫切解决的问题。应急系统能否顺利完成救援任务首先需要有效可靠的物资存储保障系统支持。从有效性方面来说，救援单位只有在正确的时间、地点及时地接收到充足的应急物资，才能更好地发挥救援能力。从可靠性方面来说，在救援过程中应急物资的存储点一直是需要重点保护的目标，如果应急物资存储点布局不合理，很容易遭受灾难的侵蚀而导致大量物资在存储和运输过程中损失，对救援造成严重的影响。因此结合救援地区的地形、交通运输条件和安全情况，对应急物资的储存点进行合理的布局和配置，以最少的成本保证救援单位应急物资的需求，是保证救援顺利进行的重要条件。

应急物资储存点布局优化属于选址问题，对于选址问题的研究国外早在20世纪初就已经开始了。Alfred Weber率先提出了单一物流配送中心的选址问题[注]Weber A.Theory of the location of industries[M].Chicago:University of Chicago Press,1929.，随后Hoover等也对配送中心选址问题进行了研究[注]Hoover E M.Location theory and the shoe leather industries[M].Cambridge:Harvard University Press,1937.。在此基础上，大量的模型被相继提出用于研究选址问题，如P-中值方法[注]Hakimi S L.Optimum locations of switching centers and the absolute centers and medians of a graph[J].Operations Research,1964,12(3):450.、启发式方法[注]Kuehn A A,Hamburger M J.A heuristic program for locating warehouses[J].Management Science,1963,9(4):643.、集覆盖模型[注]Roth R.Computer solutions to minimum-cover problems[J].Operations Research,1969,17(3):455.、P-中介问题模型[注]Murray A T,Gerrard R A.Capacitated service and regional constraints in location-allocation modeling[J].Location Science,1997,5(2):103.、整数规划模型等[注]Aikens C H.Facility location models for distribution planning[J].European Journal of Operational Research,1985,22(3):263.，之后有关选址问题的研究方法不断改进并且逐渐趋于成熟。我国相关的研究虽然起步较晚，但是研究成果大量涌现，近年来对于选址问题的研究也逐渐融入了一些新的理念，开始从库存战略、运输战略、服务战略等不同方面采用不同的方法来深入研究选址问题。例如，税文兵等通过库存持有成本对传统选址模型进行修正，建立了考虑库存成本的配送中心选址模型并进行求解[注]税文兵,叶怀珍,张诗波.考虑库存成本的配送中心动态选址模型及算法[J].公路交通科技,2010,27(4):149.;赵斌等根据聚类算法的思想考虑了运输距离限制的双配送中心选址问题[注]赵斌,王媛,李珍萍.带距离限制的双配送中心选址方法[J].物流技术,2011,30(1):69.;董开帆等为了提高物流系统的服务水平，对具有经济性和时效性的配送中心选址问题进行了研究[注]董开帆,干宏程,张惠珍.考虑经济性和时效性的配送中心选址模型研究[J].上海理工大学学报,2013,35(4):336.;汤希峰等针对传统选址模型忽视物流服务水平的情况，建立了物流成本最小并且服务可靠度最大的配送中心多目标优化模型[注]汤希峰,毛海军,李旭宏.物流配送中心选址的多目标优化模型[J].东南大学学报:自然科学版,2009,39(2):404.。另外，随着Multi-Agent技术的发展，选址问题的动态特征开始引起人们的关注，一部分学者开始通过仿真方法研究选址问题。例如，崔国山等基于Agent研究了机场应急资源动态调配问题[注]崔国山,韩松臣,朱新平.基于Agent的机场应急资源动态调配研究[J].现代交通技术,2009,6(2):78.;杜艳平等基于Agent方法研究了铁路货运站布局优化问题[注]杜艳平,贾利民,赵云云,等.基于Agent-人元模型的铁路货运站布局调整方法[J].物流技术,2010,29(16):49.;王亚良等通过Multi-Agent技术研究了应急物资的储备和调度[注]王亚良,金寿松,董晨晨.应急物资储备选址与调度建模研究[J].浙江工业大学学报,2014,42(6):682.;周庆忠提出了基于Agent的油料保障调运模型，但是并没有对具体选址问题进行研究[注]周庆忠.基于Agent的信息化作战油料保障调运模型[J].兵器装备工程学报,2016,37(3):49.。国内对于选址问题的模型求解效率研究也很多，学者们通过不同的方法对选址模型进行求解，以增加算法的效率。如杨春周等通过粒子群优算法降低了物流配送中心选址问题计算的复杂度[注]杨春周,战希臣,王慧锦.军事物流配送中心选址模型的构建[J].计算机仿真,2012(5):19.;李东等采用基于时间约束的启发式算法将多阶响应的物流中心选址模型转化为可行子问题进行求解[注]李东,匡兴华,晏湘涛,等.多阶响应下军事物流配送中心可靠选址模型[J].运筹与管理,2013(1):147.;李绍斌等通过遗传算法得到了多配送中心选址问题的最优解[注]李绍斌,杨西龙,李耀庭,等.基于遗传算法的多军事物流配送中心选址决策[J].物流技术,2015,34(21):213.。另外，有的学者考虑了应急物资配送的设施和路段失效等不确定因素对选址的影响。如李东等将物资配送中设施失效时的应急配送成本作为决策目标的一部分对物流配送中心选址问题进行了研究[注]李东,晏湘涛,匡兴华.考虑设施失效的军事物流配送中心选址模型[J].计算机工程与应用,2010,46(11):3.;谢文龙和魏国强研究了不确定战时情景下的军事物流配送中心选址问题[注]谢文龙,魏国强.基于情景分析的军事物流配送中心选址模型[J].计算机工程与应用,2015,51(8):255.。

通过以上分析可以看出，应急物资选址问题的研究多集中于算法的应用和改进，忽略了应急物资存储的需求特征。具体来说，首先应急物资的存储布局相对于普通物资更加强调保障性，经济性和利益性并不是需要重点考虑的问题；其次，应急物资的存储布局需要保证应急物资调运的时效性，需要多个部门有效配合从而尽量满足救援需要；最后，应急物资存储所处的环境具有多变性和不确定性，各类灾害发生时往往会对外部环境产生一定的影响，从而使应急人员无法准确判断事态的发展。这些特征决定了应急物资的储存点布局具有不同于普通物流储存点的要求，因而需要考虑更加符合实际的储存点布局优化策略。由于应急物资储存点选址问题并不是由某一部门单独完成，不同的部门对于应急物资储存点布局的考虑角度并不是完全相同的，因此要满足应急物资储存布局的优化必须保证应急物资供应、需求和指挥等多个部门的协同配合。只有各部门协同配合，才能使应急物资存储点布局同时满足保障性、时效性等特征，并能够应对环境不确定性带来的影响，保证应急物资体系完整有序。从文献综述中可以看出，现有研究很少有学者考虑到多个部门对选址问题的共同影响，忽略了各部门协同作用对应急物资储存点布局优化的影响。针对以上问题，本文一方面基于救援环境考虑多种因素对储存点布局问题的共同影响，另一方面通过Multi-Agent技术对多个部门之间进行协同，对应急物资储存点布局优化问题进行研究。

一、 基于Multi-Agent的应急物资储存点布局优化模型

(一) 流程设计

Multi-Agent强调自主性和协调性，一方面各个Agent独立运行，另一方面全部Agent还是一个整体，协同处理问题。根据资料和实际情况，本文分别从应急物资保障Agent和需求Agent的角度确定应急物资储存点的影响因素，然后应急物资保障Agent和需求Agent的决策者根据自身需求分别对影响因素的重要程度进行打分，指挥Agent对打分结果进行统计归纳，并将结果以及对方Agent的打分策略返还给应急物资保障Agent和需求Agent的决策者，决策者得到统计结果后，根据对方Agent的打分策略，修改自己的打分，并将新的结果提交给指挥Agent进行统计归纳，如此重复直到应急物资保障Agent和需求Agent的意见统一。得到影响因素的权重之后，指挥Agent根据各影响因素的权重确定目标函数，通过遗传算法对模型所提出的目标函数进行优化求解，最后根据运算结果确定最佳布局方案，具体流程如图1所示。

图1 基于Multi-Agent的应急物资储存点布局优化流程

(二) 模型中的影响因素

应急物资储存点布局属于长期规划的基础建设，建设地点一旦选定则很难改变，因此在决策中通常要坚持综合性、协调性、经济性和战略性等原则，全面考虑到众多影响因素。本文的模型主要涉及应急物资保障Agent和需求Agent，他们关注的重点不尽相同，应急物资保障Agent更加侧重布局的成本，而应急物资需求Agent更加在意物资是否安全送达以及到达时间，但总的来说可以概括为成本要素、安全要素和时间要素三个方面。

1. 成本要素

建设成本：将应急物资储存点建在不同的地区会导致建设成本方面的差异，从储存点安全的角度考虑，需要尽量避免建设在地形复杂、地貌崎岖的偏远位置，而在城市中心地区建设成本显然更高，因此需要权衡处理储存点安全性和建设成本问题。

运输成本：运输成本的多少直接由运输距离决定，通过合理的布局，可以使应急物资储存点与各需求点的距离尽力缩短，降低运输成本。

2. 安全要素

运输损耗：由于突发事件等因素对运输环境造成的不确定性影响，应急物资在输送过程中损失的可能性较大，因此物资从储存点到需求点所需的时间越长，其损耗的可能性越大。

储存损耗：由于应急物资储存点必然要建设在容易发生突发事件的区域附近才能保证其时效性，因而应急物资储存点极易受到突发事件的影响，储存点的物资损耗由储存点的地形地貌和地理位置等因素决定，由于这些因素不容易直接量化，需要领域专家进行打分。

3. 时间要素

保障距离：应急物资储存点与需求点之间的距离直接决定运输的时间，距离越远则运输时间越久，物资需求的保障越难得到满足。

交通情况：短距离的应急物资主要通过公路运输，因此交通情况主要由储存点附近的道路数量以及每条道路的宽度和拥堵程度等道路质量决定，交通情况同样能够影响物资运达需求点的时间。

(三) Multi-Agent 模型

1. 应急物资保障Agent和需求Agent

打分策略：应急物资保障Agent和需求Agent的决策者首先会通过资料和实际情况根据自身需求总结影响应急物资储存点布局和配置的影响因素,并将其方案提交给指挥Agent，当指挥Agent统计归纳并筛选出重要的影响因素，保障Agent和需求Agent的决策者根据自己的经验对给出的影响因素进行打分。

打分修改策略：对于保障Agent和需求Agent的决策者而言，其打分修改策略主要受到自己原来的打分方案、自己所在Agent打分方案的平均值以及对方Agent打分方案的平均值影响。因此以应急物资保障Agent为例，其打分方案的修改模型可以用下式表示：

(1)

其中,Sij表示决策者i对影响因素j提出的打分方案，Xj和Yj分别表示应急物资保障Agent和需求Agent所有决策者对于影响因素j打分的平均值。α,β,μ分别表示自己原先提出的打分方案、应急物资保障Agent所有决策者打分方案的平均值,以及应急物资需求Agent所有决策者打分平均值对本方案修改的影响程度，并且α+β+μ=1。

最终修改策略：应急物资保障Agent和需求Agent的决策者在接收到最终修改通知时，可以按照平时的修改策略对方案进行修改。

2. 指挥Agent

统计打分方案：指挥Agent主要对所有决策者的打分方案进行统计，如果所有方案中各影响因素权重排序一致，结束打分过程，如果方案中各影响因素权重排序不一致，指挥Agent将打分结果返回应急物资保障Agent和需求Agent的决策者重新打分。本文采用平均值法对方案中的各影响因素打分进行统计处理。

确定影响因素权重：重复打分过程直到应急物资保障Agent和需求Agent所提交的方案各影响因素权重排序一致或者重复次数达到设定的阈值，指挥Agent将最后一次所有决策者的打分方案平均值作为最终结果，确定各影响因素权重。

确定目标函数并求解：指挥Agent根据各影响因素的权重将多目标优化问题化简为各目标线性加权的单目标函数，根据目标函数以及约束条件，通过遗传算法确定目标函数的最优解，从而优化应急物资储存点布局。

(四) 应急物资储存点布局优化模型

mi(i=1,2,…,m)为一系列可供选择的应急物资储存点，如果选定在备选点i建设储存点，则mi=1，否则mi=0；si表示储存点i所储存的物资数量；nj(j=1,2,…,n)为应急物资需求点；dj表示应急物资需求点j所需要的物资数量；rij表示物资储存点i运输到需求点j之间的运输关系，如果存在运输关系，则rij=1，否则rij=0；cij表示物资储存点i到物资需求点j单位距离单位物资数量的运费；fi表示应急物资储存点i需要的建设费用；lij表示物资储存点i到需求点j的距离；vij表示物资储存点i到需求点j的运输速度；ηi表示物资储存点i的交通状况，具体由该交通部门的专家确定，基准值为ηi=1，若交通状况好于基准值,则ηi>1，反之则ηi<1；gij表示物资储存点i到需求点j单位距离单位数量的运输损耗程度；hi表示物资储存点i的安全程度，由该领域专家确定，1-hi表示物资储存点i的损耗程度；wk(k=1,2,…,6)为由Multi-Agent 模型协同决定的各影响因素的权重。

根据应急物资布局优化模型中的影响因素，本文的目标包括成本、安全和时间三个方面，成本函数F1由建设成本和运输成本决定，成本函数越小越好；安全函数F2由运输损耗和储存损耗决定，损耗越小越好；时间函数F3由保障距离和交通状况决定，时间函数越小越好。F1、F2和F3的表达式如下：

(2)

(3)

(4)

因此，应急物资储存点布局优化模型的目标函数为：

minF=F1+F2+F3

(5)

约束条件为：

(6)

(7)

其中，约束条件(6)保证了各受灾地点的需求都能得到满足，约束条件(7)表示确保应急物资的需求只能由一个物资储存点满足，不能同时由多个储存点共同满足。

二、 遗传算法相关理论

遗传算法(Genetic Algorithms，简称GA)，是一种借鉴生物界自然选址和遗传学机理上的迭代自适应概率性搜索算法。它由Holland在1962年提出，到20世纪60年代末期，该算法已经形成了数学框架，能够实现简单形式上的计算。到目前为止，遗传算法常用于优化问题的求解中，尤其是在目标函数比较复杂或者比较抽象的问题里，遗传算法有独特的优势。而且，遗传算法还可以求解多目标的优化问题。

遗传算法基于自然选择与遗传的原理，把生物进化过程中适者生存法则与种群内部染色体的信息随机交叉变化机制联合在一起，具有能够对全局进行快速寻优特点的搜索算法。它和传统的搜索方式截然不同，不再完全依靠梯度信息，而是基于对自然进化过程的学习模仿，采取新的人工进化方法，进而对目标群体实施随机搜索直至得到最优解。遗传算法把问题域中的每一个可能的解当作是生物种群里的一个染色体或是个体，然后对每一个染色体进行编码变成符号串，按照达尔文研究的生物进化论中自然选择和淘汰的进程，根据遗传学中选择、交换与变异对种群进行随机重复的操作。然后对每一个染色体依据事先设定的目标适应度函数实施评价过程，按照适者生存、优胜劣汰进化法则，持续直到获得相对较优的群体，并且在全局同时开展一致的搜索方法搜索优化种群里的最优个体，进而获得达到条件规定的最优解。

(一) 遗传算法优化过程

遗传算法在完整的进化生命周期中，具体的遗传操作有着随机性的特征，然而其并非完全随机搜索，在寻优过程中它根据历史信息进而推断整合在新一代里能够提升期望值的点集。通过迭代次数持续的增加，种群不断进化最终找到一个与环境最相适应的个体，即为所求问题的最优解。标准的遗传算法可以用8元组来描述：GA=(C,E,P0,M,Φ,Γ,Ψ,T)，其中C是个体的编码方法，E是个体适应度评价函数，P0是初始群体，M是群体大小，Φ是选择算子，Γ是交叉算子，Ψ是变异算子，T是遗传运算终止条件。这些算子的不同构成了不同的遗传算法，但其构造过程都相似，根据Holland(1992)遗传算法基本步骤如下：

(1) 选择编码策略，把参数集合转换成位串结构空间；

(2) 定义适应度函数；

(3) 确定遗传策略，包括选择群体大小，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数；

(4) 随机初始化生成初始种群；

(5) 计算群体中个体的适应度值；

(6) 按照遗传策略，运用选择、交叉和变异算子作用于群体，生成下一代群体；

(7) 判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回。一般的，最优的染色体并不是一定在最后一代中才产生，因此从进化过程开始，就一直记录保存最好的染色体，一旦在新一代群体中找到更好的，就用这个染色体替换之前最好的染色体，进化过程结束之后，得到的这个染色体表示的就是该目标函数的最优解。

(二) 遗传算法求解位置选址问题

应急物资存储点布局问题，也就是在空间内选择合适的仓库点以使成本在未来应急救灾时能达到效果最佳。因此，应急救灾的核心实际上就是应急物资存储点的选址问题。

根据选址问题目标区域的特点可以将选址问题分为连续选址、网格选址和离散选址等。连续选址的备选区域一定是在一个平面上，选址的数目可能会有很多，其余的结构不做关注，非常经典的运用是物流企业中心仓库的选址；网格选址的备选区域也是一个被详细分解成很多面积相等(通常为正方形区域)的平面，需要选择的地址数目是有限的，但是也非常大，相对经典的运用是仓库中很多种物品被安排在不同的存放位置等；离散选址的备选区域和以上不同，它是聚集了全部的离散备选地点，数目通常有限而且不是很多，这类模型一般最符合现实情况，最经典的运用是企业仓库中心的选址研究问题等。

根据选址成本分：是可行成本或者最优成本方案的探索；是总成本最低化的研究或者成本最大值最低化的探索；需要选址的设施有没有关联；是静态或者动态；是固定或者可变权重等选址问题。

根据选址约束分为有能力约束和无能力约束的选址问题,如果新设施能力无限制，那就是后者,反之就是前者。这里需要注意的是对不可行区域约束作出说明：针对那些在目标范围内，有些位置不应当规划成选址地点，那么这个选址问题相应地隐含不可行区域的约束。在本文中，我们的目标函数就是带约束的优化问题，保证了各受灾地点的需求都能得到满足，以及确保应急物资的需求只能由一个物资储存点满足，不能同时由多个储存点共同满足。

应急物资的存储仓库是应急抢险中物资的主要来源，其位置的好坏直接影响物资的供给速度。物资仓库的位置选择不是一个简单的过程，一般要经过数次的反复选择，才可以挑出相对最优的地点。并且物资仓库的建造，不但会对该地区的经济产生直接作用，并且会给该地区的交通环境以及生态环境带来一定的影响，因此规划时要考虑各个方面的作用。

(1) 运输成本：对于物资仓库的供求双方来说，物资仓库与它们之间的距离直接对物资仓库和运输手段(公路运输或铁路运输)、运输方式(整车运输或零担运输)等造成影响。

(2) 时间约束：在规划物资仓库过程中，一方面应该顾及实际的交通状况，物资仓库与实际的交通枢纽有没有离得很近或在未来有没有可能在物资仓库旁边修建交通中心；另一方面，要同时把交通规划作为选址布局内容的一部分，仅仅顾及物资中心而没有考虑交通布局，那么物资仓库的布局最终失败的可能性很大。物资仓库的出入库需要大量的运输过程，要考虑需求的迫切性，对于紧急事件，仓库物资的运送有一定的时间要求。因此，时间约束是考虑一个物资仓库建立起来的重要因素。

在普通的位置选址中，比如物流仓库的选择，主要以运输成本为主。在讨论物流仓库的建造地址时，通常会在各中心城市位置已知的情况下，统计调研各城市的需求主体位置，结合这些位置选择部署仓库的位置和个数。图2展示了遗传算法在位置选址优化方面的仿真结果。

图2 遗传算法位置选址仿真图

由图2可知，随着迭代次数的增加，位置的适应度函数值逐渐收敛。由于我们的优化目标是运输到各需求点位置的总距离，因此，应该是求解目标的最小值，以降低运输成本和时间成本。在已知需求节点的位置时，优化后得到5个物资存储点的位置，仿真结果如图3所示。

图3 位置选址结果

三、 应急物资储存点布局优化模型求解

在基于Multi-Agent 的应急物资储存点布局优化模型中，涉及的影响因素非常多，备选位置数据量相当庞大，传统的穷尽搜索方法将花费大量的运算时间，严重耽误有效时机。因此本文基于Holland的传统遗传算法，同时满足对不同量纲多目标优化问题的求解需求，并且确定航空弹药储存点布局最优组合以及每个储存点的航空弹药储备量，一方面通过优序数法定义适应度函数，另一方面对染色体进行分段编码，以此对传统遗传算法进行改进，具体步骤如下：

(1) 染色体编码。遗传算法不能直接处理问题空间的参数，而只能处理以染色体编码形式表示的个体，因此，要使用遗传算法就必须把优化问题的参数形式转换成染色体编码的表示形式。传统遗传算法将要解决的目标问题化简为一段染色体编码，而对于本文来说需要解决的目标函数中不仅包括应急物资储存点位置的选择，也包括储存点与需求点之间应急物资运输方案的确定，因此本文将每条染色体的编码分为两段。前一段采用二进制方式对染色体进行编码，表示应急物资储存点布局方案。首先对所有备选地址按顺序进行编号，如果在i备选地址建立储存点，则该序号对应的染色体编码为1，反之则该序号对应的染色体编码为0。后一段采用随机数方式进行编码，表示应急物资需求点与储存点之间的运输方案，每个需求点有且只有一个储存点进行物资供应保障，对需求点按顺序进行编号，如果需求点j的物资由第i个储存点供应，则该序号对应的染色体编码为i。由两段编码组成的染色体长度为所有应急物资储存点备选地址的数量m与需求点数量n之和。

(2) 初始种群。初始种群是选择、交叉和变异等操作进行的前提，为了使算法能达到最优，遗传群体应具有一定的规模，但又为了保证计算效率，规模又不能太大。本文在这里釆用随机生成的方式来构建初始种群，假如需要从m个备选地址中选取z个应急物资储存点，在初始化染色体时，先生成z个1，再将m-z个零随机插入到排列中，这样就构成了一条染色体的前一段编码，然后每个需求点随机选择一个前一段编码中已经建立的储存点，并将该储存点的序号作为该需求点的编码，这样就生成了染色体的后一段编码。反复进行该过程，则可以生成初始种群。

(3) 确定适应度评价方法。适应度评价方法是用来评估个体优劣程度的遗传操作，是整个遗传算法中的关键部分，好的适应度评价方法能够快速地将非最优个体进化到最优个体，能够解决过早收敛与过慢结束的矛盾。因为本文目标函数有三部分，并且每部分的量纲都不相同，因此本文所采用的适应度评价方法为优序法，这种方法的优点是可以将各个染色体的优劣排序直接映射到适应度函数上，有效避免了量纲不同的问题。

(8)

定义i=j时，aijl=0。则aij=∑paijp为第i个方案与第j个方案在所有目标下相互比较所得到的优序数，反之aji为第j个方案与第i个方案在所有目标下相互比较所得到的劣序数。进一步称Ki=∑jaij为第i个方案与其他所有方案在所有目标下相互比较所得到的总优序数，Hj=∑iaij为第i个方案与其他所有方案在所有目标下相互比较所得到的总劣序数。

由优序数性质可知，第i个方案的总优序数越大，则其总劣序数就越小，因此可以根据Ki的大小顺序排列所有方案的优劣次序，可以证明，如果优化问题存在最优方案，则最优方案必定排列在最前面，如果不存在最优方案，则排列在最前面的必定是非劣方案。

(4) 选择操作。精英策略操作目前已经被证实是一种能够保证遗传算法找到全局最优解的最有效策略，因此本文将采用赌轮选择法与精英策略相结合的方式进行选择操作。首先将每代群体中的个体按适应度值由大到小排列，排在第一位的为精英，直接将它复制到下一代，并排在第一位，下一代的其他个体需要根据前代群体的适应度值，采用赌轮选择法产生。具体来说，如果群体中所有的个体的适应度值的总和为∑Fiti，其中Fiti表示第i条染色体的适应度值，则该染色体被选择的概率就是其适应度值所占的比例Fiti/∑Fiti，这样就可以保证选择最优的个体生存至下一代。

(5) 交叉操作。交叉操作也是遗传算法中最重要的步骤，是为了得到具有新染色体的子代，而将父代进行染色体的交叉。这样子代就在一定程度上继承了其父代特性的同时，又出现了一些新的个体特征，从而使得种群中不断出现新个体。由于本文的染色体由两段编码组成，并且后一段编码受到前一段编码的影响，因此在每次实验中，本文按概率决定哪段编码进行交叉，概率的大小由编码的长度决定，前段编码的交叉概率为m/(m+n)，后段编码交叉的概率为n/(m+n)。本文的交叉方法采用单点交叉法，即任意不重复地从群体中选择两个个体，以交叉概率判断某两个待交叉染色体是否进行交叉，直到所有的个体都被选到。若进行交叉，则以概率判断是哪段编码进行交叉。若是前段编码进行交叉，则随机生成一个不超过备选储存点长度的数字为交叉点，将待交叉的两个染色体以被选中的交叉点之前的结构进行互换，生成两个新的个体，然后对后段编码中与前段编码矛盾的部分进行修改，随机选择一个已经建立的储存点，将该储存点的序号作为新的编码；若是后段编码进行交叉，则随机生成一个超过备选储存点长度且不超过染色体长度的数字为交叉点，将待交叉的两个染色体以被选中的交叉点之后的结构进行互换，生成两个新的个体。

(6) 变异操作。关于变异操作，一般是首先在群体中随机选择某个染色体，通过较小的概率随机地改变其结构体中某个点的染色体表达，或者某个染色体段的表达，使其与原先的染色体结构发生变化，从而产生新的更优个体，保持种群的多样性。本文的变异算子同样采用单点变异方法，基本过程与交叉操作类似，即先以变异概率判断某个待变异染色体是否进行变异，若进行变异，则判断哪段编码进行变异。如果前段编码进行变异，随机生成一个不超过备选储存点长度的数字为变异点，对其编码按位取反，并对后段编码中矛盾的部分进行随机修改；如果后段编码进行变异,则随机生成一个超过备选储存点长度且不超过染色体长度的数字为变异点，将该编码随机修改为原来储存点之外的储存点序号。

(7) 终止规则。当种群的进化代数达到预设的最大迭代次数时，计算终止，输出此时的方案即为最佳方案。

四、 案例仿真结果与分析

假如在受灾区域内，有20个需要供应的地点，根据专家实地考察和定性、定量分析，确定10个备选地址用来布局合理个数的应急物资储存点，假设各受灾地点需要的应急物资数量以及各受灾地点到任意备选地址之间的距离均已知，在10个备选地址中选取若干个地址作为应急物资储存点，对20个受灾地点进行应急物资保障，求最优布局方案。

为了对应急物资储存点布局进行优化，首先需要根据Multi-Agent模型确定应急物资布局影响因素的权重，由于Multi-Agent模型需要根据专家的打分进行协同修改，案例仿真分析中无法获取专家打分方案，因此本文首先通过程序模拟各领域专家打分结果，然后模拟Multi-Agent的协同过程给出最终的影响因素权重，以测试Multi-Agent模型的有效性。通过程序产生的应急物资保障Agent和需求Agent初始打分结果见表1。

表1 各影响因素最终权重

表1给出了经过Multi-Agent的协同之后得到的影响因素权重，可以看出由于本文的打分结果为随机产生，因此各影响因素之间的权重几乎相同，从而证明Multi-Agent模型具有有效性。由于随机产生的影响因素打分经过Multi-Agent协同作用之后权重几乎相同，因此对于仿真案例的优化不采取经过Multi-Agent协同之后的权重，而是由程序随机产生应急物资储存点布局影响因素权重，以保证影响因素权重之间具有差别，从而使实验结果更加明显。影响因素的权重虽然对应急物资储存点布局结果具有决定性的作用，但是并不影响验证模型的有效性。由于本文案例缺乏实际情景的支撑，不能获取易受灾区环境的各项实际数据，因此本文涉及易受灾区环境的参数同样由程序随机产生，模拟了一种应急物资储存点布局环境，包括每个受灾地点应急物资需求数量、受灾地点与应急物资储存点备选地址之间的距离、储存点备选地址交通状况和安全程度。另外，为了方便计算，本文将一些有关公共属性的参数设置为常数：每个储存点的建设成本均设置为1，单位距离单位数量的应急物资运输成本均设置为1、单位距离单位数量的应急物资运输损耗程度均设置为5%、任意储存点到受灾地点之间的运输速度均设置为1。

给定了模拟的易受灾区环境以及影响因素的权重，指挥Agent便可以通过本文改进的遗传算法对提出的应急物资储存点布局优化模型进行求解，设置遗传算法相关参数如下：目标存储点数量为5，程序最大迭代次数为200，种群大小为100，交叉概率为0.6，变异概率为0.01，前段编码交叉概率、变异概率均为1/3，后段编码交叉概率、变异概率均为2/3。运行程序，得到每代最高的适应度如图4所示。从图4中可以看出，随着迭代次数的增加，算法逐渐收敛，最优方案首次出现在105代，最优的染色体编码如表2和表3所列。

图4 遗传算法最优适应度

备选地址12345678910是否建址1011110000

表3 后段染色体编码

通过前段染色体编码可知，本次给定的20个应急物资储存点备选地址中，最终选择第1、3、4、5和6号备选地址进行储存点的建设可以保证应急物资储存点布局得到优化。另外，每个受灾地点所需求的应急物资由哪个储存点进行补给也可以从后段染色体编码中获得。根据最优的应急物资储存点布局方案以及补给方案，每个储存点所需要存储的物资数量可以确定，具体见表4。

表4 应急物资存储数量

通过以上实验结果可以看出，在实际操作中，只要易受灾区的环境确定，便可以邀请领域专家根据Multi-Agent模型协同确定储存点布局影响因素的权重，并通过本文所改进的遗传算法对储存点布局优化问题进行求解。

五、 结 论

本文针对应急物资储存点布局优化问题，充分考虑到应急物资保障Agent和需求Agent的独立性以及对于储存点布局的影响因素的不同认知，通过指挥Agent对整个Multi-Agent进行协同，构建了基于Multi-Agent的应急物资储存点布局优化模型。另外，本文同时考虑了成本、安全和时间等多种影响因素对应急物资储存点布局的共同影响，由于多种影响因素所产生的多个目标函数量纲都不相同，不能通过传统的遗传算法进行求解，因此，本文一方面通过Multi-Agent协同作用对目标函数进行权重化处理，另一方面通过优序数法来描述适应度，提出了一种基于Multi-Agent和优序数法改进的遗传算法对模型进行求解。从仿真实验结果可以看出，本文的模型可以很好地对应急物资储存点的布局进行优化并确定每个储存点的应急物资储备量，可以为提高应急救援系统的保障能力提供一定参考。