[發(fā)明專利]基于熵的多蟻群人車競爭-協(xié)作疏散優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201710371942.4
• 申請日: 2017-05-24
• 公開（公告）號: CN107358333B
• 公開（公告）日: 2019-09-03
• 發(fā)明（設(shè)計(jì)）人: 宗欣露;王春枝;葉志偉;劉偉;徐慧;陳宏偉;范鑫楷
• 申請（專利權(quán)）人: 湖北工業(yè)大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06Q10/06;G06Q50/26;G06N3/00
• 代理公司: 武漢開元知識產(chǎn)權(quán)代理有限公司 42104
• 代理人: 王和平;馮超

1.一種基于熵的多蟻群人車競爭-協(xié)作疏散優(yōu)化方法，其特征在于：包括如下步驟：

步驟1.將人車混合通行的疏散區(qū)域用疏散網(wǎng)絡(luò)表示：定義EN(Node,Edge)為疏散網(wǎng)絡(luò)，其中Node＝{1,2,…,n}為疏散區(qū)域中的道路交叉點(diǎn)，Edge為疏散道路或通道，

步驟2.設(shè)置模型參數(shù)：包括人員數(shù)量NP、車輛數(shù)量NV、最大迭代次數(shù)T_MAX、信息素濃度初值Q、信息素濃度揮發(fā)系數(shù)ρ(ρ∈[0,1])、信息素濃度的重要程度α、啟發(fā)式信息的重要程度β、蟻群間的通信間隔gap；

步驟3.生成規(guī)模為NP的蟻群p和規(guī)模為NV的蟻群v，即蟻群p代表人員群體，蟻群v代表車輛群體，蟻群p的螞蟻數(shù)量為NP，蟻群v的螞蟻數(shù)量為NV；

步驟4.初始化蟻群p和蟻群v中的螞蟻位置和信息素濃度；將代表人員和車輛的螞蟻隨機(jī)放置在疏散網(wǎng)絡(luò)EN的節(jié)點(diǎn)上，其中，代表車輛的螞蟻只能放置在僅允許車輛訪問的節(jié)點(diǎn)上，將初始位置加入每個螞蟻的路徑，初始化蟻群p和蟻群v各自的疏散網(wǎng)絡(luò)節(jié)點(diǎn)上的信息素濃度為步驟2設(shè)置的Q，將疏散網(wǎng)絡(luò)EN中所有邊的通過人員和車輛數(shù)設(shè)為0，初始化疏散網(wǎng)絡(luò)中各邊的通行能力C；

步驟5.根據(jù)公式(1)計(jì)算疏散網(wǎng)絡(luò)中連通邊上的啟發(fā)式信息；

式中，η_ij為具有連通關(guān)系的邊(i,j)上的啟發(fā)式信息，d_ij為邊(i,j)的長度，即節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離，i＝{1,2,…,n},j＝{1,2,…,n},(i,j)∈Edge；

步驟6.設(shè)置迭代計(jì)數(shù)器gen＝1；

步驟7.對于蟻群p和蟻群v，分別執(zhí)行步驟7-步驟20；

步驟8.從蟻群p/蟻群v中隨機(jī)選擇一個螞蟻?zhàn)鳛榈谝粋€，設(shè)k＝1；

步驟9.判斷第k個螞蟻的狀態(tài)是否為“成功撤離”，

若為“是”則執(zhí)行步驟15，

若為“否”則執(zhí)行步驟10；

步驟10.根據(jù)第k個螞蟻的當(dāng)前位置節(jié)點(diǎn)和網(wǎng)絡(luò)拓?fù)潢P(guān)系，得到第k個螞蟻當(dāng)前目標(biāo)移動節(jié)點(diǎn)集合Set_k；

步驟11.根據(jù)步驟10得到的第k個螞蟻目標(biāo)移動節(jié)點(diǎn)集合Set_k，按照公式(2)計(jì)算目標(biāo)移動節(jié)點(diǎn)集合中的每個備選節(jié)點(diǎn)的轉(zhuǎn)移概率；

