王艷愉，李 強(qiáng)

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州310018)

必經(jīng)點(diǎn)約束型最短路徑問題的研究

王艷愉，李 強(qiáng)

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州310018)

為了解決網(wǎng)絡(luò)路由中帶有必經(jīng)點(diǎn)約束的網(wǎng)絡(luò)拓?fù)渲凶顑?yōu)路徑的問題，提出了采用改進(jìn)的蟻群算法和Dijkstra算法對(duì)最優(yōu)路徑進(jìn)行規(guī)劃。首先，針對(duì)含有必經(jīng)點(diǎn)約束的問題，在信息素初始化時(shí)增加在必經(jīng)點(diǎn)上的信息素。其次，為了能夠更好地找到最優(yōu)解，采用了狼群分配算法進(jìn)行信息素更新，提高了收斂速度，并且采用了Dijkstra算法對(duì)螞蟻找到的最優(yōu)路徑進(jìn)行二次優(yōu)化。最后，分別用不同節(jié)點(diǎn)和必經(jīng)點(diǎn)規(guī)模的網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，并與基本的蟻群算法進(jìn)行了比較，證明了改進(jìn)蟻群算法的正確性和高效性。

最短路徑；蟻群算法；必經(jīng)點(diǎn)約束

0 引言

互聯(lián)網(wǎng)技術(shù)和應(yīng)用的不斷發(fā)展，對(duì)當(dāng)今網(wǎng)絡(luò)通信流量的要求不斷增大。流量大、速度快、費(fèi)用低的傳輸方式是網(wǎng)絡(luò)傳輸?shù)年P(guān)鍵。路徑最短、代價(jià)最低的網(wǎng)絡(luò)路由能夠大大降低通信成本、節(jié)約網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)資源的利用率[1]。

最短路徑問題是組合優(yōu)化領(lǐng)域的經(jīng)典問題之一，它廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、交通工程、通信工程、系統(tǒng)工程、運(yùn)籌學(xué)、信息論、控制理論等眾多領(lǐng)域[2]。目前已有許多學(xué)者對(duì)最短路徑問題進(jìn)行了研究，但大多數(shù)傳統(tǒng)的最短路徑問題研究只考慮了起點(diǎn)和終點(diǎn)，并沒有考慮有節(jié)點(diǎn)約束的網(wǎng)絡(luò)，在實(shí)際應(yīng)用中，如軍事運(yùn)輸、物流運(yùn)輸?shù)纫紤]一些必須經(jīng)過的點(diǎn)。例如在軍事運(yùn)輸中，部隊(duì)在執(zhí)行任務(wù)過程中必須經(jīng)過一些重要的戰(zhàn)略地點(diǎn)，如加油站、軍火庫、橋梁等含有重要設(shè)施或資源的地點(diǎn)。因此研究含有必經(jīng)點(diǎn)約束的網(wǎng)絡(luò)最短路徑問題有很重要的實(shí)際意義。

Dijkstra算法是經(jīng)典的最短路徑算法，雖然使用該算法找到的是全局最優(yōu)的最短路徑[3]，但在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量較大、網(wǎng)絡(luò)邊數(shù)較多時(shí)，存在內(nèi)存占用大、時(shí)間復(fù)雜度高等不足[4]，并且Dijkstra算法不能很好地解決含必經(jīng)點(diǎn)約束的最短路徑問題。蟻群算法具有并行性、魯棒性、正反饋性等特點(diǎn)[5]，已被廣泛應(yīng)用于求解組合優(yōu)化問題，如著名的旅行商問題、車間任務(wù)調(diào)度問題、網(wǎng)絡(luò)路由等許多復(fù)雜的組合優(yōu)化問題[6]，但基本蟻群算法在求解路徑規(guī)劃問題時(shí)存在著容易陷入局部最優(yōu)、迭代次數(shù)多、時(shí)間復(fù)雜度高等不足[7-8]。

