• / 18
  • 下載費用:30 金幣  

基于云自適應粒子群算法的交通路徑搜索系統及方法.pdf

關 鍵 詞:
基于 自適應 粒子 算法 交通 路徑 搜索 系統 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201310716858.3

申請日:

2013.12.20

公開號:

CN103678649A

公開日:

2014.03.26

當前法律狀態:

駁回

有效性:

無權

法律詳情: 發明專利申請公布后的駁回IPC(主分類):G06F 17/30申請公布日:20140326|||實質審查的生效IPC(主分類):G06F 17/30申請日:20131220|||公開
IPC分類號: G06F17/30; G06N3/12 主分類號: G06F17/30
申請人: 上海電機學院
發明人: 寧建紅
地址: 200240 上海市閔行區江川路690號
優先權:
專利代理機構: 上海思微知識產權代理事務所(普通合伙) 31237 代理人: 鄭瑋
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201310716858.3

授權公告號:

||||||

法律狀態公告日:

2018.03.27|||2014.04.23|||2014.03.26

法律狀態類型:

發明專利申請公布后的駁回|||實質審查的生效|||公開

摘要

本發明公開了一種基于云自適應粒子群算法的交通路徑搜索系統及方法,該系統至少包括:模糊期望值模型建立模組,通過將交通路網節點與節點之間的距離描述成模糊變量的形式,建立模糊期望值模型;以及最短路徑計算模組,根據獲得的模糊期望值模型利用云自適應粒子群算法計算獲得交通路網節點和節點之間的最短距離,本發明通過利用云模型的隨機性和穩定傾向性的特點,并采用云模型的X條件云發生器自適應調節慣性權重,從而提高了避免陷入局部最優的能力,具有收斂速度快,魯棒性好的優點,能更快地搜索到交通網絡的最短路徑。

權利要求書

權利要求書
1.  一種基于云自適應粒子群算法的交通路徑搜索系統,至少包括:
模糊期望值模型建立模組,通過將交通路網節點與節點之間的距離描述成模糊變量的形式,建立模糊期望值模型;以及
最短路徑計算模組,根據獲得的模糊期望值模型利用云自適應粒子群算法計算獲得交通路網節點和節點之間的最短距離。

2.  如權利要求1所述的基于云自適應粒子群算法的交通路徑搜索系統,其特征在于,該模糊期望值模型為,

其中,為模糊變量,表示節點i到節點j的距離,設函數f(X,c~)=Σi=1nΣj=1nc~ijxij,]]>則期望值為:
E[f(X,c~)]=∫0+Cr{f(X,c~)≥r}dr-∫-0Cr{f(X,c~)r}dr]]>

3.  如權利要求2所述的基于云自適應粒子群算法的交通路徑搜索系統,其特征在于,該最短路徑計算模組至少包括:
初始化模組,用于初始化粒子種群,隨機產生各粒子的速度和位置向量,并且將個體的歷史最優設為當前位置,而群體中最優的個體位置作為整個粒子群當前的最優位置;
解碼模組,通過解碼獲得各粒子所代表路徑的長度;
目標值計算模組,利用模糊模擬計算各粒子的目標值;
適應度函數計算模組,根據粒子的目標值,計算各個粒子的適應度函數值;
第一判斷模組,判斷粒子當前的適應度函數值是否比其歷史最優值好,若該粒子當前的適應度函數值比其歷史最優值要好,則歷史最優被當前位置所替代;
第二判斷模組,判斷粒子的歷史最優是否比全局最優好,若該粒子的歷史最優比全局最優要好,則全局最優被該粒子的歷史最優所替代;
慣性權重自適應調整模組,根據粒子不同的適應度值,用利用云模型的X條件云發生器自適應調整粒子的慣性權重ω;
速度和位置更新模組,根據各粒子的慣性權重,利用速度更新公式及位置更新公式對每個粒子的速度和位置進行更新,對每個粒子利用速度更新公式和位置更新公式對速度和位置進行更新,并使速度每一維的坐標值為[-(n-1),n-1],使位置每一維的坐標值為[1,n]內的整數,n為種群的大小。

