基于方差的優良粒子群多約束路由選擇算法

馬 剛

（福建師范大學閩南科技學院計算機系，福建泉州 362332）

通過使用電腦、手機等終端以實現計算機網絡通信，已經成為了大眾必不可少的生活方式之一，為了使通信業務網提供高質量的信號傳輸服務，在電路創建、連接、調度、釋放時需要遵循一定的管理原則，運營商在路由選擇中需要考慮如下的因素〔1〕：

（1）同類互斥原則：同類型同向電路盡量選擇不同的路徑；

（2）可靠性原則：路由選擇應考慮網絡鏈路的可靠性；

（3）負荷分擔原則：開通的電路應在不同傳輸系統之間進行負荷分擔；

（4）最少轉接次數原則：電路路由應盡可能減少在不同傳輸系統間的轉接。

我們把以上原則轉換為另外一種用于描述最優路由路徑選擇的網絡理論概念，就是指使用現有的有效資源為用戶、應用需求提供新請求的最佳實時路由〔2-3〕。多約束路由選擇是一個NP完全問題，雖然已有部分學者提出了逼近算法，但是至今還沒有被徹底解決。國內外許多研究人員提出了若干個智能算法，想找出一個算法來解決網絡路由選擇問題，通過研究發現，一種叫做基于粒子群優化算法的路由選擇算法，取得了比較好的通信效果。

這種新興的智能算法——粒子群優化算法（Particle Swarm Optimization，PSO）是在 1995年由Eberhart和Kennedy提出的模擬鳥群集體協作而共同飛行覓食（目標）的行為算法〔4-5〕。該算法是一種概念簡明，實現方便，參數設置較少的多約束目標搜索算法，在簡單的約束條件下目標搜索較為精確，但是人們往往使用的是更新后的PSO算法，這種新的PSO算法已經廣泛應用在工程領域中。本文就提出了基于傳統粒子群算法之上，利用方差而得到的新粒子作為后繼優良粒子，根據這些優良粒子搜索目標，獲得最佳的路由。

1 問題描述

計算機網絡的理論來源于圖論及其集合，王樹禾教授出版的《圖論》教材〔6〕中把網絡模型表示用賦權圖G=（V，E）來描述，其中V是圖中所有節點組成的集合，E是圖中所有邊的集合，每一條邊表示相鄰兩節點間的直達通信路徑，假定相鄰兩節點間最多僅有一條邊。對于一個路由請求R，路由算法如果能夠找到一條具有最小費用的路徑L，同時滿足條件：帶寬限制，端到端時延限制，端到端費用限制。Bandwidth，Delay分別代表要求的帶寬、時延。目標是找鏈路路徑L，不僅滿足所有約束條件，而且鏈路傳輸費用之和最小，即s.t.約束條件如下所示。

2 粒子群算法及算法更新

傳統粒子群算法描述是：Van den Bergh通過時粒子群中最佳粒子始終處于運動狀態，得到保證收斂到局部最優的改進算法，但其性能并不佳〔7〕。Kennedy等研究粒子群的拓撲結構，分析粒子間的信息流，提出了一系列的拓撲結構〔8-10〕。Angeline將選擇算子引入到PSO中，選擇每次迭代后的較好的粒子并復制到下一代，以保證每次迭代的粒子群都具有較好的性能〔6〕。傳統的粒子群算法描述公式如下：Vk+1=wVk+c1r1（Pidk-Xk）+c2r2（Pgdk-Xk）；Xk+1=Vk+1+Vk+1；其中，w為慣性權重；r1和r2為分布于［0，1］之間的隨機數；k是當前迭代次數；Pid為個體最優粒子位置；Pgd為全局最優粒子位置；c1和c2為常數；V為粒子速度；X為粒子位置。

為了讓粒子群算法具有很強的發現較好解的能力，不易陷入局部最優，綜合其改進模式如下：

（1）算法的具體參數設定和調整策略：如Shi和Eberhart在速度項添加的慣性權重，后來提出的模糊自適應調整慣性權重思想。

（2）修改了算法的總體結構：適應粒子之間的信息交換，進一步影響了算法的尋優能力。

（3）混合算法：粒子群算法和其他算法結合。

為了挑選更優的下一代粒子，利用高等數學方差來從下一代粒子群中獲取優越的粒子。首先統計系統中所有路由的總路徑數和總費用，進而獲取路由的平均費用f。利用這個平均費用值作為參的粒子作為優越的粒子（e值是很小的數）。考值，從新生成的下一代粒子群體中，把符合公式

3 基于數學方差的粒子群優化算法設計

在本研究解決的問題中，定義網絡中兩個節點間存在通路作為自我；否則，即為非自我。根據優化設計思想，具體算法設計為：

