紀 喆

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

智能計算在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用

紀 喆

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

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

智能優(yōu)化算法；最優(yōu)化技術(shù)；人工魚群算法

1 引言

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

2 基于改進的人工魚群算法的路由優(yōu)化

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

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

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

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

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

（3）追尾行為：當某一條魚或幾條魚發(fā)現(xiàn)食物時，它們附近的魚會尾隨而來，導(dǎo)致更遠處的魚也會尾隨過來。

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

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

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

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

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

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

2.3 人工魚群算法步驟

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

⊙ 在參數(shù)區(qū)間內(nèi)隨機生成m條人工魚個體作為初始魚群。

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

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

⊙ 判斷是否滿足結(jié)束條件，如果滿足結(jié)束，否則轉(zhuǎn)上一步。

最終公告板中的值就是最優(yōu)值。

2.4 基于人工魚群算法的路由優(yōu)化

2.4.1 禁忌表和藐視準則

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

2.4.2 禁忌計算

設(shè)人工魚Xi和Xj，新的人工魚的產(chǎn)生按如下禁忌計算方法進行：

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

2.4.3 仿真實現(xiàn)與性能評價

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

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

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

2.5 進一步的研究工作

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

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

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

3 結(jié)束語

本文對智能計算的一種算法——人工魚群算法進行了系統(tǒng)的介紹，并將它應(yīng)用到路由優(yōu)化中。對網(wǎng)絡(luò)管理中的過程進行動態(tài)路由選擇，提供了新的方法，同時對算法的性能進行了評價。

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

[2] 丁建立，陳增強，袁著祉．智能仿生算法及其網(wǎng)絡(luò)優(yōu)化中的應(yīng)用研究進展[J]．計算機工程與應(yīng)用；2003.12

[3] 單曉娟．智能計算及其在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用[D]．山東大學，2007

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

10.3969/J.ISSN.1672-7274.2017.09.006

TN915文獻標示碼：B

1672-7274（2017）09-0015-02