探討人工魚群算法的結構和原理

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

關鍵詞:人工魚群;算法最優解;收斂性

中圖分類號:TP311文獻標識碼: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

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

1 人工魚群算法的結構剖析

魚類的活動中，覓食行為和追尾行為等相關行為與尋優命題的解決有著較密切的關系，如何利用簡便有效的方式來構造并實現這些行為將是人工魚群算法實施的主要問題。

1.1 基本定義

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

1.2 覓食行為

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

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

1.3 追尾行為

設人工魚當前位置為Xj ，在其視野范圍內尋找目標函數值最優的伙伴xi ，如果該伙伴所處的位置具有較高的食物濃度，且不太擁擠，則人工魚從當前位置向該伙伴移動，否則執行覓食行為[2]。

1.4 最優解的獲取

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

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

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

2.1 算法思想

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

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

Step2:分別計算各人工魚狀態的食物濃度，選擇最大食物濃度的人工魚個體狀態記錄到公告板內;

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

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

2.2 仿真實例

本文研究的仿真函數如下:

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

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

然后再用人工魚群算法對函數進行3O次優化，每次優化均迭代100次，得到3O個最優函數值的平均值及其與函數實際最優值之間的平均誤差和標準差，結果見表2。

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

……

// 第一步:

M=length(LB);//決策變量的個數

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

for i=1:M

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

X(i，:)=x;

end

//輸出變量初始化

//細胞結構，每一個元素是M×N矩陣，記錄每一代的個體

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

ALLY=zeros(K，N); //細胞結構，每一個元素是M×1向量，記錄每一代的最優個體

BESTX=cell(K，1); //K×1矩陣，記錄每一代的最優個體的評價函數值

BESTY=zeros(K，1);

k=1;//迭代計數器初始化

// 第二步:迭代過程

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 算法收斂性

對于一種算法，其收斂性往往是人們所首要關心的問題。在人工魚群算法中，人工魚的覓食行為奠定了算法收斂的基礎，聚群行為增強了算法收斂的穩定性和全局性，追尾行為則增強了算法收斂的快速性和全局性，其行為評價也對算法收斂的速度和穩定性提供了保障。總的來說，算法中對各參數的取值范圍還是很寬容的，并且對算法的初值也基本無要求。算法中，使人工魚逃逸局部極值實現全局尋優的因素主要有以下幾點:

1) 覓食行為中抑number的次數較少時，為人工魚提供了隨機游動的機會，從而能跳出局部極值的鄰域。

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

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

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

3 小結

總之，人工魚群算法是一種新型的思路，從具體的實施算法到總體的設計理念，都不同于傳統的設計和解決方法，但同時它又能與傳統方法相融合，因此，從具體的數學問題到更高層次的管理調度等問題，具有良好的應用前景。

參考文獻:

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

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