一種基于粒子群和魚群的混合優(yōu)化算法

李玉毛，于志遠

（1.赤峰學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，內(nèi)蒙古 赤峰 024000；2.赤峰學(xué)院 附屬醫(yī)院，內(nèi)蒙古 赤峰 024000）

1 引言

從二十世紀九十年代就產(chǎn)生了通過模擬生物群體行為來解決優(yōu)化問題的演化計算技術(shù)，稱為群體智能[1].在1995年，美國學(xué)者Kennedy和Eberhart提出了粒子群優(yōu)化算法(Particle Swarm Optimization)，就是通過對鳥群的某些行為的觀察研究，提出的一種新穎而有效的進化算法[2].李曉磊等在2002年提出的人工魚群算法(Artificial Fish)則是通過模擬人工魚的覓食行為來處理優(yōu)化問題.但兩個算法都存在不足，鑒于二者的關(guān)系，結(jié)合二者的優(yōu)點，提出了一種混合優(yōu)化算法，可有效地提高算法的尋優(yōu)能力.

2 關(guān)于粒子群算法和人工魚群算法的基本原理及其存在的問題

2.1 粒子群優(yōu)化算法原理

PSO算法的基本原理是通過個體間的協(xié)作與競爭，實現(xiàn)復(fù)雜空間中的最優(yōu)解的搜索.首先，在D維可行解空間中初始化一群粒子(設(shè)有N個)，對應(yīng)于優(yōu)化問題在D維空間中的N個潛在的解，然后根據(jù)下面兩個值來確定它的下次迭代的速度和位置：一個是每個粒子目前搜索到的最優(yōu)位置，稱為個體最優(yōu)極值；另一個是整個群體迄今為止搜索到的最優(yōu)位置，稱為全局極值.根據(jù)這兩個值來進行迭代，直到找到滿意的解為止[3].

基本的PSO的迭代模型如下：

2.2 人工魚群算法的基本原理

在一片水域中，魚往往能自行或尾隨其他魚找到食物多的地方，因而魚生存多的地方就是食物多的地方，人工魚群算法就是根據(jù)這一特點，通過構(gòu)造人工魚來模仿魚群的覓食、聚群及追尾行為，從而實現(xiàn)尋優(yōu).人工魚群算法[4]具體行為描述如下：

設(shè)x=(x1,x2,…,xN)為人工魚當(dāng)前狀態(tài)，對應(yīng)優(yōu)化函數(shù)中的N個潛在解(其中N表示人工魚的個數(shù))，yi=f(xi)(i=1,2,…,N)表示人工魚當(dāng)前的食物濃度，對應(yīng)優(yōu)化函數(shù)中的N個函數(shù)值，dij=||xi-xj||表示人工魚個體之間的距離，Visual表示人工魚視野范圍，Step表示移動的最大步長，σ表示擁擠度因子.

(1)覓食行為：人工魚群當(dāng)前狀態(tài)為xi(i=1,2,…,N)野范圍內(nèi)隨機選擇一個狀態(tài)xj，當(dāng)該環(huán)境的狀態(tài)優(yōu)于原來的狀態(tài)時，則向該方向前進一步；反之，則重新選擇隨機狀態(tài)xj，判斷是否滿足前進條件；如此反復(fù)Try number次后，如果仍不滿足，則隨機移動一步.

(2)聚群行為：人工魚群當(dāng)前狀態(tài)為xi(i=1,2,…,N)，其視野范圍內(nèi)伙伴數(shù)為nf，如果(nf/N)

每條人工魚搜索當(dāng)前所處環(huán)境的狀態(tài)，按照“進步最快的原則”或者“進步即可的原則”從中選擇一個合適的行為，使得各人工魚不斷向最優(yōu)化方向前進，并且在公告板上記錄其每次搜索到的最值，最終全部人工魚集結(jié)在幾個局部極值的周圍，且較優(yōu)的極值區(qū)域周圍能集結(jié)較多的人工魚.

根據(jù)以上對粒子群和人工魚群的敘述可以看出，二者均屬于種群優(yōu)化算法，由于二者概念簡單，需要調(diào)整的參數(shù)少，易于編程，本身沒有類似求導(dǎo)等復(fù)雜的數(shù)學(xué)操作，且在搜索的過程中是多個粒子同時展開搜索，具有隱含并行性，在處理優(yōu)化問題尤其是復(fù)雜問題時，已經(jīng)相對于傳統(tǒng)的優(yōu)化算法顯示出了明顯的優(yōu)勢，因而受到人們廣泛的關(guān)注和青睞，近幾年已成功應(yīng)用于多個領(lǐng)域.

2.3 兩個算法存在的問題

粒子群算法和人工魚群算法都有各自的優(yōu)缺點，對于粒子群算法它的優(yōu)點是收斂速度快，缺點是由于在算法初期各粒子很快地向最優(yōu)值聚攏，也就是在最優(yōu)值附近粒子群表現(xiàn)出強烈的“趨同性”，算法容易陷入局部最優(yōu)但收斂速度快，最終收斂到某一局部極值，即出現(xiàn)“早熟”現(xiàn)象，尤其是當(dāng)解空間是非凸集時，更易陷入局部收斂.人工魚群算法由于其引入了擁擠度因子[5]，從而能夠很好地跳出局部極值，并盡可能地搜索到其他的極值，最終向全局極值靠攏，卻在接近最優(yōu)值時往往停滯不前，而且算法對初值和各種參數(shù)的選擇也不很敏感，但是當(dāng)尋優(yōu)域較大或處于變化平坦的區(qū)域時，一部分人工魚將處于無目的的隨機游動中，這就影響了尋優(yōu)的效率.

