基于改進果蠅優(yōu)化算法的人群疏散仿真

張 超, 梁西陳, 魏三強,2

(1.宿州職業(yè)技術學院計算機信息系,安徽宿州234101;2.中國礦業(yè)大學信息與控制工程學院,江蘇徐州221116)

基于改進果蠅優(yōu)化算法的人群疏散仿真

張 超1, 梁西陳1, 魏三強1,2

(1.宿州職業(yè)技術學院計算機信息系,安徽宿州234101;2.中國礦業(yè)大學信息與控制工程學院,江蘇徐州221116)

基本果蠅優(yōu)化算法收斂精度不高,易陷入局部極值,在人群疏散仿真中存在疏散路徑不平滑的缺陷。為此,借鑒螢火蟲算法思想,賦予果蠅個體感知域,在感知域內(nèi)有鄰居時,向鄰居集合內(nèi)味道濃度最佳的果蠅個體飛去,沒有鄰居時,向果蠅群體味道濃度最佳的個體飛去。向鄰居集合最優(yōu)個體學習時,為了防止算法陷入局部最優(yōu),采用局部極值和全局極值相結合的動態(tài)位置搜索方式。迭代開始階段果蠅個體主要向局部極值方向飛去,以便獲得多個極值點。隨著迭代次數(shù)增加,果蠅群體極值所占比重逐漸增加,在確保求解精度的同時提高收斂速度。將改進的算法在4個經(jīng)典測試函數(shù)上進行性能分析,實驗結果表明,改進的算法在收斂速度,特別在收斂精度上有顯著提高。將改進的算法應用在雙出口房間人群疏散仿真中,實現(xiàn)了疏散路徑平滑、疏散仿真度較好的效果。

果蠅優(yōu)化算法;人群疏散仿真;螢火蟲算法;智能算法;群體動畫

0 引言

隨著經(jīng)濟社會的發(fā)展和城市化進程的加快,大型購物商場、廣場、影院、火車站等公共場所人員流動量大容易造成緊急突發(fā)事件,在突發(fā)事件發(fā)生時如何以最快的速度將大量人員疏散到安全的地點成為學者們研究的熱點問題[1]。各種疏散模型被相繼提出并應用在人群疏散仿真中,如元胞自動機模型[2]、Agent模型[3-4]、基于密度模型[5]、格子氣模型[6]、社會力模型、離心力模型[7]等。目前已有的疏散模型主要可分為宏觀和微觀兩大類。宏觀模型以人群整體為研究對象,不考慮人群個體之間的交互和影響,大多通過流體力學理論、動態(tài)網(wǎng)絡均衡理論、路徑選擇模型對密集人群的流體運動過程和路徑選擇行為進行刻畫,仿真度較差[8]。微觀模型充分考慮個體行為特征和個體之間的差異,以人群個體行為作為研究對象,成為人群疏散研究的熱點,如文獻[2-6],但也存在計算量大、運算速度慢等缺點。

群體智能算法是對自然界生物群體涌現(xiàn)現(xiàn)象的仿生設計,有著其他模型無法比擬的優(yōu)點,能夠實現(xiàn)個體之間的信息交互及自組織特性,被廣泛應用于函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度問題、自動控制、機器學習、圖像處理等領域[9-11]。鑒于群體智能算法在模擬群體行為特征上的優(yōu)點,近年來,學者們相繼開展群體智能算法在人群疏散仿真領域的研究。萬江華等[12]對標準粒子群算法的慣性權重進行優(yōu)化,加入了影響力因子,很好地模擬了突發(fā)事件中的領導者行為;張鵬等[13]提出一種基于種群劃分思想的新型蜂群算法,實現(xiàn)了人群疏散的均衡分布,提高了應急疏散的效率;晁素娜等[14]將改進的螢火蟲算法應用在人群疏散仿真中,提高了疏散路徑的平滑性和穩(wěn)定性。因此,將群體智能算法應用到人群疏散仿真中能夠為人群疏散領域的研究提供新的方法。果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm,FOA)[15]是一種新型的群體智能算法,因其算法原理簡單、參數(shù)少、實時性好,現(xiàn)已被廣泛應用于神經(jīng)網(wǎng)絡優(yōu)化、工業(yè)設計等科學和工程領域[16-17]。為此,本文提出將果蠅優(yōu)化算法應用到人群疏散仿真中,為人群疏散仿真研究提供一種新的思路。

