基于改進人工魚群算法的光網絡最優環路徑搜索研究*

魏 星

(桂林航天工業學院科技處 桂林 541004)

基于改進人工魚群算法的光網絡最優環路徑搜索研究*

魏 星

(桂林航天工業學院科技處 桂林 541004)

針對環路由搜索存在的問題,為提高環形光網絡利用率,提出了一種改進人工魚群算法用于解決光網絡最優環路徑搜索問題。探索了魚群聚群行為、移動步長等改進策略,加快了算法收斂速度,提高了算法的精度和效率。最后,以20個光節點的環形網絡為例,重點研究了改進的人工魚群算法進行環路由搜索、設備選型、系統設計及管理等內容,提高了光網絡效率,節省了光網絡建設成本。

光網絡; 改進的人工魚群算法; 最優環路徑; 光損耗

1 引言

在光網絡的組織結構中,環形光網絡具有鏈路結構簡單、網絡自愈能力強和網絡利用率高等優點,因此,它被作為一種重要的拓撲形式廣泛應用于智能光網絡中。目前,路由與波長分配的優化問題是智能光網絡中面臨的關鍵問題之一,而在環形光網絡中,最優環路由搜索就是在網絡中找到一條路徑從某個起點出發,經過網絡中所有節點,最后回到起點,并且要求環路長度最短,從而實現光網絡的節點設備、光纜線路的最優配置方案。研究最優環路由搜索問題,對于提高環形光網絡傳輸效率,節省網絡建設成本有著重要的意義[1～3]。

環路由搜索問題是一個非確定性多項式(NP-hard)問題,對于規模較小的問題一般采用精確算法求解,但是算法的求解時間較長,因此,在求解這類問題時,采用智能式啟發算法會取得較好的效果。目前,蟻群算法、人工魚群算法等智能算法已經成為求解環路由搜索問題的主要方法。

人工魚群算法[4～5](AFSA)最早由李曉磊博士于2003年提出,該算法通過模擬魚群的覓食、聚群、追尾等各種行為,具有初始值要求不高,前期收斂速度快,魯棒性較強等特點,被廣泛應用于解決各類組合優化問題。但是,魚群算法也存在后期收斂速度慢,算法結果精度不高等缺點,因此,本文對基本魚群算法進行了改進,改進了魚群聚群行為、移動步長等新思想,使之適用于環路由搜索問題,最后通過仿真實驗表明了改進人工魚群算法具有收斂速度快、結果不精確等特點。

2 魚群算法及行為描述[6]

在一片水域中,魚聚集數目最多的地方一般就是本水域中營養最為豐富的地方,魚群算法就是基于這個特點來模仿魚群覓食等行為,從而實現全局尋優,這就是魚群算法的基本思想[6]。

魚群在覓食過程中主要有幾個基本行為,即:覓食、聚群、追尾和隨機等行為。人工魚群算法就是利用魚群的基本行為,從魚群的底層個體出發,通過個體的局部尋優,最終達到全局最優的目的。下面就幾個基本行為進行描述。

1) 覓食行為:這是魚循著食物多的方向游動的一種行為,是一種向較優方向迭代尋優的方式。其描述為:首先,比較目前狀態的函數與其感知范圍內狀態隨機函數的大小,如果隨機函數更大,則向新狀態靠近一步,反之,重新選取新狀態,判斷條件;當選擇次數達到一定值后,仍不滿足條件,則隨機選擇狀態。

2) 聚群行為:魚在游動過程中為了保證自身的生存和躲避危害會自然地聚集成群,這種行為能保證魚群伙伴間不會過于擁擠,魚群移動方向大致相同。其描述為:人工魚搜索當前相鄰的伙伴數目,計算其中心位置的函數,并比較中心函數與目前的狀態函數,如中心函數更優且擁擠度不高,則向中心位置靠近一步,反之進行覓食行為。

3) 追尾行為:當魚群中有個體魚發現了食物,其附近的魚會尾隨而來,快速到達食物區域。其描述為:比較當前魚范圍內的所有狀態函數,找出范圍內最大目標函數,且其位置擁擠度較低,則向其位置移動一步,進行追尾行為;反之,進行覓食行為。

4) 隨機行為:魚在水中為了在更大范圍內搜尋食物或伙伴進行的一種隨機的游動行為。

3 人工魚群算法的改進

