基于MATLAB的人工魚群混合改進算法

胡振，楊華

基于MATLAB的人工魚群混合改進算法

胡振，楊華

針對群體智能優化算法普遍存在的容易早熟、收斂較慢等缺陷，提出了一種人工魚群混合改進算法。在算法中對人工魚的狀態施加Cauchy變異算子，以增強魚群的全局搜索能力；同時融入非線性規劃函數，使其局部搜索能力也得到改善。用MATLAB編程實現該算法，并用3個標準函數進行測試，結果表明其精度與收斂速度皆比基本人工魚群算法有顯著提高。

人工魚群算法；柯西變異；非線性規劃；標準函數

0 引言

群體智能優化算法廣泛應用于機器學習、信號處理、模式識別、組合優化、控制系統設計等領域，包括遺傳算法、粒子群算法、蟻群算法、人工蜂群算法、人工魚群算法等，它們雖然在智能計算中顯示了無與倫比的優越性，但也共同存在著明顯缺陷：其一為容易陷入局部最優，從而引發“早熟”現象；其二是搜索效率低，使得收斂速度較慢。研究者們對此提出的改進方案主要有兩種思路：一是對算法本身進行改進，如在遺傳算法中改進編碼方法、自適應算子概率、引入精英策略[1-2]，粒子群優化算法中自適應控制最優位置、慣性權重和學習因子的動態調整[3-4]，蟻群算法中信息素更新方式與信息素揮發因子的自適應改進[5-6]等；二是在算法中融入其它方法構成混合算法，如蟻群算法中引入粗糙集[7]、粒子群優化算法與共軛梯度法結合[8]、量子行為粒子群優化算法中嵌入非線性規劃[9]等。本文以人工魚群算法為研究對象，綜合應用上述兩種思路對其進行改進，得到一種融入Cauchy變異算子和非線性規劃函數的人工魚群混合改進算法。

1 基本人工魚群算法

人工魚群算法[10](Artificial Fish Swarm Algorithm，AFSA)是根據魚類活動特點提出的一種基于動物行為的自治體尋優方法，具有良好的求取全局極值的能力，且對初值和參數選擇不敏感，簡單、易實現、魯棒性強、可并行處理。

1.1 算法描述

AFSA初始化一個人工魚群，通過迭代搜尋最優解。在每次迭代過程中，人工魚通過下列行為更新自身狀態：

（1）隨機行為

人工魚隨機移動的行為。Xi在視野范圍內隨機選擇一個狀態，然后向該方向移動一步。該行為可用如下函數如公式（1）：

式(1)中：rand()為[0,1]區間的隨機數。

（2）覓食行為

人工魚循著食物多的方向游動的一種行為。Xi在其視野內隨機選擇一個狀態Xj，分別計算其目標函數值Yi、Yj并進行比較，若Yj比Yi優，則Xi向Xj方向移動一步；否則，Xi繼續在其視野范圍內隨機移動、選擇狀態Xj，判斷是否滿足前進條件…，反復嘗試trynumber次之后，若仍未滿足前進條件，則執行隨機行為。可用函數表示如公式（2）：

（3）聚群行為

人工魚在游動過程中盡量向臨近伙伴的中心移動并避免過分擁擠的一種尋優行為。Xi搜索其視野內的伙伴數目nf及中心位置Xc，若Xc較優且不太擁擠，則Xi向Xc移動一步，否則執行覓食行為。可表示為如下函數如公式（3）：

（4）追尾行為

人工魚向視野范圍內的最優方向移動的一種行為。Xi搜索其視野內的最優伙伴Xo，若Xo的周圍不太擁擠，則Xi向Xo移動一步，否則執行覓食行為。其函數表示如公式（4）：

式（1）~（4）描述的是求最小值問題（最大值問題可轉換為最小值問題）。實際應用時，根據所要解決問題的性質，人工魚對當前所處環境進行評價，即模擬聚群、追尾等行為，從中選擇行動后食物濃度最小者實際執行，缺省為覓食行為。

1.2 問題的解決

問題的解決是通過自治體在自主活動過程中以某種形式表現出來的。在尋優過程中，通常會有兩種形式：

一種形式是通過人工魚的最終分布情況來確定最優解的分布。通常隨著尋優過程的進行，人工魚往往會聚集在極值點的周圍，而且全局最優的極值點周圍通常能聚集較多的人工魚；

另一種形式則在人工魚個體狀態中表現出來，即在尋優過程中，跟蹤記錄最優個體的狀態。

2 人工魚群算法的改進