4.  如權利要求3所述的基于云自適應粒子群算法的交通路徑搜索系統,其特征在于:該初始化模組中,對每一維,位置坐標是在[1,n]內的整數,速度坐標是∈[-(n-1),n-1],第一維的速度和位置坐標都為1。

5.  如權利要求4所述的基于云自適應粒子群算法的交通路徑搜索系統,其特征在于,適應度函數計算模組根據如下公式計算各個粒子的適應度函數值:
f(Xi)=1E[f(X,c~)]]]>
其中為粒子的目標值。

6.  如權利要求5所述的基于云自適應粒子群算法的交通路徑搜索系統,其特征在于,該X條件云發生器為:
假設粒子群的平均適應度值為
Ex=favg,
En=變量搜索范圍/c3,
He=En/c4,
En′=RANDN(En,He),
w=0.9-0.5e-(f(Xi)-Ex)22(En)2]]>
其中c3、c4為控制參數,c3=3,c4=10,ω為慣性權重,Ex、En、He分別為期望值、熵、超熵。

7.  如權利要求6所述的基于云自適應粒子群算法的交通路徑搜索系統,其特征在于,該速度更新公式與位置更新公式分別為:
vid(t+1)=w×vid(t)+c1×rand()×pid-xid(t))+c2×rand()×(pgd-xid(t))
xid(t+1)=xid(t)+vid(t+1)
其中,xid(t)表示在t時刻,第i個粒子在第d維的位置,其飛行速度為vid(t),該粒子當前搜索到的最優位置為pid,整個粒子群當前的最優位置為pgd,w是慣性權重,c1和c2是學習因子,rand()是0~1間的隨機數。

8.  一種基于云自適應粒子群算法的交通路徑搜索方法,包括如下步驟:
步驟一,將交通路網節點和節點之間的距離描述成模糊變量的形式,建立模糊期望值模型;
步驟二,隨機產生各粒子的速度和位置向量,并且將個體的歷史最優設為當前位置,而群體中最優的個體位置作為整個粒子群當前的最優位置;
步驟三,通過解碼獲得各粒子所代表路徑的長度;
步驟四,使用模糊模擬計算所有粒子的目標值;
步驟五,根據各粒子的目標值,計算各個粒子的適應度函數值;
步驟六,若粒子當前的適應度函數值比其歷史最優值要好,則其歷史最優被當前位置所替代;
步驟七,若該粒子的歷史最優比全局最優要好,則全局最優被該粒子的歷史最優所替代;
步驟八,根據各粒子不同的適應度值,用云模型的X條件云發生器自適應調整各粒子的慣性權重;
步驟九,對每個粒子利用速度更新公式和位置更新公式對速度和位置進行更新,并使速度每一維的坐標值為[-(n-1),n-1],使位置每一維的坐標值為[1,n]內的整數,n為種群的大小;
步驟十,進化迭代次數加1,若還沒有到達結束條件,轉到步驟三,否則輸出并結束。

9.  如權利要求8所述的一種基于云自適應粒子群算法的交通路徑搜索方法,其特征在于,該X條件云發生器為:
假設粒子群的平均適應度值為
Ex=favg,
En=變量搜索范圍/c3,
He=En/c4,
En′=RANDN(En,He),
w=0.9-0.5e-(f(Xi)-Ex)22(En)2]]>
其中c3、c4為控制參數,c3=3,c4=10,ω為慣性權重,Ex、En、He分別為期望值、熵、超熵。

10.  如權利要求9所述的一種基于云自適應粒子群算法的交通路徑搜索方法,其特征在于,該速度更新公式與位置更新公式分別為:
vid(t+1)=w×vid(t)+c1×rand()×pid-xid(t))+c2×rand()×(pgd-xid(t))
xid(t+1)=xid(t)+vid(t+1)
其中,xid(t)表示在t時刻,第i個粒子在第d維的位置,其飛行速度為vid(t), 該粒子當前搜索到的最優位置為pid,整個粒子群當前的最優位置為pgd,w是慣性權重,c1和c2是學習因子,rand()是0~1間的隨機數。

說明書

