探討人工魚群算法的結(jié)構(gòu)和原理

摘要:人工魚群算法是一種基于模擬魚群行為的優(yōu)化算法。該文首先分析了人工魚群算法的定義、覓食以及追尾行為，其次剖析了最優(yōu)解的獲取，并進(jìn)一步探討了算法原理及其收斂性。

關(guān)鍵詞:人工魚群;算法最優(yōu)解;收斂性

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)36-10235-03

The Structure and Principle of Artificial Fish-Swarm Algorithm

LI Bin

(Guangdong Institute of Science and Technology Guangdong， Zhuhai 519075， China)

Abstract: Artificial fish-swarm algorithm is a kind of fish behavior simulation-based optimization algorithm. This paper firstly has analyzed the definition of artificial fish-swarm algorithm， foraging， as well as rear-end behavior， followed by analysis of the optimal solution of the acquisition. Then the paper has explored the theory and convergence of the algorithm.

Key words: artificial fish; optimal solution of algorithm; convergence

人工魚群算法是一種基于動(dòng)物行為的尋求全局最優(yōu)的新思路，是行為主義人工智能的一個(gè)典型應(yīng)用。算法利用了魚的覓食、聚群和追尾行為，從構(gòu)造單條魚的簡單底層行為做起，通過魚群中各個(gè)體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來。該算法具有良好的克服局部極值、取得全局極值的能力，并且算法的實(shí)現(xiàn)無需目標(biāo)函數(shù)的梯度值等特性，故其對搜索空間具有一定的自適應(yīng)能力。本文就是針對人工魚群算法，研究其結(jié)構(gòu)及原理。

1 人工魚群算法的結(jié)構(gòu)剖析

魚類的活動(dòng)中，覓食行為和追尾行為等相關(guān)行為與尋優(yōu)命題的解決有著較密切的關(guān)系，如何利用簡便有效的方式來構(gòu)造并實(shí)現(xiàn)這些行為將是人工魚群算法實(shí)施的主要問題。

1.1 基本定義

人工魚個(gè)體的狀態(tài)可表示為向量X=(x1，x2…，xn)，其中 Xi(i=1，…，n)為欲尋優(yōu)的變量;人工魚當(dāng)前所在位置的食物濃度表示為Y=f(x)，其中Y為目標(biāo)函數(shù)值;人工魚個(gè)體之間的距離表示為dij=‖Xi-Xj‖ ;Visual表示人工魚的感知距離;step表示人工魚移動(dòng)的最大步長;δ表示擁擠度因子[1]。

1.2 覓食行為

人工魚的覓食行為的基本流程如圖1所示。

人工魚在當(dāng)前位置Xj 的鄰域中遍歷每一個(gè)鄰居，找到其中食物濃度最高(在進(jìn)行極大值尋優(yōu)時(shí)為最高，進(jìn)行極小值尋優(yōu)時(shí)為最低，在本節(jié)中以極大值尋優(yōu)為例)的鄰居，并判斷該鄰居是否在禁忌表中，如果不在禁忌表中，則將該網(wǎng)格點(diǎn)插入禁忌表，人工魚移動(dòng)到該網(wǎng)格點(diǎn)，并將該點(diǎn)的食物濃度與公告板信息進(jìn)行比較，如果優(yōu)于公告板，則更新公告板狀態(tài);如果Xi在禁忌表中，則判斷是否滿足藐視準(zhǔn)則，如果不滿足藐視準(zhǔn)則，則重新初始化當(dāng)前的人工魚，以便在更廣闊的范圍內(nèi)進(jìn)行尋優(yōu)，相當(dāng)于在同樣的存儲(chǔ)空間中增加了進(jìn)行尋優(yōu)的人工魚個(gè)數(shù)。

1.3 追尾行為

設(shè)人工魚當(dāng)前位置為Xj ，在其視野范圍內(nèi)尋找目標(biāo)函數(shù)值最優(yōu)的伙伴xi ，如果該伙伴所處的位置具有較高的食物濃度，且不太擁擠，則人工魚從當(dāng)前位置向該伙伴移動(dòng)，否則執(zhí)行覓食行為[2]。

1.4 最優(yōu)解的獲取