式中，P_ij為從節(jié)點(diǎn)i移動到節(jié)點(diǎn)j的轉(zhuǎn)移概率，(group＝{p,v})為蟻群p/蟻群v中邊(i,j)上的信息素濃度，η_ij為邊(i,j)上的啟發(fā)式信息，s為第k個螞蟻目標(biāo)移動節(jié)點(diǎn)集合Set_k中的節(jié)點(diǎn)，為邊(i,s)上的信息素濃度，η_is為邊(i,s)上的啟發(fā)式信息，α和β分別為步驟2設(shè)置的信息素濃度和啟發(fā)式信息的重要程度；

步驟12.根據(jù)步驟11得到的轉(zhuǎn)移概率按照公式(3)計(jì)算蟻群p/蟻群v中第k個螞蟻在當(dāng)前時刻的熵；

為蟻群group(group＝{p,v})中第k個螞蟻在t時刻的熵；

步驟13.將第k個螞蟻的當(dāng)前位置節(jié)點(diǎn)記為from，根據(jù)步驟11得到的轉(zhuǎn)移概率得到轉(zhuǎn)移概率最大的節(jié)點(diǎn)，記為to，將第k個螞蟻移動到節(jié)點(diǎn)to，同時將to加入第k個螞蟻的路徑path_k，更新邊(from,to)上的通過螞蟻數(shù)量Num_(from,to)(t+1)＝Num_(from,to)(t)+1，記錄第k個螞蟻通過邊(from,to)的時間；

步驟14.根據(jù)步驟13得到的最新位置to判斷該位置是否為出口位置，

若為“是”，則代表第k個螞蟻已到達(dá)出口，標(biāo)記該螞蟻狀態(tài)為“成功撤離”，記錄第k個螞蟻的路徑為path_k，執(zhí)行步驟16，

若為“否”則執(zhí)行步驟15；

步驟15.螞蟻計(jì)數(shù)器k增加1，若k≤當(dāng)前蟻群的螞蟻數(shù)(NP/NV)，說明還未遍歷完該蟻群中的所有螞蟻，返回步驟9，否則表明完成了一個時間步的搜索，執(zhí)行步驟16；

步驟16.判斷當(dāng)前蟻群中所有螞蟻的狀態(tài)是否為“成功撤離”，若是則表明本輪迭代完成，將本輪迭代的時間步數(shù)記為T，執(zhí)行步驟17，否則返回步驟8；

步驟17.根據(jù)步驟13得到的當(dāng)前蟻群的疏散網(wǎng)絡(luò)中各個邊的通行個體數(shù)量，按照公式(6)計(jì)算邊(i,j)上的負(fù)載程度；

其中，Num_ij為疏散過程中邊(i,j)上通過的螞蟻數(shù)，C_ij為步驟4所設(shè)置的邊(i,j)的通行能力，T為步驟16得到的本輪疏散時間；

步驟18.計(jì)算當(dāng)前蟻群的疏散目標(biāo)值：根據(jù)步驟13得到的螞蟻通過路徑上各個邊的時間，按照公式(7)計(jì)算當(dāng)前蟻群所有螞蟻的疏散時間總和f₁，根據(jù)步驟17得到的當(dāng)前蟻群疏散網(wǎng)絡(luò)中各個邊的負(fù)載程度，按照公式(8)計(jì)算當(dāng)前蟻群在整個疏散網(wǎng)絡(luò)的負(fù)載程度f₂；

為步驟13得到的第k個螞蟻的通過邊(i,j)的時間，N為當(dāng)前蟻群的螞蟻數(shù)，其值為NP或NV，l_ij為步驟17得到的邊(i,j)上的負(fù)載程度，path_k為步驟14得到的第k個螞蟻的路徑；