說明書基于云自適應粒子群算法的交通路徑搜索系統及方法
技術領域
本發明涉及一種不確定環境下的交通路徑搜索系統及方法,特別是涉及一種基于云自適應粒子群算法的不確定環境的交通路徑搜索系統及方法。
背景技術
傳統的交通最短路徑的選擇往往是城市任意兩個地點的最短路徑,而駕駛員需要搜尋的是行駛時間最短的路徑。現實生活中行駛長度最短的路徑不一定就是行駛時間最短的路徑,因為隨時都有可能出現交通阻塞等意外情況,路網交通狀態具有實時可變的特點,具有不確定性的因素。根據這種情況,當前最常見的做法是把交通路網節點和節點之間的距離描述成模糊變量的形式,該模糊變量符合某種隸屬函數的分布,建立模糊期望值模型求解模糊最短路徑問題。由于一般模糊變量其隸屬函數的形式是多種多樣的,對于有些模糊變量來說,很難求出其具體的期望值,因此只能采用一些智能算法來進行求解。
粒子群算法PSO(particle swarm optimization)是由Kennedy和Eberhart在研究鳥類和魚類的群體行為基礎上于1995年提出的一種群智能算法。其思想來源于人工生命和演化計算理論,模仿鳥群飛行覓食行為,通過鳥集體協作使群體達到最優。PSO模擬鳥群的捕食行為,每個優化問題的解都是搜索空間中的一只鳥,稱之為“粒子”。所有的粒子都有一個由被優化的函數決定的適應值,每個粒子還有一個速度決定它們飛翔的方向和距離。然后粒子們就追隨當前的最優粒子在解空間中進行搜索,直至搜索到最優解。
粒子群算法采用實數求解,并且需要調整的參數較少,易于實現。但是該算法也存在易于陷入局部最優,出現早熟收斂的問題。在計算粒子的速度時,將慣性權重引入算法,通過實驗研究表明,該參數對算法的性能有較大的影響。 如果w值較大,有利于跳出局部最優,進行全局尋優;而w值較小,有利于局部尋優,加速算法收斂。一般的做法是將w值隨著迭代次數的增加而線性減少。但是這樣做較依賴于迭代次數,不能反映實際粒子變化的情況,不能反映實際優化搜索過程。
發明內容
為克服上述現有技術存在的不足,本發明的主要目的在于提供一種基于云自適應粒子群算法的交通路徑搜索系統及方法,其通過利用云模型的隨機性和穩定傾向性的特點,并采用云模型的X條件云發生器自適應調節慣性權重,從而提高了避免陷入局部最優的能力,具有收斂速度快,魯棒性好的優點,能更快地搜索到交通網絡的最短路徑。
為達上述及其它目的,本發明一種基于云自適應粒子群算法的交通路徑搜索系統,至少包括:
模糊期望值模型建立模組,通過將交通路網節點與節點之間的距離描述成模糊變量的形式,建立模糊期望值模型;以及
最短路徑計算模組,根根據獲得的模糊期望值模型利用云自適應粒子群算法計算獲得交通路網節點和節點之間的最短距離。
進一步地,該模糊期望值模型為,

