基于改進(jìn)蟻群算法的通信業(yè)務(wù)智能調(diào)配分析研究*

繆巍巍 吳海洋 施 健 呂順利

(1.江蘇省電力公司 南京 210024)(2.南京南瑞集團(tuán)公司 南京 210003)

?

基于改進(jìn)蟻群算法的通信業(yè)務(wù)智能調(diào)配分析研究*

繆巍巍1吳海洋1施 健2呂順利2

(1.江蘇省電力公司 南京 210024)(2.南京南瑞集團(tuán)公司 南京 210003)

電力通信光傳輸網(wǎng)絡(luò)的業(yè)務(wù)路由調(diào)配符合多約束條件的路由路徑特點,傳統(tǒng)的路由計算方法難以實現(xiàn)最優(yōu)化的業(yè)務(wù)路徑生成。論文在蟻群算法的基礎(chǔ)上借鑒A*算法的思想,提出了一種改進(jìn)的蟻群算法,有效避免了蟻群算法中雜亂搜索和容易導(dǎo)致局部最優(yōu)的缺陷。通過實驗仿真,改進(jìn)后的蟻群算法在不同的網(wǎng)絡(luò)拓?fù)鋱D上均能得到較優(yōu)解,驗證了算法的穩(wěn)定性和優(yōu)越性,具有較好的可行性和實用性,可為通信業(yè)務(wù)的智能調(diào)配提供輔助分析支持。

電力通信網(wǎng); 智能調(diào)配; 蟻群算法; A*算法

Class Number TP391

1 引言

隨著智能電網(wǎng)和“三集五大”體系的全面推進(jìn),電力企業(yè)對于通信業(yè)務(wù)的需求呈現(xiàn)爆發(fā)式增長的趨勢。電力通信網(wǎng)作為電力系統(tǒng)的專用網(wǎng)絡(luò),其承載的通信業(yè)務(wù)主要是與電力生產(chǎn)、運行相關(guān)的通信業(yè)務(wù),包括繼電保護(hù)業(yè)務(wù)、穩(wěn)定控制業(yè)務(wù)、遠(yuǎn)動業(yè)務(wù)、調(diào)度業(yè)務(wù)、辦公業(yè)務(wù)等,這些業(yè)務(wù)對路徑選擇、可靠性等方面有特殊要求,業(yè)務(wù)路由的不同調(diào)配方式可能會對電力系統(tǒng)的安全穩(wěn)定運行帶來不同的潛在風(fēng)險。因此,針對電力通信的網(wǎng)絡(luò)拓?fù)浼軜?gòu)和當(dāng)前通信業(yè)務(wù)的需求分布,在保證網(wǎng)絡(luò)資源有效利用的同時,科學(xué)合理地調(diào)配與選擇路由路徑,使得通信業(yè)務(wù)能夠獲得滿足其服務(wù)要求的傳輸路徑,已成為增強網(wǎng)絡(luò)運維效能、提升網(wǎng)絡(luò)運維水平的重要工作[1]。

通信業(yè)務(wù)的路由調(diào)配是圖論研究中的一個經(jīng)典算法問題,路徑選擇由于其日益廣泛的應(yīng)用而倍受關(guān)注。專家們從不同的視角審視這個問題,并提出了很多算法,同時也對這些算法進(jìn)行了改進(jìn)。計算路由路徑的常用算法[2～6]有傳統(tǒng)的Dijkstra算法、floyd算法以及啟發(fā)式算法如A*算法、蟻群算法、遺傳算法等。由于電力通信業(yè)務(wù)的路由調(diào)配不是簡單的選擇最短路徑,而是需要考慮眾多約束條件,因此在具有兩個或兩個以上的約束條件或者所求頂點數(shù)較多的情況下,傳統(tǒng)的Dijkstra算法和Floyd算法就不再具有優(yōu)勢。當(dāng)賦權(quán)拓?fù)鋱D中存在大量頂點時,傳統(tǒng)的搜索算法均需要對圖中所有頂點進(jìn)行迭代遍歷,耗費時間長,得到的也不一定是最優(yōu)解。目前常用的算法是蟻群算法,或蟻群算法與其他算法相結(jié)合的混合算法,如蟻群算法和遺傳算法結(jié)合。但是該算法存在著搜索雜亂和容易陷入局部最優(yōu)的缺陷,同時多個啟發(fā)式算法的組合又產(chǎn)生了很多不確定性。