魚群算法的數學模型描述如下[9～11]:人工魚個體的狀態為向量Xi=(x1,x2,…,xn),其中:xi(i=1,2,…,n)為魚群個體變量;用Y=f(x)表示人工魚當前位置食物濃度;個體間的距離和感知距離分別為dij=‖Xi-Xj‖和Visual;Step為移動步長:δ為擁擠度因子,try_number為嘗試次數,Rand()為(0,1)之間的隨機數。其具體覓食過程中的覓食、聚群、追尾和隨機等幾個基本行為的數學模型可參見文獻[2]中的詳細描述,本文在此不再重復描述。

基本魚群算法是一種隨機群智能算法,也存在收斂速度慢、效率不高等不足,本文改進了魚群的聚群行為,并討論移動步長的改進方法,使之更好運用于光網絡最短的求解問題。

1) 聚群行為的改進

在魚群算法中,聚群行為能夠很好地跳出局部極值,并盡可能搜索到其它的極值,最終搜索到全局極值,通過改進聚群行為達到提高魚群的收斂效率的目的。

具體描述為:當前人工魚Xi鄰域內人工魚數目為nf,中心位置狀態用Xc表示,當Yc/nf>δYi,說明中心位置食物濃度較高,且擁擠度較低,則人工魚向中心位置移動一步,進行聚群行為;反之,進行覓食行為。在人工魚向食物濃度較高的中心位置狀態Xc移動過程中,如果在其感知范圍內發現有另一個狀態Xv的食物濃度大于Xc,這時,人工魚便放棄向中心位置狀態Xc的移動,轉向目前食物濃度更高的狀態Xv,即Xi/next=Xv。

通過以上的聚群行為改進,人工魚能動態地調整移動方向,能實時地朝著食物濃度更大的狀態移動,從而節省了搜索時間,提高了搜索精度及效率。

2) 步長改進策略

在原始魚群算法中,采用隨機步長的方式,移動步長Rand()Step為隨機數。隨機移動擴大了尋優范圍,但是導致魚群的隨機性增加,收斂速度下降;如果采用固定步長,步長越大,收斂速度越快,但是,達到一定數值后,步長過大,會出現震蕩現象,收斂速度會減慢。所以,在實際的優化問題中,可以考慮采用合適的固定步長或變尺度方法來提高算法收斂。

因此,本文做如下改進:

在覓食行為中,人工魚Xi與其感知內的任意人工魚Xj的狀態關系為

Xj=Xi+Rand()·Visual

當前人工魚Xi的食物濃度為Yi,其感知內的任意人工魚Xj的食物濃度Yj,即Yi

(1)

反之,重新選擇Xj;則按式(2)移動一步:

(2)

其中:Rand()為(0,1)之間的隨機數。

4 組網實例

在實際應用中,光網絡的路由通信會受到多種條件的限制,比如:山川、河流等地域特點,在工程中,光纜路由的設計一般都是通過工程師依據傳統設計經驗和用戶需求通過人工繪圖、計算來實現的,但是,這種方式缺乏可靠的理論依據,設計的路由不一定是最優的,成本也不一定最低。因此,本文選用20個節點的環網的路由優化來演示工程應用,主要采用智能算法來設計20個節點的光網絡路由,求得最短路徑,節省網絡建設費用。

4.1 優化設計

環形光網絡自愈能力強,當網絡出現故障時,能夠在極短的時間自動恢復中斷的業務。在仿真實驗中,采用單纖環連接環路中20個節點,在環網光網絡的保護時,采用以復用段為基礎的鏈路倒換(也稱光復用段倒換)方式,其環形保護結構使用光復用段共享保護環(OMS-SPRING),系統采用光交叉連接和光分插復用設備,具有系統容量大、升級改造簡單等特點,其對于的路由算法有很多,下面我們就采用改進的人工魚群算法來進行路由求解。

4.2 用改進人工魚群算法求最短路徑

本實驗中,利用文獻[7]中的仿真環境,在網路平面中隨機產生的20個光節點,節點的坐標如表1所示。

表1 隨機的20個光節點坐標值表

隨機的20個節點的初始位置如圖1所示。

圖1 隨機的20個節點坐標圖

人工魚群算法的各個參數設置如下[8]:其中人工魚群中的參數Trynumber=50,Visual0=2.5,δ=2,L=30,魚群種群數量N=30。

