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

杜　博，夏春蕾，戴曙光

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

?

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

杜博，夏春蕾，戴曙光

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

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

其中，Lij為ij路段長(zhǎng)度；Q為非負(fù)常量，表示該路段殘留的信息素濃度。

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

(3)

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

(4)

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

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

(5)

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

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

(6)

(7)

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

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

(8)

3　混合蟻群算法及其改進(jìn)

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

3.1蟻群算法改進(jìn)

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

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

(9)

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

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

(10)

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

τij(t+n)=

(11)

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

3.2粒子群算法改進(jìn)

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

(12)

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

4　算法仿真分析

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

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

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

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

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

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

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

5　結(jié)束語(yǔ)

文中通過(guò)建立動(dòng)態(tài)路阻權(quán)值模型，對(duì)現(xiàn)實(shí)道路網(wǎng)絡(luò)用數(shù)學(xué)模型進(jìn)行抽象化表達(dá)，再分析蟻群算法和粒子群算法各自特點(diǎn)，將兩個(gè)算法進(jìn)行融合，形成融合型算法。并根據(jù)路徑搜索問(wèn)題對(duì)蟻群算法和粒子群算法進(jìn)行針對(duì)性改進(jìn)，采用圖論實(shí)驗(yàn)對(duì)改進(jìn)后的混合算法進(jìn)行仿真，證明新算法在求解準(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]袁振洲.動(dòng)態(tài)交通分配中道路阻抗模型的研究[J].中國(guó)公路學(xué)報(bào),2002,15(3):92-95.

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

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

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

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

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

[8]王越,葉秋冬.蟻群算法在求解最短路徑問(wèn)題上的改進(jìn)策略[J].計(jì)算機(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]那日蘇,李強(qiáng),烏力吉.基于仿生學(xué)改進(jìn)的粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(6):61-63.

[11]何少佳,劉子揚(yáng).基于慣性蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(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

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

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

10.16180/j.cnki.issn1007-7820.2016.09.002

TP273

A

1007-7820(2016)09-004-04