基于遗传算法的人员疏散路径优化控制

张惠彬 黄顺祥 刘峰 关彩虹

(1.中国人民解放军北部战区疾病预防控制中心 沈阳 110030； 2.中国人民解放军防化学院 北京 102205)

0 引言

大气污染化学事故一直威胁着人民生命财产安全，同时严重影响着生态环境。在2006—2010年间，我国共发生危险化学品事故490起，共造成879人死亡，其中较大事故70起，死亡310人，重大事故5起，死亡96人。事故发生后，对人员及时疏散是控制事故损失的最重要的措施之一，只有及时有效的进行人员疏散才能大量减少人员伤亡。NISHINARI等[1]运用蚁群算法对人员疏散路径的优化问题进行研究，并进行了仿真实验。叶启文[2]对城市轨道交通突发事件的人员疏散问题进行研究，并运用遗传算法进行目标优化。薛李生辉等[3]运用粒子群算法研究公共场所突发事件人员疏散问题。靳宁[4]将蚁群算法与Agent理论相结合，将人员疏散过程中的物理因素与人员的社会行为进行结合研究。

遗传算法GA (Genetic Algorithm)是进化算法EA (Evolutionary Algorithm)中最有代表性的一类，这种算法旨在通过模拟自然界生物的遗传进化过程，找到最优解。20世纪70年代美国密歇根大学的HOLLAND[5]教授出版的著作以及JONG[6]发表的博士论文最早提出了遗传算法的概念体系，80年代是遗传算法发展最迅速的时期，不管是应用研究还是理论研究都成了热门课题，从1985年开始，每两年都要召开一次遗传算法国际会议(ICGA)，并成立了国际遗传算法协会(ISGA)。1989年，GOLDBERG[7]对遗传算法进行了全面剖析，撰写《搜索、优化和机器学习中的遗传算法》一书，总结了遗传算法的主要研究成果。2000年，HAN等[8]提出了量子遗传算法( Quantum Genetic Algorithm)，该算法将量子的态矢量表达形式引入遗传编码中，用量子旋转门来实现染色体基因的调整，这一调整为该算法在计算机上的执行提供了扎实的理论基础。2009年，章琳等[9]提出了基于遗传算法的多小波自适应去噪算法，该算法能通过遗传算法自适应地寻求图像去噪后的最小均方差。

本文拟通过遗传算法对优化模型求解，并对算法进行适当调整，以期得到最理想的疏散路径。

1 人员疏散路径优化模型的建立

1.1 建模基本思想

影响人员疏散的因素主要有三方面，一是疏散路线的距离，二是道路的通行难易程度，三是化学毒剂的大气扩散情况。计算疏散路线的距离，可以把整个区域每一个路口设为一个节点，通过分段计算各节点间的距离，就能得到整条疏散路径的距离。道路通行难易程度可以看成是路径的通行修正系数，主要由日常车辆行驶速度决定。化学毒剂的大气扩散因素是最重要的影响因素[10]，直接影响人员的伤亡，所以是最应该避开的因素，如果避不开，也要选择扩散浓度低的路径。进行路径优化前首先就要进行大气扩散模拟[11-12]，应用扩散模拟的浓度场数据，运用毒负荷模型进行毒性计算，选取伤亡概率最小的路段通行。通过以上三方面因素的影响，定义疏散当量长度，该当量长度最小的路径就是最优路径。

1.2 数学模型的建立

1.2.1 节点矩阵

从事发点到疏散安置点的整个区域中，有n个节点，第i节点的坐标为(xi,yi)，事发点坐标为(x1,y1)，从第i个节点到第j个节点之间的距离为dij，通行难易程度为kij。

D=[dij]

D表示节点间的距离矩阵，用矩阵表示为：

(1)

从矩阵中可以看出，当节点i等于节点j时，dij=0，另外，在实际通行时并不是所有的节点间都有路段连接，那么在计算时可以把这些节点间的距离值设成较大的值，比如，节点i和节点j之间不能相连，那么dij=Na，这样就能确保最优路径不会出现无法连通的路段。

同理，设通行难易程度矩阵为：

K=[kij]

(2)

1.2.2 目标函数