針對上述存在的缺點,本文提出了一種改進(jìn)的蟻群算法。針對蟻群算法中由于初始信息素濃度相同所帶來的初期螞蟻運動隨機(jī)性問題,借鑒了A*算法的思想,以當(dāng)前節(jié)點到目的節(jié)點的距離為參考,使螞蟻尋食具有一定的方向性;同時根據(jù)求解質(zhì)量的不同在信息素更新時,賦予不同的權(quán)值,從而增加解空間的多樣性,并采用全局更新機(jī)制,改善了蟻群算法中容易陷入局部最優(yōu)的問題。最后通過與其他搜索算法的比較,驗證了本算法的可行性和實用性。

2 A*算法基本原理

A*算法[7～10]在人工智能中是一種典型的啟發(fā)式搜索算法,其算法被廣泛地應(yīng)用于很多領(lǐng)域。A*算法的基本思想是從搜索空間的初始節(jié)點開始,先廣度優(yōu)先搜索,再用估價函數(shù)f(i)對該輪搜索到的各個子節(jié)點進(jìn)行評估,選出最佳子節(jié)點,再從這個最佳子節(jié)點開始進(jìn)行新一輪的啟發(fā)式搜索直到目標(biāo)節(jié)點為止?？梢夾*算法中最為關(guān)鍵的部分是其評估函數(shù)[6]的設(shè)計,該函數(shù)在保留了傳統(tǒng)算法中只考慮已發(fā)生行為對問題影響的同時,增加了將發(fā)生行為對問題的影響度。評估函數(shù)f(i)的公式定義如下所示:

f(i)=g(i)+h(i)

(1)

式中,f(i)是評估函數(shù),g(i)是初始節(jié)點s到當(dāng)前節(jié)點i的實際代價度量,h(i)是從當(dāng)前節(jié)點i到目標(biāo)節(jié)點e的最小代價啟發(fā)值。由于g(i)是直接計算出來,而h(i)卻需要依靠對問題特性的經(jīng)驗估計來確定。針對不同的問題類型,h(i)的設(shè)計方式會有所不同,h(i)設(shè)計的優(yōu)劣將直接關(guān)系到該評估函數(shù)f(i)的優(yōu)劣,而f(i)設(shè)計的好壞則直接決定著該A*算法的性能優(yōu)劣。f(i)越小,表示選擇節(jié)點i所需要花費的代價越小,節(jié)點i被選擇的概率也就越大。因此,在A*算法中f(i)的設(shè)計至關(guān)重要。在通信業(yè)務(wù)路由路徑設(shè)計中,h(i)一般用歐式距離式(2)或曼哈頓距離式(3)表示均滿足可采納要求:

(2)

h(i)=|xG-xi|+|yG-yi|+|zG-zi|

(3)

在針對網(wǎng)絡(luò)的最短路徑計算問題中,通過添加從當(dāng)前節(jié)點到目的節(jié)點的距離作為參考,使得搜索過程能夠始終朝著距離目的節(jié)點較近的節(jié)點進(jìn)行,搜索過程更具有目的性和方向性。因此,A*算法在搜索區(qū)域上會優(yōu)于傳統(tǒng)的搜索算法,有效避免了傳統(tǒng)搜索算法雜亂搜索導(dǎo)致的搜索范圍大、耗時長的缺點。

3 基于蟻群算法的改進(jìn)算法

3.1 蟻群算法雜亂搜索的改進(jìn)

