基于遺傳-禁忌算法的應急救援前攝性調度優化

張全全，譚文安,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