黃柏儒，樊曉光，禚真福，黃 雷，楊永建，李曉輝

(1.空軍工程大學(xué) 航空航天工程學(xué)院，陜西 西安710038;2.濟南空軍航空中心修理廠，山東 濟南250117)

0 引 言

2002 年，國內(nèi)學(xué)者李曉磊等人［1，2］模仿魚類行為方式提出的一種基于動物行為的新型仿生優(yōu)化方法—人工魚群算法(artificial fish swarm algorithm，AFSA)。該算法能克服局部極值的干擾，具有良好的全局搜索能力，由于算法只需要對問題進行優(yōu)劣的比較，對搜索空間有一定的自適應(yīng)能力，并具有對初值與參數(shù)選擇不敏感、魯棒性好、簡單易實現(xiàn)和使用靈活等諸多優(yōu)點。目前已應(yīng)用于解決連續(xù)性優(yōu)化問題、組合優(yōu)化等問題［3，4］的求解，取得了良好的效果。但AFSA 運行后期存在搜索的盲目性較大、尋優(yōu)結(jié)果精度低和運算速度慢等缺點，從而影響了其搜索質(zhì)量和效率［5，6］。一些學(xué)者從不同方面提出了改進人工魚群算法(IAFSA)，以解決標準AFSA 的各種缺陷。文獻［6］提出了具有逃逸行為、繁殖能力和基于多個算子的人工魚行為改進算法;文獻［7］提出了一種自適應(yīng)調(diào)整視野步長并提高魚群搜索速度的IAFSA;文獻［8］提出用整個魚群的中心位置和全局極值位置代替人工魚的鄰域中心位置和鄰域極值位置的IAFSA。文獻［9］提出了四種視野步長自適應(yīng)的IAFSA。

針對魚群算法全局搜索能力較強，而局部搜索能力偏弱的特點，本文提出一種引入貪心魚群的改進人工魚群算法(IAFSASF)，在文獻［7］的改進算法的基礎(chǔ)上對人工魚群的局部收斂能力作針對性優(yōu)化，實驗證明:改進方法行之有效，優(yōu)化效果明顯，同時降低了算法的時間復(fù)雜度，具有更好的計算性能。

1 AFSA

1.1 數(shù)學(xué)模型

AFSA 的尋優(yōu)機理是模擬自然界中魚的覓食、聚群和追尾行為以及魚群之間的相互協(xié)助行為等，其數(shù)學(xué)模型描述如下:

1.2 算法分析

人工魚的覓食、聚群和追尾行為使AFSA 具有良好的搜索能力，擁擠度因子可以有效地防止人工魚陷于局部極值，因此，算法能夠迅速向全局最優(yōu)解的收斂。但算法在后期進行高精度求解時，由于擁擠度因子作用，人工魚無法大量聚集到最優(yōu)解周圍，進而影響尋優(yōu)的效率和精度。

2 IAFSASF

雖然基本AFSA 全局搜索能力較強，但精確求解能力較弱，文獻［7］提出了隨著迭代次數(shù)增加而逐漸縮小步長與視野的改進方法，取得了良好的優(yōu)化效果。但該方法并沒有解決局部精確求解時，人工魚受擁擠度因子相互排斥的問題。假設(shè)人工魚數(shù)量在到達某個程度之后，算法陷入局部極值的概率不會隨人工魚數(shù)量的增加而明顯提高，因此，將一定比例的人工魚轉(zhuǎn)換為具有更利于局部尋優(yōu)的行為策略的貪心魚(貪心魚的比例表示為β，0 ＜β ＜1)，從而使算法在后期的收斂性得到改善，故提出IAFSASF。

2.1 貪心魚群的行為描述

貪心魚的行為策略不同于普通的人工魚，其總是跟隨在當前處于食物濃度最高的人工魚Fbest的周圍執(zhí)行覓食行為，如果貪心魚不在Fbest的跟蹤距離之內(nèi)，則貪心魚迅速地移動到Fbest的附近一個隨機位置，再執(zhí)行覓食行為。貪心魚的覓食范圍為普通人工魚的50%，隨機選取覓食范圍內(nèi)的一個位置，若Ynext比Ynow優(yōu)，則移動到該位置。若貪心魚反復(fù)嘗試try_number 之后未能找到最高的食物濃度位置，則隨機移動一步。當貪心魚到達的新位置的最高食物濃度位置比Ybest更優(yōu)時，F(xiàn)best將得知并直接到達該位置。此外，貪心魚的聚群和追尾行為改為直接隨機移動一步。覓食行為的偽代碼描述如下:

其中，dtail為貪心魚的跟蹤距離，Step/2 為貪心魚的步長為普通人工魚的50%。(此處以求極小值舉例，下文均以求極小值問題討論。)