人群的應急疏散過程是人的個體移動行為、路徑選擇行為和群體博弈行為共同作用的結果。人在緊急事件中往往表現(xiàn)出恐慌、親和和從眾的心理特征。在應急疏散中表現(xiàn)為向人多的地方靠攏或跟隨最近的逃生者移動,應急疏散中的人總是希望以最快的速度到達安全區(qū)域,這與果蠅優(yōu)化算法中果蠅群體總是向離食物源近的味道濃度最高的果蠅飛去有著類似的行為選擇特征。因此,將果蠅優(yōu)化算法應用到人群疏散仿真中在理論上是可行的。但基本果蠅優(yōu)化算法中在算法的每次迭代過程中所有果蠅都飛向群體中味道濃度最高的個體,依賴全局信息引導果蠅進行位置搜索,缺乏局部信息的搜索,這種機制降低了種群的多樣性,極易使算法陷入局部最優(yōu)而無法跳出局部極值[18],導致在人群疏散仿真時疏散路徑不夠平滑。

針對基本果蠅優(yōu)化算法在人群疏散仿真時疏散路徑不夠平滑的缺陷,本文參考螢火蟲算法(Glowworm Swarm Optimization,GSO)[19],將局部極值加入到果蠅的位置更新中,以擴展群體的多樣性,增加局部極值點。當前果蠅個體在可視范圍內(nèi)有鄰居時,向鄰居集合中味道濃度最優(yōu)(局部極值)的個體飛去,模擬人群在緊急疏散時總是向離自己最近的逃生者移動的行為特征;當前個體沒有鄰居時,向果蠅群體味道濃度最優(yōu)(全局極值)的個體飛去。向鄰居集合最優(yōu)個體學習時,為了防止算法陷入局部最優(yōu),采用局部極值和全局極值相結合的動態(tài)位置搜索方式。迭代尋優(yōu)開始階段果蠅個體主要向局部極值方向飛去,以便獲得多個極值點。隨著迭代次數(shù)的增加,果蠅群體極值所占比重逐漸增加,從而確保求解精度的同時提高收斂速度。將改進的算法在4個常用的經(jīng)典測試函數(shù)上進行性能分析,實驗結果表明,改進的算法在收斂速度和精度上均有顯著提高。將改進的果蠅優(yōu)化算法應用在人群疏散仿真中實現(xiàn)了疏散路徑平滑、疏散仿真度較好的效果。

1 果蠅優(yōu)化算法

2011年,潘文超[16]根據(jù)果蠅覓食的群體特征提出了果蠅優(yōu)化算法。吳小文等[20]將果蠅優(yōu)化算法與遺傳算法、蟻群算法、魚群算法,免疫算法、粒子群算法等5種算法在Schaffer函數(shù)上進行性能分析對比實驗,得出FOA具有算法簡單、易于實現(xiàn)、較容易應用于解決實際問題。近年來,果蠅優(yōu)化算法已被廣泛應用于科學和工程等領域。

1.1 果蠅優(yōu)化算法基本原理[17]

果蠅具有敏銳的嗅覺和視覺器官,可以嗅到距離達40 km以外的食物源散發(fā)的氣味,飛近食物后利用敏銳的視覺能夠發(fā)現(xiàn)食物和同伴聚集的位置,并迅速向該位置飛去。

根據(jù)果蠅覓食的特點,FOA可以歸納為如下步驟:

(1)設置種群規(guī)模sizepop和最大迭代次數(shù)maxgen(或目標精度),隨機初始化果蠅群體位置坐標(X,Y)

式中:s為可調(diào)參數(shù);rand()是介于0～1的隨機數(shù)。

(2)賦予果蠅個體利用嗅覺搜索食物的隨機方向(RandomValue)和位置(X(i),Y(i))

(3)由于無法準確獲知食物源的位置,先估算每個果蠅個體與原點之間的距離d,再取其倒數(shù)作為果蠅個體i的味道濃度判定值S(i)