定义当量长度L，该当量长度主要受三方面因素影响，分别为路径长度，通行难易程度，以及大气扩散的影响，在三因素影响下，当量长度最小的路径就是最优路径。

目标函数表示为：

(3)

dij用节点间的坐标来确定，即：

(4)

kij由两节点间的距离和日常行车速度vij来确定，即：

(5)

λ表示用罚函数的形式把大气扩散的影响引入到模型参与计算，主要由节点的扩散浓度来决定，这里引入轻度危害浓度阈值ca，中度危害浓度阈值cb，重度危害浓度阈值cc，致死危害浓度阈值cd，那么：

(6)

2 基于遗传算法的优化求解方法

对于人员疏散的路径优化问题，没有现成的算法设计可用，需要有针对性地进行算法设计，从而实现算法的有效运行，找到最优路径。算法设计完成后，应用Matlab软件编写源代码，进行计算求解。

2.1 染色体编码设计以及初始化种群

在编码设计时，主要考虑了两种编码设计，一种是[0-1]之间的随机数编码，一种是[1-n]之间的自然数随机编码，都属于浮点数编码。自然数随机编码简单直观，便于理解，就是将染色体的自然数顺序确定为路径经过节点的顺序，起点1和终点n保持不变。随机数编码就是在[0-1]之间随机产生n个随机数，但是第一个基因为0，第n个基因为1，以保证起点和终点不参与遗传，这些随机数按数值大小升序确定节点，比如：

对于染色体V=[0 0.012 0.176 0.765 0.489 0.243 0.315 1]

对应的路径就是L=[1 2 3 7 6 4 5 8]

应用随机数编码进行数值实验时，实验结果出现了走回头路的现象，因为这些随机数每个都不一样，所以染色体基因都不同，即使经过最大遗传代数迭代，依然如此。所以，随机数编码不适用人员疏散的路径优化。

自然数编码简单直观，中间节点随机产生，本文采用自然数编码进行路径优化。并随机产生100个个体作为初始种群。

2.2 适应度函数的建立

适应度函数一般都建立在目标函数的基础上，本文建立的适应度函数同样以目标函数为基础。通过分析目标函数可知，每个个体的目标值均为正值，因此，考虑到适应度函数的简单适用原则，建立适应度函数为：

(7)

其中，L(i)表示种群中第i个个体的目标函数取值。

2.3 选择算子

计算出种群中个体的适应度之后，就要进行选择，目的是选择适应度高的个体进行下一步的遗传操作。常用的选择算子有轮盘赌选择、随机竞争选择、最佳保留选择、无回放随机选择等，本文采用轮盘赌选择算子进行计算。其计算过程如下：

首先，计算种群中每个个体的适应度总和Fz：

(8)

其次，计算种群中每个个体的选择概率pi，计算公式如下：

(9)

2.4 交叉算子

交叉算子通过模拟生物个体之间的交配，产生新的个体。常用的方法有单点交叉、两点交叉与多点交叉、均匀交叉以及算数交叉等。本文选用单点交叉产生新的个体，不选用多点交叉以及其他交叉方法是由人员疏散路径优化问题本身决定的，因为多点交叉等方法对个体结构的破坏性较大，不能很好的延续母体的优点，对于路径问题，一段好的路径选择不宜设置多个交叉点，所以本文选择单点交叉算子，交叉方法如下：

2.5 变异算子

在遗传算法中，变异算子虽然是生成新个体的辅助算子，但作用却十分关键，因为变异算子能有效防止算法进入局部最优陷阱。本文选择互换变异算子，即在一定概率的情况下，在部分个体中随机指定两个有效基因互换位置，达到产生新个体的目的，变异方法如下：

A=(1 3 5 4 6 7 5 3 7 9)

随机互换位置为2和5，得到新个体B：

B=(1 6 5 4 3 7 5 3 7 9)

2.6 新个体的逻辑处理

初始种群中的个体经过交叉和变异后生成新的个体，由于这些个体都是自然数编码，所以这些生成的新个体中难免会有重复的数字，每一个新个体代表着一条新的路径，如果路径中出现重复的节点就代表着走回头路，这明显是错误的，如果这一问题不能解决就会导致计算无法收敛。这一问题的解决方法如下：