其中,為模糊變量,表示節點i到節點j的距離,設函數f(X,c~)=Σi=1nΣj=1nc~ijxij,]]>則期望值為:
E[f(X,c~)]=∫0+Cr{f(X,c~)≥r}dr-∫-0Cr{f(X,c~)r}dr]]>
進一步地,該最短路徑計算模組至少包括:
初始化模組,用于初始化粒子種群,隨機產生各粒子的速度和位置向量,并且將個體的歷史最優設為當前位置,而群體中最優的個體位置作為整個粒子群當前的最優位置;
解碼模組,通過解碼獲得各粒子所代表路徑的長度;
目標值計算模組,利用模糊模擬計算各粒子的目標值;
適應度函數計算模組,根據粒子的目標值,計算各個粒子的適應度函數值;
第一判斷模組,判斷粒子當前的適應度函數值是否比其歷史最優值好,若該粒子當前的適應度函數值比其歷史最優值要好,則歷史最優被當前位置所替代;
第二判斷模組,判斷粒子的歷史最優是否比全局最優好,若該粒子的歷史最優比全局最優要好,則全局最優被該粒子的歷史最優所替代;
慣性權重自適應調整模組,根據粒子不同的適應度值,用利用云模型的X條件云發生器自適應調整粒子的慣性權重ω;
速度和位置更新模組,根據各粒子的慣性權重,利用速度更新公式及位置更新公式對每個粒子的速度和位置進行更新,對每個粒子利用速度更新公式和位置更新公式對速度和位置進行更新,并使速度每一維的坐標值為[-(n-1),n-1],使位置每一維的坐標值為[1,n]內的整數,n為種群的大小。
進一步地,該初始化模組中,對每一維,位置坐標是在[1,n]內的整數,速度坐標是∈[-(n-1),n-1],第一維的速度和位置坐標都為1。
進一步地,適應度函數計算模組根據如下公式計算各個粒子的適應度函數 值:
f(Xi)=1E[f(X,c~)]]]>
其中為粒子的目標值。
進一步地,該X條件云發生器為:
假設粒子群的平均適應度值為
Ex=favg,
En=變量搜索范圍/c3,
He=En/c4,
En′=RANDN(En,He),
w=0.9-0.5e-(f(Xi)-Ex)22(En)2]]>
其中c3、c4為控制參數,c3=3,c4=10,ω為慣性權重,Ex、En、He分別為期望值、熵、超熵。
進一步地,該速度更新公式與位置更新公式分別為:
vid(t+1)=w×vid(t)+c1×rand()×pid-xid(t))+c2×rand()×(pgd-xid(t))
xid(t+1)=xid(t)+vid(t+1)
其中,xid(t)表示在t時刻,第i個粒子在第d維的位置,其飛行速度為vid(t),該粒子當前搜索到的最優位置為pid,整個粒子群當前的最優位置為pgd,w是慣性權重,c1和c2是學習因子,rand()是0~1間的隨機數。
為達到上述目的,本發明還提供一種基于云自適應粒子群算法的交通路徑搜索方法,包括如下步驟:
步驟一,將交通路網節點和節點之間的距離描述成模糊變量的形式,建立模糊期望值模型;
步驟二,隨機產生各粒子的速度和位置向量,并且將個體的歷史最優設為 當前位置,而群體中最優的個體位置作為整個粒子群當前的最優位置;
步驟三,通過解碼獲得各粒子所代表路徑的長度;
步驟四,使用模糊模擬計算所有粒子的目標值;
步驟五,根據各粒子的目標值,計算各個粒子的適應度函數值;
步驟六,若粒子當前的適應度函數值比其歷史最優值要好,則其歷史最優被當前位置所替代;
步驟七,若該粒子的歷史最優比全局最優要好,則全局最優被該粒子的歷史最優所替代;
步驟八,根據各粒子不同的適應度值,用云模型的X條件云發生器自適應調整各粒子的慣性權重;
步驟九,對每個粒子利用速度更新公式和位置更新公式對速度和位置進行更新,并使速度每一維的坐標值為[-(n-1),n-1],使位置每一維的坐標值為[1,n]內的整數,n為種群的大小;
步驟十,進化迭代次數加1,若還沒有到達結束條件,轉到步驟三,否則輸出并結束。
進一步地,該X條件云發生器為:
假設粒子群的平均適應度值為
Ex=favg,
En=變量搜索范圍/c3,
He=En/c4,
En′=RANDN(En,He),
w=0.9-0.5e-(f(Xi)-Ex)22(En)2]]>
其中c3、c4為控制參數,c3=3,c4=10,ω為慣性權重,Ex、En、He分別 為期望值、熵、超熵。
進一步地,該速度更新公式與位置更新公式分別為:
vid(t+1)=w×vid(t)+c1×rand()×pid-xid(t))+c2×rand()×(pgd-xid(t))
xid(t+1)=xid(t)+vid(t+1)
其中,xid(t)表示在t時刻,第i個粒子在第d維的位置,其飛行速度為vid(t),該粒子當前搜索到的最優位置為pid,整個粒子群當前的最優位置為pgd,w是慣性權重,c1和c2是學習因子,rand()是0~1間的隨機數。
與現有技術相比,本發明一種基于云自適應粒子群算法的交通路徑搜索系統及方法將云自適應粒子群算法引入不確定環境交通路徑搜索問題,根據該算法收斂速度快的特點,能夠高效地搜索出交通最短路徑,同時具備了穩定傾向性和隨機性的特點,能夠快速搜索出最短路徑,提高了出行者的出行效率,本發明具有一定的通用性,采用本發明,面對不同類型的復雜交通網絡,網絡中弧的權值可能服從不同的隸屬函數分布,也能迅速為出行者選出合適的出行路線。
附圖說明
圖1為本發明一種基于云自適應粒子群算法的交通路徑搜索系統的系統架構圖;
圖2為本發明一種基于云自適應粒子群算法的交通路徑搜索方法的步驟流程圖;
圖3為本發明較佳實施例中云自適應粒子群算法的流程圖。
具體實施方式
以下通過特定的具體實例并結合附圖說明本發明的實施方式,本領域技術人員可由本說明書所揭示的內容輕易地了解本發明的其它優點與功效。本發明亦可通過其它不同的具體實例加以施行或應用,本說明書中的各項細節亦可基 于不同觀點與應用,在不背離本發明的精神下進行各種修飾與變更。
在介紹本發明之前,先簡要說明一下云模型的有關概念。云模型是李德毅院士提出的一種定性知識描述和定性概念與其定量數值表示之間的不確定性轉換模型,主要反映客觀世界中事物或人類知識中概念的模糊性和隨機性,并把二者完全集成在一起。云模型在知識表達時具有不確定中帶有確定性、穩定之中又有變化的特點,體現了自然界物種進化的基本原理。云模型是一個遵循正態分布規律并具有穩定傾向的隨機數集,其三個數字特征用期望值Ex、熵En和超熵He來表征,反映了定性概念的整體特性。云自適應粒子群算法根據粒子適應度值來確定慣性權重的值,由X條件云發生器自適應調整粒子群的慣性權重,由于云模型云滴具有隨機性和穩定性傾向性的特點,使慣性權重既滿足快速尋優能力,又具有隨機性,隨機性可以保持個體多樣性從而避免搜索陷入局部極值。而穩定傾向性又可以很好地保護較優個體從而對全局最值進行自適應定位。
圖1為本發明一種基于云自適應粒子群算法的交通路徑搜索系統的系統架構圖。如圖1所示,本發明一種基于云自適應粒子群算法的交通路徑搜索系統,運用云模型進化算法求解最短路徑,其至少包括:模糊期望值模型建立模組11以及最短路徑計算模組12
其中模糊期望值模型建立模組11通過將交通路網節點和節點之間的距離描述成模糊變量的形式,建立模糊期望值模型,其中,該模糊變量符合某種隸屬函數的分布。在本發明之較佳實施例中,該模糊期望值模型的建立方法如下:
在有向圖G(V,E)中,V是頂點集合,E是邊的集合,cij表示節點i到節點j的距離cij≥0,但是很多時候cij是不確定的,是模糊的,可以用模糊變量表示,其中源點為節點1,終點為節點n,求1到n的最短路徑。

