求解Logit隨機用戶均衡問題的改進人工魚群算法

摘 要： 針對人工魚群算法求解大型優化問題時存在探索能力差以及搜索盲目性大的缺點，設計一種定向搜索變異的改進人工魚群算法，該算法在迭代過程中不僅保證魚群在當前狀態下能夠自適應變異，并且還可以使其向當前最優位置移動。隨后將這種改進人工魚群算法應用于求解Logit隨機用戶均衡問題，構建了隨機用戶均衡交通分配問題新的模型和求解方法。仿真結果表明，該方法具有較好的穩定性和收斂速度，具有在大型城市交通分配問題中應用的潛力。

關鍵詞： 人工魚群算法； 自適應變異； 交通分配； Logit隨機用戶均衡

中圖分類號： TN911?34； TP18 文獻標識碼： A 文章編號： 1004?373X（2016）03?0127?04

Improved artificial fish swarm algorithm for solving Logit stochastic user equilibrium problem

LIU Bingquan1， DU Wei2

（1. College of Mathematics and Information Science， Weinan Normal University， Weinan 714099， China；

2. College of Transportation， Nantong University， Nantong 226019， China）

Abstract： Since the artificial fish swarm algorithm has the disadvantages of poor exploration ability and big searching blindness for solving the large optimization problem， an improved artificial fish swarm algorithm based on directed search variation was designed. The algorithm in the iterative process can ensure the adaptive variation of the fish swarm in current situation， and make the fish swarm move towards the optimal position. This algorithm is applied to solving the Logit stochastic user equilibrium problem， and the new model and solving method for stochastic user equilibrium traffic assignment were constructed. The simulation results show that the method has good stability and fast convergence rate， and has the application potential for traffic assignment problem in big cities.

Keywords： artificial fish swarm algorithm； adaptive variation； traffic assignment； Logit stochastic user equilibrium

0 引 言

人工魚群算法（AFSA）是一種模擬魚群行為進行隨機搜索的群體智能優化算法，該算法對初始值和參數的選擇不敏感，并且使用靈活，魯棒性強，由于在算法中僅考察適應度函數，無須了解所求問題的內部信息，因此該算法具有良好的克服局部極值，取得全局極值的能力[1?2]。AFSA進行迭代的基本機理是通過群體之間的信息共享和個體自身調整求取全局最優解。其主要利用魚的覓食、聚群和追尾行為，從構造單個魚的底層行為開始，通過魚群中各個體的局部尋優達到全局最優，該算法已經在交通規劃、電網系統中取得了良好的應用效果[3?4]。但是人工魚群算法在解決大型優化問題時，其保持探索與開發平衡的能力較差，并且算法運行后期搜索的盲目性較大，當一部分人工魚處于漫無目的的隨機移動或人工魚在非全局極值點出現較嚴重聚集情況時，其收斂速度將大大減慢，甚至有時會陷入局部極值，搜索性能劣化，使得該算法得到的是滿意解，其精度不是很高，從而影響了算法的質量和效率[5?6]。因此設計一種搜索性能更好、迭代效率和計算精度更高的改進人工魚群算法具有很好的應用前景。

本文針對人工魚群算法求解大型優化問題時存在探索能力差以及搜索盲目性大的缺點，提出了一種具有定向搜索和自適應變異的改進人工魚群算法，在算法迭代過程中，使該算法既具有向當前全局最優點靠攏，又具有避免陷入局部最優的特點，并將該算法用于求解隨機用戶平衡交通分配問題，構建了求解這類問題新的模型和方法。仿真結果表明，該算法在求解交通優化問題時，具有較好的收斂速度和良好的尋優能力，適合在大規模城市交通分配問題中應用。

1 定向搜索變異人工魚群算法原理

令[N]表示人工魚的規模，向量[yi=（yi1，yi2，…，yim+1）]表示人工魚[i]的當前位置狀態，[Y=F（y），Yi=F（yi）]表示人工魚的適應度函數，[dij=yi-yj]表示人工魚[yi]與[yj]之間的距離，[visual]和[δ]表示人工魚的視野范圍和擁擠度因子，[S]表示人工魚每次覓食時最大試探次數，random（）表示隨機數。算法的實現原理如下：

（1） 覓食行為