本文提出了一種能夠適用于在網(wǎng)絡(luò)中求含有必經(jīng)點(diǎn)約束的最短路徑問題的蟻群算法信息素更新策略和狀態(tài)轉(zhuǎn)移策略，采用這種策略改進(jìn)后的蟻群算法使得邊上的信息素濃度能夠不斷朝著含必經(jīng)點(diǎn)的最優(yōu)路徑去變化，收斂速度加快，更容易達(dá)到全局最優(yōu)，與此同時(shí)，在用蟻群算法找出的最優(yōu)路徑上使用Dijkstra算法對(duì)路徑進(jìn)行二次優(yōu)化，最后通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 問題定義

定義有向圖G=(V,E),其中V={v1,v2,…,vn}是頂點(diǎn)集，E={e1,e2,…,en}是邊集，W={wij|i,j∈V}表示頂點(diǎn)i到頂點(diǎn)j的權(quán)重。對(duì)于給定的頂點(diǎn)o，d以及V的子集V′，尋找o到d的節(jié)點(diǎn)不重復(fù)的最短無環(huán)路徑P，使得P經(jīng)過V′中所有的頂點(diǎn)，并且o到d的路徑的代價(jià)最小，即權(quán)重最小。

2 蟻群算法介紹

蟻群算法是由Dorigo、Maniezzo和Colorni等于1991年首先提出來的,它來源于螞蟻尋食的行為。通過研究發(fā)現(xiàn)，螞蟻個(gè)體之間是通過一種叫做信息素的外激素進(jìn)行信息傳遞的。螞蟻在行走過程中能感知周圍信息素的強(qiáng)度，并朝著信息素濃度高的方向移動(dòng)，當(dāng)某只螞蟻發(fā)現(xiàn)食物時(shí)，它在回巢的過程當(dāng)中，會(huì)在返回的路上釋放信息素作為標(biāo)記，同伴發(fā)現(xiàn)后會(huì)沿著此路尋找到食物。當(dāng)同伴中多只螞蟻都發(fā)現(xiàn)了食物但路徑長短不同時(shí)，因?yàn)槲浵佋诙痰穆窂缴贤邓枰臅r(shí)間相對(duì)較小，所以單位時(shí)間內(nèi)走過的螞蟻越來越多，在這條路徑上的信息素濃度就會(huì)越強(qiáng)，因此，該路徑上的螞蟻就會(huì)越來越多，逐漸選出一條最優(yōu)的道路，其原理如圖1所示。

圖1 螞蟻尋找食物的過程

3 基本蟻群模型

(1)

其中novisited(k)表示螞蟻從i位置到下一步可以選擇的節(jié)點(diǎn)，應(yīng)防止螞蟻選擇重復(fù)的節(jié)點(diǎn)。經(jīng)過n個(gè)時(shí)刻，螞蟻完成了一次循環(huán)，所有路徑的信息素調(diào)整公式如下：

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

(2)

式中，(1-ρ)為信息素殘留因子，ρ∈(0,1)。

(3)

公式(3)表示所有經(jīng)過邊(i,j)的螞蟻留下的信息素。

(4)

式中，Q是信息素強(qiáng)度，為常量；Lk表示第k只螞蟻在本次循環(huán)中走的路徑總長度。

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

為了使蟻群算法能夠解決帶有必經(jīng)點(diǎn)約束的最短路徑問題，針對(duì)基本蟻群算法的收斂性不足、容易陷入局部最優(yōu)、搜索耗時(shí)嚴(yán)重等不足，需要對(duì)基本蟻群算法進(jìn)行優(yōu)化。

4.1改進(jìn)蟻群算法的狀態(tài)轉(zhuǎn)移策略