在傳統(tǒng)的蟻群算法尋路算法中,蟻群k(k=1,2,3,…,n)在t時刻從當(dāng)前節(jié)點i尋找下一個節(jié)點j時的狀態(tài)轉(zhuǎn)移概率為

(4)

其中,allowed=C-tabuk,表示蟻群k(k=1,2,3,…,n)下一步允許選擇的節(jié)點集合,α是信息素啟發(fā)式因子,用于表征信息素重要程度的參數(shù),反映了蟻群在運動過程中所積累的信息素在螞蟻運動時所起的作用。β是期望啟發(fā)式因子,用于表征啟發(fā)函數(shù)重要程度的參數(shù),反映了螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度。ηij(t)為啟發(fā)式函數(shù),其表達(dá)式如下所示:

(5)

傳統(tǒng)的蟻群算法未能充分利用啟發(fā)式函數(shù)ηij(t),將其與通信網(wǎng)絡(luò)的最短路由求解緊密結(jié)合起來。在式(5)中,啟發(fā)式函數(shù)ηij(t)只考慮了上一節(jié)點到當(dāng)前節(jié)點所付出的代價,并沒有考慮當(dāng)前節(jié)點到目的節(jié)點的代價,借鑒A*算法的思想,在啟發(fā)式函數(shù)ηij(t)中新增兩個參數(shù)dje(t)和γ。dje(t)表示當(dāng)前節(jié)點j到目的節(jié)點e的最小代價。啟發(fā)因子γ用于區(qū)別啟發(fā)式函數(shù)中已經(jīng)實際付出的g(i)和將付出的最小代價h(i)對螞蟻尋找路徑的重要性。修正后的啟發(fā)式函數(shù)ηij(t)如下所示:

(6)

將式(6)替換到式(4)中,得到修正后的概率轉(zhuǎn)移公式:

(7)

3.2 蟻群算法蟻群算法雜亂搜索的改進(jìn)

當(dāng)采取局部更新機(jī)制時,能夠在一定程度上實現(xiàn)快速的信息素積累,同時可給其他螞蟻的尋路過程提供經(jīng)驗值,但卻容易造成局部最優(yōu),且這需要對每一只螞蟻每走一步均要進(jìn)行信息素的更新,運算代價較大。針對局部更新機(jī)制存在的缺點,本文采用全局更新機(jī)制的蟻周模型,同時引入權(quán)值參數(shù)λ,可根據(jù)每只螞蟻尋找到的路徑的優(yōu)劣賦予不同的權(quán)值。根據(jù)權(quán)值的不同,對螞蟻所走路徑上的信息素濃度進(jìn)行不同程度的更新,有效地改善了蟻群混合算法中的局部最優(yōu)問題。

(8)

式中,Q表示的是信息素強度,是一個正的常數(shù)值,l(xk(t))表示蟻群k(k=1,2,3,…,n)在本次循環(huán)中所走的總路徑長度,從上式可見,信息素強度Q與路徑總長度l(xk(t))成反比例關(guān)系。

改進(jìn)后的更新機(jī)制將判斷每只螞蟻每次所走路徑是否接近最優(yōu)路徑,當(dāng)螞蟻所尋找的路徑很接近最優(yōu)解時就相應(yīng)的增加信息素濃度,加快收斂的速度;如果螞蟻搜索到的解的質(zhì)量不高或者很差時就不對該路徑的信息素濃度更新,或者只賦予一個很小的信息素增量值,避免對螞蟻尋找最短路徑造成干擾。

本文采用每次螞蟻所走路徑的長度與平均路徑長度進(jìn)行比較來尋找最優(yōu)解。若所走路徑長度大于平均值,則說明有偏離最優(yōu)解的趨勢,這時將賦予一個較小的權(quán)值或0;若所走路徑長度小于平均值,則說明有朝向最優(yōu)解的趨勢,這時將賦予一個較大的權(quán)值。因此,權(quán)值參數(shù)λ表達(dá)式如下:

(9)

則改進(jìn)后的蟻群算法信息素增量的更新機(jī)制變?yōu)?/p>