(4)將果蠅個體i的味道濃度判定值代入味道濃度判定函數(shù)(類似適應度函數(shù)Fitness),求出每個果蠅個體所處位置的味道濃度Smell(i)。

(5)根據(jù)初始味道濃度值尋找果蠅群體初始極值(極大或極小值)

(6)存儲果蠅群體最佳味道濃度值及其對應的位置坐標(X,Y),這時果蠅群體利用視覺向該位置飛去

(7)進入迭代尋優(yōu),重復執(zhí)行步驟(2)～(5),并判斷味道濃度是否優(yōu)于前一迭代味道濃度,若是,執(zhí)行步驟(6);否則,返回步驟(2),直至滿足最大迭代次數(shù)或設定精度,算法停止。

1.2 改進的果蠅優(yōu)化算法

1.2.1 算法的改進設計

在FOA算法的每次迭代過程中,所有果蠅都飛向群體中味道濃度最高的個體,依賴全局信息引導果蠅進行位置搜索,缺乏局部信息的搜索,這種機制降低了種群的多樣性,極易使算法陷入局部最優(yōu)而無法跳出局部極值,導致算法收斂精度不高,在人群疏散仿真時導致疏散路徑不夠平滑。在FOA算法中當前迭代味道濃度最優(yōu)的個體是通過果蠅個體所處位置與原點距離之倒數(shù)估算而來,未必是全局最優(yōu)。為此,參考螢火蟲算法,為果蠅個體設置感知域,將局部極值加入到果蠅個體的位置更新中,以擴展群體的多樣性。當前果蠅個體在感知域內(nèi)有鄰居時,向鄰居集合中味道濃度最優(yōu)(局部極值)的個體學習;沒有鄰居時,向果蠅群體味道濃度最優(yōu)(全局極值)的個體學習。向鄰居集合最優(yōu)個體學習時,為了防止算法陷入局部最優(yōu),采用局部極值和全局極值相結合的動態(tài)位置搜索方式。迭代尋優(yōu)開始階段果蠅個體主要向局部極值方向飛去,以便獲得多個極值點。隨著迭代次數(shù)的增加,果蠅群體極值所占比重增加,從而確保求解精度的同時提高收斂速度。改進算法記為GFOA(G lowworm Fruit Fly Optimization Algorithm)。

果蠅按下式獲取鄰居集合:

式中:Nei(t)是果蠅i第t次迭代時的鄰居集合,j∈Nei(t);di,j(t)是果蠅i和j第t次迭代時的歐式距離;Rid是果蠅i的感知域;Smell(i)、Smell(j)是果蠅i和j在第t次迭代時所處位置的味道濃度。

果蠅按下式動態(tài)調(diào)整感知域,

鄰居集合密度高就縮小感知范圍;反之,增加。

式中:nt為常數(shù);鄰居數(shù)的上限;β為感知域更新率。

如果果蠅i在當前迭代時鄰居集合為空,按式(2)的隨機方向和位置搜尋食物。否則,按下式的局部極值和全局極值相結合的動態(tài)位置搜尋食物:

式中,X(j)、Y(j)為局部最優(yōu)果蠅個體所處位置。

w1和w2的取值范圍在[c1,c2]之間,c1、c2的取值范圍在[0.6,4]之間,且c1＞ c2。w1隨著迭代次數(shù)t的增加而線性減少,w2隨著迭代次數(shù)t的增加而線性增加?；竟壦惴ㄒ陨弦坏^程中味道濃度最佳的果蠅個體所處位置,作為下一迭代過程中所有果蠅個體的開始搜索位置。味道濃度最佳果蠅個體所處位置由其距原點距離之倒數(shù)估算而來。在4個經(jīng)典測試函數(shù)Schwefelf、Sphere、Griewank、Schaffer上尋找最優(yōu)值的實驗來看,雖能很快收斂,但精度不高,易陷入局部極值。式(9)通過當前個體到局部最優(yōu)個體和全局最優(yōu)個體的歐式距離,作為下一迭代的開始搜索位置,該位置將局部最優(yōu)和全局最優(yōu)2個因素都加入進來,是個動態(tài)調(diào)整值,適當提高c1、c2取值,可以擴展果蠅群體多樣性和搜索空間,顯著提高收斂精度。