人工魚當前狀態為[yi，]在其視野范圍內隨機選擇一個狀態[y，]當[Y

（2） 聚群行為

人工魚當前狀態為[yi，]探索其視野范圍內（[dij≤visual]）的同伴數目[nf，]如果[nf≠0，]探索同伴中心位置[yc=（yc1，yc2，…，ycn），]其中[yck=j=1nfyjknf；]計算[yc]的適應度[Yc，]取[δ=1+nfN，]若[Yi<δYc，]表明同伴中心位置適應度較優并且不太擁擠，則執行[yi=yc，]否則利用概率為[pt]的正態變異因子對[yi]進行變異操作：[yij=yij?exp（Nj（0，Δσ）），][j=1，2，…，int（pt?n），][Nj（0，Δσ）]是相互獨立的均值為0，方差為[Δσ]的符合正態分布的隨機數。為使適應值過高的人工魚趨向當前最佳狀態，令：

如果[nf=0，]則執行覓食行為。

（3） 追尾行為

人工魚當前狀態為[yi，]探索其視野范圍內（[dij≤visual]）的同伴數目[nf，]如果[nf≠0，]探索適應度最優的同伴狀態[ym，]取[δ=1+nfN，]若[Yi<δYm，]表明[ym]位置適應度較優并且不太擁擠，則執行[yi=ym，]否則利用概率為[pt]的正態變異因子對[yi]進行變異操作：[yij=int[yij?exp（Nj（0，Δσ））]，][j=1，2，…，int（pt?n） 。]與聚群行為相同，為避免搜索盲目性，令：

如果[nf=0，]則執行覓食行為。

（4） 公告板

設立一個公告板，對人工魚所處的環境狀態及濃度值進行記錄，每條人工魚在行動一次后就將自身當前狀態與公告板比較，如果優于公告板則用自身狀態取代公告板狀態。

為有效避免算法后期搜索的盲目性，算法在第[t]次聚群和追尾迭代過程中，可按下式動態調整人工魚的視野范圍與變異概率：

其中：[visual=25，visualmin=0.001；][T]為最大迭代次數；取[pmin=0.4， pmax=1]。如果人工魚狀態越出搜索邊界，則自動取邊界值，從式（1），式（2）可以發現，隨著迭代次數的增加，視野范圍在逐漸減少，并且人工魚越聚集，變異概率越大，從而減小了算法搜索的盲目性及陷入局部最優的缺點。

2 Logit隨機用戶均衡交通分配模型的人工魚

群算法

2.1 Logit隨機用戶均衡交通分配模型

交通分配是交通規劃與管理的基礎，在路網設計和信號配時方面得到了廣泛的應用和研究，而Logit隨機用戶均衡分配作為一種更符合現實的交通分配方式，近年來受到交通科學界的高度關注[7?8]。對于道路網絡[G=（N，A）]，其中[N]為網絡節點集，表示道路交叉口；[A]為有向弧集，即路段集合。Logit隨機用戶均衡分配模型為：

其中：[xa]為路段[a]上的交通量，它們組成的向量為[x=（…，xa，…）；][ta（xa）]為路段[a]行駛時間函數，與路段[a]的交通量有關；路徑[k]行駛時間[twk=a∈Ataxaδwak；][fwk]為OD對[w]間第[k]條路徑的交通量，其向量為[f=（…，fwk，…）；][δwa，k]為路段?路徑相關變量，如果OD對[w]間路徑[k]經過路段[a，]則[δrsak=1，]否則為0；[qw]為OD對[w]間的交通需求量。

模型（3）要求任意一條路徑流量均大于0，這與事實不符，而由KKT條件可知，該優化模型等價于如下方程系統：

模型（5）是一個非光滑函數，用解析方法并不容易求解，因此采用本文提出的改進人工魚群算法來求解。

2.2 Logit隨機用戶均衡交通分配模型的人工魚群算法步驟

在隨機均衡交通分配模型的人工魚群算法中，各人工魚狀態向量[yi（t）]的每個坐標[yij（t）]對應網絡的路徑交通流量[fwk，]為了滿足式（5）的約束，需要將[fwk]進行如下形式的歸一化處理：

從而適合Logit隨機用戶均衡交通分配模型的人工魚群算法的基本步驟為：

Step1：

（1） 給定群體規模[N]，探索次數[S]，置迭代次數[t=1]；

（2） 各人工魚狀態向量[yi（t）]的每個坐標[yij（t）]（[i=1，2，…，N]）對應的[fwk]隨機取[0～qw（w∈W）]之間的數；

（3） 按式（6）進行歸一化處理，置：[fwk=fwk?qwk∈Kwfwk，]并將[F（f）=w∈Wk∈Kwfwk?p∈Kwe-θ?twp（f）-qw?e-θ?twk（f）qw]作為適應度函數；

（4） 評價所有個體并取適應度最小者進入公告板；

（5） 設定最大迭代次數[T。]

Step2：

（1） 各人工魚按照上一節改進人工魚群算法原理分別執行覓食、聚群、追尾行為，得到人工魚狀態向量[yi（t）]并按式（6）進行歸一化處理；

（2） 將[F（f）]作為適應度函數，檢驗自身狀態與公告板狀態，如果優于公告板狀態，則取代當前公告板狀態。

Step3：

若迭代次數[t+1≥T，]算法結束；否則，置[t=t+1]轉Step2。

3 仿真實驗與結果分析

下面采用文獻[9]道路交通網絡進行數值試驗和結果分析，設各條路段的最大通行能力為80；有4個OD對：1—9（OD對1），9—1（OD對2），3—7（OD對3），7—3（OD對4），設各OD交通量均為100，每個OD對均有6條有效路徑；本文采用路段行駛時間函數：[ta（xa）=][t0a1+0.5×xaca4]。

在改進人工魚群算法中，人工魚群體規模取為100，探索次數[S=20]，最大迭代次數[T=500]或適應值小于0.08時算法結束，[α=0.5，θ=0.3]，圖1為本文改進人工魚群算法的適應度函數收斂曲線。可以發現，改進人工魚群算法收斂的速度非常快，僅迭代234次算法結束，而且該算法在迭代后期的收斂性趨于穩定。圖2給出了不同OD對內各路徑流量的變化趨勢，算法大約迭代100次以后，各路徑流量逐步趨于穩定。

直方圖3給出了算法得到的各OD對內路徑行駛時間，當OD對交通需求分配到各路徑后，其路徑行駛時間差異不大，這充分體現了Logit隨機用戶均衡交通分配解的特征，表明這種改進人工魚群算法有能力求解該類型交通分配問題。

4 結 語

具有定向搜索和自適應變異的改進人工魚群算法在迭代過程中既具有向當前極值點靠攏，又具有避免陷入局部最優的特點，在一定程度上提高了算法的迭代效率和計算精度。隨后將該算法應用于Logit隨機用戶均衡交通分配問題中，構建了該問題新的優化模型，并采用改進人工魚群算法求解。仿真計算結果表明：

（1） 基于定向搜索變異的人工魚群算法迭代運算簡單，搜索能力強；每次迭代都進行變異操作，增強了算法的穩定性和收斂性。

（2） 隨機用戶平衡交通分配的人工魚群算法能夠在較短的時間內獲取分配結果，可以提高分配效率，具有較好的收斂速度和良好的尋優能力，具有在大規模城市交通分配問題中應用的潛力。

參考文獻

[1] 李曉磊，路飛，田國會，等.組合優化問題的人工魚群算法應用[J].山東大學學報，2004，34（5）：64?67.

[2] 王培崇，李麗榮，高文超，等.應用佳點集的混合反向學習人工魚群算法[J].計算機應用研究，2015，32（7）：1?7.

[3] 姜山，季業飛.改進的人工魚群混合算法在交通分配中的應用[J].計算機仿真，2011，28（6）：326?329.

[4] 曾鳴，舒彤，史慧，等.兼顧分布式發電商利益的有源配電網規劃[J].電網技術，2015（5）：1379?1383.

[5] 吳昌友.一種新的改進人工魚群優化算法[J].智能系統學報，2015，10（3）：1?6.

[6] 俞凱耀，席東民.人工魚群算法優化的PID 神經網絡解耦控制[J].計算機仿真，2014，31（10）：350?353.

[7] WATLING D P. Stability of the stochastic equilibrium assignment problem： a dynamical systems [J]. Transportation Research， 1999， 33B（4）： 281?312.

[8] HOROWITZ J L. The stability of stochastic equilibrium in a two link transportation network [J]. Transportation Research， 1984， 18B（1）： 13?28.

[9] 度巍，王先甲，黃崇超.求解隨機用戶平衡問題的粒子群演化算法[J].武漢理工大學學報（交通科學與工程版），2010，34（3）：616?619.