(10)

改進(jìn)后的信息素更新機(jī)制采用全局更新避免了局部更新容易造成的局部最優(yōu)現(xiàn)象,同時通過引入權(quán)值λ可智能地根據(jù)蟻群所尋路徑的解的質(zhì)量不同賦予不同的值,有效加快了蟻群向最優(yōu)解收斂的速度。

改進(jìn)后的蟻群算法流程步驟如圖1所示。

圖1 改進(jìn)蟻群算法流程

1) 初始化。初始化蟻群算法的信息素濃度。

2) 判斷蟻群算法是否結(jié)束,即是否達(dá)到最大迭代次數(shù)Ne_max。如果達(dá)到迭代次數(shù)則結(jié)束,轉(zhuǎn)到步驟8),否則轉(zhuǎn)到步驟3)。

3) 放置螞蟻。根據(jù)問題的規(guī)模,隨機(jī)放置一定數(shù)量的螞蟻。

4) 螞蟻尋路。螞蟻尋找相鄰近的未訪問節(jié)點,通過計算轉(zhuǎn)移概率,確定下一個節(jié)點。

5) 修改禁忌表。在螞蟻尋找路徑的過程中動態(tài)的修改禁忌表表(Tabu),已經(jīng)訪問過的節(jié)點避免重復(fù)訪問。

6) 遍歷完成。判斷螞蟻是否遍歷了所有節(jié)點,或者尋找到了目的節(jié)點,若是執(zhí)行步驟7),否則跳轉(zhuǎn)到步驟4)繼續(xù)尋路。

7) 信息素的更新。計算平均路徑和最短路徑,并根據(jù)信息素的更新機(jī)制對信息素進(jìn)行更新。

8) 輸出最優(yōu)解。

4 算法驗證與比較

4.1 算法驗證

圖2 傳統(tǒng)蟻群算法的最短路徑以及收斂曲線圖

本文利用Waxman拓?fù)渖善?隨機(jī)生成25個節(jié)點的網(wǎng)絡(luò)拓?fù)淠Ｐ?設(shè)置節(jié)點1為起始節(jié)點,節(jié)點23為目標(biāo)節(jié)點。在此拓?fù)淠Ｐ偷幕A(chǔ)上運行傳統(tǒng)的蟻群算法,其經(jīng)過迭代計算后得到的最短路徑及收斂曲線圖如圖2所示,加粗線條即為傳統(tǒng)的蟻群算法最終找到的最優(yōu)路徑。

在相同的網(wǎng)絡(luò)拓?fù)淠Ｐ蜕线\行改進(jìn)后的蟻群算法,其經(jīng)過迭代計算后得到的最短路往以及收斂曲線如圖3如下,加粗線條即為改進(jìn)后的蟻群算法最終尋找的最優(yōu)路徑。

圖3 改進(jìn)蟻群算法的最短路徑以及收斂曲線圖

從以上兩幅圖對比可見,改進(jìn)后的蟻群算法其搜索到的路徑明顯優(yōu)于傳統(tǒng)的蟻群算法。同時,改進(jìn)后的蟻群算法收斂速度明顯優(yōu)于傳統(tǒng)算法,提高了算法效率。

4.2 算法比較

基于圖論最短路由計算的經(jīng)典算法主要有Dijkstra算法和floyd算法。本文從算法的時間復(fù)雜度和空問復(fù)雜度兩個維度將改進(jìn)后的蟻群算法與這兩種經(jīng)典算法進(jìn)行橫向比較。Dijkstra算法是用來求解一個指定頂點到圖中所有其他頂點間的最短路徑,若要求解任意點到點的單播路由時需要對每一個網(wǎng)元節(jié)點重復(fù)使用Dijkstra算法,即增加一個for循環(huán),導(dǎo)致和Floyd算法的時間復(fù)雜度一樣。在matlab中,數(shù)據(jù)是以數(shù)組的方式進(jìn)行存儲的,所以每個算法的空間復(fù)雜度是一樣的,由分析知,三者之間的區(qū)別具體如表1所示。