1.2.2 GFOA算法的執(zhí)行流程

基于1.2.1節(jié)的改進,GFOA算法的基本步驟如下:

(1)設置種群規(guī)模sizepop和最大迭代次數(shù)maxgen(或目標精度),根據(jù)式(1)為果蠅群體初始化位置坐標。

(2)如果果蠅個體沒有鄰居,按式(2)設定果蠅個體搜尋食物的方向和距離;否則,按式(9)搜尋食物,并根據(jù)式(8)動態(tài)調(diào)整果蠅感知域。

(3)根據(jù)式(3)計算果蠅個體i的味道濃度判定值S(i)。

(4)根據(jù)式(4)計算每個果蠅個體初始位置的味道濃度Smell(i)。

(5)根據(jù)式(5)計算出果蠅群體初始極值bestSmell(極大或極小值)。

(6)根據(jù)式(6)存儲果蠅群體依據(jù)初始位置計算的最佳味道濃度值Smellbest及其對應的最佳位置坐標(X,Y)。

(7)進入迭代尋優(yōu),首先,依據(jù)果蠅個體初始位置,按式(7)獲取果蠅的鄰居集合Nei(t),重復執(zhí)行步驟(2)～(5),并判斷味道濃度是否優(yōu)于前一迭代味道濃度,若是,執(zhí)行步驟(6);否則,返回步驟(2),直至滿足最大迭代次數(shù)或目標精度,算法停止。

2 GFOA算法的性能分析

2.1 實驗部署

為了驗證GFOA算法的尋優(yōu)性能,對FOA和GFOA做對比分析實驗。從標準函數(shù)測試集CEC2005中選取4個經(jīng)典測試函數(shù),函數(shù)的表達式、變量范圍、理論極值見表1。在主頻2.50 GHz的CPU、4 GB內(nèi)存、64 bit Win10操作系統(tǒng)的計算機上,使用MatlabR2012a編程實現(xiàn)。

程序參數(shù)設置:

Schwefelf、Sphere、Schaffer函數(shù) s= 100,Griewank 函數(shù) s=300,RandomValue=20·rand()?10,Schwefelf、Sphere、Griewank函數(shù):c1=1.8,c2=0.6,Schaffer函數(shù):c1=4,c2=3。

表1 測試函數(shù)Tab.1 Test function

2.2 實驗結果與分析

用FOA和GFOA算法分別對表1中4個經(jīng)典測試函數(shù)隨機獨立連續(xù)運行20次,實驗結果見表2。從表2中可以看出,對2個單峰函數(shù)、2個多峰函數(shù),GFOA算法在最差值、最優(yōu)值、優(yōu)化平均值和標準差4個評價指標上均優(yōu)于FOA算法。圖1中,由于GFOA的收斂精度顯著優(yōu)于FOA,故在同一坐標系下味道濃度收斂進化曲線近似為直線,為了便于觀察,對Schwefelf、Sphere、Griewank函數(shù)的味道濃度取10為底的對數(shù)處理,對于Griewank函數(shù),GFOA算法的味道濃度進化曲線出現(xiàn)間斷,表示GFOA算法在該函數(shù)上已尋找到最優(yōu)值0,對數(shù)的真數(shù)為0時不顯示。由圖1可見,GFOA算法收斂到最優(yōu)值的速度明顯優(yōu)于FOA。FOA算法在Sphere、Griewank函數(shù)上分別有2次陷入局部極值;在Schwefelf函數(shù)上有3次陷入局部極值。在Sphere函數(shù)上陷入局部極值的尋優(yōu)結果為:0.007 723、0.008 244。在Griewank上陷入局部極值的尋優(yōu)結果為:0.001 253,0.001 165。GFOA算法對于強烈震蕩的多峰值函數(shù)f3、f4,均能快速收斂到函數(shù)的理論極值點,對于函數(shù)f1、f2,GFOA算法的收斂精度較FOA算法有顯著提高。函數(shù)f4被認為是最難尋得極值點的函數(shù),其在理論極值周圍分布著很多極值點。GFOA算法在函數(shù)f4上未陷入“早熟收斂”現(xiàn)象,而使果蠅個體在進化后期停滯不前。

