人工魚群算法研究綜述

鄒 康，劉 婷，鮑韋韋，張立毅，肖志濤

(1.天津工業(yè)大學電子與信息工程學院，天津 300387;2.天津大學電子信息工程學院，天津 300072;3.天津商業(yè)大學信息工程學院，天津 300134)

近年來，人工智能學科飛速發(fā)展，學者們通過研究動物群體和人類社會的智能行為，提出了群體智能(Swarm Intelligence)算法。它具備天然的分布式和自組織特征［1］，是通過模擬自然界生物群體行為來實現(xiàn)人工智能的一種方法。典型的群體智能算法主要有粒子群算法、蟻群算法、等。

2002 年，李曉磊等［2］成功地將動物自治體的概念引入優(yōu)化算法，提出了人工魚群算法(Artificial Fish Swarm Algorithm，AFSA)。它采用自下而上的思路，應用了基于行為的人工智能方法，因為是從分析魚類的活動出發(fā)進行尋優(yōu)，故稱為人工魚群算法。目前，關(guān)于AFSA算法的研究已經(jīng)滲透到多個應用領(lǐng)域，并且得到了很好的應用效果，成為群智能計算領(lǐng)域的研究熱點之一。

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

在一片水域中，魚生存數(shù)目最多的地方一般就是本水域中富含營養(yǎng)物質(zhì)最多的地方，依據(jù)這一特點來模仿魚群的覓食等行為，從而實現(xiàn)全局尋優(yōu)，這就是AFSA的基本思想［2］。基本人工魚群算法是用來解決連續(xù)值域內(nèi)不受約束的優(yōu)化問題，在離散域內(nèi)將行為定義稍加改動也同樣適用。

假設(shè)有條人工魚，當前狀態(tài)為Xi，隨機選擇人工魚另一狀態(tài)為Xj;其中，xi=［xid］(i=1，2，L，SN，d=1，2，L，D)是一個D 維向量，xi=［xid］(i=1，2，L，SN，d=1，2，L，D)同為一個D 維向量;狀態(tài)Xi的食物濃度(適應度函數(shù))為Yi=f(Xi)，其中f(.)為目標函數(shù);人工魚個體之間的距離表示為di，j=‖Xi－Xj‖，其感知距離(視野范圍)為Visual，移動步長為step，擁擠度因子為δ。算法中，幾種行為與尋優(yōu)命題的解決有著較密切的關(guān)系。

(1)覓食行為

設(shè)人工魚當前狀態(tài)為Xi，在其感知范圍內(nèi)隨機選擇一個狀態(tài)Xj，在求極大值問題時，若Yi＜Yj，則向該方向前進一步，即Xi/next;反之，再重新隨機選擇狀態(tài)Xj，判斷是否滿足前進條件;這樣反復嘗試try_number 次后，若仍不滿足前進條件，則隨機移動一步。其數(shù)學表達式為:

式中，Rand為一個(0，1)的隨機數(shù)。

(2)聚群行為

設(shè)人工魚探索當前鄰域內(nèi)(di，j＜Visual)的伙伴數(shù)目nf及中心位置狀態(tài)Xc，如果Yc/nf＞δYi，表明伙伴中心有較多的食物且其周圍不太擁擠，則朝伙伴中心位置方向前進一步;否則執(zhí)行覓食行為。其數(shù)學表達式為:

(3)追尾行為

設(shè)鄰域內(nèi)(di，j＜Visual)探索到的食物濃度最大狀態(tài)為Xmax，如果Ymax/nf＞δY，表明Xmax狀態(tài)具有較高的食物濃度且其周圍不太擁擠，則朝Xmax的方向前進一步;否則執(zhí)行覓食行為。其數(shù)學表達式為:

(4)公告板

用來記錄最優(yōu)人工魚個體的狀態(tài)。

2 基本人工魚群算法的改進

2.1 初始化的改進

初始化種群是算法進行搜索的起點。AFSA算法的初始種群生成是隨機的，通常情況下可以保證初始魚群分布均勻，但對于個體的質(zhì)量不能保證，解群中有一部分遠離最優(yōu)解。

宋瀟瀟等［3］提出了基于極坐標編碼的改進人工魚群算法。它通過設(shè)定編碼規(guī)則，并將此編碼方式運用到三種行為當中，計算出每一個編碼母體獲得的人工魚的概率，選擇大概率的母體作為算法初始化的起點，有效提高算法的收斂性。宋志宇等［4］利用混沌系統(tǒng)產(chǎn)生混沌變量，并在參數(shù)允許范圍內(nèi)隨機產(chǎn)生各個人工魚個體的初始狀態(tài)。陳廣洲等［5］引入了免疫算法中的消亡算子，經(jīng)算子運算更新，相互比較，摒棄非優(yōu)個體，將其重新初始化，以此保持種群的多樣性。

2.2 算法參數(shù)的改進

AFSA算法參數(shù)較多，且通常情況下是固定的，δ 設(shè)置不合理，收斂效果不明顯。在算法后期，隨著人工魚個體逐漸靠近最優(yōu)點，這時當前較好的解只有一兩位元素與最優(yōu)解不同，所以在其附近仍采用在Visual 與step 范圍內(nèi)覓食的方式尋優(yōu)是不合理的。

