杜　博，夏春蕾，戴曙光

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

?

融合改進蟻群和粒子群算法的路徑搜索應(yīng)用

杜博，夏春蕾，戴曙光

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

針對車輛路徑搜索對其計算質(zhì)量和效率要求較高問題，且原始蟻群算法和標(biāo)準(zhǔn)粒子群算法均存在局部優(yōu)先解、停滯以及收斂速度較慢等缺陷，提出一種融合改進的蟻群和粒子群路徑搜索算法。在融合算法前期提高粒子群算法收斂速度，利用其進行粗搜索，后期利用改進的蟻群算法進行細搜索。通過仿真分析表明，融合后的改進算法在路徑規(guī)劃和計算效率上均有較大提升。

路阻模型；融合算法；路徑搜索；仿真分析

隨著中國城市化進程速度加快，汽車保有量與城市道路設(shè)施比例失衡導(dǎo)致的城市交通問題日益突出，目前已成為制約眾多城市經(jīng)濟發(fā)展的重要因素[1]。因此，為緩解城市交通問題，如何運用現(xiàn)代化信息手段提高城市道路設(shè)施資源利用率已成為眾多行業(yè)學(xué)者的研究熱點之一[2]。文中從車輛出行路徑規(guī)劃著手，改進融合蟻群算法。通過分析蟻群算法和粒子群算法各自特點，將兩個算法進行融合，形成融合型算法。并根據(jù)路徑搜索問題對蟻群算法和粒子群算法進行針對性改進，采用圖論實驗對改進后的混合算法進行仿真，證明融合算法在求解準(zhǔn)確度和效率上均略有提升。

1　建立城市道路和路阻函數(shù)

為更加真實的抽象描述實際道路情況，需要對道路路網(wǎng)建立合適的路阻函數(shù)模型。合理的動態(tài)路阻權(quán)值模型不僅是對實際城市路網(wǎng)中車輛通行力的準(zhǔn)確表達，更是后續(xù)檢驗路徑搜索能力和提供較優(yōu)出行決策的前提。目前路阻模型中較為典型的有BPR模型、Davidson模型、TRRL模型等[2-3]，此處以具有代表性的BPR路阻模型結(jié)合國內(nèi)城市交通情況，提出了如下道路和路阻模型

t(q)=t0[1+α1(q1/c1)β1+α2(q2/c2)β2]

(1)

其中，q1、q2分別表示機動車和非機動車的流量；c1、c2分別表示上面兩者的通行能力；α1、β1、α2、β2為回歸系數(shù)。

2　原始蟻群和粒子群算法模型

2.1原始蟻群Ant-quantity算法模型

蟻群算法(Ant Colony Optimization, ACO)是一種模擬進化算法[4-5]，該算法具有較強的魯棒性、正反饋、并行性和分布式協(xié)作等優(yōu)點，但其搜索時間長、易陷入局部解優(yōu)先和搜索停滯等問題。

當(dāng)前描述蟻群算法有諸多代表模型，在此選取Ant-quantity模型為改進對象，具體如下

(2)

其中，Lij為ij路段長度；Q為非負常量，表示該路段殘留的信息素濃度。

螞蟻k將n個節(jié)點全部遍歷結(jié)束之后，需要對ij路段的信息素進行局部更新

(3)

其中，ρ和τ0分別表示路段信息素揮發(fā)系數(shù)和路段信息素初值，其中τ0一般設(shè)為0。若數(shù)量為m的螞蟻全部遍歷完所有節(jié)點時，對于ij路段信息素累加值如下

(4)

與此同時，可得到m個路線解，在此需挑出所有路線解中距離最短的解，并將該路線解進行如下的信息素全局更新

τij(t+n)=(1-ρ)τij(t)+ρΔτij(t)

(5)

2.2標(biāo)準(zhǔn)粒子群算法數(shù)學(xué)模型

粒子群算法[6-7](Particle Swarm Optimization, PSO)，雖目前粒子群算法在不同改進后性能有所提升，但仍有如控制參數(shù)選擇、過早收斂等缺陷。以下以標(biāo)準(zhǔn)粒子群算法為改進對象

(6)

(7)

式(6)和式(7)中，ω的不同取值對算法性能影響與Vmax相似。目前慣性權(quán)值多采用線性遞減權(quán)值策略

ω(t)=(ωs-ωe)(Tmax-t)/Tmax+ωe