表2 實驗結果Tab.2 Experimental results

圖1 味道濃度收斂趨勢圖Fig.1 Convergent tendency chart of smell concentration

表3為固定精度下的FOA算法和GFOA算法的平均迭代次數(shù)和成功率。其中,Schwefelf、Sphere、Griewank函數(shù)的目標精度設為:10?10,Schaffer函數(shù)設為:10?10～1。表中實驗結果使用“平均迭代次數(shù)/成功率”數(shù)值格式,其中使用1代表百分之百收斂到目標精度。由表3可知,在較高目標精度下GFOA算法均能百分百成功收斂,而基本FOA算法均不能收斂到固定精度。GFOA算法在4個函數(shù)上的平均迭代次數(shù)分別為:20.15,12.1,13.3,12.3,說明改進的算法有效提高了算法的收斂速度。

表3 固定精度下平均迭代次數(shù)與成功率Tab.3 Number of iterationsand success rate under fi xed precision

3 基于GFOA的人群疏散仿真方法

人群在應急疏散中的行為總是呈現(xiàn)向人多的地方靠攏或跟隨最近的逃生者移動,并伴隨復雜的自組織現(xiàn)象產(chǎn)生。人群在應急疏散中所涌現(xiàn)的群體特性與覓食中的果蠅群體有著類似的行為選擇特征。果蠅總是向味道濃度高的離食物源近的果蠅飛去,而應急疏散中的人總是希望以最快的速度到達安全區(qū)域。GFOA算法賦予果蠅個體感知范圍,在覓食過程中優(yōu)先向自己視線范圍內(nèi)的味道濃度高的果蠅飛去,而應急疏散中的人也擁有自己的視野,會根據(jù)實際情況判斷選擇最佳逃生路線。因此,使用改進的果蠅優(yōu)化算法引導人群疏散仿真能夠獲得良好的疏散效果。

3.1 雙出口教室人群疏散仿真方案

選定雙出口教室作為人群疏散仿真場景。在房間內(nèi)隨機初始化N個果蠅(粒子),果蠅味道濃度與果蠅個體和房間出口距離成反比(將此作為GFOA算法的適應度函數(shù)Fitness),距離出口越近,味道濃度越濃。果蠅群體依據(jù)與房間2個出口的距離長短選擇從哪個出口逃生。這樣,果蠅群體按照與出口的距離劃分為2個區(qū)塊。每個區(qū)塊內(nèi)的果蠅按照GFOA算法搜索出口,當其視野范圍內(nèi)有鄰居時,向鄰居集合中疏散位置最佳的果蠅移動,沒有鄰居時,向區(qū)塊內(nèi)疏散位置最佳的果蠅移動,直至所有果蠅都到達安全出口。

使用Flash Develop+Action Script3.0開發(fā)仿真程序。人群在疏散過程中能夠自動避開障礙物。為此,在仿真程序中添加碰撞檢測和避免算法,以實現(xiàn)具有真實感行為的仿真效果。仿真程序選用層次包圍盒和歐式距離相結合的碰撞檢測和避免算法[21]。該算法能夠實現(xiàn)人群在疏散過程中自動避開教室內(nèi)的課桌等障礙物,并防止與墻壁產(chǎn)生穿插現(xiàn)象。

3.2 仿真結果與分析