2.2 視野步長的動態(tài)調(diào)整

根據(jù)文獻［7］的研究結(jié)果，將人工魚的視野步長按式(1)作動態(tài)調(diào)整

其中，Visualmin=0.001;Stepmin=0.000 2;t 為當前迭代次數(shù);Tmax為最大迭代次數(shù)。

2.3 普通人工魚的覓食行為改進

基本AFSA 中人工魚覓食時向食物濃度更高的位置移動一步的搜索方式效率較差。為了加快搜索速度，人工魚可以直接移動到該位置。

2.4 IAFSASF 的程序流程

1)設(shè)定人工魚群規(guī)模M 和貪心魚的比例β，視野Visual和步長Step、擁擠度δ、和最大重復(fù)嘗試次數(shù)try_number、最大迭代次數(shù)Tmax等參數(shù)，初始化M(1－β)條普通的人工魚和Mβ 條貪心魚，并在搜索范圍內(nèi)隨機初始化每條人工魚的位置。

李白模仿鮑照的樂府詩創(chuàng)作，分為兩類，一類為全擬作，情感指向上與鮑照原作妙合無垠，“擬其題，拓其旨，用其詞，襲其句，仿其意?！绷硪活悶橥}新作，創(chuàng)新策略表現(xiàn)為：情感指向個性化，失意中潛藏著豁達，這種豪情逸氣成了情感的主旋律；敘事密度上，變鮑照用典繁復(fù)為敘事線條疏朗，側(cè)重渲染神奇瑰麗的意境；拓寬了主題寓意，寓諷諫和憂患意識于各種題材。

2)計算每條人工魚的適應(yīng)度，與公告板的的歷史最優(yōu)狀態(tài)和當代最優(yōu)狀態(tài)相比較，若有更優(yōu)值，則更新它們。

3)每條普通人工魚或貪心魚執(zhí)行覓食、追尾、聚群和隨機行為，更新自己的位置。

4)根據(jù)式(1)調(diào)整人工魚和貪心魚的視野和步長，并重置公告板的當代最優(yōu)狀態(tài)。

5)檢查是否滿足終止條件(達到預(yù)設(shè)的迭代代數(shù)或?qū)?yōu)精度)，如果滿足終止條件，輸出最優(yōu)解，算法終止;否則，轉(zhuǎn)步驟(2)。

3 仿真實驗與分析

為更好地比較改進后算法的效果，仿照文獻［7］所做的仿真實驗，本文以求相同3 個測試函數(shù)的最小值為例，設(shè)計程序進行仿真實驗。測試軟件平臺為Java 和Windows XP，機器主頻為3.4GHz，內(nèi)存為2GB。3 個測試函數(shù)如下:

1)Rastrigin 函數(shù)

－10 ＜xi＜10，是多峰函數(shù)，在xi=0(i=1，2，…，D)時取得全局最小點，最小值為0;

2)Griewank 函數(shù)

－600 ＜xi＜600，是多峰函數(shù)，xi=0(i=1，2，…，D)時取得全局最小點，最小值為0;

3)Rosenbrock 函數(shù)

－100 ＜xi＜100，是非凸、病態(tài)單峰函數(shù)，xi=1(i=1，2，…，D)時取得全局最小點，最小值為0。

3.1 固定進化迭代次數(shù)

固定進化迭代次數(shù)的收斂速度、精度和性能實驗參數(shù)設(shè)置如下:人工魚群規(guī)模為50，維度為2，δ=5，最大反復(fù)嘗試次數(shù)為try_number=5;對于f1，Visual=2.85，Step =1.25，β=0.2;對于f2，Visual=300，Step=18，β=0.15;對于f3，Visual=25，Step=3，β=0.65。對于式(1)取Visualmin=0.001，Stepmin=0.000 2，S=3。三種算法的迭代次數(shù)均為100，重復(fù)實驗50 次。

表1 列出了AFSA，IAFSA，AFSASF 求解函數(shù)f1，f2，f3所得的尋優(yōu)結(jié)果。由表1 可以看出:IAFSASF 在IAFSA 已取得的優(yōu)化效果的基礎(chǔ)上更進一步，不僅精度得到提升，程序運行時間也更少。尤其了對于f3，其作為單峰函數(shù)，相對而言算法不易陷入局部極值，β 可以取值較大，因此，尋優(yōu)精度提升和運行時間減少都更加顯著。圖1～圖3 分別是f1，f2，f3采用AFSA，IAFSA，AFSASF 運行50 次得到的函數(shù)平均最小值對數(shù)的進化曲線。由圖1～圖3 可以看出IAFSASF 對IAFSA 的收斂性改進效果明顯，尤其是對f3函數(shù)。