AFSA的不足之處主要有：（1）算法獲取的是滿意解域，對于精確解的獲取還需進行適當改進；（2）若尋優的域較大或處于平坦區域，則部分人工魚會處于無目的隨機移動狀態，這將影響尋優效率，容易陷入局部最優；（3）算法的參數較多，且取固定值，致其收斂速度在初期較快、后期則往往減慢。

2.1 現有的改進方案

2.1.1 對AFSA本身的改進

大多數改進措施都著眼于AFSA內部，如：在算法中引入生存機制和競爭機制，使用公告板，加入變異算子，動態調整視野、步長和擁擠度因子，運用分區域搜索、深度優先遍歷技術，采取分階段、變參數尋優策略，……，等等。具體改進方案多為其中數項措施的組合。

2.1.2 AFSA與其他方法的融合

AFSA與其他技術、方法融合即構成混合優化算法，已經提出的融合方案有：AFSA與模擬退火算法，AFSA與小生境技術，AFSA與禁忌搜索算法，AFSA與遺傳算法，……等等。

2.2 基于MATLAB的人工魚群混合改進算法

本文針對AFSA的缺陷，提出一種基于MATLAB的混合改進算法。其主要思路為：（1）在AFSA中引入Cauchy變異算子，增強其全局尋優能力；（2）在此基礎上融入非線性規劃函數，提高算法的局部搜索效率，加快其收斂速度。通過這兩種措施的綜合作用，顯著改善算法的計算精度和尋優速度。

2.2.1 在AFSA中引入Cauchy變異算子

Cauchy分布具有兩翼較長的概率特性，它比Gaussian分布的范圍更寬，很容易產生遠離原點的隨機數。因此，在AFSA的迭代過程中，當人工魚選擇執行某種行為后，對其當前狀態增加Cauchy分布隨機數擾動項作為變異算子，可保持人工魚群的多樣性，減少其陷入局部最優的可能性，從而增強算法的全局搜索能力，防止發生早熟現象。相應的改進公式為公式（5）：

公式（5）中： π(tan( -0))5. *rand()可得標準Cauchy分布隨機數，其中rand()為[0,1]區間的均勻分布隨機數；Xi為人工魚的當前狀態。

需要注意的是，這種改進策略可能導致人工魚超出優化變量取值范圍的幾率增加，故應隨之進行粒子越界處理。

設增加Cauchy變異算子后的人工魚狀態為Xi，優化變量取值范圍為[rl,rr]，則越界處理為公式（6）：

AFSA經過如此改進后，可稱之為C-AFSA。

2.2.2 將非線性規劃函數融入算法

C-AFSA的全局搜索性能有了顯著增強，但其局部搜索能力尚待改善。為此，我們再在C-AFSA中融入非線性規劃函數，構成一種混合改進算法，稱之為CN-AFSA。

非線性規劃

（1）非線性規劃（Nonlinear Programming）研究n元實函數在一組等式或不等式約束條件下的極值問題，且目標函數和約束條件至少有一個是未知量的非線性函數。其一般形式為公式（7）：

（2）C-AFSA中融入非線性規劃函數

求解非線性規劃問題的經典算法皆以梯度下降法為基礎，其特點是局部搜索能力較強。因此，將C-AFSA與非線性規劃結合，可增強算法的搜索能力，提高計算精度，并加快收斂速度。

Matlab提供了求解非線性規劃問題的函數fmincon()，可從一個預估值開始搜索約束條件下多元非線性函數的最小值。其約束條件如下：

其中：x為變量，A、b為線性不等約束，Aeq、beq為線性相等約束；c、ceq分別為非線性不等約束和非線性相等約束；lb、ub分別為x的下界與上界。x、b、beq、lb和ub是向量，A和Aeq為矩陣，f(x)、c(x)和ceq(x)為非線性函數。

fmincon()函數的調用格式為：

式（7）中：fun為目標函數，x0為x的初設值，lb、ub為x的下界和上界，其余參數則可缺省。

將非線性規劃函數嵌入C-AFSA中即構成CN-AFSA：令C-AFSA每迭代10次即執行1次非線性規劃，調用時將人工魚的當前狀態傳遞給fmincon()函數的參數x0，以此為初設值進行局部搜索，從而提高算法的精度和速度。

2.2.3 CN-AFSA的執行流程

Step 1 在目標搜索空間初始化人工魚群。

Step 2 各人工魚分別模擬追尾行為和聚群行為，選擇目標函數值較優的行為實際執行，缺省行為方式為覓食行為。

Step 3 對人工魚的狀態按式(5)實施變異，并進行越界處理。

Step 4 若當前迭代次數為10的倍數，則調用非線性規劃函數。

