胡清準(zhǔn)，邱曉暉

(南京郵電大學(xué) 通信工程學(xué)院，江蘇 南京 210003)

0 引 言

在復(fù)雜的交通路網(wǎng)中，找到一條到目的地合適的行車路徑是智能交通系統(tǒng)的重要組成部分。更好的道路規(guī)劃可以緩解交通擁堵，緩解城市交通壓力，方便人們出行。行車路徑規(guī)劃問題也是城市智能交通的重要組成部分[1-2]。它是一種行程路徑的設(shè)計(jì)與優(yōu)化?，F(xiàn)有資源再利用與配置的基礎(chǔ)是智能停車引導(dǎo)系統(tǒng)的重要研究?jī)?nèi)容。行車路徑的設(shè)計(jì)是引導(dǎo)車輛參考實(shí)時(shí)路況問題設(shè)計(jì)的最佳行車路線，減少駕駛者在道路上的代價(jià)消耗。合理的行車路徑，一方面可以避免因路況不熟悉而造成停車使用者迷路的情況，減少車輛在復(fù)雜路網(wǎng)中的交通時(shí)長(zhǎng)，優(yōu)化交通流在道路網(wǎng)絡(luò)中的分布，另一方面可以減少停車使用者因長(zhǎng)時(shí)間找不到停車位，而選擇路邊非法停車，在一定程度上提高了交通安全[3-4]。

現(xiàn)代啟發(fā)式算法中的遺傳算法和蟻群算法都屬于仿生學(xué)算法，兩種算法對(duì)于求最短路徑問題都有一定的優(yōu)勢(shì)，并取得了一定的成果。但同時(shí)兩種算法在設(shè)計(jì)時(shí)都有各自的缺點(diǎn)，遺傳算法通過不停的迭代進(jìn)化卻沒有利用反饋信息，導(dǎo)致冗余迭代，降低了求解效率。而蟻群算法由于在初期信息素匱乏，導(dǎo)致算法速度慢[5-6]。通過將兩種算法相結(jié)合，提取兩種算法的優(yōu)點(diǎn)，可以加快算法的迭代速度，提高求解效率。

目前，利用仿生學(xué)遺傳-蟻群算法解決路徑優(yōu)化問題已經(jīng)取得了一定的成果[7-9]。針對(duì)兩種算法的優(yōu)化問題，國(guó)內(nèi)外很多學(xué)者對(duì)這兩種算法進(jìn)行改進(jìn)。例如，文獻(xiàn)[7]提出基于云模型的蟻群算法，文獻(xiàn)[8]提出多工種螞蟻分工的蟻群算法，文獻(xiàn)[9]提出將蟻群算法與遺傳算法中的變異因子結(jié)合，對(duì)遺傳算法中的交叉長(zhǎng)度的變化和蟻群算法中的信息素保留率進(jìn)行改進(jìn)。但改進(jìn)的算法同樣存在較多問題，如陷入局部解、收斂速度慢、求解精度低等。因此，文中從基本蟻群算法入手，結(jié)合遺傳和蟻群算法的各自優(yōu)點(diǎn)，將兩種算法的尋優(yōu)過程循環(huán)多次。在蟻群算法的每一次循環(huán)迭代后，將蟻群算法產(chǎn)生的最優(yōu)解加入到遺傳算法中，用以加快遺傳算法的迭代速度。同時(shí)，將遺傳算法算出的解設(shè)為較優(yōu)路徑來(lái)更新蟻群算法中的信息素分配，實(shí)現(xiàn)參數(shù)調(diào)整。多次相互指導(dǎo)能有效解決蟻群算法前期效率低和遺傳算法后期冗余迭代的問題。實(shí)驗(yàn)結(jié)果表明，GACHA算法可以有效地避開局部較優(yōu)解，加快算法迭代速度，提高求解效率。它具有良好的收斂性和求解效率并且能在復(fù)雜路網(wǎng)中找到合適條件的最短路徑。

1 算法原理

1.1 基本遺傳算法

遺傳算法是由達(dá)爾文的進(jìn)化論思想衍生出來(lái)的仿生學(xué)最優(yōu)化算法，通過適應(yīng)度函數(shù)對(duì)較優(yōu)個(gè)體進(jìn)行不斷選擇的過程。同時(shí)為保持種群的多樣性和具有求全局最優(yōu)解的能力，較優(yōu)個(gè)體需進(jìn)行交叉和變異操作產(chǎn)生新的種群。通過不斷的選擇和迭代進(jìn)化，找到最優(yōu)個(gè)體，也就是最優(yōu)解[10-11]。