表1 算法比較

從上表可以看出三種常用算法的空間復(fù)雜度是一樣的,而從時間復(fù)雜度上來比較時,對于求出所有頂點問的最短路徑來講Dijkstra算法和Floyd算法是一樣的,而與蟻群算法比較三者的數(shù)量級是一樣的,區(qū)別在于Nc,m的取值,通過對Nc,m進(jìn)行合理的取值,可以降低算法的時間復(fù)雜度。

為驗證實際算法效率,本文使用拓?fù)渖善麟S機(jī)依次生成網(wǎng)元數(shù)量為10、20、30、40、50、60、70、80、90、100的拓?fù)鋱D,并分別使用Dijkstra算法、Floyd算法和蟻群算法依次對這些拓?fù)鋱D求解,最后計算每個算法對不同網(wǎng)元數(shù)量的拓?fù)鋱D求解所耗平均時間。

圖4 三種算法平均耗時比較

圖中為了比較的統(tǒng)一性將Nc,m的取值分別固定為50和60。從圖4中可以看出,使用Dijkstra算法和Floyd算法求解任意點到點的單播路由時所耗時間相差不大。蟻群算法與Dijkstra算法和Floyd算法比較,在網(wǎng)元數(shù)量較少時耗時比較長,而當(dāng)網(wǎng)元數(shù)量逐漸增多時蟻群算法的優(yōu)越性就體現(xiàn)出來,因為Dijkstra算法和Floyd算法需要對所有來訪問的節(jié)點進(jìn)行權(quán)值更新,當(dāng)網(wǎng)元數(shù)量很多時,計算量就比較大,從而導(dǎo)致算法的計算時間比較長。再加上蟻群算法是一種智能仿生算法,它具有快速的并行計算能力和正反饋機(jī)制,能夠以信息素的形式對多個參數(shù)進(jìn)行統(tǒng)一處理。這些是Dijkstra算法和Floyd算法所不具有的。因此,在求解多約束條件下的通信網(wǎng)絡(luò)業(yè)務(wù)智能調(diào)配時使用蟻群算法是比較有優(yōu)勢的。

5 結(jié)語

本文對通信業(yè)務(wù)智能調(diào)配過程中經(jīng)常使用的傳統(tǒng)蟻群算法進(jìn)行了分析與研究,針對蟻群算法中存在的雜亂搜索和局部最優(yōu)的缺陷,改進(jìn)后的蟻群算法借鑒了A*算法的思想,綜合考慮了從當(dāng)前節(jié)點到起始節(jié)點所花費的代價,增加了從當(dāng)前節(jié)點到目標(biāo)節(jié)點將花費的代價作為參考,使得螞蟻搜索具有了方向性和目的性。與此同時,在信息素更新時采用了全局更新機(jī)制,增加了一個自適應(yīng)參數(shù),可根據(jù)螞蟻尋找到路徑的優(yōu)劣程度賦予不同的權(quán)值,避免了局部更新機(jī)制所導(dǎo)致的局部最優(yōu)解問題。

最后利用仿真環(huán)境對蟻群算法和改進(jìn)后的蟻群算法進(jìn)行驗證,實驗結(jié)果表明改進(jìn)后的蟻群算法可較好的解決了蟻群算法中存在的雜亂搜索和局部最優(yōu)的缺陷。同時,在復(fù)雜網(wǎng)絡(luò)條件下的算法效率比傳統(tǒng)路由算法也有較大的提升。

本文提出了改進(jìn)的蟻群算法,求解業(yè)務(wù)路由的效率和質(zhì)量較高,對于通信業(yè)務(wù)的智能調(diào)配具有較強的實用性。但該算法中很多參數(shù)的取值均需根據(jù)通信網(wǎng)絡(luò)的實際情況在大量實驗總結(jié)的基礎(chǔ)上才能確定最優(yōu)值,后續(xù)研究工作中應(yīng)著力開展這方面的研究工作,確保實驗結(jié)果更加有效和完善。

