一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法
2023-06-11 18:34:16 2
一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法
【專利摘要】本發明提供了一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法，本發明是一種基於群智能的人員疏散行為仿真優化方法，主要建立與實際場景相一致的二維元胞自動機數學模型，用元胞蟻群算法對人員疏散行為進行模擬，通過人工勢能場的勢能評價標準對人員路徑進行判斷選擇，從而更加符合真實場景疏散規律，提高疏散效率，提供合理疏散方案。
【專利說明】一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法
【技術領域】
[0001] 本發明屬於智能系統建模及優化領域，具體的為一種基於勢能驅動元胞蟻群算法 的室內疏散仿真優化方法。
【背景技術】
[0002] 疏散問題可以根據疏散場景抽象成為一個複雜的大規模動態網絡，最簡單直接的 方法是利用傳統的最短路徑算法求解，但是這種算法適用於小規模靜態路網的路徑尋優， 而對於大規模動態網絡，當網絡規模增大時，算法的複雜度就會迅速增加，這種傳統的最短 路徑算法的運算能力缺陷導致無法滿足系統的需求。由於智能算法計算時間不會隨著網絡 規模的增大而明顯增加，相對傳統的最短路徑算法而言，更加適合解決建築物人員疏散這 種大規模網絡的路徑搜索問題。
[0003] 蟻群優化算法（AntColonyOptimization:AC0)是Colorni和Dorigo等在 20 世 紀90年代初提出的一種新型分布式智能仿生類算法，它模擬和借鑑了現實世界中螞蟻種 群的覓食行為特徵。螞蟻在運動時會在通過的路徑上釋放一種特殊的分泌物--信息素來 尋找路徑。當它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行，同時釋放出 與路徑有關的信息素。螞蟻走的路徑越長，則釋放的信息量越小。當後來的螞蟻再次碰到 這個路口的時候，選擇信息量較大的路徑概率相對較大，這樣便形成了一個正反饋機制。最 優路徑上的信息量越來越大，而其他路徑上的信息量卻會隨時間的流逝消減，最終整個蟻 群會找出最優路徑。該方法具有可並行性、尋優能力強、適應性強和易於其他算法結合等優 點，但也存在一定缺陷，如搜索時間長、對複雜問題的描述能力不強和容易出現搜索停滯等 等。
[0004] 人工勢能場（ArtificialPotentialField:APF)是一種模擬電勢場分布的規劃方 法，其概念首先由Khatib提出，並成功應用於機械臂避碰。人工勢能場的思想借鑑了"物 體運動一般由勢能較高的位置向勢能較低的位置運動"這一物理規律，根據人員對建築物 內部及出口的熟悉程度、障礙物的分布、離出口的距離、火災等外界因素的影響等初始化網 格勢能。其特點是規劃速度快，能夠保證路徑的安全，但由於勢函數存在引力和斥力相等的 局部極小點，會使算法停滯而無法抵達目標位置，又由於沒有代價函數對航跡優劣進行衡 量而不能保證路徑的最優。
[0005] 人工勢能場的物理特性與緊急情況下人員的運動規律非常相近，而蟻群算法所表 現出的自組織性、群體性也非常適合應急疏散問題建模，螞蟻在覓食過程中通過釋放信息 素來進行交流和消息互通，以幫助同伴更快地找到食物，這與人在疏散過程中的相互協作 具有很大的相似性。用螞蟻代表疏散中的個體，螞蟻可以通過勢能值的負梯度方向找到通 往安全出口的路徑，能夠加快疏散進程，同時優化結果克服了人工勢能場的局部極小問題。
【發明內容】
[0006] 為了克服現有技術的不足，本發明提出了一種基於勢能驅動元胞蟻群算法的室內 疏散仿真優化方法，一方面利用勢能場的物理特性和蟻群算法的自組織性、正反饋機制從 微觀上模擬了人員的運動規律，另一方面在仿真的同時完成了人員疏散路徑的優化，解決 了人工勢能場的局部極小問題，提高了疏散效率。
[0007] 本發明的技術方案是，一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方 法，包括如下步驟：
[0008] 步驟1.建立二維元胞自動機的建築物疏散模型；
[0009] 二維元胞自動機C定義為以下四元組：
[0010] C=(D2,S,N,f)
[0011] 其中，D2為二維元胞空間，S是有限狀態機集合，對於位于格位r上的元胞在t時 刻的狀態可以表示為：
[0012] S= (S1 (r,t),S2 (r,t), --?,Sz (r,t)}
[0013] 式中Sz(r，t)表示格位r上的元胞在t時間的第z個狀態；N為以r為中心元胞的 鄰域，N= (N1,N2,…，N1J是D2的有限的序列子集，n為格位r上的元胞的鄰居元胞個數，f 為中心元胞r與鄰居間的移動規則；
[0014] 步驟2.設置模型參數；包括蟻群算法相關參數和勢能場增益係數，疏散人員個數 m、蟻群算法的信息素和啟發式信息重要程度a和0，信息素揮發係數q，勢能場增益係數 L和12，信息素強度初始值Q，算法的最大迭代次數T;
[0015] 步驟3.初始化疏散場景；根據建築物內布局對二維元胞空間進行疏散場景模擬， 隨機設置障礙物的位置和大小，根據建築物真實場景標註出口元胞位置，隨機設置疏散人 員在疏散開始時所處元胞位置，根據每個元胞是被障礙物、人員佔據還是空閒設置其初始 狀態，初始化元胞之間路徑上的信息素強度為步驟2設置的Q，將所有人員狀態標註為人 "未疏散"；
[0016] 步驟4?計算場景的人工勢能場；
[0017] 根據步驟3人員在元胞中的分布，按以下公式計算每個元胞的總勢能：
【權利要求】
1. 一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法，其特徵在於，包括如下 步驟； 步驟1.建立二維元胞自動機的建築物疏散模型； 二維元胞自動機C定義為以下四元組： C = (D2, S, N, f) 其中，D2為2維元胞空間，S是有限狀態機集合，對於位于格位r上的元胞在t時刻的 狀態可以表示為： S = (S1 (r, t), S2 (r, t), --?, Sz (r, t)} 式中Sz(r，t)表示格位r上的元胞在t時間的第z個狀態；N為以r為中心元胞的鄰 域，N = (N1, N2,…，N1J是D2的有限的序列子集，n為格位r上的元胞的鄰居元胞個數，f為 中心元胞r與鄰居間的移動規則； 步驟2.設置模型參數；包括蟻群算法相關參數和勢能場增益係數，疏散人員個數m、蟻 群算法的信息素和啟發式信息重要程度a和0，信息素揮發係數q，勢能場增益係數〖i和 € 2,信息素強度初始值Q，算法的最大迭代次數T ; 步驟3.初始化疏散場景；根據建築物內布局對二維元胞空間進行疏散場景模擬，隨機 設置障礙物的位置和大小，根據建築物真實場景標註出口元胞位置，隨機設置疏散人員在 疏散開始時所處元胞位置，根據每個元胞是被障礙物、人員佔據還是空閒設置其初始狀態， 初始化元胞之間路徑上的信息素強度為步驟2設置的Q，將所有人員狀態標註為人"未疏 散"； 步驟4.計算場景的人工勢能場； 根據步驟3人員在元胞中的分布，按以下公式計算每個元胞的總勢能：
式中Uatt(i)和^1)分別是元胞i處的引力勢能和斥力勢能，Pg(i)為元胞i到目 標元胞ig的歐式距離，U〖2是相應的勢能場增益係數，P⑴是人員k與障礙物之間的 最近距離，P ^為障礙物對人產生影響的最大距離；
其中，-grad[Uatt(i)]和-grad[l4ep(i)]分別表示元胞i點處吸引力勢能的負梯度和排 斥力勢能的負梯度，€ p 12是相應的勢能場增益係數，P g(i)為元胞i到目標元胞ig的歐 式距離，▽ P (i)表示障礙物指向元胞i的單位向量； 因此，綜合因素對人員在元胞i處產生的總勢能可以表示為： Ui = SUatt ⑴ +SUrep ⑴ (5) 步驟5.根據步驟4得到的人員在當前可移動元胞的總勢能值，計算可移動路徑上的啟 髮式信息； 在t時刻，人員由元胞i移動到元胞j上，利用人工勢能場對出口和障礙物的感知能 力，對蟻群算法的啟發信息nu(t)進行改進，引導人員尋找路徑，其公式為：
其中，nij(t)為元胞i與元胞j之間路徑上的啟發式信息，dj，6Xits是元胞j到出口的 距離，HiinW^xitsIj e Jj表示元胞j距離出口的最短歐式距離，Ji是元胞i附近的鄰居集 合，Ui為步驟4得到的元胞i的總勢能值； 步驟6.設置迭代計數器NC = 1 ; 步驟7.從所有疏散人員中隨機選擇一名人員作為第一個開始疏散，設k = 1 ; 步驟8.判斷第k個人員的當前狀態是否為"已疏散"狀態，若是則執行步驟15,否則執 行下一步； 步驟9.根據第k個人員所在的元胞，得到其鄰居元胞的集合； 步驟10.根據步驟9得到的鄰居元胞集合，判斷其當前時刻的狀態，鄰居元胞為空閒可 移動點或是被佔位不可移動點，根據鄰居元胞狀態和禁忌規則判斷第k個人員可移動的元 胞鄰居集； 步驟11.根據步驟10得到的可移動元胞鄰居集，判斷第k個人員是否有可移動的元 胞，若有，執行下一步；若沒有則在這一時刻停留在當前元胞位置，執行步驟15 ; 步驟12.根據當前時刻的第k個人員所處元胞與鄰居元胞路徑上的信息素強度和步驟 5得到的啟發式信息，計算第k個人員選擇鄰居可移動元胞的概率； 在t時刻，第k個人員由元胞i轉移到元胞j的狀態轉移概率公式如下所示：
式中，4(0是人員k由元胞i轉移到元胞j的轉移概率，T yt)是元胞i與元胞 j之間路徑上的信息素強度，HijU)是元胞i與元胞j之間路徑上的啟發式信息，a和 3是常量參數，用來表示信息素和啟發信息的重要程度，Ji表示元胞i附近的鄰居集合；
代表元胞i到所有鄰居元胞的啟發式信息和信息素乘機的累加和； 步驟13.根據步驟12得到的轉移概率得出第k個人員的轉移概率最大的鄰居元胞，將 第k個人員移動到此元胞處，更新該元胞的狀態，將該元胞加入該人員的疏散路徑； 步驟14.根據步驟13得到的第k個人員的最新移動到的元胞，判斷人員k是否達到出 口，若已到達，則標記該人員為"已疏散"狀態，否則標記該人員為"未疏散"狀態； 步驟15.疏散人員計數加1，即k = k+1，對下一個人員進行可移動元胞搜索； 步驟16.如果k < m，則說明還未遍歷所有疏散人員，返回到步驟8,否則表明所有人員 完成了一個時間步的搜索，執行下一步； 步驟17.判斷所有人員的當前狀態是否都為"已疏散"狀態，若是則表明所有人員完成 了從初始元胞到出口的路徑搜索，即本輪疏散模擬完成，執行下一步，否則返回步驟7 ; 步驟18.根據步驟13得到的每一個人員從其初始元胞到出口的疏散路徑，按照公式 (8)-(10)來更新每個人員疏散路徑上元胞之間的信息素強度： T Jj (t+At) = (1-q) X Tij (t) +A Tij (t+At) (8)
其中，T u(t)表示t時刻元胞i與元胞j之間路徑上的信息素強度函數，Q為常數，是步 驟2設置的信息素強度初始值，Lk為k個人員第在本次循環中所走的路徑長度，edge (i，j) 代表元胞i與元胞j之間的路徑，Pathk是人員k經過的路徑；q為步驟2設置的信息素強 度揮發係數； 步驟19.迭代計數器NC加1，即NC = NC+1 ; 步驟20.當NC T，迭代結束，執行下一步； 步驟21.輸出最優疏散路徑和疏散時間，演示最優疏散方案。
2. 根據權利要求1所述的一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法， 其特徵在於：所述的步驟1中以f為中心元胞r與鄰居間的移動規則採用Moore型鄰居定 義，以中心元胞的上、下、左、右、左上、左下、右上、右下這八個方向上的元胞為其鄰居，此 時鄰居半徑同樣為r = 1，行人可以在同一時間向這八個方向移動到達鄰近空閒元胞。
3. 根據權利要求2所述的一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法， 其特徵在於：所述的步驟9中得到其鄰居元胞的位置集合為第k個人員所在位置的上，下， 左，右，左上，左下，右上，右下8個方向的元胞。
4. 根據權利要求1所述的一種基於勢能驅動元胞蟻群算法的室內疏散仿真優化方法， 其特徵在於，本方法的參數設置為：蟻群算法參數a = 1，0 = 2, P = 0. 5,Q = 1，最大循 環次數T = 100 ;勢能場增益係數€ 1 = 2, € 2 = 1。
5. 根據權利要求1或2或3或4所述的一種基於勢能驅動元胞蟻群算法的室內疏散仿 真優化方法，其特徵在於，所述的步驟10中的禁忌規則為： (1) 一個元胞只能容納一個人員； (2) 在建築物的人員可以向空閒元胞和出口移動，從出口的元胞不能向建築物內的元 胞移動； (3) 若多個人員同時競爭同一個空閒元胞，隨機選擇一人進入，其他人重新選擇路徑， 直到所有人員在網格上找到自己下一時刻唯一目標為止； (4) 當人員不能選擇當前最優站位時，則在不考慮出口方向情況寫選擇一個次優元胞 作為站位； (5) 人員選擇元胞不能是自己上一步所在的元胞，除非周圍其他的元胞都不可被訪問。
【文檔編號】G06F17/50GK104361178SQ201410667474
【公開日】2015年2月18日 申請日期:2014年11月20日 優先權日:2014年11月20日
【發明者】宗欣露, 尹宇潔, 葉志偉, 王春枝, 劉偉, 陳宏偉, 徐慧 申請人:湖北工業大學