1.1.1 編 碼

編碼是將實(shí)際求解問題的實(shí)際參數(shù)通過編碼變成遺傳算法中的基因碼組。在實(shí)際操作中為操作方便，經(jīng)常轉(zhuǎn)換成二進(jìn)制基因碼，通過0或1便是表示個(gè)體具體的某一個(gè)變量值。一個(gè)個(gè)體是一個(gè)二進(jìn)制字符串，字符串長(zhǎng)度由求解的精度決定。

1.1.2 確定適應(yīng)度函數(shù)

設(shè)計(jì)適應(yīng)度函數(shù)的目的是計(jì)算和評(píng)價(jià)每個(gè)個(gè)體在當(dāng)前環(huán)境中的適應(yīng)度值，然后決定該個(gè)體是被保留還是被放棄。目標(biāo)函數(shù)f(x)被設(shè)置為適應(yīng)度函數(shù)。個(gè)體的適應(yīng)值越小，個(gè)體的素質(zhì)越好。

1.1.3 交叉操作

通過將父系中剩余的染色體配對(duì)，一對(duì)配對(duì)的染色體被交叉并以交叉概率PC重組以產(chǎn)生后代個(gè)體。改進(jìn)的兩點(diǎn)交叉方法可以在一定程度上提高種群的多樣性。

1.1.4 變異操作

變異操作是指從進(jìn)化的種群個(gè)體中選擇部分，然后改變個(gè)體基因碼即二進(jìn)制字符串的部分順序，或者使基因碼部分發(fā)生交換“突變”，以保持種群多樣性，防止算法過早收斂。

1.2 基本蟻群算法

蟻群算法(ant colony optimization，ACO)是通過觀察螞蟻覓食路徑選擇過程而啟發(fā)的路徑優(yōu)化算法。它源于真實(shí)螞蟻在尋找食物時(shí)相互協(xié)作，通過信息素的調(diào)節(jié)，給后面的螞蟻以指導(dǎo)啟發(fā)，而得出最優(yōu)路徑問題。蟻群算法通過信息素的調(diào)節(jié)和轉(zhuǎn)移，可以保持種群的多樣性，優(yōu)化全局尋優(yōu)能力[12-13]。

蟻群算法是一種啟發(fā)式仿生學(xué)算法，在螞蟻覓食過程中，蟻群通過相互間的協(xié)助總能夠?qū)ふ业揭粭l從蟻巢和食物源的最優(yōu)路徑。圖1顯示了這樣一個(gè)覓食的過程。

圖1 螞蟻覓食

在圖1中，當(dāng)螞蟻發(fā)現(xiàn)一個(gè)食物源時(shí)，螞蟻們從巢穴沿著一條直線向食物源行走，并沿著這條線返回。如果在巢穴和食物源之間突然出現(xiàn)另一條道路，則螞蟻去食物源的路上將有一個(gè)岔路口，螞蟻需要選擇是向左邊行駛還是向右邊行駛。在最開始不知道的情況下，螞蟻隨機(jī)選擇，概率相等，所以兩條路的螞蟻幾乎一樣多。螞蟻?zhàn)哌^會(huì)留下信息素用于指導(dǎo)后面的螞蟻行駛，隨著時(shí)間的推移，上邊路段相同時(shí)間經(jīng)過的螞蟻會(huì)多一些，會(huì)留下更濃的信息素，指導(dǎo)這后面的螞蟻行駛，如此形成正反饋，從而吸引更多的螞蟻沿著這條路行駛。

蟻群算法遵循的規(guī)則：

(1)感知范圍：螞蟻只能觀察到其周圍一個(gè)方形區(qū)域，模擬相關(guān)參數(shù)為速度半徑r，可觀察和移動(dòng)的范圍為r×r區(qū)域。

(2)環(huán)境指導(dǎo)：行走的路徑上可能會(huì)有障礙物或者其他螞蟻的信息素，信息素以一定速度進(jìn)行揮發(fā)。

(3)食物刺激：在周圍尋找食物過程中，當(dāng)食物源出現(xiàn)在其感知范圍內(nèi)，就會(huì)發(fā)現(xiàn)食物，否則，沿著信息素的概率比選擇行駛路徑，即使信息素很少仍然有較低的概率會(huì)選擇，巢穴信息素指導(dǎo)規(guī)則相同。