3 基于粒子群算法和人工魚群算法的一種新的混合算法

本文結(jié)合魚群算法和粒子群算法兩者的優(yōu)點，提出了一種新的混合優(yōu)化算法.由于算法是粒子群和魚群混合算法，而粒子群算法隱含了魚群算法中的追尾行為，故為了減少計算量將魚群算法中的追尾行為去掉，去掉追尾行為的魚群算法我們稱之為簡單粒子群算法(SAF).首先初始化一群體，從同一種群出發(fā)分別用SAF算法和PSO算法進行搜索，各自的迭代次數(shù)由各自目前找到的最優(yōu)值和上次的最優(yōu)值的偏差決定，不妨設(shè)SAF當(dāng)前找到的最優(yōu)值為BBp(p為當(dāng)前迭代次數(shù))，PSO算法當(dāng)前的最優(yōu)值為Bq(q為當(dāng)前迭代次數(shù))，即當(dāng)|BBp-BBp-1|

3.1 混合優(yōu)化算法流程：

Step1：初始化有關(guān)參數(shù)

設(shè)置群體大小N及終止條件，初始化粒子群算法的參數(shù) c1，c2，w和簡單魚群算法的參數(shù) nf，Try number，σ 等.

Setp2：群體初始化

在解空間范圍內(nèi)隨機產(chǎn)生N個個體作為初始解，計算N個個體的適應(yīng)值，將最優(yōu)值記入公告板.

Step3：簡單魚群迭代

進行一次魚群搜索得到的最優(yōu)值記為BBp，若|BBp-BBp-1|

Step4：粒子群迭代

進行一次粒子群搜索得到的最優(yōu)值記為 Bq，若|Bq-Bq-1|

Step5：比較

若(BBp

Step6：檢驗公告板的值

若算法達到終止條件的要求，則停止迭代，輸出公告板的值，否則，轉(zhuǎn)入Step3.

3.2 混合優(yōu)化算法性能分析

為了驗證新的混合優(yōu)化算法的性能，本文選擇四個經(jīng)典函數(shù)用于優(yōu)化試驗，將混合優(yōu)化算法和標準粒子群算法、標準魚群算法、文獻[6]結(jié)果比較.

以上測試函數(shù)均取維數(shù)D=30，種群大小N=100，設(shè)優(yōu)化函數(shù)各維數(shù)的上、下限分別為a、b，根據(jù)經(jīng)驗值對算法中的參數(shù)如下設(shè)置，σ＝0.382，Visual=(b-a)/5，Step=(b-a)/10，Try number=N/5，c1=c2=2，w=0.8，停止條件為最大迭代次數(shù)為200次，其中混合優(yōu)化算法(PSO-AF)的迭代次數(shù)規(guī)定為粒子群迭代次數(shù)和簡單魚群算法迭代次數(shù)的一半之和，將本文算法和標準粒子群算法(BPSO)，標準魚群算法(BAF)，改進的基本粒子群算法(MPSO)[6]算法分別進行10次獨立的試驗，四種算法運行平均最優(yōu)值如表1所示.

從表1可以看出，混合優(yōu)化算法的每個測試函數(shù)的收斂精度明顯優(yōu)于其他三種算法，而且它的穩(wěn)定性也有很大幅度的提高.

表1 四種算法運行平均最優(yōu)值

4 結(jié)束語

本文提出基于粒子群算法和人工魚群算法的一種新的混合算法(PSO-AF)，解決了兩種算法：基本粒子群算法容易陷入局部最優(yōu)但收斂速度快，魚群算法全局收斂能力好卻在接近最優(yōu)值時往往停滯不前經(jīng)過仿真測試，我們提出的混合優(yōu)化算法能夠很好地跳出全局最優(yōu)并很快向極值靠攏，是一種比較可行的優(yōu)化算法，但不足的是文中很多參數(shù)只能憑借經(jīng)驗取定，其理論值還有待于通過分析算法的收斂性而進一步確定.

〔1〕Kennedy J,Eberhart R C.Shi Y.Swarm Intelligence[M].San Francisco:Morgan Kaufman Publishers,2001.

〔2〕Kennedy J,Eberhart R C.Particle Swarm Optim ization[R].Proc.IEEE Int,Ioont.On Nerual Networds.IEBE Service Center,Piscataway,NJ,1995(4):1942-1948.

〔3〕徐宗本.計算智能（第一冊）-模擬進化計算.北京:高等教育出版社,2004.114-116.

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

〔5〕修春曉,張雨虹.基于蟻群與魚群的混合優(yōu)化算法[J].計算機工程，2008（4）.

〔6〕王曉英,邢志棟,黃瑞平.改進的粒子群優(yōu)化算法[J].計算機應(yīng)用與軟件，2008（3）.