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

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

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

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

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

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

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

(1)覓食行為

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

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

(2)聚群行為

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

(3)追尾行為

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

(4)公告板

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

2 基本人工魚群算法的改進(jìn)

2.1 初始化的改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

李亮等［13］通過(guò)鄰域禁忌搜索，構(gòu)造兩點(diǎn)禁忌尋優(yōu)算子對(duì)解空間進(jìn)行無(wú)重復(fù)的搜索，以此來(lái)跳出局部最優(yōu)點(diǎn)，確保算法的高效性。

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

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

3 魚群算法的應(yīng)用

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

4 總結(jié)與展望

目前針對(duì)魚群算法的研究已逐漸趨于成熟，但許多問(wèn)題仍有待進(jìn)一步的研究:

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

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

［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］.浙江大學(xué)博士論文，2003.

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

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

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

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

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

［8］俞洋，殷志鋒，田亞菲.基于自適應(yīng)人工魚群算法的多用戶檢測(cè)器［J］.電子與信息學(xué)報(bào)，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］.計(jì)算機(jī)與應(yīng)用化學(xué)，2009，26(10):1257－1261.

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

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

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

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