张全全，谭文安,2

(1.南京航空航天大学 计算机科学与技术学院，江苏 南京 210016;2.上海第二工业大学 计算机与信息学院，上海 201209)

基于遗传-禁忌算法的应急救援前摄性调度优化

张全全1，谭文安1,2

(1.南京航空航天大学 计算机科学与技术学院，江苏 南京 210016;2.上海第二工业大学 计算机与信息学院，上海 201209)

应急救援活动本身具有不确定性和复杂性的特点。为了对救援活动的顺利开展进行支持，文中以最小化救援损失为目标，研究应急救援前摄性调度优化问题。首先对问题进行界定，对问题进行符号化表示，并由此定义出资源约束下的救援计划调度优化模型。根据救援活动的紧急程度分配优先级，并定义出优化目标函数。该问题是强NP-hard的，由此根据现代优化算法的特点设计出遗传禁忌启发式算法。最后通过对某事故救援数据进行分析模拟对提出的算法进行说明。结果表明，该算法可以有效对优化模型进行求解。该研究可为突发事件的应急救援活动的开展提供决策支持。

前摄性调度；遗传算法；禁忌算法；应急救援

0 引 言

伴随着经济的高速增长，各类安全事故频发，给经济发展和社会稳定造成了不小的影响。及时有效的救援可以最大程度挽救生命财产的损失。为了应对各种突发事件，国家和企业在应急救援方案的制定和实施上投入了大量人力、物力和财力。由于突发事件固有的不确定性，想要高效地开展救援计划并非易事[1]。因此，合理科学的应急救援计划对于优化资源利用率、保证救援活动的开展具有很大的指导意义[2-3]。

前摄性调度是指基于同类突发事件的历史数据，在救援活动不确定性的基础上，预先对应急救援活动进行规划并形成救援计划[4-5]。通过对历史资料的分析，可以结合救援目标，合理地进行推测，进而形成救援活动的计划[6]。

文中基于已发生事件的各项数据，结合对未来事件的预测，以最小化救援损失为目标，提出了资源约束下的应急救援计划。

1 问题描述

对于某个突发事件，其救援过程可以表示为一个AoN网络[7]，每个节点代表救援活动，活动间的连线代表活动间的逻辑关系。救援活动i的救援时间为di，其对资源的需求为ri，资源总量为R。在没有资源约束的情况下，救援活动计划为U0=(u01,u02,…,u0n)。

2 优化模型

救援计划调度优化模型如下所示。

(1)

s.t.

(2)

uj≥ui+di,i∈Vi

(3)

(4)

ui≥0,i=1,2,…,n

(5)

其中，FT为已完成活动集合；PT为正在进行的活动集合；Vi为活动i的紧后集合。(1)为目标函数，即最小化因计划调整而导致的损失；约束条件式(2)将计划调整时已完成救援活动的开始时间定义为初始计划开始时间；(3)用来约束活动之间的逻辑关系；(4)是资源约束，即某一时刻各救援活动所需要的资源总量不能大于现有资源总量；(5)为决策变量的定义域约束。

3 遗传禁忌混合算法

文献[8]被认为是遗传算法(GA)与禁忌算法(TS)进行混合的理论基础。文中将遗传变异操作后得到的每一条染色体作为TS的初始解Sini,然后从邻域中选一个可行解Snei，从Sini移动到Snei,再从Snei开始继续搜索,直到得到最优解。因为TS中引入了禁忌表,所以可避免循环和陷入局部最优。特赦准则为当一个移动被禁忌,但该移动的动作能使当前解优于禁忌搜索过程中搜索到的最优解时,则忽视禁忌。

文中在遗传算法中结合禁忌操作,经过遗传操作产生新一代后,对子种群采用TS快速搜索到每一编码链附近的局部最优点,可以避免陷入局部极小[9-14]。

3.1 编 码

编码：采用符号编码，该编码由n个活动开始时间组成。

适应度函数：目标函数的值越大，表明其适应度越低。

