智能計算在網絡優化中的應用

紀 喆

（青島西海岸新區膠南第一高級中學，青島 266400）

智能計算在網絡優化中的應用

紀 喆

（青島西海岸新區膠南第一高級中學，青島 266400）

本文首先對最優化方法和智能計算及其研究現狀作了簡單介紹；然后闡述了人工魚群算法及人工魚群算法在路由優化中的應用；最后對智能優化算法進行了總結和展望。

智能優化算法；最優化技術；人工魚群算法

1 引言

智能計算就是借用自然界生物界規律的啟迪根據其原理模仿設計求解問題的算法，目前，人們已提出了三十多種神經網絡模型，這些模型都是從神經元、神經網絡的狀態、傳播規則、活躍規則、輸出函數、學習算法、互連模式、環境、穩定狀態、操作模式等十個方面來進行描述。按照學習算法支待的操作類型分類，則學習算法至少可以分為自聯想器、模式聯想器、模式分類器和正則探測器四類。

2 基于改進的人工魚群算法的路由優化

2.1 人工魚群算法的基本概念

人工魚群算法是李曉磊等人于2002年提出的一種基于動物自治體的優化方法，是集群智能思想的一個具體應用，該算法根據水域中魚生存數目最多的地方就是本水域中富含營養物質最多的地方這一特點來模擬魚群的覓食行為而實現尋優。它的主要特點是不需要了解問題的特殊信息，只需要對問題進行優劣的比較，通過各人工魚個體的局部尋優行為，最終在群體中使全局最優值突現出來，有著較快的收斂速度。

人工魚群算法主要利用魚的三大基本行為：覓食、聚群和追尾行為，采用自上而下的尋優模式從構造個體的底層行為開始，通過魚群中各個體的局部尋優，達到全局最優值在群體中凸顯出來的目的。

（1）覓食行為：這是魚趨向食物的一種活動，一般認為它是通過視覺或味覺來感知水中的食物兩或食物濃度來選擇行動的方向。

（2）聚群行為：大量或少量的魚聚集成群，進行集體覓食和躲避敵害，這是它們在進化過程中形成的一種生存方式。

（3）追尾行為：當某一條魚或幾條魚發現食物時，它們附近的魚會尾隨而來，導致更遠處的魚也會尾隨過來。

人工魚群算法就是通過模擬魚類的覓食、聚群、追尾等行為在搜索域中進行尋優的。

2.2 人工魚群算法的行為描述

（1）覓食行為：設置人工魚當前狀態，并在其感知范圍內隨機選擇另一個狀態，如果得到的狀態的目標函數大于當前的狀態，則向新選擇得到的狀態靠近一步，反之，重新選取新狀態，判斷是否滿足條件，選擇次數達到一定數量后，如果仍然不滿足條件，則隨機移動一步[6]。

（2）聚群行為：人工魚探索當前鄰居內的伙伴數量，并計算伙伴的中心位置，然后把新得到的中心位置的目標函數與當前位置的目標函數相比較，如果中心位置的目標函數優于當前位置的目標函數并且不是很擁擠，則當前位置向中心位置移動一步，否則執行覓食行為[6]。

（3）追尾行為：人工魚探索周圍鄰居魚的最優位置，當最優位置的目標函數值大于當前位置的目標函數值并且不是很擁擠，則當前位置向最優鄰居魚移動一步，否則執行覓食[6]。

根據所要解決的問題性質，對人工魚當前所處的環境進行評價，從而選擇一種行為。較常用的評估方法是：選擇各行為中使得向最優方向前進最大的方向，也就是各行為中使得人工魚的下一步狀態最優的行為，如果沒有能使下一個狀態優于當前狀態的行為，則采用隨機行為。

2.3 人工魚群算法步驟

⊙ 設定魚群的參數，包括魚群的規模m，最大迭代次數gen，人工魚的感知范圍Visual，最大移動步長step，擁擠度因子d等。

⊙ 在參數區間內隨機生成m條人工魚個體作為初始魚群。

⊙ 計算每條魚的食物濃度函數（目標函數），把最優的值放入公告板[7]中。

⊙ 對于每條人工魚執行以下操作：計算出追尾行為、聚群行為的值，采用行為選擇策略，選擇最優的行為作為魚的移動方向，缺省行為是覓食行為。計算出每條魚的食物濃度函數（目標函數），其最優值與公告板中的值進行比較，最終公告板中始終保持最優的值。