(4)行動(dòng)準(zhǔn)則：螞蟻按照信息素的比例向信息素濃度高的路徑行走，信息素濃度小的路徑也有小概率被行走，當(dāng)完全沒有信息素時(shí)按原有方向行走并記錄當(dāng)前位置。

(5)避開障礙：當(dāng)螞蟻行走過程遇到障礙，起初按隨機(jī)概率選擇前行，并留下信息素，當(dāng)有信息素指引時(shí)，將按照覓食規(guī)則移動(dòng)。

1.2.1 狀態(tài)轉(zhuǎn)移規(guī)則

狀態(tài)轉(zhuǎn)移規(guī)則是選擇下一節(jié)點(diǎn)的標(biāo)準(zhǔn)。下一個(gè)節(jié)點(diǎn)的選擇取決于兩節(jié)點(diǎn)之間的距離和之間信息素濃度的大小。狀態(tài)轉(zhuǎn)移概率表示為：

(1)

其中，α表示信息素啟發(fā)式因子，β表示期望值啟發(fā)式因子，allowedk={0,1,…,n-1}表示螞蟻下一步允許選擇的節(jié)點(diǎn)，τα(i,j) 表示存儲(chǔ)在路段L(i,j)上的信息素濃度，ηβ(i,j)表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的可見度,通常取值為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間距離的倒數(shù)。

1.2.2 信息素更新

當(dāng)螞蟻尋找到一條路徑時(shí)，需完成對(duì)這條路徑信息素的更新，之后對(duì)所經(jīng)過路徑上的信息素濃度進(jìn)行全局更新，以確保選擇最優(yōu)路徑的概率增加，信息素更新規(guī)則如下:

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

(2)

(3)

其中，ρ∈(0，1)為螞蟻信息素的揮發(fā)系數(shù)，τij(t+n)為(t+n)時(shí)刻路徑上信息素的濃度，Δτij(t)為本次循環(huán)中最優(yōu)路徑上的信息素增量，Lk為本次覓食過程中螞蟻k所走的路徑長(zhǎng)度，Q為螞蟻k路徑過程中總的信息素量，m為此次循環(huán)螞蟻數(shù)量。

2 混合算法

2.1 混合的基本思想

經(jīng)過專家和學(xué)者們對(duì)遺傳和蟻群算法進(jìn)行的大量實(shí)驗(yàn)表明，遺傳算法與蟻群算法的總體進(jìn)化迭代曲線如圖2所示。

圖2 速度-時(shí)間曲線

從圖2中可以看出，遺傳算法在搜索的初期(T0-Tb區(qū)間段)具有較快的向最優(yōu)解靠近的進(jìn)化速度，在Tc之后進(jìn)化迭代速度明顯下降，在到達(dá)Tg時(shí)刻之后，其開始落后于蟻群算法。相比較于遺傳算法，蟻群算法由于在搜索的初期(T0-Tb區(qū)間段)信息素較少且分布平均，導(dǎo)致算法進(jìn)化速度緩慢。隨著各條線路信息素的積累，Td時(shí)刻后，蟻群算法的收斂速度開始迅速增加。通過分析,遺傳算法前期雖然具有快速的全局搜索能力，但是沒有反饋信息，導(dǎo)致后期的冗余迭代，降低了算法的求解效率。蟻群算法通過信息素的反饋，進(jìn)行啟發(fā)式的指導(dǎo)，具有更好的收斂能力。但是由于前期信息素少且分布較為平均，導(dǎo)致前期運(yùn)算緩慢[14]。

因此通過將遺傳算法和蟻群算法相結(jié)合，其主要目的是結(jié)合兩種算法的優(yōu)勢(shì)，去除兩種算法的不足，實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ)。為此,可以在算法多次循環(huán)迭代中，循環(huán)結(jié)合，相互指導(dǎo)。在蟻群算法的每一次循環(huán)迭代后，將蟻群算法產(chǎn)生的最優(yōu)解加入到遺傳算法中，用以加快遺傳算法的迭代速度。同時(shí)，將遺傳算法算出的解設(shè)為較優(yōu)路徑來(lái)更新蟻群算法中的信息素分配，實(shí)現(xiàn)參數(shù)調(diào)整。多次相互指導(dǎo)能有效解決蟻群算法前期效率低和遺傳算法后期冗余迭代的問題。

遺傳算法與蟻群算法相結(jié)合的優(yōu)點(diǎn)是，當(dāng)遺傳算法達(dá)到一定的搜索階段時(shí)，可以克服搜索最優(yōu)解的效率低下和蟻群算法初始信息素的不足[11-13]。同時(shí)，也可以充分發(fā)揮各自的優(yōu)勢(shì)，尋找最佳解決方案，彌補(bǔ)彼此的不足。

