引入貪心魚群的改進人工魚群算法

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

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

0 引 言

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

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

1 AFSA

1.1 數學模型

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

1.2 算法分析

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

2 IAFSASF

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

2.1 貪心魚群的行為描述

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

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

2.2 視野步長的動態調整

根據文獻［7］的研究結果，將人工魚的視野步長按式(1)作動態調整

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

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

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

2.4 IAFSASF 的程序流程

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

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

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

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

4)根據式(1)調整人工魚和貪心魚的視野和步長，并重置公告板的當代最優狀態。

5)檢查是否滿足終止條件(達到預設的迭代代數或尋優精度)，如果滿足終止條件，輸出最優解，算法終止;否則，轉步驟(2)。

3 仿真實驗與分析

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

1)Rastrigin 函數

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

2)Griewank 函數

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

3)Rosenbrock 函數

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

3.1 固定進化迭代次數

固定進化迭代次數的收斂速度、精度和性能實驗參數設置如下:人工魚群規模為50，維度為2，δ=5，最大反復嘗試次數為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。三種算法的迭代次數均為100，重復實驗50 次。

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

表1 三種算法的尋優結果Tab 1 Search results of three algorithms

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

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

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

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

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

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

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

3.2 固定收斂精度

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

表2 目標精度下的進化迭代次數統計結果Tab 2 Statistics result of evolution iteration numbers under target precision

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

4 結束語

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

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

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

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

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

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

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

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

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

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

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