(8)

3　混合蟻群算法及其改進

針對以上缺點，引入一種融合的智能優(yōu)化粒子群算法，并對兩個算法進行優(yōu)化融合。在路徑搜索初期采用粒子群算法進行粗搜索，并適當(dāng)增加粗搜索過程中最優(yōu)路徑上的初始信息素濃度，后期則使用蟻群算法進行細搜索，組合改進后的融合算法。

3.1蟻群算法改進

針對蟻群算法出現(xiàn)搜索時間長、易陷入局部解優(yōu)先和搜索停滯等問題，從限制信息素濃度、啟發(fā)函數(shù)、信息素全局更新規(guī)則3方面進行改進，以最大程度提高求解效率。蟻群搜索出的解路線可能不是全局最優(yōu)解，而是局部最優(yōu)解。在此引入最大最小信息素[8-9]，該思想和粒子群算法中對粒子速度加以限制，通過這種方法可適當(dāng)分散各路段信息素分布，從而使蟻群擴大路徑搜索，增加最優(yōu)解的全局性，有效避免了局部最優(yōu)解和算法搜索停滯的發(fā)生。

在實際路線中最優(yōu)解隨著算法迭代數(shù)增加而更加優(yōu)化，應(yīng)考慮在不同迭代情況下對后續(xù)螞蟻路段選擇傾向的不同影響程度，而非原先蟻群算法中啟發(fā)函數(shù)一般只以1/Lij這樣和距離有關(guān)的靜態(tài)值。具體如下

(9)

其中，ηij(g)和g2max分別表示算法第g次迭代時的啟發(fā)函數(shù)和算法迭代極值；Lbest(g)和μ分別表示算法前g-1次迭代時的最佳距離解和算法迭代指導(dǎo)因子。

路段信息素初值已不是0或統(tǒng)一值，而是因前期搜索影響形成具有一定差異性的初值，避免螞蟻對一些極差解路線的探索。改進如下

(10)

式(10)對前期粒子群搜索的最佳路線各路段信息素初值均增加Δτpso，而對于其他路段的信息素初值不做任何修改。以避免數(shù)量有限的蟻群資源在較差路段上進行探索搜索，進而提高算法搜索效率。具體改進規(guī)則如下

τij(t+n)=

(11)

從式(11)可看出，每次迭代后對處于最差路線且信息素增量最少路段的信息素抑制為Δτij(t)，而其他路段均比其高出(1-ρ)τij(t)。

3.2粒子群算法改進

為實現(xiàn)對粒子飛行速度的控制和調(diào)節(jié)，標(biāo)準(zhǔn)PSO引入了慣性權(quán)重ω，該權(quán)值策略為線性遞減的。但算法在應(yīng)用中通常均是非線性且高度復(fù)雜的，這一矛盾說明了這種慣性權(quán)重與實際情況不符[10-11]。粒子群算法凹函數(shù)不僅不會降低算法收斂精度，且能較大幅度提高算法收斂速度。將權(quán)值策略改進為如下形式

(12)

其中，ωs和ωe分別表示初始和終止迭代慣性權(quán)值，在收斂速度和求解精度平衡點上一般取值0.95和0.4；g和g1max分別表示算法當(dāng)前迭代數(shù)和粒子群算法的迭代極值。

4　算法仿真分析

為檢驗改進混合算法搜索路線的性能，在Visual Studio應(yīng)用程序下，將城市道路網(wǎng)抽象模擬成基于點線圖論的方式，其中點表示道路交叉口，線表示道路路段。對城市局部路網(wǎng)模型說明：首先，對于道路網(wǎng)數(shù)據(jù)，按道路等級分為4級，1級道路如節(jié)點4～11，2級道路如節(jié)點10～11，3級道路如節(jié)點3～4，4級道路如節(jié)點2～9。路段的距離和車流量分別標(biāo)示在兩節(jié)點之間，如1～2路段上的8.9和410。道路網(wǎng)中某些節(jié)點設(shè)有收費站點，如節(jié)點9。如圖1所示，程序選擇節(jié)點1作為起始節(jié)點，節(jié)點49作為終止節(jié)點，程序仿真結(jié)果如圖1和圖2所示。

圖1　城市局部路網(wǎng)模型

圖2　算法收斂與求解曲線圖