初始种群中的个体有n个基因，为了便于说明假设n=9，A0，B0为其中两个个体：

A0=(1 3 5 4 7 2 6 8 9)

B0=(1 2 5 8 6 3 7 4 9)

单点交叉后，产生新个体A1，B1：

A1=(1 3 5 4 7 3 7 4 9)

B1=(1 2 5 8 6 2 6 8 9)

互换变异后，产生新个体A2，B2：

A2=(1 4 5 4 7 3 7 3 9)

B2=(1 8 5 8 6 2 6 2 9)

这时可以看出A2，B2中均有重复的数字出现，这时采取的方法是，对于这些重复的数字，前面的数字保留，后面出现的数字变成9并且移到个体序列最后的位置。对于有n个基因的个体来说，就是把后面出现的重复数字变成n，并移到个体序列最后的位置。A2，B2经过如上操作，变成新个体A3，B3：

A3=(1 4 5 7 3 9 9 9 9)

B3=(1 8 5 6 2 9 9 9 9)

个体逻辑处理的Matlab程序如下：

%%种群中有90个个体，每个个体有13个基因，该种群变异后的逻辑重整%%

p3=ones(90,13)*13;

for i=1∶90

p2=unique(p1(i,:),'stable');

w=length(p2);

p3(i,1∶w)=p2;%重整后的新种群

end

3 数值实验

为了验证算法的可行性，在这里设计一个案例进行数值实验，该案例通过分析就可得知最优路径的大致范围，再通过算法计算最优路径，看算法能否找到该路径，从而验证算法的可行性。

3.1 实验案例设计

如图1所示，在节点1处的化工厂发生爆炸事故，大量硫化氢气体发生泄漏，在厂区内的监测设备监测到硫化氢气体浓度已经超过安全浓度阈值，且浓度迅速上升，此时主导风向为西南风，在节点1附近的群众需要立即撤离。假设经过大气扩散模拟，得到扩散区域内的浓度场分布，在各节点处的模拟扩散浓度如表1所示，可以看出2，5节点处的扩散浓度超过了重度危害浓度阈值，节点3处的扩散浓度超过了中度危害浓度阈值，6，4节点处的扩散浓度超过了轻度危害浓度阈值，人员疏散路径经过这些节点时惩罚系数λ迅速变大，导致当量长度L变大，从而被算法舍弃。

表1 节点扩散浓度

图1 疏散区域路径分布

3.2 算法求解

运用MATLAB2014a软件编写源代码，进行算法计算，其中初始种群规模100，最大遗传代数500，代差0.9，交叉概率0.7，变异概率0.05。经过500次迭代，输出结果固定，最小当量长度为97，最优路线为：1-8-9-10-12-13。图2表示500次迭代过程中解的变化以及种群均值的变化，由图中可以看出，迭代开始后解和种群均值迅速变小，且在100次迭代后保持了稳定，体现了算法的稳定性以及收敛速度较快的特点。算法选择的最优路线为：1-8-9-10-12-13。尽管疏散区域南部道路通行难度较大，但是受毒气扩散的影响较小，由于惩罚系数的限制，使选择中部或北部区域道路的路径当量长度增大，驱动算法选择南部区域的道路，体现了算法的准确性以及可行性。

图2 500次迭代后种群均值变化和解的变化

4 结论

本文对大气污染化学事故中的人员应急疏散问题进行了研究，建立了人员疏散路径优化模型，设计了关于人员疏散路径优化问题的遗传算法，并通过数值实验，验证了算法的可行性。主要结论如下：

(1)影响人员疏散的因素主要有三方面原因，一是疏散路线的距离，二是道路的通行难易程度，三是化学毒剂的大气扩散情况。本文依据这三方面影响因素，建立了人员疏散路径优化模型。

(2)建立了适用于计算人员疏散路径优化问题的遗传算法方案。其中新个体的逻辑重整方法，成功解决了算法无法收敛的问题。根据遗传算法方案，编写了MATLAB程序。

(3)通过数值实验，模拟疏散现场，发现算法能很快得到计算结果，并且迅速收敛，验证了算法的可行性和适行性。