⊙ 判斷是否滿足結束條件，如果滿足結束，否則轉上一步。

最終公告板中的值就是最優值。

2.4 基于人工魚群算法的路由優化

2.4.1 禁忌表和藐視準則

算法中禁忌表的表項表達為一條人工魚，表的深度依求解問題的復雜度而定，若禁忌表已滿，則按先進先出的原則更新表項，禁忌長度設為定值。需要指出的是，由于當前的禁忌對象對應狀態的適配值可能很好，因此在算法中設置判斷，若禁忌對象對應的適配值優于當前最優解（"best so far"）狀態，則無視其禁忌屬性而仍采納其為當前選擇，也就是通常所說的藐視準則。

2.4.2 禁忌計算

設人工魚Xi和Xj，新的人工魚的產生按如下禁忌計算方法進行：

Xnew=Xi+η(Xi-Xj)其中，η∈[0,1]是預設概率值，"-"運算完成對Xi和Xj的比較，"+"運算完成Xj對Xi的置換操作，即：解Xj和解Xi中不同分量以η的概率發生置換操作，而相同分量保持不變。人工魚個體之間的距離，即兩個解之間的距離定義為：d(i,j)=Xi-Xj。

2.4.3 仿真實現與性能評價

基于NS2平臺進行了仿真實現，在多個實際與虛擬的網絡拓撲上對本文所描述的算法；基于粒子群和遺傳算法的QoS組播路由算法和基于遺傳算法的QoS組播路由算法，進行仿真實驗與性能評價。

2.4.4 滿足用戶QoS約束的概率的比較

設定多次組播請求，每次請求的源節點和組播目的節點隨機產生，其他參數不變，運行三種算法，以可用帶寬和延遲為例，分別統計三種算法所得到的最優組播樹的可用帶寬和延遲滿足用戶QoS要求的概率與進化代數的關系，仿真結果表明，TAFQM算法和PGAQM算法均能較快的找到可用帶寬和延遲滿足用戶QoS約束概率較大的組播樹，TAFQM算法的收斂速度優于另外兩種算法。總體上講，三種算法經過30次左右的迭代，滿足用戶QoS約束的概率已達95%以上。

2.5 進一步的研究工作

作為一個前沿性的熱點研究領域，人工魚群算法已引起越來越多國內研究者的關注，但因人工魚群算法（AFSA）起步較晚，與遺傳算法、神經網絡、蟻群算法、粒子群算法和免疫算法相比，人工魚群算法理論還不完善、不成熟，研究處于初步階段，在今后的工作中，還有很多方面有待進一步的探索和研究：

（1）人工魚群算法的理論研究。人工魚群算法的理論研究還存在許多問題需要進一步解決，比如初始化參數選擇問題、收斂速度問題等，這些均帶有經驗性和直覺性，至今沒有經過嚴格的數學論證。今后人工魚群算法的收斂性證明和理論分析仍然是一個非常具有挑戰性的研究方向。

（2）人工魚群算法的改進研究。人工魚群算法因處于初步階段，因此，其算法的改進仍是目前研究的一大重要方向。根據目前的研究可知，對人工魚群算法在初始化、參數與其他方法的結合和群體多樣化方面的改進仍需積極探索與完善。特別是研究人工魚群算法與其他智能算法和的融合技術，能夠提高算法優化性能，因此，研究人工魚群算法與模擬退火算法、遺傳算法、粒子群算法、蟻群算法等智能優化算法的融合技術，對智能算法的研究具有重要意義。

3 結束語

本文對智能計算的一種算法——人工魚群算法進行了系統的介紹，并將它應用到路由優化中。對網絡管理中的過程進行動態路由選擇，提供了新的方法，同時對算法的性能進行了評價。

[1] 李曉磊．一種新型的智能優化方法-人工魚群算法[D]．杭州:浙江大學，2003

[2] 丁建立，陳增強，袁著祉．智能仿生算法及其網絡優化中的應用研究進展[J]．計算機工程與應用；2003.12

[3] 單曉娟．智能計算及其在網絡優化中的應用[D]．山東大學，2007

[4] 王聯國，洪毅，趙付青．一種改進的人工魚群算法[J]．計算機工程，2008, 34 (19) :192-19

10.3969/J.ISSN.1672-7274.2017.09.006

TN915文獻標示碼：B

1672-7274（2017）09-0015-02