[發明專利]一種基于多蟻群的組合交通疏散優化方法

有效

• 申請號: 201310224838.4
• 申請日: 2013-06-07
• 公開（公告）號: CN103336999A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 馬云龍;章鋒
• 申請（專利權）人: 同濟大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/26;G06N3/00;G08G1/00
• 代理公司: 上海寶鼎專利代理有限公司 31222
• 代理人: 崔維

技術領域

本發明涉及智能交通仿真與評估領域。

背景技術

傳統的群智能算法解決路徑規劃主要是針對一個或幾個個體，尋找路徑最短或其他的目標的路徑解決方案，在緊急疏散路徑規劃中，研究目標通常為大規模待疏散人群，由于恐慌或擁堵會造成人員速度的變化，因此在疏散路徑規劃中更需要著重考慮多疏散人員的路徑組合優化，這樣傳統的路徑規劃方法很難直接應用于疏散規劃中。因此需要一種從全局角度出發面向大規模疏散人員的疏散路徑規劃方法。

為了更好得從宏觀上提供大型場館應急疏散的全局路徑優化分析，一些研究人員提出了將蟻群算法應用于疏散路徑優化。蟻群算法可以很好地模擬大規模人群疏散時行人的速度變化情況，同時其正反饋特性和較強的局部搜索能力使得它適合解決緊急疏散中的路徑規劃問題。蟻群算法雖然能夠比較好地解決緊急疏散中的路徑優化問題，但自身方面也存在一些不足，如易出現停滯現象而陷入局部最優解等。

蟻群優化(Ant?colony?optimization，ACO)算法具有結構簡單、適合分布式計算、易于與其他算法結合、魯棒性強等優點，因而得到了廣泛的應用。ACO的生態屬性及設計思想決定了ACO的并行化是避免早熟收斂、提升效率的自然方向。并行策略可粗略地分為精細并行策略和粗糙并行策略。諸多文獻和實驗表明，龐大的通信開銷是精細并行策略的主要瓶頸；而粗糙并行策略，多個蟻群并行地工作在不同的處理器中，各算法的區別在于信息交換的時機和內容，一種極端情況是完全不交換，獨立運行。共享信息素矩陣是信息交換的另一種形式。盡管已經實現了一些ACO并行算法，但不同的交換策略會產生什么樣的行為，以及相對于順序版本算法的性能將得到何種程度的改進仍然是兩個有待解決的問題。在疏散研究中，并行蟻群或多蟻群的應用并不多見，各蟻群間也毫無聯系。

發明內容

針對現有技術的缺陷，本發明提供一種基于多蟻群疏散優化的信息素交互方法，其特征在于，包括：a.將不同蟻群的螞蟻初始化至待疏散地區的網絡節點上；b.所述螞蟻構建從初始的網絡節點至出口節點的疏散路徑并更新信息素，其中，所述出口節點包含于所述疏散網絡節點中；c.重復所述步驟b至自上一次蟻群間信息素交互的時間間隔到達此次交互時間間隔；d.所述蟻群根據信息素交互規則交互并更新所述信息素；e.重復所述步驟b至所述步驟d，直至滿足第一條件生成最優疏散路徑。

優選地，所述更新信息素包括：當一蟻群內所有螞蟻的疏散路徑構建完成后，更新所述疏散路徑經過的網絡節點相對應的邊沿的信息素，其中每兩個網絡節點與一條邊沿相對應；以及比較此次構建的最優的疏散路徑與第一疏散路徑，并將最優的疏散路徑替換所述第一疏散路徑，根據所述第一疏散路徑更新所述信息素，其中，所述第一疏散路徑初始為所述蟻群的螞蟻第一次構建的疏散路徑的最優的疏散路徑。

優選地，所述螞蟻根據如下公式構建從初始的網絡節點至出口節點的疏散路徑：

ηij=1tij·Cij;]]>

其中，i、j為所述網絡節點序號，k為一蟻群內的螞蟻序號，t_ij為邊(i，j)的通行時間，C_ij為邊(i，j)的通行能力，η_ij為啟發式，表示為邊沿(i，j)的通行時間t_ij乘以通行能力C_ij的倒數，表示所述蟻群第t次迭代時從網絡節點i到網絡節點j的轉移概率，U為當前螞蟻k允許訪問的網絡節點的集合，d(i，j)為網絡節點i到網絡節點j的距離，α，β分別代表所述信息素和所述啟發式的權重，τ_ij(t)表示所述蟻群第t次迭代時邊沿(i，j)的信息素，τ(i，j)表示邊沿(i，j)的信息素，q∈[0，1]是均勻分布的隨機數，q₀是參數。

優選地，根據如下公式更新所述疏散路徑經過的網絡節點相對應的邊沿的信息素：

τ_ij′＝(1-ρ)τ_ij+ρΔτ_ij；