[發明專利]基于人工魚群算法的交通路徑搜索方法

在審

• 申請號: 201410697094.2
• 申請日: 2014-11-27
• 公開（公告）號: CN104392283A
• 公開（公告）日: 2015-03-04
• 發明（設計）人: 寧建紅
• 申請（專利權）人: 上海電機學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

技術領域

本發明涉及一種基于人工魚群算法的交通路徑搜索方法。

背景技術

傳統的交通路徑搜索方法一般是選擇城市任意兩個地點之間的最短路徑，而駕駛員需要搜尋的則是行駛時間最短的路徑，而現實生活中，由于交通阻塞等意外情況，行駛長度最短的路徑不一定就是行駛時間最短的路徑。根據這種情況，通常采用一些智能算法來進行最短路徑的求解。

一種是粒子群算法(PSO，英文全稱：particle?swarm?optimization)，PSO模擬鳥群的捕食行為，每個優化問題的解都是搜索空間中的一只鳥，稱之為“粒子”，所有的粒子都有一個由被優化的函數決定的適應值，每個粒子還有一個速度決定它們飛行的方向和距離，然后粒子們就追隨當前的最優粒子在解空間中進行搜索，直至搜索到最優解。但是該算法存在易于陷入局部最優，出現早熟收斂的問題。在計算粒子的速度時，將慣性權重w引入算法。通過實驗研究表明，該參數對算法的性能有較大的影響，如果w值較大，有利于跳出局部最優，進行全局尋優；而w值較小，有利于局部尋優，加速算法收斂，一般的做法是將w值隨著迭代次數的增加而線性減少，但是這樣做又依賴于迭代次數，不能反映實際粒子變化的情況，不能反映實際優化搜索過程。

另一種智能算法是遺傳算法，它模擬自然選擇和自然遺傳過程中發生的繁殖、交配和變異現象，根據適者生存、優勝劣汰的自然法則，通過選擇、交叉和變異等遺傳算子，使群體一代一代地進行到搜索空間中越來越好的區域，直至獲得最優解。遺傳算法有三個基本算子：選擇、交叉和變異，這三個算子的實現也有許多參數，如交叉概率和變異概率，并且這些參數的選擇嚴重影響解的品質，而目前這些參數的選擇大部分是依靠經驗。遺傳算法善長全局搜索，然而其局部搜索能力卻明顯不足，搜索到最優解或滿意解的速度較慢，存在易陷入局部最優解和選擇壓力過大造成的早熟收斂等問題。

發明內容

本發明提供一種基于人工魚群算法的交通路徑搜索方法，以解決上述技術問題。

為解決上述技術問題，本發明提供一種基于人工魚群算法的交通路徑搜索方法，包括如下步驟：其中，設定算法的最大迭代次數為Max，種群的大小為n，參數的維數為d，第i條魚的狀態位置為(X_i1,X_i2,X_i3,…,X_id)，第i條魚的食物濃度為f(X_i)，經過模糊模擬后的最短路徑值為

S1：初始化算法參數，視野visual＝45、步長step＝0.3、嘗試次數try_number＝100，擁擠度因子λ＝0.8，迭代最大次數Max＝200；

S2：在解空間內對魚群進行隨機初始化，置迭代次數t＝1，生成n個人工魚個體，形成初始魚群，每一個人工魚代表從起點到目標點的一種路徑；

S3：使用模糊模擬計算人工魚的目標值取出當前最優解X_gbest，寫入公告板；

S4：判斷算法是否到達最大迭代次數Max，若是，則輸出公告板上的最優解，算法結束；若否則執行步驟S5-S9；

S5：魚群中全部個體執行隨機的自由游動，并更新各自的自身狀態X_i；

S6：在視野visual內執行覓食操作，并移動一個步長step；

S7：執行聚群操作；

S8：執行追尾操作；

S9：令迭代次數t＝t+1，然后返回執行步驟S3。

較佳地，所述自由游動的步驟為：魚在自己視野visual內隨機移動一個步長step。

較佳地，所述覓食操作的步驟為：魚在其視野visual之內隨機選擇一新狀態X_j，若f(X_j)＜f(X_i)，則向該狀態移動；否則，繼續生成新的X_j進行嘗試，嘗試try_number次后仍然不能移動，則隨機移動一步，X_j＝X_i+visual·random()，其中random()為[0,1]間的隨機數。