表1 三種算法的尋優(yōu)結(jié)果Tab 1 Search results of three algorithms

圖1 函數(shù)f1 的平均最小值進化曲線Fig 1 Average minimum evolution curve of f1

圖2 函數(shù)f2 的平均最小值進化曲線Fig 2 Average minimum evolution curve of f2

圖3 函數(shù)f3 的平均最小值進化曲線Fig 3 Average minimum evolution curve of f3

圖4 AFSA 下函數(shù)f3 的第100 代魚群分布圖Fig 4 The 100 iteration fish swarm distribution of f3 by AFSA

圖5 IAFSA 下函數(shù)f3 的第100 代魚群分布圖Fig 5 The 100 iteration fish swarm distribution of f3 by IAFSA

圖6 IAFSASF 下函數(shù)f3 的第100 代魚群分布圖Fig 6 The 100 iteration fish swarm distribution of f3 by IAFSASF

圖4～圖6 分別是在f3函數(shù)下AFSA，IAFSA 和IAFSASF運行到第100 代時的人工魚群分布情況?？梢悦黠@看出:AFSA 由于視野步長不變，難以向全局最優(yōu)解有效收斂，影響了尋優(yōu)效率;IAFSA 收斂到后期，由于視野步長已變得過小，有相當一部分人工魚無法到達全局最優(yōu)解附近參與尋優(yōu);相比之下，由于不受擁擠度因子的制約IAFSASF 下的貪心魚群能夠更好地向全局最優(yōu)解聚集，最優(yōu)人工魚因為可以獲知新的最優(yōu)位置又提高了魚群整體的尋優(yōu)能力。

3.2 固定收斂精度

固定收斂精度下的進化迭代次數(shù)實驗參數(shù)設(shè)置如下:人工魚群規(guī)模為20，目標收斂精度為0.000 1，最大迭代次數(shù)為500，其他參數(shù)同3.1 節(jié)所示。表2 為3 個函數(shù)的給定的收斂精度下獨立運行100 次的統(tǒng)計結(jié)果。其中，成功率等于達到給定收斂精度的運行次數(shù)除以總的實驗次數(shù)。

表2 目標精度下的進化迭代次數(shù)統(tǒng)計結(jié)果Tab 2 Statistics result of evolution iteration numbers under target precision

由表2 可以看出:IAFSASF 成功率與IAFSA 相當，平均迭代次數(shù)稍好于IAFSA，這驗證了本文對人工魚群數(shù)量與陷入局部極值概率之間關(guān)系的假設(shè)。從最小迭代次數(shù)可以看出:IAFSASF 具有更強的能力迅速尋找到全局最優(yōu)解的精確解，在計算性能方面相較于另外兩種算法有明顯優(yōu)勢。

4 結(jié)束語

IAFSASF 進一步提高了算法的局部尋優(yōu)能力，同時有效地減少了算法的運行時間。其中貪心魚群的比例β 對于不同的函數(shù)的最佳取值不同，一般而言，對于多峰函數(shù)這類局部極值較多的問題取值稍小，對單峰函數(shù)則可以取值稍大，或者將一小部分普通的人工魚以2～3 倍數(shù)量的貪心魚替換，則可以在相同運行時間下獲得更精確的全局最優(yōu)解。IAFSASF 實現(xiàn)簡單，效果明顯。

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

［2］ 李曉磊.一種新型的智能優(yōu)化算法—人工魚群算法［D］.杭州:浙江大學(xué)，2003.

［3］ 李曉磊，路 飛，田國會，等.組合優(yōu)化問題的人工魚群算法應(yīng)用［J］.山東大學(xué)學(xué)報:工學(xué)版，2004(5):64－67.

［4］ 賈 強，季仲梅，王建輝.改進的人工魚群算法及其在無線定位中的應(yīng)用［J］.計算機應(yīng)用研究，2011(6):2147－2150.

［5］ 王聯(lián)國，施秋紅.人工魚群算法的參數(shù)分析［J］.計算機工程，2010，36(24):169－171.

［6］ 王西鄧.人工魚群算法的改進研究［D］.西安:西安建筑科技大學(xué)，2007.

［7］ 王聯(lián)國，洪 毅，趙付青，等.一種改進的人工魚群算法［J］.計算機工程，2009(19):192－194.

［8］ 王聯(lián)國，洪 毅，施秋紅.全局版人工魚群算法［J］.系統(tǒng)仿真學(xué)報，2009(23):7483－7486.

［9］ 劉彥君，江銘炎.自適應(yīng)視野和步長改進的人工魚群算法［J］.計算機工程與應(yīng)用，2009，45(25):35－37.

［10］江銘炎，袁東風.人工魚群算法及其應(yīng)用［M］.北京:科學(xué)出版社，2012.