初始种群的产生：在不违反逻辑关系的前提下，安排一个活动序列，该序列由n个活动组成。

3.2 选 择

文中采用如下选择策略：将每代群体中的候选解按适应度由大到小排列，将排在第一位的最佳个体直接复制进入下一代；下一代群体的另外n-1个候选解则根据前代群体的n个个体的适应度，计算上代群体中所有个体适应度的总和，再计算每个个体的适应度所占的比例，作为其被选择的概率。

3.3 交 叉

对每一次的候选解，按一定的交叉概率p1进行交叉操作。

(1)从待交叉个体集合中选定一个染色体。

(2)产生0～1之间的随机数r1，决定染色体是否交叉。如r1

(3)依随机产生1～n之间的随机数r2和r3，将两个位置的元素交换。

3.4 变 异

变异概率为p2的变异算子实现步骤如下：

(1)产生0～1之间的随机数r3，判断是否需要变异。如果r3

(2)随机产生1～n之间的随机数r4和r5，逆转r4和r5两点的基因排列顺序。

3.5 禁忌邻点

1)在某个时间发生变化时，在未发生的活动集合中，忽略资源约束的前提下，利用动态关键路径法计算其余活动的时间窗。

2)从未发生的活动集合中随机选择一个活动，使其满足逻辑和资源约束。

具体算法步骤如下：

(1)初始种群,计算种群中个体的适应度。

(2)根据适应度按最佳个体复制和轮盘赌方法选择下一代染色体。

(3)按交叉概率p1执行交叉。

(4)按变异概率p2执行变异。

(5)对变异后的染色体进行筛选，对不符合逻辑约束的m个候选解进行过滤，然后根据适应度对新的种群补充m个染色体，转步骤4。

(6)对新产生的种群进行禁忌搜索。

①分别将种群中的每个染色体作为禁忌搜索的初始解，独立进行如下步骤。

②计算初始解Sini的目标函数值Lossini。定义禁忌算法的终止条件，即探测可行解的总数N。初始化禁忌表，令计数num=0。

③生成Sini的一个邻点Snei，计算其函数值Lossnei，检查该点是否位于禁忌表内，若是转步骤⑤；否则转步骤④。

④令Snei为当前解，更新禁忌列表，若Lossnei

⑤若Lossnei

⑥判断是否符合终止条件n≥N，若成立转步骤⑦；否则转步骤③。

⑦返回搜索到的满意解及其目标函数值。

(7)判断是否满足遗传算法迭代次数，若满足，在种群中筛选Loss值最低的染色体，停止算法并输出优化结果，否则转步骤3对新种群继续操作。

4 实 验

根据某事故数据(见图1)提取出实验所需各项指标，如表1所示。

表1 活动计划表

图1 算例的AoN网络图

忽略资源约束的情况下，各活动可以在由关键路径决定的最早时间执行，此时造成的损失为0，如图2所示。考虑资源约束(本例中设同一时刻资源总量为55)，如图3所示，则可能在某一时间发生活动对资源需求总量超过了资源上限，此时就需要对原来的活动序列进行调整，如表2所示。

利用前述的遗传禁忌算法，可以求得该救援项目的满意解为：

(0，1，1，2，2，10，3，3，4，9，4，7，13，14，9，16，15，21)

此时的损失值Lossbest为88。

图2 无资源约束下的活动执行

图3 资源约束下的活动执行

5 结束语

文中以最小化救援损失为目标，对救援活动进行前摄性调度优化，并由此形成救援计划。通过对问题的界定提出了调度优化模型。设计了遗传禁忌算法，结合遗传算法与禁忌算法的优点，求得问题的最优解。最后通过一个算例说明算法的可行性。

活动执行无逻辑约束的可以同时进行，但是由于资源约束的存在使得原本可以同时开始的活动面临先后执行的问题。此时根据权重进行排序，先满足优先权高的活动，执行完后再为优先权低的活动进行资源调配，这样造成的损失最小。该研究可为应急救援的开展提供决策支持。

