馬 剛

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

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

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

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

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

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

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

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

1 問題描述

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

2 粒子群算法及算法更新

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

為了讓粒子群算法具有很強的發(fā)現(xiàn)較好解的能力，不易陷入局部最優(yōu)，綜合其改進模式如下：

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

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

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

為了挑選更優(yōu)的下一代粒子，利用高等數(shù)學方差來從下一代粒子群中獲取優(yōu)越的粒子。首先統(tǒng)計系統(tǒng)中所有路由的總路徑數(shù)和總費用，進而獲取路由的平均費用f。利用這個平均費用值作為參的粒子作為優(yōu)越的粒子（e值是很小的數(shù)）?？贾担瑥男律傻南乱淮Ｗ尤后w中，把符合公式

3 基于數(shù)學方差的粒子群優(yōu)化算法設計

在本研究解決的問題中，定義網(wǎng)絡中兩個節(jié)點間存在通路作為自我；否則，即為非自我。根據(jù)優(yōu)化設計思想，具體算法設計為：

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

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

（2）根據(jù)路由請求信息，統(tǒng)計與此路由有關的總費用和總路徑數(shù)，計算出平均費用f。

（3）產(chǎn)生初始抗體。隨機產(chǎn)生一批初始抗體N。

（4）計算粒子適應度；

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

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

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

4 仿真實驗結果

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

表1 節(jié)點與邊的網(wǎng)絡權值

圖1 網(wǎng)絡拓撲結構

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

表2 實驗結果

5 測試e值

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

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

表3 實驗統(tǒng)計e值

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

6 結語

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

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

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

〔3〕熊翱.傳送網(wǎng)網(wǎng)絡質量評價模型和優(yōu)化方法〔D〕.北京：北京郵電大學，2013.

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

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

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

〔7〕劉波.粒子群優(yōu)化算法及其工程應用〔M〕.北京：電子工業(yè)出版社，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.