[1] ZHENG Rong-rong, ZHAO Zi-yan, LIU Shi, et al. Importance Based Power Communication Service Routing Assignment Algorithm[J]. Electric Power Information Technology,2012,10:23-28.

[2] Dijkstra E W. ANoteonTwoProblemsinConnection withGraphs[J]. Numer Math,1959(1):269-271.

[3] Kang Hwan, Lee, Byunghee, Kim Kabil. Pathplanning algorithm using the particle swarm optimization and the improved dijkstra algorithm[J]. Proceedings-2008Pacific-Asia. Workshop on Computational Intelligence and Industrial Application, PACIIA,2008:1002-1004.

[4] Gang LIU, Ramakrishnan G.A*Prune: An Algorithm for Finding K Shortest Paths Subjectto Multiple Constraints[J]. Proceedings IEEE INFOCOM,2001(2):743-749.

[5] Anwar M A. Integrating Knowledge-Base and Dijkstra’S Algorithmfor Finding Best Alternate Route Dynamically[C]//Multi Topic Conference, 2003. INMIC 2003. 7th International[S.1]: the IEEE Press,2003:428-433.

[6] Dai Zhiquan, Guan Yong, Guan Ran. Dynamic Adjustment A* Routing Algorithm[C]//2010 International Conference on Innovative Computing and Communication and 2010 Asia-Pacific Conference on Information Technology and Ocean Engineering,2010:316-318.

[7] Aini. A, Salehipour. A. Speedingup the Floyd—Warshall algorithmforthecycledshortestpathproblem[J]. Applied Mathematics Letters,2011,25(1):1-5.

[8] Nannicini, G., Delling, D., Liberti, L., et al. Bidirectional A* search for time-dependent fast paths[C]//WEA 2008. LNCS,2008:334-346.

[9] Wen Cao, Hui Shi, Shulong Zhu, et al. Applicationof AnImproved A* Algorithmin RoutePlanning[C]//WRIGlobal Congress, China, Xiamen,2009:253-257.

[10] Dorigo M, Maniezzno V, Colorni A. The ant System: Optimization by a cooperating agents[J]. IEEE Transcation on Systems Man and Cybernatic,1996,26(1):29-41.

Intelligent Allocation of Communication Services Based on Improved Ant Colony Algorithm

MIAO Weiwei1WU Haiyang1SHI Jian2LV Sunli2

(1. Jiangsu Provincial Power Company, Nanjing 210024)(2. Nanjing NARI Group Corporation, Nanjing 210003)

The traffic routing deployment of power communication optical transmission network is in accordance with the characteristics of the multi constraint conditions, and the traditional routing algorithm is difficult to achieve the optimization of the business path generation. Based on the ant colony algorithm, this paper proposes an improved ant colony algorithm based on the idea of A* algorithm, which effectively avoids the defects of random search and easily lead to local optimum in the ant colony algorithm. Through the simulation experiment, the improved ant colony algorithm in different network topology can obtain a better solution, verify the stability of the algorithm and the superiority, has good feasibility and practicability for deployment of intelligent communication services provide supplementary analysis support.

power communication network, intelligent allocation, ant colony algorithm, A* algorithm

2016年7月12日,

2016年8月28日

繆巍巍,男,碩士研究生,高級工程師,研究方向:電力通信傳輸網(wǎng)絡(luò)、智能電網(wǎng)、通信網(wǎng)絡(luò)運維。吳海洋,男,博士研究生,工程師,研究方向:電力通信網(wǎng)絡(luò)、模式識別、信號處理。施健,男,碩士研究生,高級工程師,研究方向:通信網(wǎng)管、專家系統(tǒng)。呂順利,男,碩士研究生,高級工程師,研究方向:電力自動化、智能電網(wǎng)、通信運維。

TP391

10.3969/j.issn.1672-9722.2017.01.009