步驟19.根據(jù)步驟18得到的當(dāng)前蟻群的疏散目標(biāo)值f₁和f₂，按照以下Pareto支配分別確定蟻群p/蟻群v的Pareto最優(yōu)解集ND_set_p/ND_set_v，該P(yáng)areto最優(yōu)解集為迭代過程中滿足F₁和F₂最小的若干個疏散方案的集合；

步驟20.根據(jù)步驟19得到的蟻群p/蟻群v的Pareto最優(yōu)解集ND_set_p/ND_set_v，分別對ND_set_p/ND_set_v中的每一個解，即相應(yīng)群體的疏散方案，按照公式(9)/(11)更新其方案中所有螞蟻經(jīng)過路徑上邊的信息素濃度：

對于蟻群p：

為蟻群p第gen次(gen＝{1,2,…})迭代邊(i,j)上的信息素濃度，ρ為步驟2設(shè)置的信息素濃度揮發(fā)系數(shù)，為蟻群p在邊(i,j)上的信息素濃度增量，根據(jù)公式(10)計(jì)算：

其中，Q為步驟2設(shè)置的信息素濃度初值，path_k為步驟13得到的第k個螞蟻的路徑，為步驟13得到的第k個螞蟻的通過邊(i,j)的時間；

對于蟻群v：

為蟻群v第gen次迭代邊(i,j)上的信息素濃度，ρ為步驟2設(shè)置的信息素濃度揮發(fā)系數(shù)，為蟻群v在邊(i,j)上的信息素濃度增量，根據(jù)公式(10)計(jì)算：

其中，Q為步驟2設(shè)置的信息素濃度初值，path_k為步驟13得到的第k個粒子的路徑，為步驟13得到的第k個螞蟻的通過邊(i,j)的時間；

步驟21.根據(jù)步驟2設(shè)置的蟻群間通的信間隔gap，若gen mod gap＝＝0，即達(dá)到規(guī)定的迭代間隔，則蟻群p和蟻群v之間進(jìn)行通信，執(zhí)行下一步，否則執(zhí)行步驟25；

步驟22.蟻群間通信：蟻群p和蟻群v中的螞蟻除了通過各自的信息素搜索出口外，還通過蟻群間的通信來共享信息素，以改進(jìn)搜索過程；蟻群p和蟻群v按照公式(13)～公式(18)來更新各自群體的信息素：

τ^p＝λ_pτ^p+(1-λ_p)τ^v (13)

τ^v＝λ_vτ^v+(1-λ_v)τ^p (14)

λ_p、λ_v∈[0,1]分別是蟻群p和蟻群v的通信因子，是衡量蟻群p和蟻群v相互影響的參數(shù)；S_p、S_v分別是蟻群p和蟻群v的平均熵；為步驟12得到的t時刻蟻群p(蟻群v)中第k個螞蟻的熵，NP和NV分別是蟻群p和蟻群v的螞蟻數(shù)量；

步驟23.根據(jù)步驟18得到的蟻群p和蟻群v各自的疏散目標(biāo)f₁和f₂，按照公式(19)和(20)計(jì)算整個多蟻群系統(tǒng)的疏散目標(biāo)F₁和F₂，F(xiàn)₁和F₂即為優(yōu)化的兩個疏散目標(biāo)值；

步驟24.根據(jù)Pareto支配關(guān)系確定整個多蟻群系統(tǒng)的Pareto最優(yōu)解集ND_set；

步驟25.迭代計(jì)數(shù)器gen增加1；

步驟26.若gen≤T_MAX，T_MAX是步驟2中設(shè)置的最大迭代次數(shù)，將蟻群p和蟻群v中的所有螞蟻放置于步驟4設(shè)置的各自的初始位置節(jié)點(diǎn)上，重復(fù)步驟6-22，否則，迭代結(jié)束執(zhí)行步驟27；

步驟27.輸出Pareto最優(yōu)解集ND_set。