通過本文改進的人工魚群算法的計算,得到光網絡中20個節點最優環路徑搜索結果如圖2所示。

圖2 20個節點最優環路徑圖

本文改進的人工魚群算法仿真搜索到的最優路徑環如下:

1→10→14→8→9→19→12→6→11→7→2→3→16→13→20→17→4→18→5→15→1

最優路徑總長度為283.936km。通過分析,可以得知,一方面,由于本文算法對魚群的聚群行為進行了改進,人工魚能動態地、實時地朝著食物濃度更大的狀態移動,提高了搜索效率,并最終達到全局最優;另一方面,在算法中后期,改進了步長策略,使之按感知區域內食物濃度的變化進行覓食行為,提高了局部搜索能力,減少了隨機搜索。因此,本文方法適用于實際的光網絡最短路徑的求解應用。

4.3 設備的選型

在實際的工程中,可選用華為技術有限公司OptiX OSN 3500智能光傳輸設備進行組網,該設備是華為公司根據城域網現狀及發展趨勢,開發的新一代智能光傳輸設備,融合SDH(Synchronous Digital Hierarchy)、Ethernet、PDH(Plesiochronous Digital Hierarchy)等技術,實現了在同一個平臺上高效地傳送語音和數據業務;一個機柜可以安裝2個OptiX OSN 3500子架,其采用雙層子架結構,分為出線板區、風扇區、插板區和走纖區。

OptiX OSN 3500可以實現線性復用段保護、復用段保護環,并且支持環網間互通業務的保護,對保護方式互異的環網(如:SNCP和MSP環網)間的互通業務也能夠提供保護,被廣泛應用于光網絡組網中。因此,本工程采用該設備連接環路中20個節點,組成環形光網絡。

4.4 系統設計

1) 光纖參數。本工程選用G.655光纖在光纜上,衰減系數為0.22dB/km,而G.655光纖1530～1560nm波長區色散為1.0～6ps/nm.km,傳輸相同的10Gb/s系統時,因色散很低,因此,不需要色散補償。

2) 其他光器件參數。本工程中光波長轉發器的插入損耗為2dB,光分插復用器和光選擇器的插入損耗分別為6.5dB、5dB。

3) 光節點間的損耗計算。基于前文的求解計算,得到了20個節點的最短路徑,節點間的損耗按廠家提供的參數進行。

光損耗=實際距離(km)*光纖衰耗系數(dB/km)+接頭衰耗(0.5dB×2)。

比如:節點1到節點10的光損耗計算:

A1-10=17.692km×0.22dB/km+0.5dB×2=4.892dB

節點20到節點17的光損耗計算:

A20-17=7.000km×0.22dB/km+0.5dB×2=2.540dB

同理,其他節點間的光損耗如表2所示。

表2 最短路徑距離及損耗表

4.5 系統管理

工程由OptiX OSN 3500架構后,采用系統自帶的iManager系列的網絡管理系統進行統一管理。網絡管理系統通過Qx接口或MML接口,實現對整個光傳輸系統的配置、故障、安全等方面的管理、維護及測試。提高了網絡服務質量、降低了維護成本,保證網絡資源的合理使用。

5 結語

本文針對傳統光纜路由的組織以人工計算、繪圖決策等問題進行改善,研究了環形光網絡路由搜索問題,對基本魚群算法進行了改進,提出了魚群感知距離自適應、移動步長自適應等方法,并將改進魚群算法應用于具體環形光網絡組建實例中,計算了最短路徑,研究了設備選型,系統損耗計算及網絡管理,結果表明,本文的方法在解決環路由搜索等優化問題中具有較好的效果。

[1] 羅芳瓊,侯睿.混合蟻群算法在光網絡最優環路徑搜索中的應用[J].光通信研究,2014,6(3):8-10,23. LUO Fangqiong, HOU Rui. Study on optimum ring path search based on hybrid ant colony algorithm in optical networks[J]. Study on Optical Communications,2014,6(3):8-10,23.

[2] 尹珊.靈活光網絡中的資源優化[D].北京:北京郵電大學,2014. YIN Shan. Resource optimization in flexible optical WDM networks[D]. Beijing: Beijing University of Posts and Telecommunications,2014.