Step 5 如果尚未滿足終止條件（達到最大迭代次數或預定的誤差范圍），則重復執行Step 2~4；否則執行Step 6。

Step 6 算法終止，輸出最優解。

3 算法測試

我們在Windows XP系統環境中用MATLAB編程實現了本文提出的人工魚群混合改進算法，選用3個有代表性的標準函數測試其有效性，并在相同條件下用AFSA和C-AFSA進行對比測試，以分析基本人工魚群算法與改進算法在優化精度、收斂速度和魯棒性等方面的差異。

3.1 標準函數選擇

（1）Schaffer F6

具有強烈振蕩的二維多峰函數，最小值附近有無數局部極小點，在(0,0)處有最小值0。

（2）Rastrigin

高維多峰函數，有很多局部極小點，在(0,0,…,0)處有最小值0。

（3）Griewank

非線性多模態函數，有許多局部極小點，數目與問題的維數有關，在(0,0,…,0)處有最小值0。

3.2 測試結果分析

用3個標準函數對AFSA及其改進算法進行測試時，運行參數都設置為：人工魚群群規模50，最大迭代次數100；覓食時最多試探次數30，視野、步長和擁擠度因子分別為1、0.1和0.618。以函數值小于10-5為優化目標，分別獨立運行50次，所得結果如表1所示：

表1 標準函數測試結果

圖1 Griewank函數尋優的迭代過程

另兩個函數的迭代過程與之相似。

表1的結果表明：當人工魚群規模不大、迭代次數較少時，AFSA不能收斂到預設的優化目標值，且其尋優結果與理論值相差甚遠；C-AFSA則顯著改善了尋優效果，3個標準函數都能部分達到預設的優化目標；CN-AFSA進一步提高了計算精度，不僅其尋優結果已非常接近理論最小值，且其穩定性更好，收斂速度大為加快。

4 總結

本文提出了人工魚群算法的一種混合改進方案，在基本人工魚群算法中引入了Cauchy變異算子，并進而融入MATLAB的非線性規劃函數，所得改進算法的優化精度、收斂速度和魯棒性都有顯著提高。與現有的其它改進算法相比，本文算法簡單、容易實現，復雜度無明顯增加，能保持較高的運行效率。而且，本文對人工魚群算法的改進思想可從兩方面加以推廣：

（1）在算法中采用Gauss變異算子來代替Cauchy變異算子，同樣可達到增加人工魚群的多樣性，進而增強其全局尋優能力的目的。

（2）可應用于其它群體智能優化算法，如粒子群優化算法、蟻群算法、量子粒子群優化算法等。

[1] 劉懷蘭,牛輝,王佳.基于改進遺傳算法的智能組卷模型優化[J].華中科技大學學報(自然科學版),2013,41(5):82-85.

[2] 馬登武,郭小威,呂曉峰.基于改進遺傳算法的艦載機彈藥調度[J].計算機工程與應用,2012,48(8):246-248.

[3] 郜振華,梅莉,祝遠鑒.復合策略慣性權重的粒子群優化算法[J].計算機應用,2012,32(8):2216-2218.

[4] 趙遠東,方正華.帶有權重函數學習因子的粒子群算法[J].計算機應用,2013,33(8):2265-2268.

[5] 陳明杰,黃佰川,張旻.混合改進蟻群算法的函數優化[J].智能系統學報,2012,7(4):370-376.

[6] 高芳,韓璞,翟永杰.基于變異操作的蟻群算法用于連續函數優化[J].計算機工程與應用,2011,47(4):5-8.

[7] 盧宇凡,張莉.基于粗糙集和蟻群算法的機器人路徑規劃研究[J].計算機與數字工程,2012,40(12):7-9.

[8] 王儉臣,齊曉慧,單甘霖.基于進食粒子群和共軛梯度的混合優化策略[J].計算機應用,2013,33(8):2257-2260.

[9] 胡振.QPSO混合算法在 PID控制器優化中的應用[J].計算機系統應用,2014,23(10):233-238.

[10] 李曉磊,邵之江,錢積新.一種基于動物自治體的尋優模式:魚群算法[J].系統工程理論與實踐,2002,22(11):32-38.

TP301.6 文獻標志碼：A

2014.12.29）

1007-757X(2015)08-0028-03

四川高等職業教育研究中心立項課題（GZY14C42；南充市應用技術研究與開發資金項目（14A0079）

胡 振（1967-），男，漢，四川岳池人，南充職業技術學院，信息與管理工程系，副教授，研究方向：智能算法應用、微機系統運維技術，南充，637000