由于蟻群算法是一種正反饋算法，這種正反饋機(jī)制可能使得在局部最優(yōu)路徑上的信息素濃度不斷增大，隨著迭代次數(shù)的增加，螞蟻選擇最優(yōu)路徑的概率逐漸降低，導(dǎo)致最后在最優(yōu)路徑上的信息素遠(yuǎn)低于局部最優(yōu)路徑上的信息素濃度，無法求出最優(yōu)解。為此，本文對(duì)蟻群算法的狀態(tài)轉(zhuǎn)移策略進(jìn)行了改進(jìn)，引入了隨機(jī)螞蟻?zhàn)尤?，并參與狀態(tài)轉(zhuǎn)移和信息素更新，從而擴(kuò)大搜索解空間，使得算法得到最優(yōu)解的概率更大。改進(jìn)后的狀態(tài)轉(zhuǎn)移策略公式如下：

(5)

其中，r為隨機(jī)子群，其螞蟻數(shù)量為mr，p為信息子群，其螞蟻數(shù)量為mp，mr約為mp的1/20左右，mr+mp=m，m為螞蟻的總數(shù)。

在式(5)中，隨機(jī)子群并不是完全隨機(jī)地選擇下一個(gè)點(diǎn)，而是根據(jù)啟發(fā)因子進(jìn)行狀態(tài)轉(zhuǎn)移，而信息子群則根據(jù)信息素濃度按照概率選擇下一個(gè)點(diǎn)，從而使得蟻群算法的全局搜索能力得到了很好的提高。

4.2改進(jìn)蟻群算法的信息更新策略

4.2.1狼群算法簡介

狼群算法(Wolf Algorithm，WA)是2007年楊晨光等人根據(jù)狼群的捕食行為提出來的。狼群算法的主要思想是，狼群捕到獵物后，不是平均分配食物，而是先分配給最強(qiáng)壯的狼，再分配給其他弱小的狼。這樣可以保證最強(qiáng)壯的狼不被餓死，能夠繼續(xù)捕獲獵物，從而保證整個(gè)狼群不被餓死。

4.2.2基于狼群算法的信息素更新策略

傳統(tǒng)的蟻群算法中，由于螞蟻是根據(jù)路徑上信息素的濃度進(jìn)行路徑選擇，路徑上既有好的螞蟻留下的信息素，也有不好的螞蟻留下的信息素，好的螞蟻找到最優(yōu)路徑的概率更大，差的螞蟻找到最優(yōu)路徑的概率則很低，因此差的螞蟻留下的信息素會(huì)誘導(dǎo)后續(xù)其他螞蟻向著錯(cuò)誤的方向發(fā)展，從而導(dǎo)致陷入局部最優(yōu)。

為此，本文采用狼群算法思想對(duì)信息素更新策略進(jìn)行優(yōu)化，即在每次循環(huán)結(jié)束后找出最好的螞蟻和最差的螞蟻，增大最好螞蟻找到的路徑上的信息素，去掉最差螞蟻在路徑上留下的信息素，其信息素更新公式如下：

(6)

(7)

(8)

式中，L*是本次循環(huán)中局部最優(yōu)的路徑長度，L**是本次循環(huán)中局部最差的路徑長度，δ和ω分別為本次循環(huán)中局部最優(yōu)和最差螞蟻的個(gè)數(shù)。

5 改進(jìn)蟻群算法的計(jì)算步驟

改進(jìn)蟻群算法的主要計(jì)算步驟如下：

(1)蟻群初始化

確定蟻群規(guī)模m，初始化啟發(fā)式信息參數(shù)α，β，每只螞蟻的信息素為Q，最大迭代次數(shù)Nc，初始化每條路徑上的初始信息素τij(0)=C以及信息素增量Δij(0)=0，初始化包含必經(jīng)點(diǎn)的路徑上的初始信息素為τxy(0)=D,(x,y∈K),K為必經(jīng)點(diǎn)集，并且Dgt;C。

(2)將m只螞蟻放到起點(diǎn)位置，并初始化m只螞蟻的禁忌表tubai(i=1,2,…,m)以及novisitedi(i=1,2,…,m)，將起點(diǎn)添加到當(dāng)前禁忌表tuba中，同時(shí)更新novisited表。

(3)路徑構(gòu)建

