胡振，楊華

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

胡振，楊華

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

人工魚群算法；柯西變異；非線性規(guī)劃；標準函數(shù)

0 引言

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

1 基本人工魚群算法

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

1.1 算法描述

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

（1）隨機行為

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

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

（2）覓食行為

人工魚循著食物多的方向游動的一種行為。Xi在其視野內(nèi)隨機選擇一個狀態(tài)Xj，分別計算其目標函數(shù)值Yi、Yj并進行比較，若Yj比Yi優(yōu)，則Xi向Xj方向移動一步；否則，Xi繼續(xù)在其視野范圍內(nèi)隨機移動、選擇狀態(tài)Xj，判斷是否滿足前進條件…，反復(fù)嘗試trynumber次之后，若仍未滿足前進條件，則執(zhí)行隨機行為?？捎煤瘮?shù)表示如公式（2）：

（3）聚群行為

人工魚在游動過程中盡量向臨近伙伴的中心移動并避免過分擁擠的一種尋優(yōu)行為。Xi搜索其視野內(nèi)的伙伴數(shù)目nf及中心位置Xc，若Xc較優(yōu)且不太擁擠，則Xi向Xc移動一步，否則執(zhí)行覓食行為?？杀硎緸槿缦潞瘮?shù)如公式（3）：

（4）追尾行為

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

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

1.2 問題的解決

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

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

另一種形式則在人工魚個體狀態(tài)中表現(xiàn)出來，即在尋優(yōu)過程中，跟蹤記錄最優(yōu)個體的狀態(tài)。

2 人工魚群算法的改進

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

2.1 現(xiàn)有的改進方案

2.1.1 對AFSA本身的改進

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

2.1.2 AFSA與其他方法的融合

AFSA與其他技術(shù)、方法融合即構(gòu)成混合優(yōu)化算法，已經(jīng)提出的融合方案有：AFSA與模擬退火算法，AFSA與小生境技術(shù)，AFSA與禁忌搜索算法，AFSA與遺傳算法，……等等。

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

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

2.2.1 在AFSA中引入Cauchy變異算子

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

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

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

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

AFSA經(jīng)過如此改進后，可稱之為C-AFSA。

2.2.2 將非線性規(guī)劃函數(shù)融入算法

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

非線性規(guī)劃

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

（2）C-AFSA中融入非線性規(guī)劃函數(shù)

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

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

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

fmincon()函數(shù)的調(diào)用格式為：

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

將非線性規(guī)劃函數(shù)嵌入C-AFSA中即構(gòu)成CN-AFSA：令C-AFSA每迭代10次即執(zhí)行1次非線性規(guī)劃，調(diào)用時將人工魚的當(dāng)前狀態(tài)傳遞給fmincon()函數(shù)的參數(shù)x0，以此為初設(shè)值進行局部搜索，從而提高算法的精度和速度。

2.2.3 CN-AFSA的執(zhí)行流程

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

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

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

Step 4 若當(dāng)前迭代次數(shù)為10的倍數(shù)，則調(diào)用非線性規(guī)劃函數(shù)。

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

Step 6 算法終止，輸出最優(yōu)解。

3 算法測試

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

3.1 標準函數(shù)選擇

（1）Schaffer F6

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

（2）Rastrigin

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

（3）Griewank

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

3.2 測試結(jié)果分析

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

表1 標準函數(shù)測試結(jié)果

圖1 Griewank函數(shù)尋優(yōu)的迭代過程

另兩個函數(shù)的迭代過程與之相似。

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

4 總結(jié)

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

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

（2）可應(yīng)用于其它群體智能優(yōu)化算法，如粒子群優(yōu)化算法、蟻群算法、量子粒子群優(yōu)化算法等。

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

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

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

[4] 趙遠東,方正華.帶有權(quán)重函數(shù)學(xué)習(xí)因子的粒子群算法[J].計算機應(yīng)用,2013,33(8):2265-2268.

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

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

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

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

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

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

TP301.6 文獻標志碼：A

2014.12.29）

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

四川高等職業(yè)教育研究中心立項課題（GZY14C42；南充市應(yīng)用技術(shù)研究與開發(fā)資金項目（14A0079）

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