因此,模糊期望值模型的可建立如下所示:

設函數f(X,c~)=Σi=1nΣj=1nc~ijxij]]>
用模糊期望值模型求解最短路徑問題,方法就是取目標函數和約束條件的期望值,因為目標函數中含有模糊變量,可以根據模糊變量期望值的定義求出其期望值,約束條件不含模糊變量,還保持原來的形式。
因此,該模糊期望值模型又可表示如下:

若為一般的模糊變量,則也為模糊變量,其期望值為:
E[f(X,c~)]=∫0+Cr{f(X,c~)≥r}dr-∫-0Cr{f(X,c~)r}dr]]>
以下進行模糊模擬
首先分別從的α水平集中均勻的產生 b11,b12,…,b1n,…,bn1,bn2,…,bnn,記為B=(b11,b12,…,b1n,…,bn1,bn2,…,bnn),如果α水平集不容易確定,可以給出包含α水平集的超幾何體,從包含α水平集的超幾何體產生bij。令u=u11(b11)∧u12(b12)∧…∧unn(bnn),其中uij(x)為的隸屬函數,計算f(X,B),重復以上過程N次,得到f1(X,B),f2(X,B),…fN(X,B)及u1,u2,…,uN。
對于任意的r≥0,可信性近似等于:
12(max1kN{uk|fk(X,B)&GreaterEqual;r}+min1kN{1-uk|fk(X,B)<r})]]>
對于任意的r<0,可信性近似等于:
12(max1kN{uk|fk(X,B)r}+min1kN{1-uk|fk(X,B)>r})]]>
模擬步驟如下:
Step1:置m=0
Step2:分別從的α水平集中均勻的產生b11,b12,…,b1n,…,bn1,bn2,…,bnn,令B=(b11,b12,…,b1n,…,bn1,bn2,…,bnn)。
Step3:計算u=u11(b11)∧u12(b12)∧…∧unn(bnn)和f(X,B)。
Step4:重復Step2,Step3N次。
Step5:令a=f1(X,B)∧f2(X,B)∧…∧fn(X,B)。
b=f1(X,B)∨f2(X,B)∨…∨fn(X,B)。
Step6:從[a,b]中均勻產生r。
Step7:如果r≥0,則m=m+Cr{f(X,B)≥r}。
Step8:如果r≤0,則m=m-Cr{f(X,B)≥r}。
Step9:重復Step6至Step8共N次。
Step10:
由于一般模糊變量其隸屬函數的形式可以多種多樣,對于有些模糊變量來說,很難求出其具體的期望值。這時,可以采用基于模糊模擬的云自適應粒子 群算法進行求解。
最短路徑計算模組12根據獲得的模糊期望值模型利用云自適應粒子群算法計算獲得交通路網節點和節點之間的最短距離。在介紹最短路徑計算模組之前,先介紹粒子群算法原理與云模型的相關概念及操作。
粒子群算法原理:在PSO中,每個優化問題的解看作搜索空間中的一只鳥(即粒子),所有的粒子都有一個被優化的函數決定的適應值,并且有一個速度決定它們飛翔的方向和速率,粒子們追隨當前的最優粒子在解空間中搜索。算法首先初始化一群隨機粒子,然后通過迭代找到最優解。在每一次迭代中,粒子通過跟蹤兩個“極值”即個體極值和全局極值來更新自己的速度與位置。在d維目標搜索空間中,由種群數為m的粒子組成粒子群,其中在t時刻,第i個粒子在第d維的位置為xid(t),其飛行速度為vid(t),該粒子當前搜索到的最優位置為pid(pbest),整個粒子群當前的最優位置為pgd(gbest)。在找到這兩個最優值時,粒子根據如下的公式來更新自己的速度和新的位置:
vid(t+1)=w×vid(t)+c1×rand()×pid-xid(t))+c2×rand()×(pgd-xid(t))  (1)
xid(t+1)=xid(t)+vid(t+1)  (2)
其中,w是慣性權重,c1和c2是學習因子,通常c1=c2=2,rand()是0~1間的隨機數。在每一維粒子的速度都會被限制在一個最大速度vmax,如果某一維更新后的速度超過用戶設定的vmax,那么這一維的速度就被限定為vmax。在本發明中,公式(1)被稱為速度更新公式,公式(2)被稱為位置更新公式。
云模型:正態云模型的定義,設T為論域u上的語言值,映射Cr(x):則Cr(x)在u上的分布,稱為T的隸屬云,簡稱云。當Cr(x)服從正態分布時,稱為正態云模型。
正態云模型是一個遵循正態分布規律、具有穩定傾向的隨機數集,用期望值Ex、熵En、超熵He三個數值來表征。期望值Ex:在數域空間最能夠代表這個定性概念的點,反映了云的重心位置。熵En:一方面反映了在數域空間可被 語言值接受的范圍;另一方面還反映了在數域空間的點能夠代表這個語言值的概率,表示定性概念的云滴出現的隨機性,它揭示了模糊性和隨機性的關聯性。超熵He:是熵的不確定度量,即熵的熵,反映了在數域空間代表該語言值的所有點的不確定度的凝聚性,即云滴的凝聚度。
基本云發生器算法:
INPUT:{Ex,En,He},n//數字特征和云滴數
OUTPUT:{(x1,μ1),(x2,μ2)…(xn,μn)}//n個云滴
FOR i=1to n
//生成期望值為En、方差為He的正態隨機數
En′=RANDN(En,He),
xi=RANDN(Ex,En′)
μi=e-(xi-Ex)22(En)2]]>
DROP(xi,μi)//生成第i個云滴。
X條件云發生器算法:
INPUT:{Ex,En,He},n,x0
OUTPUT:{(x0,μ1),(x0,μ2)…(x0,μn)}
FOR i=1to n
En′=RANDN(En,He)
μi=e-(x0-Ex)22(En)2]]>
DROP(x0,μi)
最短路徑計算模組12進一步包括:初始化模組120、解碼模組121、目標值計算模組122、適應度函數計算模組123、第一判斷模組124、第一判斷模組124、慣性權重自適應調整模組126以及速度和位置更新模組127。
其中初始化模組120用于初始化粒子種群,隨機產生各粒子的速度和位置向量,并且將個體的歷史最優設為當前位置,而群體中最優的個體位置作為整個粒子群當前的最優位置,對每一維,位置坐標是在[1,n]內的整數,速度坐標是∈[-(n-1),n-1],設第一維的速度和位置坐標都為1。在本發明較佳實施例中,設定迭代次數為Max,種群的大小為n,即共有n個粒子。種群中粒子的位置及其速度采用實數編碼。d表示參數的維數,f(X)表示適應度函數。第i個粒子的位置為(xi1,xi2,xi3,…,xid),第i個粒子的速度為(v11,v12,v13,…,v1d),第i個粒子的適應度函數為f(Xi)。
解碼模組121,通過解碼獲得各粒子所代表路徑的長度。對于某個粒子,第1維坐標值為1,第2維坐標值為路徑上第2個節點的節點號,第i維坐標值為路徑上第i個節點的節點號,以此類推。每一個粒子代表一條路徑,通過解碼可以得到每條路徑的長度。
目標值計算模組122,利用模糊模擬計算粒子的目標值,即適應度函數計算模組123,根據粒子的目標值,計算各個粒子的適應度函數值,令適應度函數為第一判斷模組124,判斷粒子當前的適應度函數值是否比其歷史最優值好,若該粒子當前的適應度函數值比其歷史最優值要好,那么歷史最優將會被當前位置所替代;第二判斷模組125,判斷粒子的歷史最優是否比全局最優好,若該粒子的歷史最優比全局最優要好,那么全局最優將會被該粒子的歷史最優所替代;慣性權重自適應調整模組126,根據粒子不同的適應度值,用云模型的X條件云發生器自適應調整粒子的慣性權重ω。假設粒子群的平均適應度值為
Ex=favg
En=變量搜索范圍/c3
He=En/c4
En′=RANDN(En,He)
w=0.9-0.5e-(f(Xi)-Ex)22(En)2]]>
其中c3、c4為控制參數,c3=3,c4=10。
速度和位置更新模組127,利用速度更新公式及位置更新公式對每個粒子的速度和位置進行更新,并使速度每一維的坐標值為[-(n-1),n-1],如果取值大于n-1,則取值n-1,小于-(n-1)則取值-(n-1);并使位置每一維的坐標值為[1,n]內的整數,如果取值大于n,則取值n,小于1,則取1。
圖2為本發明一種基于云自適應粒子群算法的交通路徑搜索方法的步驟流程圖,圖3為本發明較佳實施例中云自適應粒子群算法的流程圖。如圖2及圖3所示,本發明一種基于云自適應粒子群算法的交通路徑搜索方法,利用云自適應例子群算法求解交通網點節點與節點間的最短路徑,其包括如下步驟:
步驟201,將交通路網節點和節點之間的距離描述成模糊變量的形式,建立模糊期望值模型,該模糊期望值模型可表示如下:

若為一般的模糊變量,則也為模糊變量,其期望值為:
E[f(X,c~)]=&Integral;0+Cr{f(X,c~)&GreaterEqual;r}dr-&Integral;-0Cr{f(X,c~)r}dr]]>
步驟202,初始化粒子種群,隨機產生各粒子的速度和位置向量,并且將個體的歷史最優設為當前位置,而群體中最優的個體位置作為整個粒子群當前的最優位置,對每一維,位置坐標是在[1,n]內的整數,速度坐標是∈[-(n-1),n-1],設第一維的速度和位置坐標都為1。在本發明較佳實施例中,設定迭代次數為Max,種群的大小為n,即共有n個粒子。種群中粒子的位置及其速度采用實數編碼。d表示參數的維數,f(X)表示適應度函數。第i個粒子的位置為(xi1,xi2,xi3,…,xid),第i個粒子的速度為(v11,v12,v13,…,v1d),第i個粒子的適應度函數為f(Xi)。
步驟203,通過解碼獲得各粒子所代表路徑的長度。對于某個粒子,第1維坐標值為1,第2維坐標值為路徑上第2個節點的節點號,第i維坐標值為路徑上第i個節點的節點號,以此類推。每一個粒子代表一條路徑,通過解碼可以得到每條路徑的長度。
步驟204,使用模糊模擬計算所有粒子的目標值,即
步驟205,根據粒子目標值,計算各個粒子的適應度函數值,令適應度函數為f(Xi)=1E[f(X,c~)].]]>
步驟206,若粒子當前的適應度函數值比其歷史最優值要好,那么其歷史最優將會被當前位置所替代。
步驟207,若該粒子的歷史最優比全局最優要好,那么全局最優將會被該粒子的歷史最優所替代。
步驟208,根據粒子不同的適應度值,用云模型的X條件云發生器自適應調整粒子的慣性權重ω。假設粒子群的平均適應度值為
Ex=favg
En=變量搜索范圍/c3
He=En/c4
En′=RANDN(En,He)
w=0.9-0.5e-(f(Xi)-Ex)22(En)2]]>
其中c3、c4為控制參數,c3=3,c4=10。
步驟209,對每個粒子利用速度更新公式和位置更新公式對速度和位置進行更新。并使速度每一維的坐標值為[-(n-1),n-1],如果取值大于n-1,則取值n-1,小于-(n-1)則取值-(n-1);并使位置每一維的坐標值為[1,n]內的整數,如果取值大于n,則取值n,小于1,則取1。
步驟210,進化代數加1,如果還沒有到達結束條件(例如迭代次數到達最大值Max),轉到步驟203,否則輸出并結束。
可見,本發明云自適應粒子群算法利用了正態云模型的穩定傾向性、隨機性特點。穩定傾向性可以較好地保護較佳個體從而實現對最優值的自適應定位,隨機性可以保持個體多樣性從而提高算法防止陷入局部極值。每個粒子都被賦予一個隨機速度在整個路徑問題空間運動,并且通過計算適應度值可以對自己所處的環境加以評估。根據每個粒子的適應度值,能夠自適應地計算其慣性權重,適應度值較高的,慣性權重較低,適應度值較低的,慣性權重較高。使適應度較大的個體在較小的鄰域內進行搜索,適應度較小的個體在較大的鄰域內進行搜索。基于以上原因,交通最短路徑很快能夠搜索得到。
綜上所述,本發明一種基于云自適應粒子群算法的交通路徑搜索系統及方法將云自適應粒子群算法引入不確定環境交通路徑搜索問題,根據該算法收斂速度快的特點,能夠高效地搜索出交通最短路徑,同時具備了穩定傾向性和隨機性的特點,能夠快速搜索出最短路徑,提高了出行者的出行效率,本發明具有一定的通用性,采用本發明,面對不同類型的復雜交通網絡,網絡中弧的權 值可能服從不同的隸屬函數分布,也能迅速為出行者選出合適的出行路線。
上述實施例僅例示性說明本發明的原理及其功效,而非用于限制本發明。任何本領域技術人員均可在不違背本發明的精神及范疇下,對上述實施例進行修飾與改變。因此,本發明的權利保護范圍,應如權利要求書所列。

關于本文
本文標題:基于云自適應粒子群算法的交通路徑搜索系統及方法.pdf
鏈接地址:http://www.pqsozv.live/p-6180535.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
钻石光影