通過分析仿真結(jié)果可知，采用蟻群算法和粒子群算法求得的最佳路線總權(quán)值分別為242.4和261.0，而融合算法為233.2。此外，融合算法在迭代150次后開始迅速收斂，并在250次后解趨于穩(wěn)定。從仿真曲線可知，融合算法在路線規(guī)劃質(zhì)量和求解效率上均略優(yōu)于蟻群和粒子群算法。

為進一步檢驗混合蟻群算法在最優(yōu)路徑搜索時求解的質(zhì)量，本文通過安裝在另一臺計算機中自帶Network Analyst功能的ArcMap應(yīng)用程序，實現(xiàn)路徑搜索，如圖3所示。

圖3　ArcMap正常路況的路徑規(guī)劃

如圖3所示，在對環(huán)路進行路徑規(guī)劃時ArcMap只為追求權(quán)值最小的線路，總距離為0.61 km，時間為0.915 min。

5　結(jié)束語

文中通過建立動態(tài)路阻權(quán)值模型，對現(xiàn)實道路網(wǎng)絡(luò)用數(shù)學(xué)模型進行抽象化表達，再分析蟻群算法和粒子群算法各自特點，將兩個算法進行融合，形成融合型算法。并根據(jù)路徑搜索問題對蟻群算法和粒子群算法進行針對性改進，采用圖論實驗對改進后的混合算法進行仿真，證明新算法在求解準(zhǔn)確度和效率上均略有提升。

[1]Halim Ceylan,Michael G H Bell.Traffic signal timing optimisation based on genetic algorithm approach, including drivers’routing [J].Transportation Research,2004,38(4):71-76.

[2]袁振洲.動態(tài)交通分配中道路阻抗模型的研究[J].中國公路學(xué)報,2002,15(3):92-95.

[3]田璠.基于道路擁擠收費的出行時間價值研究[D].大連:大連理工大學(xué),2009.

[4]張銀玲,牛小梅.蟻群算法在移動機器人路徑規(guī)劃中的仿真研究[J].計算機仿真,2011,28(6):231-234.

[5]王胥鵬,胡勁松.一種改進的微粒群算法[J].計算機應(yīng)用研究,2009,26(10):3642-3645.

[6]曾明如,徐小勇,劉亮,等.改進的勢場蟻群算法的移動機器人路徑規(guī)劃[J].計算機工程與應(yīng)用,2015,51(22):33-37.

[7]柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學(xué)報,2011,39(5):1220-1224.

[8]王越,葉秋冬.蟻群算法在求解最短路徑問題上的改進策略[J].計算機工程與應(yīng)用,2012,48(13):35-38.

[9]楊帆,胡春平,顏學(xué)峰.基于蟻群系統(tǒng)的參數(shù)自適應(yīng)粒子群算法及其應(yīng)用[J].控制理論與應(yīng)用,2010,27(11):1479-1488.

[10]那日蘇,李強,烏力吉.基于仿生學(xué)改進的粒子群算法[J].計算機工程與應(yīng)用,2014,50(6):61-63.

[11]何少佳,劉子揚.基于慣性蟻群算法的機器人路徑規(guī)劃[J].計算機工程與應(yīng)用,2012,48(15):245-248.

Application of Improved Fused ACO and PSO Algorithms in Vehicle Routing Search

DU Bo, XIA Chunlei, DAI Shuguang

(School of Optical-electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

The ant colony and particle swarm optimization have the disadvantages of local preferred solution, stagnation and low convergence speed. A fusion of improved ant colony and particle swarm algorithm is proposed to meet the high quality and efficiency requirements of vehicle routing search., use the coarse search is used in the early stage, and the improved ant colony algorithm for the following fine search. Simulation shows that the improved algorithm significant improves the efficiency of path planning and calculation.

impedance model; fused algorithm; path search; simulated analysis

2015- 12- 20

國家自然科學(xué)基金資助項目(61170277)；上海市教委科研創(chuàng)新重點基金資助項目(12zz137)；上海市一流學(xué)科建設(shè)基金資助項目(S1201YLXK)

杜博(1990-)，男，碩士研究生。研究方向：汽車電子。夏春蕾(1974-)，女，講師。研究方向：信號與信息處理。戴曙光(1957-)，男，教授。研究方向：信息處理，測試計量技術(shù)。

10.16180/j.cnki.issn1007-7820.2016.09.002

TP273

A

1007-7820(2016)09-004-04