基本魚群算法獲取的僅僅是系統(tǒng)的滿意解域，無法獲取精確或較精確的最優(yōu)解。通過基于網(wǎng)格劃分策略的引入，可以有效的解決最優(yōu)解的獲取問題。由于在改進(jìn)算法中使用了禁忌搜索算法，在尋優(yōu)的過程中減少了大量無用的計(jì)算，提高了尋優(yōu)的速度，強(qiáng)制不滿足藐視準(zhǔn)則的人工魚進(jìn)行初始化，能夠在系統(tǒng)的解空間上進(jìn)行更加全面的搜索，同時(shí)充分利用了魚群的公告板信息，在搜索過程中，如果公告板信息維持一定的次數(shù)沒有更新，則可認(rèn)為公告板的信息存在于系統(tǒng)的滿意解域中。如果公告板歷史最優(yōu)解xi 相鄰的兩個(gè)對稱網(wǎng)格點(diǎn)xi 和xi-1 到xj 的坡度相等，則xi 即為系統(tǒng)的精確最優(yōu)解;如果坡度不相等，則令:

即以其鄰居確定的變量向量取值范圍重新進(jìn)行網(wǎng)格劃分，直到max(gridLengthi)<(i=1，2，…，n)，這樣就可以獲取系統(tǒng)的精確或較精確的最優(yōu)解。

2 人工魚群算法的原理描述

2.1 算法思想

鑒于以上描述的人工魚行為，每個(gè)人工魚探索它當(dāng)前所處的環(huán)境狀況和伙伴的狀況，其實(shí)伙伴的狀況相對于其自身應(yīng)該也是歸屬于環(huán)境的狀況，從而選擇一種行為，最終，人工魚集結(jié)在幾個(gè)局部極直的周圍。根據(jù)所要解決的問題性質(zhì)，對人工魚當(dāng)前所處的環(huán)境進(jìn)行評價(jià)，從而選擇一種行為。人工魚首先模擬執(zhí)行聚群、追尾行為，然后評價(jià)行動(dòng)后的值，選擇其中最大者來實(shí)際執(zhí)行，缺省行為方式為覓食行為。人工魚群算法的算法思想描述如下:

Stepl:若所要解決的問題的搜索域比較大，則“縮小”搜索域，然后在搜索域內(nèi)隨機(jī)產(chǎn)生N個(gè)人工魚個(gè)體，若所要解決的問題的搜索域不大，則直接在搜索域內(nèi)隨機(jī)的產(chǎn)生N個(gè)人工魚個(gè)體，組成初始群體;

Step2:分別計(jì)算各人工魚狀態(tài)的食物濃度，選擇最大食物濃度的人工魚個(gè)體狀態(tài)記錄到公告板內(nèi);

Step3:各人工魚分別模擬改進(jìn)聚群行為和追尾行為，缺省行為為覓食行為，然后選擇最優(yōu)的行為作為實(shí)際執(zhí)行行為，并與公告板記錄進(jìn)行比較，若優(yōu)于公告板記錄，則以自身替換公告板記錄;

Step4:判斷是否滿足終止條件，若滿足，則輸出公告板記錄，算法終止;若不滿足，則執(zhí)行Step3。

2.2 仿真實(shí)例

本文研究的仿真函數(shù)如下:

該函數(shù)有無窮多個(gè)極值點(diǎn)，但只有一個(gè)(0，0)為全局最小點(diǎn)，函數(shù)值為0。該函數(shù)的特點(diǎn)是在其最小值點(diǎn)附近存在一個(gè)圈谷，其取值為0.009716，從而，在優(yōu)化中非常容易陷入局部極值陷阱，一般優(yōu)化方法對此函數(shù)很難奏效。因此，該函數(shù)已成為測試進(jìn)化算法效能的一個(gè)標(biāo)準(zhǔn)函數(shù)，很多研究中被采用。

本文分別采用人工魚群算法對該函數(shù)進(jìn)行優(yōu)化，對結(jié)果進(jìn)行比較。取不同的隨機(jī)初始群體對函數(shù)進(jìn)行3O次優(yōu)化，在給定世代內(nèi)，若群體中的最優(yōu)個(gè)體的函數(shù)值達(dá)到給定的閾值，認(rèn)為算法成功收斂。其中算法中的參數(shù)取最大迭代次數(shù)為200，閾值為0.001，算法中的參數(shù)N=100，Trynumber=30，δ=0.618，對于人工魚群算法取最優(yōu)參數(shù)Visual=10，Step=0.8，計(jì)算結(jié)果如表1。

然后再用人工魚群算法對函數(shù)進(jìn)行3O次優(yōu)化，每次優(yōu)化均迭代100次，得到3O個(gè)最優(yōu)函數(shù)值的平均值及其與函數(shù)實(shí)際最優(yōu)值之間的平均誤差和標(biāo)準(zhǔn)差，結(jié)果見表2。