將果蠅種群規(guī)模設定為40,隨機進行一次疏散仿真實驗,圖2截取了疏散仿真程序運行時的3種狀態(tài)。圖2(a)為果蠅初始分布狀態(tài),圖2(b)為疏散中期果蠅分布狀態(tài),圖2(c)為疏散即將完成時的狀態(tài)。圖2中標記1和2的為出口安全區(qū)域,課桌被包圍在層次包圍盒(圓)中。圖2(b)顯示,果蠅群體按照與出口距離長短劃分為2個區(qū)塊進行疏散,果蠅在各自區(qū)塊內(nèi)依據(jù)GFOA算法搜索鄰居集合的最優(yōu)果蠅或全局最優(yōu)果蠅,并跟隨該果蠅移動疏散。由于添加了碰撞檢測和避免算法,果蠅在疏散過程中能夠自動避開包圍在層次包圍盒(圓)中的課桌,防止了與教室墻壁的穿插。由圖2(c)可見,果蠅陸續(xù)到達安全區(qū)域,即將完成疏散。圖3是GFOA算法和FOA算法生成的疏散路徑曲線對比圖,從圖中可知,FOA算法生成的疏散路徑曲線不光滑,特別在疏散中后期,果蠅個體都向全局最優(yōu)位置靠近,造成疏散路徑出現(xiàn)跳躍,從而導致在進行人群疏散仿真時的仿真度不高,而GFOA算法生成的疏散路徑曲線平穩(wěn)光滑,說明GFOA算法使用局部最優(yōu)和全局最優(yōu)相結合的動態(tài)位置更新方式,有效提高了人群疏散的仿真度。如圖2(a)所示,仿真程序設計了開始和停止疏散功能,有利于觀察分析疏散仿真過程。仿真程序設計了路徑導出功能,可以將果蠅個體的疏散路徑數(shù)據(jù)導出,使用MAYA的路徑動畫技術制作人群仿真動畫。

圖2 雙出口教室人群疏散仿真狀態(tài)圖Fig.2 Statediagram of crowd evacuation simulation from aclassroom with two exits

圖3 GFOA算法和FOA算法生成的疏散路徑曲線圖Fig.3 Evacuation path map generated by GFOA algorithm and FOA algorithm

綜上所述,使用GFOA算法能夠完成雙出口房間的人群疏散,且獲得了光滑平穩(wěn)的疏散路徑。

4 結語

本文提出將果蠅優(yōu)化算法應用到人群疏散仿真的研究中,為人群疏散仿真研究提供一種新的思路。

針對果蠅優(yōu)化算法收斂精度不高、易陷入局部最優(yōu)、在應用到人群疏散仿真中存在疏散路徑不平滑的缺陷,提出了一種改進的果蠅優(yōu)化算法,并在4個經(jīng)典測試函數(shù)上做了性能分析實驗。實驗結果表明,

改進的算法在收斂速度、特別在收斂精度上有顯著提升。將改進的算法應用在雙出口房間人群疏散仿真中,獲得了疏散路徑平滑、仿真度較好的疏散效果,具有良好的實際應用參考價值。

[1] 吳雙,劉弘.人群疏散的社會力蟻群模型[J].山東師范大學學報:自然科學版,2016,31(3):15-20.

[2] 賈斌,高自友,李克平,等.基于元胞自動機的交通系統(tǒng)建模與模擬[M].北京:科學出版社,2007.

[3] ZHONG J H,CAI W T,LUO L B,et al.Ea-based evacuation planning using agent based crowd simulation[C]//TOLI A,DIALLO S Y,RYZHOV I O,et al.Simulation Conference(WSC).Piscataway,NJ,USA:IEEE,2014:395-406.

[4] 陳佳俊,安曉宇,蔡希輝,等.基于Agent的人員疏散系統(tǒng)設計與實現(xiàn)[J].計算機工程,2010,36(14):264-266.

[5] ZHONGJH,HU N,CAIWT,et al.Density-based evolutionary framework for crowd model calibration[J].Journal of Computational Science,2015(6):11-22.

[6] 郭細偉,陳建橋,魏俊紅.格子氣模型在地鐵站人群疏散運動中的應用[J].武漢理工大學學報(交通科學與工程版),2014,38(3):567-571.

