李玉毛，于志遠(yuǎn)

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.3 兩個(gè)算法存在的問題

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

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

本文結(jié)合魚群算法和粒子群算法兩者的優(yōu)點(diǎn)，提出了一種新的混合優(yōu)化算法.由于算法是粒子群和魚群混合算法，而粒子群算法隱含了魚群算法中的追尾行為，故為了減少計(jì)算量將魚群算法中的追尾行為去掉，去掉追尾行為的魚群算法我們稱之為簡(jiǎn)單粒子群算法(SAF).首先初始化一群體，從同一種群出發(fā)分別用SAF算法和PSO算法進(jìn)行搜索，各自的迭代次數(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和簡(jiǎn)單魚群算法的參數(shù) nf，Try number，σ 等.

Setp2：群體初始化

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

Step3：簡(jiǎn)單魚群迭代

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

Step4：粒子群迭代

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

Step5：比較

若(BBp

Step6：檢驗(yàn)公告板的值

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

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

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

以上測(cè)試函數(shù)均取維數(shù)D=30，種群大小N=100，設(shè)優(yōu)化函數(shù)各維數(shù)的上、下限分別為a、b，根據(jù)經(jīng)驗(yàn)值對(duì)算法中的參數(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ù)和簡(jiǎn)單魚群算法迭代次數(shù)的一半之和，將本文算法和標(biāo)準(zhǔn)粒子群算法(BPSO)，標(biāo)準(zhǔn)魚群算法(BAF)，改進(jìn)的基本粒子群算法(MPSO)[6]算法分別進(jìn)行10次獨(dú)立的試驗(yàn)，四種算法運(yùn)行平均最優(yōu)值如表1所示.

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

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

4 結(jié)束語(yǔ)

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

〔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〕徐宗本.計(jì)算智能（第一冊(cè)）-模擬進(jìn)化計(jì)算.北京:高等教育出版社,2004.114-116.

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

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

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