人工魚群算法改進方法概述

費 騰， 張立毅

（1. 天津大學 電子信息工程學院， 天津 300072； 2. 天津商業大學 信息工程學院， 天津 300134）

2002 年，我國學者李曉磊[1]模擬魚群運動行為模式提出了魚群算法。 魚群算法中將魚群個體隨機分布在包含著若干局部最優值和一個最優值的解空間中，把最優值看作是最大的食物濃度。 人工魚覓食、聚群、追尾和隨機4 種行為通過移動策略來控制，個體鄰域通過視野來控制，搜索進度通過步長來控制，魚群聚集的程度通過擁擠度因子來控制。 魚群每完成一次迭代，都要進行公告更新，用以公告最優狀態。 魚群算法全局搜索能力較強，在參數估計、神經網絡、組合優化中得到廣泛應用。

雖然人工魚群算法具有簡單易實現，不需要了解問題的特殊信息，在一定程度上避免局部最優，具有全局并行能力等優點，但是，其仍然具有參數選定憑借經驗，算法后期搜索精度不高及收斂速度慢等缺點。

正是由于魚群算法仍有問題需要改進，因此，近些年來，對于魚群算法的改進研究十分活躍。 通過對改進方法的歸納， 主要從涉及自身改進和與其他算法融合兩個大方向進行。 其中魚群算法的自身改進主要包括參數改進，行為改進及鄰域結構的改變。

1 人工魚群算法自身改進

1.1 人工魚群算法參數改進

群智能算法主要是基于對于生物群落的行為的模仿而建立起來。 但由于數學研究水平的限制，算法無法絲毫不差的模仿出生物群落的所有行為。 特別是對群智能算法的參數選擇，大部分都需要大量實驗選定，或者通過經驗積累選定。正是因為如此，學者對于魚群算法改進的一個方面就是對其參數進行優化。 魚群算法參數比較多，近些年來，人們對于魚群算法參數的優化主要集中在步長和視野上。2005 年，Wang Cuiru[2]提出一種改進人工魚群算法，為了提高當人工魚群的最優值在定義的迭代次數后不變時， 增加一種跳躍行為，并改變人工魚的隨機參數， 可以增加獲得全局最優值的概率，用以提高人工魚群算法的穩定性和全局搜索力，并將這種改進人工魚群算法應用于前饋神經網絡模型的優化。 2009 年，王連國提出一種改進的人工魚群算法，在覓食行為中讓人工魚直接移動到較優位置，以加快算法的搜索速度，動態調整人工魚的視野和步長， 使其在算法運行初期保持最大值，并逐漸由大變小。 該算法較好地平衡了全局搜索能力和局部搜索能力，提高了算法運行效率和精度。 仿真結果表明，改進的人工魚群算法收斂性能比原有算法提高了1 倍以上。 2009年，Tian W[3]提出去除人工魚行為的步長限制，加入跳躍行為來優化人工魚的參數，用來提高全局的搜索能力。 同年，陳廣洲等針對基本魚群算法在迭代前期，算法具有較強的搜索能力，但在運行后期，其搜索能力減弱，易陷入局部極值，且搜索到的最優解精度不高。 針對上述弱點，提出對可視域和步長采用自適應變化策略，引入變異算子策略，通過消亡操作對部分個體進行重新初始化或變異，對基本魚群算法進行改進，并以函數優化和多維變量的非線性優化問題為例進行了實驗研究。 劉彥君提出了四種自適應人工魚群算法，通過賦予人工魚更多的智能，使每條人工魚都能根據魚群的狀態自動地選擇適時調整自身的視野和步長， 從而簡化了參數設定，提高了收斂速度和尋優精度實驗結果表明，改進后的人工魚群算法，在尋優精度、收斂速度及克服局部極值的能力方面均有提高。 2010 年，王宗利提出在移動步長中增加評價函數從而使人工魚群算法更快收斂。 2012 年，張英杰等針對經典魚群算法收斂速度慢、尋優精度低的缺陷，提出了一種基于參數動態調整的改進人工魚群算法，動態調整視野和擁擠度因子以提高算法的搜索效率，改進去交叉算子以消除交叉路徑，引入了再尋優算子確保再次搜索去交叉后路徑能夠快速找到最優值。 求解TSP 問題的實驗結果表明改進的人工魚群算法提高了收斂速度增強了搜索最優解的能力。

