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

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

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

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

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

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

（1） 覓食行為

人工魚當前狀態(tài)為[yi，]在其視野范圍內(nèi)隨機選擇一個狀態(tài)[y，]當[Y

（2） 聚群行為

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

如果[nf=0，]則執(zhí)行覓食行為。

（3） 追尾行為

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

如果[nf=0，]則執(zhí)行覓食行為。

（4） 公告板

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

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

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

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

群算法

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

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

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

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

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

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

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

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

Step1：

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

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

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

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

（5） 設定最大迭代次數(shù)[T。]

Step2：

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

（2） 將[F（f）]作為適應度函數(shù)，檢驗自身狀態(tài)與公告板狀態(tài)，如果優(yōu)于公告板狀態(tài)，則取代當前公告板狀態(tài)。

Step3：

若迭代次數(shù)[t+1≥T，]算法結(jié)束；否則，置[t=t+1]轉(zhuǎn)Step2。

3 仿真實驗與結(jié)果分析

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

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

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

4 結(jié) 語

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

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

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

參考文獻

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

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

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

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

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

[6] 俞凱耀，席東民.人工魚群算法優(yōu)化的PID 神經(jīng)網(wǎng)絡解耦控制[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.