[發(fā)明專利]一種基于多蟻群的組合交通疏散優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310224838.4
• 申請(qǐng)日: 2013-06-07
• 公開（公告）號(hào): CN103336999A
• 公開（公告）日: 2013-10-02
• 發(fā)明（設(shè)計(jì)）人: 馬云龍;章鋒
• 申請(qǐng)（專利權(quán)）人: 同濟(jì)大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q50/26;G06N3/00;G08G1/00
• 代理公司: 上海寶鼎專利代理有限公司 31222
• 代理人: 崔維

1.一種基于多蟻群的組合交通疏散優(yōu)化方法，其特征在于，包括：?

a.將不同蟻群的螞蟻初始化至待疏散地區(qū)的網(wǎng)絡(luò)節(jié)點(diǎn)上；?

b.所述螞蟻構(gòu)建從初始的網(wǎng)絡(luò)節(jié)點(diǎn)至出口節(jié)點(diǎn)的疏散路徑并更新信息素，其中，所述出口節(jié)點(diǎn)包含于所述疏散網(wǎng)絡(luò)節(jié)點(diǎn)中；?

c.重復(fù)所述步驟b至自上一次蟻群間信息素交互的時(shí)間間隔達(dá)到此次交互時(shí)間間隔；?

d.所述蟻群根據(jù)信息素交互規(guī)則交互并更新所述信息素；?

e.重復(fù)所述步驟b至所述步驟d，直至滿足第一條件生成最優(yōu)疏散路徑。?

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述更新信息素包括：?

當(dāng)一蟻群內(nèi)所有螞蟻的疏散路徑構(gòu)建完成后，更新所述疏散路徑經(jīng)過的網(wǎng)絡(luò)節(jié)點(diǎn)相對(duì)應(yīng)的邊沿的信息素，其中每兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)與一條邊沿相對(duì)應(yīng)；以及?

比較此次構(gòu)建的最優(yōu)的疏散路徑與第一疏散路徑，并將最優(yōu)的疏散路徑替換所述第一疏散路徑，根據(jù)所述第一疏散路徑更新所述信息素，其中，所述第一疏散路徑初始為所述蟻群的螞蟻第一次構(gòu)建的疏散路徑的最優(yōu)的疏散路徑。?

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述螞蟻根據(jù)如下公式構(gòu)建從初始的網(wǎng)絡(luò)節(jié)點(diǎn)至出口節(jié)點(diǎn)的疏散路徑：?

其中，i、j為所述網(wǎng)絡(luò)節(jié)點(diǎn)序號(hào)，k為一蟻群內(nèi)的螞蟻序號(hào)，t_ij為邊(i，j)的通行時(shí)間，C_ij為邊(i，j)的通行能力，η_ij為啟發(fā)式，表示為邊沿(i，j)的通行時(shí)間t_ij乘以通行能力C_ij的倒數(shù)，表示所述蟻群第t次迭代時(shí)從網(wǎng)絡(luò)節(jié)點(diǎn)i到網(wǎng)絡(luò)節(jié)點(diǎn)j的轉(zhuǎn)移概率，U為當(dāng)前螞蟻k允許訪問的網(wǎng)絡(luò)節(jié)點(diǎn)的集合，d(i，j)為網(wǎng)絡(luò)節(jié)點(diǎn)i到網(wǎng)絡(luò)節(jié)點(diǎn)j的距離，α，β分別代表所述信息素和所述啟發(fā)式的權(quán)重，τ_ij(t)表示所述蟻群第t次迭代時(shí)邊沿(i，j)的信息素，τ(i，j)表示邊沿(i，j)的信息素，?q∈[0，1]是均勻分布的隨機(jī)數(shù)，q0是參數(shù)。?

4.根據(jù)權(quán)利要求2所述的方法，其特征在于，根據(jù)如下公式更新所述疏散路徑經(jīng)過的網(wǎng)絡(luò)節(jié)點(diǎn)相對(duì)應(yīng)的邊沿的信息素：?

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

其中，i、j為所述網(wǎng)絡(luò)節(jié)點(diǎn)序號(hào)，τ_ij′為邊沿(i，j)更新的信息素，τ_ij為邊沿(i，j)原來的信息素，k為一蟻群內(nèi)的螞蟻序號(hào)，M為所述蟻群內(nèi)的螞蟻個(gè)數(shù)，為螞蟻k通過邊沿(i，j)所需要的時(shí)間，P_k為螞蟻k的疏散路徑經(jīng)過的網(wǎng)絡(luò)節(jié)點(diǎn)的集合，Q是常數(shù)，表示所述螞蟻從初始的網(wǎng)絡(luò)節(jié)點(diǎn)至出口節(jié)點(diǎn)的疏散路徑所生成的總信息素，ρ是局部信息素衰變參數(shù)，其中，0＜ρ＜1。?

5.根據(jù)權(quán)利要求2所述的方法，其特征在于，根據(jù)所述第一疏散路徑更新所述信息素的公式如下所示：?

τ_ij′＝(1-γ)τ_ij+γΔτ_ij；?

其中，i、j為所述網(wǎng)絡(luò)節(jié)點(diǎn)序號(hào)，τ_ij′為邊沿(i，j)更新的信息素，τ_ij邊沿(i，j)原來的信息素，Q是常數(shù)，表示所述螞蟻從初始的網(wǎng)絡(luò)節(jié)點(diǎn)至出口節(jié)點(diǎn)的疏散路徑所生成的總信息素，L是所述第一疏散路徑的長度，r是全局信息素衰變參數(shù)，其中，0＜r＜1。?

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述此次交互時(shí)間間隔根據(jù)如下公式計(jì)算：?

其中，Δt_m為所述此次交互時(shí)間間隔，Δt_m-1為上一次交互時(shí)間間隔，ω_ave為平均收斂因子，a是一個(gè)常數(shù)。?

7.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述平均收斂因子ω_ave根據(jù)如下公式計(jì)算：?

其中，i、j為所述網(wǎng)絡(luò)節(jié)點(diǎn)序號(hào)，U是所述待疏散地區(qū)所有邊沿(i，j)的集合，ω(m)為一蟻群m的收斂因子，是所述蟻群m中邊沿(i，j)上的信息素，和分別是所述蟻群m中信息素的最大值和平均值，s是蟻群個(gè)數(shù)。?