（1）輸入請求。輸入路由請求的各項參數R。

綜上所述,使用乳房按摩能夠促進足月孕產婦宮頸成熟與分娩,臨床可以推薦使用該方法進行促進孕產婦宮頸成熟。

（2）根據路由請求信息，統計與此路由有關的總費用和總路徑數，計算出平均費用f。

（3）產生初始抗體。隨機產生一批初始抗體N。

（4）計算粒子適應度；

（5）更新下一代粒子群；

（6）利用公式|xi-f|=＜e從下一代的粒子種群中選取更優良的粒子群；

（7）如滿足結束條件，則輸出結果；否則，轉（4）。

4 仿真實驗結果

本文設計的網絡拓撲結構如圖1所示。其中，每個頂點用＜ delay，loss，delay_change＞表示，其中的元素分別代表節點時延、節點丟失率和節點時延變化；每條邊用＜cost，width，delay_change＞ 表示，其中的元素分別代表邊的費用、帶寬和鏈路時延。表1給出了網絡拓撲的相關權值信息。

表1 節點與邊的網絡權值

圖1 網絡拓撲結構

假設有3個路由請求 ＜ 1，5＞、＜ 1，9＞、＜ 3、8＞。通過仿真實驗，表2給出了實驗結果。

表2 實驗結果

5 測試e值

為了確定e的值，本文首次提出了e的測量值計算方法，引入了基準測試函數?；鶞蕼y試函數又常常稱之為Benchmark函數，目前被經常使用的函數多達20個，含有多波谷峰函數、單峰函數、一維函數、高維次函數，它們分別代表著不同優化類型的工程問題，這些函數可以測試與衡量算法的性能，確定算法參數的合理區間值。下表列出了部分通用的基準函數。Sphere Model函數是基于對稱結構的一種非線性化單峰數學函數，其全局最優值被認為是min（f1）=f1（0，0，0，0，...0，0，0）=0，其數學模型公式是f1（x）=∑Xi2，是一種具有比較好的測試智能目標優化算法的高精度尋優能力的函數。

e值測定的實驗是在Matlab科學計算工具軟件中執行的，在新引入的|xi-f|=＜e條件下，更新了原來的基本粒子群優化算法PSO函數，在Matlab中對更新后的PSO優化算法提供了函數調用接口，指定了粒子數目N=50和迭代次數D=100次，慣性權值w=0.9，c1、c2因子各取值為1.3，在確保不影響獲取優化結果值的要求下，對e值設置了3種閾值，實驗結果如表3所示。

表3 實驗統計e值

由表3中的實驗結果可以分析出，e的閾值設定非常關鍵，當e在（0.55，0.832）區間時，優良的粒子占總數的比例比較小，算法的尋優結果也接近理論值。

6 結語

本研究中繼續沿用了傳統的粒子群粒子更新算法，并同時采用|xi-f|=＜e繼續對下一代粒子群進行選優，這樣就減少了下一代粒子群的總數，減少了算法的復雜性，提高了算法的進化速度，對于e值的設定較為關鍵，還要進一步通過實驗確定其值范圍，來保證粒子群算法的全局尋優能力。

〔1〕熊翱.基于改進型蟻群系統的多約束電路路由算法〔J〕.計算機工程，2008，34（11）：183-185.

〔2〕陳曦.基于免疫粒子群優化算法的多約束路由選擇算法〔J〕.長沙交通學院學報，2006，22（2）：56-59.

〔3〕熊翱.傳送網網絡質量評價模型和優化方法〔D〕.北京：北京郵電大學，2013.

〔4〕紀震，吳青華.粒子群算法及應用〔M〕.北京：科學出版社，2009：10-20.

〔5〕潘峰，李位星，高琪.動態多目標粒子群優化算法及其應用〔M〕.北京：北京理工大學出版社，2014：1-10.

〔6〕王樹禾.圖論〔M〕.北京：科學出版社，2009：10-20.

〔7〕劉波.粒子群優化算法及其工程應用〔M〕.北京：電子工業出版社，2009：13-25.

〔8〕VAN D B F.An analysis of particle swarm optimizer〔C〕//Proceedings of the 1998 conference of Evolutionary computation，Piscataway.IEEE Press，1998：67-73.

〔9〕MENDESR，KENNEDYJ.Thefullinformedparticleswarm：Simpler，maybe better〔J〕.IEEE Transaction on Evolutionary Computation，2004，8（3）：204-210.

〔10〕ANGELINE P J.Using selection to improve particle swarm optimization〔C〕//Proceeding of the 1999 Congress on Evolutionary Computation，Piscatawar.IEEE Press，1999：84-89.