1.2 人工魚群算法行為改進

人工魚群算法主要通過模擬魚群的各個行為進行尋優，因此，一些學者從改進這些行為作為切入點來改進人工魚群算法，此外，還有一些研究人員在基本魚群算法中引入一些行為來優化目標函數來提高算法的性能。 2007 年，范玉軍等人采用最優個體保留策略對覓食行為進行改進，防止群體中最優個體的退化，給出加速個體局部搜索方法，改進算法中的聚群行為和追尾行為， 使全局最優值更快地突現出來，根據雙射的定義和性質，在不影響最終尋優結果的情況下對問題的搜索域進行“縮小”，從而加速了全局搜索。2009 年，程永明與江銘炎[4]提出在基本魚群算法中引入吞食行為，即設定一個閥值，把低于閥值的人工魚淘汰掉，從而降低算法的復雜度。 2010 年，韋修喜等人根據云理論具有隨機性和穩定傾向性的特點，結合人工魚群算法的思想，由基本云生成算法實現覓食行為操作，提出一種新的人工魚群算法——云人工魚群算法。 2011 年，張嚴和楚曉麗提出一種改進的人工魚群算法，對其覓食行為、追尾行為與移動策略進行改進，設定特殊覓食行為，約束群聚行為的擁擠度區間，協調移動策略，以保障每條魚的成功覓食，避免魚群出現早熟現象，提高全局尋優能力。

1.3 人工魚群算法鄰域結構改進

學者對于鄰域結構的改進也是人工魚群算法改進的一個方面。 2008 年，王聯國等提出了一種基于鄰域正交交叉算子的人工魚群算法。 該算法采用動態調整人工魚視野和步長的方法，較好地平衡了全局搜索能力和局部搜索能力。 將人工魚的鄰域極值與該人工魚進行正交交叉運算，產生少量的具有代表性的較優個體，而新產生的個體不僅利用了本身的有用信息，同時利用了鄰域極值的最優信息，加快了算法的收斂速度，增強了算法的尋優能力。2012 年，許恒迎等人為解決基本人工魚群算法搜索后期盲目性大、 過早收斂等問題，提出了一種采用全新局部鄰域結構的人工魚群算法。 每條人工魚只能與本鄰域內的其他5 條鄰居魚通信，每次迭代前每條人工魚都要根據自身與鄰域內其他5 條鄰居魚的平均距離自適應地計算視野和步長，并對人工魚的聚群和追尾行為進行了改進，從理論上討論了該算法的收斂性。2013 年，馬廣等人提出一種基于生存行為的人工魚群算法，該算法將一種成功率達到100%的局部鄰居結構引入人工魚群算法。 由于每條人工魚能夠交流信息的人工魚數目有限，有利于魚群向各個方向游動，增大了搜索到全局最優值的機率，同時各鄰居結構之間能夠進行信息交換，加快了尋優速度；采用線性調整人工魚視野和步長的方法有效平衡算法的全局搜索能力和局部搜索能力；在對基本人工魚群算法聚群行為和追尾行為分析基礎上，提出全新的生存行為，提高了收斂速度和收斂精度。

2 人工魚群算法與其他算法的融合

各種群智能算法都有其各自的優缺點，通過混合算法的方法，可以提高算法的性能，實現算法之間的優勢互補。 近些年來，對于魚群算法的改進大部分都集中在與其他算法的結合上，因此，基于魚群算法的混合算法是基本算法改進的一大主要方面。 其中主要包括與遺傳算法的結合，與模擬退火算法的結合，與粒子群算法的結合，與蟻群算法的結合，與文化算法的結合，與混沌算法的結合，以及與其他算法的結合。另外，一些學者還將基本魚群算法與比較成熟的計算方法結合，用以優化基本魚群算法的性能。

2.1 與遺傳算法結合

2008 年，劉白通過對人工魚群算法不足的研究，在遺傳算法的基礎上， 提出了基于遺傳算法的人工魚群優化算法。該算法保留了人工魚群算法簡單、易實現的特點，同時克服了人工魚漫無目的地隨機游動或在非全局極值點的大量聚集，顯著提高了算法的運行效率和求解質量。2009 年，聶聳在保證魚群算法收斂性能的前提下減少了對人工魚數量的需求， 同時克服了人工魚在非全局極值點大量聚集的弊端，采用分段自適應調整視野策略和擬遺傳算法的交叉變異算子，有效兼顧了全局搜索與局部挖掘能力，提高了算法的收斂速度。 2010 年，李如琦[5]等將遺傳算法與人工魚群算法有機融合，提出一種種群優化人工魚群算法，采用分別對部分人工魚個體進行選擇、交叉、變異操作的策略，調整優化人工魚種群結構，較好地兼顧局部搜索和全局搜索。