下面給出的部分程序算法描述所示。通常，由AFiulot來初始化AF為隨機(jī)分布在變量域內(nèi);算法的終止條件可以根據(jù)實(shí)際情況設(shè)定，如通常的方法是判斷連續(xù)多次所得值的均方差小于預(yù)期的誤差。

……

// 第一步:

M=length(LB);//決策變量的個(gè)數(shù)

X=zeros(M，N); //蟻群位置初始化

for i=1:M

x=unifrnd(LB(i)，UB(i)，1，N);

X(i，:)=x;

end

//輸出變量初始化

//細(xì)胞結(jié)構(gòu)，每一個(gè)元素是M×N矩陣，記錄每一代的個(gè)體

ALLX=cell(K，1); //K×N矩陣，記錄每一代評價(jià)函數(shù)值

ALLY=zeros(K，N); //細(xì)胞結(jié)構(gòu)，每一個(gè)元素是M×1向量，記錄每一代的最優(yōu)個(gè)體

BESTX=cell(K，1); //K×1矩陣，記錄每一代的最優(yōu)個(gè)體的評價(jià)函數(shù)值

BESTY=zeros(K，1);

k=1;//迭代計(jì)數(shù)器初始化

// 第二步:迭代過程

while k<=K

NewX=zeros(M，N); NewY=zeros(1，N);

for n=1:N

x=X(:，n);

Xnb=AFneighbour(n，X，V);

NN=size(Xnb，2);

if NN==0

xx=AFprey(x，V，L，LB，UB);

elseif NN>=3

xx=AFswarm(x，Xnb，N，Delta，V，L，LB，UB);

else

xx=AFprey(x，V，L，LB，UB);

end

NewX(:，n)=xx;

end

for n=1:N

NewY(n)=FIT(NewX(:，n));

end

X=NewX; Y=NewY; ALLX{k}=X; ALLY(k，:)=Y; minY=min(Y); pos=find(Y==minY);

BESTX{k}=X(:，pos(1)); BESTY(k)=minY; disp(k); k=k+1;

end

……//繪圖

2.3 算法收斂性

對于一種算法，其收斂性往往是人們所首要關(guān)心的問題。在人工魚群算法中，人工魚的覓食行為奠定了算法收斂的基礎(chǔ)，聚群行為增強(qiáng)了算法收斂的穩(wěn)定性和全局性，追尾行為則增強(qiáng)了算法收斂的快速性和全局性，其行為評價(jià)也對算法收斂的速度和穩(wěn)定性提供了保障?？偟膩碚f，算法中對各參數(shù)的取值范圍還是很寬容的，并且對算法的初值也基本無要求。算法中，使人工魚逃逸局部極值實(shí)現(xiàn)全局尋優(yōu)的因素主要有以下幾點(diǎn):

1) 覓食行為中抑number的次數(shù)較少時(shí)，為人工魚提供了隨機(jī)游動(dòng)的機(jī)會(huì)，從而能跳出局部極值的鄰域。

2) 隨機(jī)步長的采用，使得在前往局部極值的途中，有可能轉(zhuǎn)而游向全局極值，當(dāng)然，其相反的一面也會(huì)發(fā)生的，就是在去往全局極值的途中，可能轉(zhuǎn)而游向局部極值，這對一個(gè)個(gè)體當(dāng)然不好判定他的禍福，但對于一個(gè)群體來說，好的一面往往會(huì)具有更大的機(jī)率。

3) 擁擠度因子的引入限制了聚群的規(guī)模，只有較優(yōu)的地方才能聚集更多的人工魚，使得人工魚能夠更廣泛的尋優(yōu)。

4) 聚群行為能夠促使少數(shù)陷于局部極值的人工魚向多數(shù)趨向全局極值的人工魚方向聚集，從而逃離局部極值;令追尾行為加快了人工魚向更優(yōu)狀態(tài)的游動(dòng)，同時(shí)也能促使陷于局部極值的人工魚向趨向全局極值的更優(yōu)人工魚方向的追隨而逃離局部極值域。

3 小結(jié)

總之，人工魚群算法是一種新型的思路，從具體的實(shí)施算法到總體的設(shè)計(jì)理念，都不同于傳統(tǒng)的設(shè)計(jì)和解決方法，但同時(shí)它又能與傳統(tǒng)方法相融合，因此，從具體的數(shù)學(xué)問題到更高層次的管理調(diào)度等問題，具有良好的應(yīng)用前景。

參考文獻(xiàn):

[1] 曲良東，何登旭.基于單純形法的雙群人工魚群算法[J]，計(jì)算機(jī)應(yīng)用，2008(8).

[2] 胡孟杰.TSP問題的人工魚群解決方案[J].中國科技信息，2009(11).