[3] 劉煥淋,李瑞艷,孔德謙.基于多目標遺傳算法優化彈性光網絡的多路徑保護機制[J].電子與信息學報,2016,6(6):1-7. LIU Huanlin, LI Ruiyan, KONG Deqian. Optimization Survivable Multipath Provisioning Based on Multiobjectives Genetic Algorithm for Elastic Optical Networks[J]. Journal of Electronics & Information Technology,2016,6(6):1-7.

[4] 李曉磊.一種新型的智能優化算法——人工魚群算法[D].杭州:浙江大學,2003. LI Xiaolei. A New Intelligent Optimization Method-Artificial Fish School Algorithm[D]. Hangzhou: Zhejiang University,2003.

[5] 李曉磊,邵之江,錢積新.一種基于動物自治體的尋優模式魚群算法[J].系統工程理論與實踐,2002,22(11):32-38. LI Xiaolei, SHAO Zhijiang, QIAN Jixin. An Optimizing Method Based on Autonomous Animats: Fish-swarm Algorithm[J]. Systems Engineering-theory & Practice,2002,22(11):32-38.

[6] 王闖.人工魚群算法的分析及改進[D].大連:大連海事大學,2008. WANG Chuang. The analysis and improvement of artificial fish-swarm Algorithm[D]. Dalian: Dalian Maritime University,2008.

[7] 魏星,李志遠,汪其.基于蟻群和粒子群的混合光網絡路由優化算法[J].桂林航天工業學院學報,2015,80(4):467-470. WEI Xing, LI Zhiyuan, WANG Qi. Hybrid optimization algorithm based on ant colony and particle swarm for routing in optical network[J]. Journal of Guilin University of Aerospace Technology,2015,80(4):467-470.

[8] 魏星,李志遠,陳艷.基于蟻群和魚群的混合優化光網絡動態RWA算法[J].光通信技術,2015,3(3):47-49. WEI Xing, LI Zhiyuan, CHEN Yan. Hybrid optimization algorithm based on ant colony and fish school for dynamic routing and wavelength assignment in optical network[J]. Optical Communication Technology,2015,3(3):47-49.

[9] 王謙,吳啟武,姜靈芝.基于人工魚群優化的光網絡攻擊感知路由算法[J].光通信研究,2014,12(6):15-18. WANG Qian, WU Qiwu, JIANG Lingzhi. An attack-aware routing algorithm for optical networks based on artificial fish swarm optimization[J]. Study on Optical Communications,2014,12(6):15-18.

[10] 王會穎,章義剛.求解聚類問題的改進人工魚群算法[J].計算機技術與發展,2010,20(3):84-87. WANG Huiying, ZHANG Yigang. An improve artificial fish swarm algorithm of solving clustering analysis problem[J]. Computer Technology and Development,2010,20(3):84-87.

[11] 喻俊松,王琪,徐蓉瑞.基于改進人工魚群算法的無人機路徑規劃[J].彈箭與制導學報,2015,6(3):37-40. YU Junsong, WANG Qi, XU Rongrui. UAV Path Planning Based on Improved Artificial Fish-swarm Algorithm[J]. Journal of Projectiles, Rockets, Missiles and Guidance,2015,6(3):37-40.

Optimum Ring Path Search Based on Improved Artificial Fish Swarm Algorithm in Optical Network

WEI Xing

(Department of Scientific Research, Guilin University of Aerospace Technology, Guilin 541004)

In allusion to the problem about optimal ring path in optical network. in order to improve the use ratio of ring optical network, a kind of method about optimum ring path is put forward based on improved artificial fish swarm algorithm. The improve strategy of the cluster behavior step and length of the fish and so on are studied, the method can accelerate speed of algorithm constriction, and improve the accuracy and efficiency of algorithm. Finally, with 20 nodes light ring network as an example, optimum ring path search is studied based on improved artificial fish swarm algorithm, equipment selection, system design and management, the efficiency of optical network is increased, the development digression of optical network is cut down.

optical network, improved artificial fish swarm algorithm, the optimum ring path, optical loss Class Number TP391

2016年10月9日,

2016年11月17日

廣西自然科學基金(編號:2014GXNSFBA118286);廣西優秀中青年骨干教師培養工程;2015年國家級大學生創新創業訓練計劃項目資助。

魏星,男,碩士,副教授,研究方向:智能算法,計算機應用。

TP391

10.3969/j.issn.1672-9722.2017.04.012