基于改進蟻群算法的通信業務智能調配分析研究*

繆巍巍 吳海洋 施 健 呂順利

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

?

基于改進蟻群算法的通信業務智能調配分析研究*

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

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

電力通信光傳輸網絡的業務路由調配符合多約束條件的路由路徑特點,傳統的路由計算方法難以實現最優化的業務路徑生成。論文在蟻群算法的基礎上借鑒A*算法的思想,提出了一種改進的蟻群算法,有效避免了蟻群算法中雜亂搜索和容易導致局部最優的缺陷。通過實驗仿真,改進后的蟻群算法在不同的網絡拓撲圖上均能得到較優解,驗證了算法的穩定性和優越性,具有較好的可行性和實用性,可為通信業務的智能調配提供輔助分析支持。

電力通信網; 智能調配; 蟻群算法; A*算法

Class Number TP391

1 引言

隨著智能電網和“三集五大”體系的全面推進,電力企業對于通信業務的需求呈現爆發式增長的趨勢。電力通信網作為電力系統的專用網絡,其承載的通信業務主要是與電力生產、運行相關的通信業務,包括繼電保護業務、穩定控制業務、遠動業務、調度業務、辦公業務等,這些業務對路徑選擇、可靠性等方面有特殊要求,業務路由的不同調配方式可能會對電力系統的安全穩定運行帶來不同的潛在風險。因此,針對電力通信的網絡拓撲架構和當前通信業務的需求分布,在保證網絡資源有效利用的同時,科學合理地調配與選擇路由路徑,使得通信業務能夠獲得滿足其服務要求的傳輸路徑,已成為增強網絡運維效能、提升網絡運維水平的重要工作[1]。

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

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

2 A*算法基本原理

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

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

(1)

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

(2)

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

(3)

在針對網絡的最短路徑計算問題中,通過添加從當前節點到目的節點的距離作為參考,使得搜索過程能夠始終朝著距離目的節點較近的節點進行,搜索過程更具有目的性和方向性。因此,A*算法在搜索區域上會優于傳統的搜索算法,有效避免了傳統搜索算法雜亂搜索導致的搜索范圍大、耗時長的缺點。

3 基于蟻群算法的改進算法

3.1 蟻群算法雜亂搜索的改進

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

(4)

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

(5)

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

(6)

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

(7)

3.2 蟻群算法蟻群算法雜亂搜索的改進

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

(8)

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

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

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

(9)

則改進后的蟻群算法信息素增量的更新機制變為

(10)

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

改進后的蟻群算法流程步驟如圖1所示。

圖1 改進蟻群算法流程

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

2) 判斷蟻群算法是否結束,即是否達到最大迭代次數Ne_max。如果達到迭代次數則結束,轉到步驟8),否則轉到步驟3)。

3) 放置螞蟻。根據問題的規模,隨機放置一定數量的螞蟻。

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

5) 修改禁忌表。在螞蟻尋找路徑的過程中動態的修改禁忌表表(Tabu),已經訪問過的節點避免重復訪問。

6) 遍歷完成。判斷螞蟻是否遍歷了所有節點,或者尋找到了目的節點,若是執行步驟7),否則跳轉到步驟4)繼續尋路。

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

8) 輸出最優解。

4 算法驗證與比較

4.1 算法驗證

圖2 傳統蟻群算法的最短路徑以及收斂曲線圖

本文利用Waxman拓撲生成器,隨機生成25個節點的網絡拓撲模型,設置節點1為起始節點,節點23為目標節點。在此拓撲模型的基礎上運行傳統的蟻群算法,其經過迭代計算后得到的最短路徑及收斂曲線圖如圖2所示,加粗線條即為傳統的蟻群算法最終找到的最優路徑。

在相同的網絡拓撲模型上運行改進后的蟻群算法,其經過迭代計算后得到的最短路往以及收斂曲線如圖3如下,加粗線條即為改進后的蟻群算法最終尋找的最優路徑。

圖3 改進蟻群算法的最短路徑以及收斂曲線圖

從以上兩幅圖對比可見,改進后的蟻群算法其搜索到的路徑明顯優于傳統的蟻群算法。同時,改進后的蟻群算法收斂速度明顯優于傳統算法,提高了算法效率。

4.2 算法比較

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

表1 算法比較

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

為驗證實際算法效率,本文使用拓撲生成器隨機依次生成網元數量為10、20、30、40、50、60、70、80、90、100的拓撲圖,并分別使用Dijkstra算法、Floyd算法和蟻群算法依次對這些拓撲圖求解,最后計算每個算法對不同網元數量的拓撲圖求解所耗平均時間。

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

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

5 結語

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

最后利用仿真環境對蟻群算法和改進后的蟻群算法進行驗證,實驗結果表明改進后的蟻群算法可較好的解決了蟻群算法中存在的雜亂搜索和局部最優的缺陷。同時,在復雜網絡條件下的算法效率比傳統路由算法也有較大的提升。

本文提出了改進的蟻群算法,求解業務路由的效率和質量較高,對于通信業務的智能調配具有較強的實用性。但該算法中很多參數的取值均需根據通信網絡的實際情況在大量實驗總結的基礎上才能確定最優值,后續研究工作中應著力開展這方面的研究工作,確保實驗結果更加有效和完善。

[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日

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

TP391

10.3969/j.issn.1672-9722.2017.01.009