每只螞蟻根據(jù)公式(5)選擇下一節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)的搜索范圍限定在其當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)矩陣內(nèi)和螞蟻個(gè)體的禁忌表tuba外，將所選路徑節(jié)點(diǎn)添加到禁忌表tuba中，同時(shí)更新novisited表。

(4)局部更新信息量

對(duì)每只螞蟻選擇的路徑(i,j)，根據(jù)公式(2)和(3)對(duì)路徑(i,j)上的信息素進(jìn)行局部更新，如果禁忌表tuba未滿，則繼續(xù)執(zhí)行步驟(3)。

(5)信息素全局動(dòng)態(tài)更新

當(dāng)所有螞蟻結(jié)束一次尋路后，在m只螞蟻中找出到達(dá)終點(diǎn)并且包含所有必經(jīng)點(diǎn)的局部最優(yōu)螞蟻和最差螞蟻，按公式(6)進(jìn)行信息素的全局動(dòng)態(tài)更新。

(6)結(jié)束判斷

判斷是否符合結(jié)束條件，若符合則輸出最優(yōu)解，否則，轉(zhuǎn)到搜索步驟重新搜索。

6 仿真實(shí)驗(yàn)

實(shí)驗(yàn)中網(wǎng)絡(luò)拓?fù)鋱D來自2016華為軟件精英挑戰(zhàn)賽。在網(wǎng)絡(luò)中，起點(diǎn)和終點(diǎn)之間可能有多條有向邊，但每條邊的權(quán)重不同，因此采用編號(hào)來標(biāo)記有向圖中的每條邊。

6.1算法正確性驗(yàn)證

為了方便描述、觀察、驗(yàn)證該算法的正確性，本實(shí)驗(yàn)選擇了網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模較小的20個(gè)點(diǎn)的稀疏圖進(jìn)行試驗(yàn)。實(shí)驗(yàn)中，選擇起始節(jié)點(diǎn)為2，終點(diǎn)為19，必經(jīng)節(jié)點(diǎn)集為191014134。網(wǎng)絡(luò)節(jié)點(diǎn)和邊信息如圖2所示,轉(zhuǎn)化后的網(wǎng)絡(luò)拓?fù)鋱D如圖3所示。

圖2 網(wǎng)絡(luò)信息圖

圖3 網(wǎng)絡(luò)拓?fù)鋱D

改進(jìn)蟻群算法的各參數(shù)的設(shè)置如下：Nc為2 000，m為50，α=6.0，β=1，ρ=0.8。通過改進(jìn)的蟻群算法計(jì)算出經(jīng)過上述必經(jīng)點(diǎn)的最短路徑為(用邊的編號(hào)來表示)：6-gt;28-gt;34-gt;8-gt;21-gt;15-gt;25-gt;10-gt;13-gt;14-gt;31。

6.2試驗(yàn)在不同網(wǎng)絡(luò)規(guī)模的時(shí)間效率

由于難以有效地對(duì)程序執(zhí)行的空間效率進(jìn)行監(jiān)測，下面通過clock()函數(shù)來粗略記錄算法的時(shí)間效率，分別對(duì)網(wǎng)絡(luò)規(guī)模為20、300、600的情況進(jìn)行多組測試計(jì)算執(zhí)行時(shí)間平均值，必經(jīng)點(diǎn)個(gè)數(shù)分別為1、5、10。實(shí)驗(yàn)結(jié)果如表1、表2、表3所示。

表1 20個(gè)節(jié)點(diǎn)執(zhí)行時(shí)間表

表2 300個(gè)節(jié)點(diǎn)執(zhí)行時(shí)間表

表3 600個(gè)節(jié)點(diǎn)執(zhí)行時(shí)間表

通過表1、表2、表3可以發(fā)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模、必經(jīng)點(diǎn)個(gè)數(shù)是影響求解效率的最主要因素。在必經(jīng)點(diǎn)個(gè)數(shù)相同、網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模較大時(shí)，執(zhí)行時(shí)間顯著增加；同樣，在網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)相同、必經(jīng)點(diǎn)個(gè)數(shù)較多時(shí)，執(zhí)行時(shí)間急劇上升。