2.2 與模擬退火算法的結合

2006 年，張梅鳳在分析AFSA 存在不足的基礎上，提出了基于變異算子與模擬退火混合的人工魚群優化算法。 該算法保持了AFSA 算法簡單、易實現的特點，克服了人工魚漫無目的隨機游動或在非全局極值點的大量聚集，顯著提高了算法的運行效率和求解質量。 2010 年，Jiang M Y[6]等在基本魚群算法的基礎上融入模擬退火算法，新算法結合了模擬退火和魚群算法的特點，混合算法精度更高，收斂速度更快。 2011年， 劉佳利用模擬退火算法中的Metropolis 判別準則改進人工魚的覓食行為，在利用人工魚全局尋優的同時并利用模擬退火算子實施局部細化， 提出一種改進的人工魚群優化算法，并用于求解多峰函數的優化問題。2012 年，劉佳和霍俊儀將局部搜索能力較強的模擬退火算法與全局優化算法——人工魚群算法進行結合，求解邊坡的最危險滑動面及其對應的最小安全系數。

2.3 與粒子群算法結合

2008 年，Chen X J 和Wang J Z[7]提出粒子群與魚群并行混合優化算法，把粒子分為兩個群，一個群采用魚群算法，一個群采用粒子群算法，共同搜索后共同返回總群，算法提高了全局尋優能力。 2009 年，張創業和莫愿斌利用協同思想與正反饋機制， 讓AFSA 群跟蹤PSO 群的全局最優解，PSO 群跟蹤AFSA 群的全局最優解的算法。 這樣， 一方面利用AF2SA 的快速找到全局極值鄰域的能力克服PSO 易陷入局部的不足； 另一方面利用PSO 的快速收斂能力來提高AFSA的收斂速度和求解精度。 2010 年，姚祥光等針對人工魚群算法局部搜索不精確、 微粒群優化算法易發生過早收斂等問題，提出一種新的人工魚群與微粒群混合優化算法。 算法的主要思想是先利用人工魚群的全局收斂性快速尋找到滿意的解域，再利用粒子群算法進行快速的局部搜索，所得混合算法具有局部搜索速度快，而且具有全局收斂性能。2012 年，高博等人提出一種改進粒子群魚群混合算法。 粒子群算法中各微?？筛鶕陨斫洑v的最好位置與群體的最好位置，動態地調整好當前的速度和位置， 從而獲得較快的收斂速度，然而，在算法后期，由于粒子的同一化，算法容易陷人局部最優人工魚群算法是種較好的全局優化方法， 但收斂速度較慢，若將兩種算法結合起來，利用粒子群算法的快速局部搜索和人工魚群的全局收斂性，使新算法不僅具有快速的局部搜索速度，而且保證具有全局收斂性能的種性能較優的優化算法。

2.4 與蟻群算法的結合

2009 年，古明家等人將人工魚群算法加入到蟻群算法的每一次迭代過程中， 利用人工魚群算法全局快速收斂的優點， 來加快蟻群算法的收斂速度和人工魚群算法的覓食行為，幫助提高了蟻群算法跳出局部最優的能力。2010 年，余高等人提出了一個基于蟻群算法和人工魚群算法相結合的QoS 組播路由算法。首先利用改進的Salama 網絡拓撲隨機生成算法，隨機生成一個網絡拓撲圖，再利用蟻群算法并行搜索的特點找出大量滿足約束條件的可行路徑，創建備選路徑集，最后使用人工魚群算法在所創建的備選路徑集中，通過執行覓食、聚群、追尾等行為求解最優組播樹。2011 年，韓芳[8]等人提出了一種融合魚群和微分進化的蟻群優化算法。 受人工魚群覓食聚群和追尾行為的啟發，在基本蟻群算法的基礎上，應用人工魚群算法的追尾行為對蟻群在可行域上搜索到的解進行改進，加快了向最優解收斂的速度。 在信息素更新機制里，通過引入微分進化算法的發散項，增加一個隨機擾動，減小了算法陷入局部最優的可能性。