[7]CHRAIBI M,SEYFRIED A,SCHADSCHNEIDER A.Generalized centrifugal-forcemodel for pedestrian dynamics[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2010,82(4):046111.

[8] 禹爾東,吳正,郭明旻.雙出口房間人群疏散的實驗研究和數(shù)學建模[J].物理學報,2014,63(9):094501.

[9] 周永權,黃正新.求解TSP的人工螢火蟲群優(yōu)化算法[J].控制與決策,2012,27(12):1816-1821.

[10]唐海波,葉春明.仿生群智能算法在生產(chǎn)調(diào)度中的應用綜述[J].工業(yè)工程,2010,13(3):1-5.

[11]陳志國,傅毅,孫俊.群體智能算法的遙感圖像處理研究[J].計算機應用研究,2013,30(8):2538-2540.

[12]萬江華,卜凡亮.粒子群算法在應急疏散中的應用研究[J].中國人民公安大學學報(自然科學版),2011,17(3):59-64.

[13]張鵬,劉弘,王愛霖.基于人工蜂群算法的疏散運動仿真[J].計算機工程,2013,39(7):261-264.

[14]晁素娜,劉弘,張鵬.基于改進螢火蟲算法的人群疏散仿真[J].山東師范大學學報(自然科學版),2015,30(1):33-37.

[15]PAN W T.A new fruit fl y optimization algorithm:Taking thefi nancial distressmodel asan example[J]．Knowledge-Based Systems,2012,26(2):69-74．

[16]潘文超.應用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡進行企業(yè)經(jīng)營績效評估[J].太原理工大學學報(社會科學版),2011,29(4):1-5

[17]姚勇濤,吳雪,吳喆.基于改進的果蠅優(yōu)化算法的WSN節(jié)點部署設計[J].華東理工大學學報(自然科學版),2016,42(4):545-551.

[18]徐富強,陶有田,呂洪升.一種改進的果蠅優(yōu)化算法[J].蘇州大學學報(自然科學版),2014,29(1):16-23.

[19]KRISHNANAND K N,GHOSE D.Glowworm swarm optimisation:A new method for optimising multi-modal functions[J].International Journal of Computational Intelligence Studies,2009,1(1):93-119.

[20]吳小文,李擎.果蠅算法和5種群智能算法的尋優(yōu)性能研究[J].火力與指揮控制,2013,38(4):17-20.

[21]張超.“靈璧三絕”動漫宣傳片中的群體動畫制作技術[J].江漢大學學報(自然科學版),2015,43(1):58-64.

Abstract:The fruit fl y optimization algorithm has low convergence precision and easily falls into local optimum,which is a weak at smoothness of path in crowd evacuation simulation.Therefore,the perceptual domain which is derived from the glowworm swarm optimization algorithm is given to the individual fruit fl y.If there are neighbors in the perceptual domain of the current fruit fl y,the current fruit fl y to the best smell one in neighbor set,otherwise fl ies to the best smell one which of fruit fl y population.When the fruit fl y learns from the best neighbors,a dynamic location search method based on the combination of local extremum and global extreme value is used to prevent the algorithm from falling into local optimum.At the beginning of the iteration,the fruit fl y fl ies to the local extreme direction to obtain multiple extreme points.With the increase of iteration,the proportion of the global optimal value increases gradually aim to ensure the convergence accuracy and improve the convergence speed.The experimental results of four test functions show that the improved fruit fl y optimization algorithm is signifi cantly improved the algorithm convergence speed and precision.The improved algorithm is applied to the simulation of crowd evacuation in the double exit room.It improves the smoothness of evacuation path and evacuation simulation effect is good.

Keywords:fruit fl y optimization algorithm;crowd evacuation simulation;fi refl y algorithm;intelligencealgorithm;crowd animation

Crowd Evacuation Simulation Based on Improved Fruit Fly Optimization Algorithm

ZHANGChao1,LIANGXichen1,WEISanqiang1,2
(1.Department of Computer Information,Suzhou Vocational and Technological College,Suzhou 234101,Anhui,China;2.School of Information and Control Engineering,China University of Mining and Technology,Xuzhou 221116,Jiangsu,China)

TP 18

A

1001-4543(2017)03-0231-08

10.19570/j.cnki.jsspu.2017.03.012

2017-04-05

張 超(1980–),男,安徽宿州人,講師,碩士,主要研究方向為智能算法研究、動漫制作技術。E-mail:zc2001888@163.com。

安徽省高校省級自然科學基金重點項目 (KJ2016A781、KJ2016A778),安徽省高校省級質(zhì)量工程項目(2015jyxm512、2014jxtd065,2015sjjd037),宿州市“551”產(chǎn)業(yè)創(chuàng)新團隊項目(宿人才2014[2]號)資助