7 結(jié)論

本文針對(duì)傳統(tǒng)蟻群算法和Dijkstra在求解必經(jīng)點(diǎn)約束型最短路徑問題中的不足，采用狼群思想對(duì)信息素更新，同時(shí)增加了隨機(jī)螞蟻?zhàn)尤簠⑴c路徑選擇，防止螞蟻陷入局部最優(yōu)，并且在螞蟻找出的最短路徑上再用Dijkstra算法進(jìn)行優(yōu)化。通過實(shí)驗(yàn)證明了采用上述改進(jìn)策略使得蟻群算法在求解必經(jīng)點(diǎn)約束型最短路徑問題上的正確性以及高效性，在實(shí)際運(yùn)用中有重要意義。

[1] 王松. 基于蟻群優(yōu)化多路徑路由算法的研究與設(shè)計(jì)[D]. 濟(jì)南：山東大學(xué), 2016.

[2] 徐慶征, 柯熙政. 必經(jīng)點(diǎn)最短路徑問題模型及相應(yīng)遺傳算法研究[J]. 系統(tǒng)工程與電子技術(shù), 2009, 31(2):459-462.

[3] 楊中秋, 張延華. 改進(jìn)蟻群算法在交通系統(tǒng)最短路徑問題的研究[J]. 現(xiàn)代電子技術(shù), 2009, 32(8):76-78.

[4] 譚國真. 時(shí)變、隨機(jī)網(wǎng)絡(luò)最優(yōu)路徑算法及其應(yīng)用研究[D]. 大連：大連理工大學(xué), 2002.

[5] 周鵬, 張駿, 史忠科. 分段路徑尋優(yōu)算法研究及實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2005, 22(12):241-243.

[6] 葛延峰, 陳濤, 孔祥勇,等. 改進(jìn)蟻群算法在城市汽車導(dǎo)航中的應(yīng)用[J]. 控制工程, 2016, 23(1):133-137.

[7] 趙凱,李聲晉,孫娟，等.改進(jìn)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的研究[J].微型機(jī)與應(yīng)用,2013,32(4):67-70.

[8] Liu Chang’an,Yan Xiaohu,Liu Chunyang,et al.The wolf colony algorithm and itsapplication[J]. Chinese Journal of Electronics, 2011,20(2):212-216.

2017-04-16)

王艷愉(1991-)，男，碩士研究生，主要研究方向：嵌入式系統(tǒng)、智能控制技術(shù)。

李強(qiáng)(1966-)，通信作者，男，博士，副教授，碩士生導(dǎo)師，主要研究方向：嵌入式智能控制理論、系統(tǒng)軟件設(shè)計(jì)等。E-mail: hzlee@hdu.edu.cn。

Study of shortest path problem constrained by designated-points

Wang Yanyu, Li Qiang

(School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou China, 310018)

In order to solve the problem of optimal path in network topology with networked constraints, this paper proposes an improved ant colony algorithm and Dijkstra algorithm to plan the optimal path. Firstly, for the problem of containing the necessary constraints, the pheromone concentrations of the designated points is increased in the initialization of ant colony algorithm. Secondly, in order to find the optimal solution better, the wolves distribution algorithm is used to update the pheromone and improve the convergence rate. Also, the Dijkstra algorithm is used to optimize the optimal path of the ants. Finally, experiments were conducted with different scale of nodes and designated-points, and compared with the basic ant colony algorithm, it proved that the improved ant colony algorithm is correct and efficient.

shortest path; ant colony algorithm; designated-point constraint

TP18

A

10.19358/j.issn.1674- 7720.2017.22.008

王艷愉，李強(qiáng).必經(jīng)點(diǎn)約束型最短路徑問題的研究J.微型機(jī)與應(yīng)用，2017,36(22)：26-29.