2.2 混合算法的步驟

2.2.1 算法參數(shù)初始設(shè)置

設(shè)置算法的初始化參數(shù)，包括遺傳算法的交叉概率Pc和異變概率Pm，螞蟻的數(shù)量m，螞蟻信息素的啟發(fā)因子及期望值啟發(fā)因子。

2.2.2 更新遺傳種群，找出較優(yōu)個(gè)體進(jìn)行編碼

根據(jù)適應(yīng)度函數(shù)計(jì)算每一個(gè)個(gè)體的適應(yīng)度，然后通過概率大小選擇較優(yōu)的個(gè)體。假設(shè)種群大小為m，父代種群Z={a1,a2,…,am},其中每個(gè)個(gè)體的適應(yīng)度大小為f(ai)，子代群體初始狀態(tài)為x=0,則具體操作過程如下:

步驟1:將所有個(gè)體按其適應(yīng)度值由大到小進(jìn)行排序，排序后的種群為Z'={b1,…,bi,…,bm}，其中f(bi-1)>f(bi)>f(bi+1)。

步驟3:計(jì)算出每一個(gè)個(gè)體被選取的概率:

之后對(duì)較優(yōu)個(gè)體進(jìn)行編碼，給每一個(gè)節(jié)點(diǎn)一個(gè)序號(hào)，從起點(diǎn)到終點(diǎn)的一組序號(hào)列為一組編碼。

2.2.3 交叉操作

系統(tǒng)隨機(jī)產(chǎn)生0到1之間的浮點(diǎn)數(shù)，當(dāng)該數(shù)小于交叉概率Pc時(shí)(一般取值0.6～0.8)，執(zhí)行交叉操作。通過將父系中的基因碼進(jìn)行配對(duì)，兩個(gè)基因碼通過交叉后再重組以產(chǎn)生后代個(gè)體。假設(shè)父代基因碼1-13-14-15-21-20-25-26-31-29-30和1-2-12-15-21-20-25-26-31-29-30隨機(jī)選取片段如14-15-21片段進(jìn)行交叉得到1-13-12-15-21-20-25-26-31-29-30和1-2-14-15-2-20-25-26-31-29-30兩個(gè)后代。交叉操作可以在種群中添加未有卻又相近的基因，從而提高種群的多樣性。

2.2.4 異變操作

系統(tǒng)隨機(jī)產(chǎn)生0到1之間的浮點(diǎn)數(shù)，當(dāng)該數(shù)小于異變概率Pm時(shí)(一般取值0～0.2)，執(zhí)行異變操作。通過交叉操作產(chǎn)生一個(gè)新基因碼后，需要在基因碼中隨機(jī)選擇若干個(gè)基因片段，然后隨機(jī)修改基因的值，從而給現(xiàn)有的染色體引入了新的基因，突破了當(dāng)前搜索的限制，更有利于算法尋找到全局最優(yōu)解。

2.2.5 遺傳循環(huán)操作

統(tǒng)計(jì)遺傳算法的迭代次數(shù)，如果達(dá)到設(shè)定的最大次數(shù)則終止循環(huán)，輸出若干組遺傳算法較優(yōu)解。否則，繼續(xù)迭代循環(huán)返回步驟2.2.2更新遺傳種群操作。

2.2.6 根據(jù)已知較優(yōu)解分布信息素

初始各路徑上的螞蟻信息素濃度為一個(gè)常數(shù)，根據(jù)遺傳算法的較優(yōu)解作為初始解，通過這些較優(yōu)解，調(diào)節(jié)并更新這些解的螞蟻路徑信息素分配，根據(jù)式(2)局部更新每條路徑上的信息量。

2.2.7 蟻群尋路操作

將m只螞蟻放在起點(diǎn)位置，從當(dāng)前位置i到下一節(jié)j的選擇概率根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則概率分布進(jìn)行選擇。同時(shí)更新禁忌表、允許訪問的節(jié)點(diǎn)列表和未訪問的節(jié)點(diǎn)列表。若當(dāng)前節(jié)點(diǎn)為終節(jié)點(diǎn)，則完成以此尋路過程的循環(huán)，否則繼續(xù)下一節(jié)點(diǎn)的選擇，直到m只螞蟻完成尋路過程，同時(shí)更新路徑信息素。

2.2.8 蟻群循環(huán)操作