2.5 與文化算法的結合

2009 年，劉凌子和周永權提出一種基于人工魚群和文化算法的新型混合全局優化算法，該混合算法的思想是將人工魚群嵌入文化算法框架中， 作為種群空間的一個進化過程；通過從進化種群中獲得的知識組成知識空間，兩空間具有各自群體并獨立并行演化，從而實現增加人工魚群的群體多樣性。 2011 年，高洪元[9]等針對到達時間差（TDOA）定位估計中的非線性最優化問題，在魚群算法中引入文化機制設計基于實數編碼的文化魚群算法， 將Chan 算法的解作為文化魚群的一個個體初始位置，并利用文化魚群算法搜索TDOA 定位的最優坐標。

2.6 與混沌算法的結合

2007 年，宋志宇等人提出一種隨機搜索優化方法——人工魚群算法，同時根據混的遍歷性和隨機性等特點，將混沌系統和人工魚群算法相結合形成了一種新的融合優化算法—混沌人工魚群算法。 將混沌人工魚群算法應用到混凝土大壩材料參數反演中。 2012 年，祁俊[10]等針對人工魚群算法易陷入局部最優的問題，提出一種基于雙混沌映射的人工魚群算法。 該方法利用映射的均勻分布性產生混沌初始魚群，增加搜索的多樣性； 其次在人工魚群演化陷入局部最優時，利用局部分布均勻的映射生成混沌變異算子對其產生擾動，使其跳出局部最優值，向全局最優值靠近。 同年，石鴻雁和邢東亞針對人工魚群算法和混沌優化算法的特點將人工魚群算法與混沌優化算法相結合提出一種混合算法。 此混合算法是利用混沌變量敏感性來提高人工魚群初始群體解的質量然后利用混沌的遍歷性和隨機性擾動使魚群算法擺脫局部極值點提高全局收斂性。

2.7 與其他算法結合

2010 年，Zhu K C[11]提出一種量子人工魚群算法，將量子算法與魚群算法相結合，構造出隨機性和方向性比較平衡的量子人工與魚群混合算法。 2011 年，陳建榮和王勇在分析人工魚群算法和捕魚算法存在不足的基礎上，提出了一種人工魚群算法與采用捕魚策略的優化算法相結合的混合算法。 該算法在優化初期使用，算法搜索局部最優域，而在優化后期則使算法在優化前期所初步確定的局部最優域中搜索最優解。 2012 年，袁卿等深入分析人工魚群算法和蟑螂算法的特點基礎，提出一種改進式蟑螂算法。 將差分進化變異因子禁忌表分別引入到蟑螂算法，加快了算法的搜索速度和獲得全局最優解的能力。 采用權衡種群中最優個體和精英個體之間的差異度的方式將改進后的蟑螂算法和人工魚群算法動態融合。 同年，王培崇提出基于人工魚群機制的聚類算法。 首先， 利用先驗知識隨機產生待求解問題的若干個聚類中心，組成一個魚群環境；其次，利用魚群個體的協作競爭機制尋找滿意的結果。 鑒于人工魚群算法后期容易陷入局部最優，根據魚群聚集度引入小生境算法，改善種群的多樣性，提高了算法的求解精度。 2013 年，鄧濤等針對人工魚群算法多峰尋優能力不足的問題提出了一種免疫人工魚群網絡算法，應用改進的覓食行為，提升了算法的局部尋優能力采用免疫網絡調節機理，保持了人工魚群多樣性不斷探尋新的局部峰值執行模式搜索法，完成精英人工魚群的精細搜索。 同年，王波為了改進在非全局極值點出現較嚴重聚集情況時，收斂速度降低，甚至陷入局部極值，搜索性能劣化的問題，采用細胞膜優化算法物質的轉運方式，對人工魚群算法的尋優行為進行改進，從而一定程度上避免算法陷入局部最優，提出了一種基于細胞膜優化的人工魚群算法。

2.8 與計算方法結合