[1] 黄 钧,杨文国,朱建明.应急资源体系研究状况与主要研究问题[J].中国应急管理,2009(2):10-13.

[2] 曹 杰,杨晓光,汪寿阳.突发公共事件应急管理研究中的重要科学问题[J].公共管理学报,2007,4(2):84-93.

[3] 刘 茂,王 炜.应急资源优化管理研究的主要问题[J].中国应急管理,2007(7):31-34.

[4]LambrechtsO,DemeulemeesterE,HerroelenW.Atabuse-archprocedurefordevelopingrobustpredictiveprojectschedules[J].InternationalJournalofProductionEconomics,2008,111(2):493-508.

[5]VonderSVD,DemeulemeesterE,HerroelenW.Proactiveheuristicproceduresforrobustprojectscheduling:anexperimentalanalysis[J].EuropeanJournalofOperationalResearch,2008,189(3):723-733.

[6]SchattemanD,HerroelenW,VonderSVD,etal.Amethodologyforintegratedriskmanagementandproactiveschedulingofconstructionprojects[J].JournalofConstructionEngineering&Management,2008,134(11):1-28.

[7]ElmaghrabySE.Activitynets:aguidedtourthroughsomerecentdevelopments[J].EuropeanJournalofOperationalResearch,1995,82(3):383-408.

[8]GloverF,KellyJP,LagunaM.Geneticalgorithmsandtabusearch:hybridsforoptimization[J].Computers&OperationsResearch,1995,22(1):111-134.

[9]NowickiE,SmutnickiC.Afasttaboosearchalgorithmforthejobshopproblem[J].ManagementScience,1996,42(6):797-813.

[10] 王 凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.

[11]LiangXu,HuangMing.Applicationoftabusearch-parallelgeneticalgorithmforjob-shopscheduling[J].ComputerIntegratedManufacturingSystem,2005,11(5):678-681.

[12] 徐 宁,李春光,张 健,等.几种现代优化算法的比较研究[J].系统工程与电子技术,2002,24(12):100-103.

[13] 李大卫,王 莉,王梦光.遗传算法与禁忌搜索算法的混合策略[J].系统工程学报,1998,13(3):28-34.

[14] 王赛一,王成山.遗传禁忌混合算法及其在电网规划中的应用[J].电力系统自动化,2004,28(20):43-46.

Proactive Scheduling Optimization of Emergency Rescue Based on Hybrid Tabu-genetic Optimization Algorithm

ZHANG Quan-quan1,TAN Wen-an1,2

(1.School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics, Nanjing 210016,China;2.School of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China)

Emergency rescue and relief is complicated and uncertain.Proactive scheduling is essential to provide decision support for emergency rescue.In this paper,first the problem is defined and signified,thus defining the rescue plan scheduling optimization model under the restriction of resources.According to the degree of emergency for rescue activities,the priority is assigned and the optimal objective function is defined.The problem is NP-hard.Then a genetic-tabu heuristic algorithm is designed in accordance with the features of modern optimal algorithms.Finally,it is elaborated by analysis and simulation of accident rescue data.Experiment shows that the algorithm can effectively solve the optimal model.The research can be able to provide the decision support for emergency rescue of accident.

proactive scheduling;genetic algorithm;tabu algorithm;emergency rescue

2015-09-17

2015-12-23

时间：2016-05-25

国家自然科学基金资助项目(6127036)；江苏省高校自然科学研究面上项目(15KJB520005)；上海第二工业大学重点学科(XXKZD1301)

张全全(1989-)，男，硕士研究生，研究方向为大规模应急资源布局与调度；谭文安，教授，CCF高级会员，研究方向为软件构架技术、协同计算、服务计算与知识管理、信息化工程及其支持环境研究等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1709.054.html

TP39

A

1673-629X(2016)06-0119-04

10.3969/j.issn.1673-629X.2016.06.026