統(tǒng)計(jì)蟻群算法的迭代次數(shù)，如果達(dá)到設(shè)定的次數(shù)則終止循環(huán)，輸出蟻群算法若干較優(yōu)解。否則，繼續(xù)迭代循環(huán)，返回步驟2.2.6分布信息素操作。

2.2.9 系統(tǒng)循環(huán)過程

統(tǒng)計(jì)系統(tǒng)循環(huán)次數(shù)，若達(dá)到設(shè)定的最大迭代次數(shù)或者達(dá)到尋優(yōu)條件，則輸出全局較優(yōu)解為問題最優(yōu)解。否則，返回步驟2.2.2更新遺傳種群操作，將蟻群算法的較優(yōu)解作為精英個(gè)體加入到遺傳算法群體中。

3 實(shí)驗(yàn)結(jié)果及分析

本仿真數(shù)據(jù)采用某市部分地圖的路網(wǎng)信息，路網(wǎng)結(jié)構(gòu)如圖3所示，其中雙向線表示城市道路。

圖3 某市路網(wǎng)結(jié)構(gòu)

路網(wǎng)包含的數(shù)據(jù)信息見圖4，其中i、j表示路網(wǎng)的節(jié)點(diǎn)，dij為相鄰節(jié)點(diǎn)間路段的實(shí)際距離，由于路段是雙向行駛且距離基本相同，即dij=dji；tij為i、j節(jié)點(diǎn)的道路擁堵情況等級(jí)。

i1122334455789j213123411510788910dij550300370480450420530470460310400410650tij1123141235512

i9101011111212131414151516j18111712161315141522162117dij560510570440600470600590450970450880510tij2331213212322

ii17171819192020212122232324jj18201920272125222423243425dijdij630760700590610930590540600560580490890tijtij1234221445312

ii24252626272929292830323233jj33262731292830313032313334dijdij5203201505305601801501503003301801100600tijtij2211245122221

圖4 路網(wǎng)包含的數(shù)據(jù)信息

將文中算法用于靜態(tài)路網(wǎng)所得的初始路徑規(guī)劃結(jié)果如圖5所示。

圖5 靜態(tài)路網(wǎng)下最優(yōu)停車路徑仿真結(jié)果

算法在靜態(tài)路網(wǎng)下20次的效果對(duì)比如表1所示。

表1 幾種算法在靜態(tài)路網(wǎng)下20次的效果對(duì)比

在動(dòng)態(tài)路網(wǎng)模型中，還需要提供路段上的實(shí)際交通擁堵狀況從而獲取動(dòng)態(tài)路權(quán)。此實(shí)驗(yàn)中給道路擁堵情況分為五個(gè)等級(jí)，道路實(shí)際權(quán)值Lij=dij*tij是本實(shí)驗(yàn)提供的與初始路線相關(guān)的部分路段的動(dòng)態(tài)擁擠度，用于動(dòng)態(tài)路網(wǎng)的仿真實(shí)驗(yàn)。

結(jié)果見表2和圖6。

表2 幾種算法在動(dòng)態(tài)網(wǎng)路下20次的效果對(duì)比

圖6 實(shí)驗(yàn)最優(yōu)解進(jìn)化曲線

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

首先對(duì)基本蟻群算法和遺傳算法的原理、流程和步驟做了詳細(xì)介紹，分析了仿生學(xué)算法在解決復(fù)雜路網(wǎng)下的最優(yōu)路徑問題的優(yōu)越性。結(jié)合遺傳、蟻群算法的特性和優(yōu)點(diǎn)，設(shè)計(jì)一種混合遺傳蟻群算法(GACHA)用于系統(tǒng)的路徑規(guī)劃中。從基本蟻群算法入手,將兩種算法的尋優(yōu)過程循環(huán)多次結(jié)合。在蟻群算法的一次迭代循環(huán)后，將蟻群算法產(chǎn)生的較優(yōu)解代替遺傳算法中的部分個(gè)體，用以加快遺傳算法的迭代速度。同時(shí)，將遺傳算法算出的解設(shè)為較優(yōu)路徑來(lái)更新蟻群算法中的信息素分配，實(shí)現(xiàn)參數(shù)調(diào)整。多次相互指導(dǎo)能有效解決蟻群算法前期效率低和遺傳算法后期冗余迭代的問題。實(shí)驗(yàn)結(jié)果表明，GACHA算法具有良好的優(yōu)化和收斂性，能夠準(zhǔn)確地找到滿足路網(wǎng)綜合要求的最優(yōu)路徑。