2007 年，于飛等針對人工魚群算法的不足，嘗試引入分區域搜索的思想、深度優先遍歷的思想以及禁忌搜索算法對該算法進行改進。 2008 年，曲良東和何登旭在分析基本人工魚群算法存在不足的基礎上，提出了基于高斯變異算子與差分進化變異算子相結合的人工魚群算法，該算法克服了人工魚漫無目的隨機游動或在非全局極值點的大量聚集，顯著提高了求解質量和運行效率。 2009 年，同樣是曲良東和何登旭[12]針對基本人工魚群算法存在的不足，根據高斯變異和歷史最優魚個體狀態，提出自適應高斯變異人工魚群算法。 該算法能克服人工魚漫無目的隨機游動從而求得全局極值，提高求解質量和運行效率。

3 結束語

雖然人工魚群算法已經應用于多個領域，但是相比于粒子群等其他經典算法，其理論基礎依舊不夠完善，仍然處在研究的初步階段，且對于人工魚群算法改進的研究也需要進行進一步深入研究，包括與新的算法的結合以及自身行為的增減等方面，以更好的發揮其在優化問題上的有效性。

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

LI Xiao-lei，SHAO Zhi-jiang，QIAN Ji-xin. An optimizing method based on autonomous animals:fish-swarm algorithm[J].Systems Engineering-theory & Practice，2002（11）:32－38.

[2] WANG Cui-ru，ZHOU Chun-lei，MA Jian-wei. An improved artificial fish-swarm algorithm and its application in feedforward neural networks [C]//2005 International Conference on Machine Learning and Cybernetics，2005:2890－2894.

[3] Tian J，Liu J C. An improved artificial fish swarm algorithm for multi-robot task scheduling [C]//proceeding of the 5th International Conference on Natural Computation，2009:129－130.

[4] 程永明， 江銘炎. 基于改進魚群算法的多用戶OFDM系統自適應自適應資源分配[J]. 計算機應用研究，2009，26（6）:2 092－2 094.

CHENG Yong-ming，JIANG Ming-yan. Adaptive resource allocation in multiuser OFDM system based on improved artificial fish swarm algorithm[J]. Application Research of Computers，2009，26（6）:2 092－2 094.

[5] 李如琦，王宗耀，謝林峰，等. 種群優化人工魚群算法在輸電網擴展規劃的應用[J].電力系統保護與控制，2010，38（23）:11－15.

LI Ru-qi，WANG Zong-yao，XIE Lin-feng，et al. Population optimization artificial fish school algorithm applied in transmission network expansion planning[J]. Power System Protection and Control，2010，38（23）:11－15.

[6] Jiang M Y，heng Y M. Simulated annealing artificial fish swarm algorithm [C]//Proceeding of the 8th World Congress on Intelligent Control and Automation，2010:1950－1953.

[7] Chen X J， Wang J Z. A novel hybrid evolutionary algorithm based on PSO and AFSA for freed forward neural training[C]//Proceeding of the 4th International Conference on Wireless Communications， Networking and Mobile Computing，2008.

[8] 韓芳，邢曉哲，方婷婷，等. 融合魚群和微分進化的蟻群算法的無功優化[J]. 黑龍江電力，2011，33（2）:125－128.

HAN Fang，XING Xiaozhe，FANG Tingting，et al. Reactive power optimization based on ant colony algorithm which combines artificial fish swarm algorithm and differential evolution algorithm[J]. Heilongjiang Electric Power，2011，33（2）:125－128.

[9] 高洪元，于雪梅，趙忠凱. 基于文化魚群算法的到達時間差定位技術[J]. 計算機工程，2011，37（14）:137－139.

GAO Hong-yuan，YU Xue-mei，ZHAO Zhong-kai. Time difference of arrival location technology based on cultural fish swarm algorithm[J]. Computer Engineering，2011，37（14）:137－139.

[10]祁俊，趙慧雅，李明. 基于雙混沌映射改進的人工魚群算法[J]. 計算機應用與軟件，2012，29（9）：230～233.

QI Jun，ZHAO Hui-ya，LI Ming. An improved Artificial fish swarm algorithm based on coupled chaotic maps[J]. Computer Applications and Software，2012，29（9）:230－233.

[11]Zhu K C，Jiang M Y. Quantum artificial fish swarm algorithm [C]//Proceeding of the 8th World Congress on intelligent Control and Automation，2010:1－5.

[12]曲良東，何登旭. 基于自適應高斯變異的人工魚群算法[J].計算機工程，2009，25（15）:182－184.

QU Liang-dong，HE Deng-xu. Artificial fish-school algorithm based on adaptive gauss mutation[J]. Computer Engineering，2009，25（15）:182－184.