王冬冬等［6］提出了分段優(yōu)化的思想，令食物濃度η為分界線，大于η 時，為前期過程，采用較大的step和Visual，能使算法較快地得到一個相對較優(yōu)的解;小于η 時為后期過程，采用較小的step和Visual，得到一個精度更高的解。黃華娟等［7］通過公式(4)和公式(5)自適應減小了步長和擁擠度因子。

其中，k為當前迭代的代數(shù)，α∈［0，1］為衰減因子。俞洋等［8］通過公式(6)逐漸減小視野。

Xiao J M 等［9］運用最優(yōu)適應值變化率K和變化方差σ2作為是否進行參數(shù)變化的衡量標準，從而避免算法的退化。

2.3 與其它算法相結(jié)合的改進

算法一般在優(yōu)化初期具有較快的收斂性，而在后期卻往往收斂較慢。雖然通過對參數(shù)的改進可以解決此問題，但是從計算復雜度、收斂效果及速率等因素來考慮，僅從算法自身改進不足難以達到更高的要求。因此，在AFSA算法中引入其它算法，綜合二者的優(yōu)點，成為AFSA 改進的一個主流趨勢。

(1)與粒子群算法相結(jié)合

羅德相等［10］將種群分為兩部分，一部分運用粒子群算法，一部分運用魚群算法，將二者比較后的最優(yōu)值賦予公告板，以此提高收斂速度。

(2)與遺傳算法相結(jié)合

張梅鳳等［11］將變異算子引入魚群算法，實現(xiàn)人工魚個體的跳變，從而調(diào)整優(yōu)化群體。曲良東等［12］引入高斯變異和差分進化兩種變異算子，通過變異使得劣解得以更新，確保了算法的尋優(yōu)性。

(3)與禁忌搜索算法相結(jié)合

李亮等［13］通過鄰域禁忌搜索，構(gòu)造兩點禁忌尋優(yōu)算子對解空間進行無重復的搜索，以此來跳出局部最優(yōu)點，確保算法的高效性。

(4)與其它算法相結(jié)合

高德芳等［14］提出魚群－蟻群算法的概念，將蟻群算法融入ASFA 中。

3 魚群算法的應用

基于魚群算法的優(yōu)點，其在很多領(lǐng)域得到廣泛應用。如對連續(xù)函數(shù)進行優(yōu)化;將算法運用到多用戶檢測;解決旅行商問題及約束優(yōu)化問題等。綜上所述，AFSA算法在很多領(lǐng)域都展現(xiàn)出了其良好的解決問題能力。

4 總結(jié)與展望

目前針對魚群算法的研究已逐漸趨于成熟，但許多問題仍有待進一步的研究:

首先，AFSA算法的基礎(chǔ)理論研究尚待完善。例如算法參數(shù)較多，且參數(shù)設(shè)置也缺乏確切的理論依據(jù)，通常依靠經(jīng)驗來設(shè)定。

其次，算法在后期收斂速度明顯降低，僅僅通過AFSA算法的計算很難得到滿意解。如何將其它智能算法與AFSA算法融合，減小甚至克服各自的缺點，構(gòu)造出創(chuàng)新性并具備實用價值的混合算法是當前研究的熱點趨勢。

［1］Bonabeau E，Dorigo M，Theraulaz G.Swarm Intelligence:Fromnatural to Artificial Systems［M］.New York:Oxford University Press，1999:40－58.

［2］李曉磊.一種新型的智能優(yōu)化方法——人工魚群算法［D］.浙江大學博士論文，2003.

［3］宋瀟瀟，孫棣華，解佳.基于極坐標編碼的改進人工魚群算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32(10):2248－2251.

［4］曲良東，何登旭.一種混沌人工魚群優(yōu)化算法［J］.計算機工程與應用，2010，46(22):40－42，37.

［5］陳廣洲，汪家權(quán)，李傳軍，等.一種改進的人工魚群算法及其應用［J］.系統(tǒng)工程，2009，27(12):105－110.

［6］王冬冬，李哲，梁麗，等.基于改進人工魚群算法求解多元非線性方程組［C］.2009 中國智能自動化會議論文集，2009:163－168.

［7］黃華娟，周永權(quán).改進型人工魚群算法及復雜函數(shù)全局優(yōu)化方法［J］.廣西師范大學學報(自然科學版)2008，26(1):194－197.

［8］俞洋，殷志鋒，田亞菲.基于自適應人工魚群算法的多用戶檢測器［J］.電子與信息學報，2007，29(1):121－124.

［9］Xiao J M，Zheng X M，Wang X H，et al.A Mdified Artificial Fish-Swam Algorithm［C］.Proceedings of the 6th World Congress on Intelligent Control and Automation，Dalian，2006:3456－3460.

［10］羅德相，周永權(quán)，黃華娟.粒子群和人工魚群混合優(yōu)化算法［J］.計算機與應用化學，2009，26(10):1257－1261.

［11］張梅鳳，邵誠，甘勇，等.基于變異算子與模擬退火混合的人工魚群優(yōu)化算法［J］.電子學報，2006，34(8):1381－1385.

［12］曲良東，何登旭.混合變異算子的人工魚群算法［J］.計算機工程與應用，2008，44(35):50－52.

［13］李亮，遲世春，林皋.禁忌魚群算法及其在邊坡穩(wěn)定分析中的應用［J］.工程力學，2006，23(3):6－10.

［14］高德芳，趙勇，郭楊，等.基于混合魚群－蟻群算法的模塊化產(chǎn)品配置設(shè)計［J］.設(shè)計與研究，2007，34(1):7－10.