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

紀(jì) 喆

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

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

紀(jì) 喆

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

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

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

1 引言

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

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

2.1 人工魚(yú)群算法的基本概念

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

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

（1）覓食行為：這是魚(yú)趨向食物的一種活動(dòng)，一般認(rèn)為它是通過(guò)視覺(jué)或味覺(jué)來(lái)感知水中的食物兩或食物濃度來(lái)選擇行動(dòng)的方向。

（2）聚群行為：大量或少量的魚(yú)聚集成群，進(jìn)行集體覓食和躲避敵害，這是它們?cè)谶M(jìn)化過(guò)程中形成的一種生存方式。

（3）追尾行為：當(dāng)某一條魚(yú)或幾條魚(yú)發(fā)現(xiàn)食物時(shí)，它們附近的魚(yú)會(huì)尾隨而來(lái)，導(dǎo)致更遠(yuǎn)處的魚(yú)也會(huì)尾隨過(guò)來(lái)。

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

2.2 人工魚(yú)群算法的行為描述

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

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

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

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

2.3 人工魚(yú)群算法步驟

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

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

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

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

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

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

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

2.4.1 禁忌表和藐視準(zhǔn)則

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

2.4.2 禁忌計(jì)算

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

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

2.4.3 仿真實(shí)現(xiàn)與性能評(píng)價(jià)

基于NS2平臺(tái)進(jìn)行了仿真實(shí)現(xiàn)，在多個(gè)實(shí)際與虛擬的網(wǎng)絡(luò)拓?fù)渖蠈?duì)本文所描述的算法；基于粒子群和遺傳算法的QoS組播路由算法和基于遺傳算法的QoS組播路由算法，進(jìn)行仿真實(shí)驗(yàn)與性能評(píng)價(jià)。

2.4.4 滿(mǎn)足用戶(hù)QoS約束的概率的比較

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

2.5 進(jìn)一步的研究工作

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

10.3969/J.ISSN.1672-7274.2017.09.006

TN915文獻(xiàn)標(biāo)示碼：B

1672-7274（2017）09-0015-02