自適應視野和步長的局部鄰域人工魚群算法

許恒迎，孫偉斌，張 霞，牛慧娟，白成林＋

（1.聊城大學 物理科學與信息工程學院，山東 聊城252000；2.山東省光通信科學與技術重點實驗室，山東 聊城252000）

0 引 言

人工魚群算法（AFSA）是李曉磊博士提出的一種基于行為的新型人工智能算法［1］，通過模擬魚群的覓食、聚群、追尾、隨機等行為實現全局尋優，具有魯棒性強、全局收斂性好以及對初值選擇不敏感等特點，目前在傳感器網絡優化、水質參數識別、多用戶檢測器、參數優化、路由選擇及組合優化等多個工程領域已得到應用并取得了良好效果［2－6］。許多研究學者針對人工魚群算法在運行后期表現出的搜索盲目性較大、尋優精度低、對于復雜問題易陷入局部極值等缺陷做出了改進，如張梅鳳等提出了基于生境的人工魚群算法，較好解決了多峰問題，但步驟比較繁瑣［7］；劉彥君通過自適應地改變人工魚的視野和步長提高了尋優精度，但是易陷入局部極值［8］；王聯國提出了全局版人工魚群算法，提高了運算速度，但目標的尋優精度有待提高［9］。在這些學者研究成果的基礎上，針對AFSA尋優精度差、易陷入局部極值和過早收斂的問題，本文提出了一種采用自適應視野和步長的局部鄰域人工魚群算法（local neighborhood artificial fish swarm algorithm，LNAFSA）。該算法采用了一種全新的局部鄰域結構，每條人工魚只能與本鄰域結構內的其他5條鄰居魚相互交換信息。每次迭代前每條人工魚都要根據自身與其他5條鄰居魚的距離自適應地計算視野和步長，增強了魚群個體之間的差異性，簡化了參數設定。在聚群行為中每條人工魚計算所在鄰域結構的中心，減少了求視野范圍內人工魚之間距離的計算量，追尾行為中則跟蹤所在鄰域結構內的最優人工魚，由于采用了這種固定的鄰域結構而無需判斷視野范圍內哪條人工魚才是鄰居，算法迭代速度得以提高。經6個經典測試函數和1個光纖通信系統偏振模色散（PMD）補償的工程實例驗證，表明該算法的尋優精度和迭代速度均得到了較大改善，有效抑制了過早收斂現象。

1 基于自適應視野和步長的局部鄰域結構人工魚群算法

1.1 全新的局部鄰域結構

在AFSA中，假設第i條人工魚的狀態表示為向量Xi＝（x1，x2，…，xn），它的感知距離為Visual，移動的步長為Step，擁擠度因子為δ，第i條人工魚對應的食物濃度為Y＝f（Xi），任意兩條人工魚i、j之間的距離定義為di，j＝‖Xi－Xj‖，則第i條人工魚的鄰域定義為N＝｛Xj｜di，j＜Visual｝，鄰居人工魚的數目為nf［1］。

文獻［1］指出人工魚的數目越多，收斂速度越快，但是迭代計算量越大，綜合考慮以上因素及測試函數的要求，人工魚的總數設定為20。受文獻［10］的啟發，我們使用模擬退火算法隨機地改變這20條人工魚之間的連接，并且將鄰居魚數目從1逐漸增加到10，這樣可以得到1300余種可能的局部鄰域結構。采用Sphere、Rastrigin、Griewank、Rosernbrock、f6等5個經典測試函數測試并比較所有局部鄰域結構的性能，發現鄰居魚數目為5時所需迭代次數最少并且迭代成功率可達到95%以上。圖1給出了LNAFSA算法采用的一種具有5條鄰居魚并且迭代成功率可以達到100%的鄰域結構拓撲圖。在該結構中，每條人工魚的生存環境位于6條人工魚（包含自身和5條鄰居人工魚）組成的空間結構中，每條人工魚只能與其鄰居人工魚交換信息。

圖1 全新局部鄰域結構的拓撲

圖1中每個圓圈代表一條人工魚，圓圈外的數字代表每條人工魚的編號，連線表示相連人工魚可以相互交換信息。這種鄰域結構中每條人工魚的生存環境可用表1表示。

表1 每條人工魚的局部鄰域結構

1.2 自適應視野和步長

在AFSA中，所有人工魚的視野Visual和步長Step都是事先設定的固定值。這是兩個非常重要的參數，直接決定了尋優結果的精度。如果視野和步長較大，人工魚全局搜索能力強并能快速收斂，但在收斂后期不可避免的出現人工魚在最優值附近來回振蕩的現象；如果視野和步長較小，人工魚收斂速度變慢，可以提高收斂精度，但在局部極值突出的情況下，很容易陷入局部極值而難以逃離。因此，有必要使視野和步長隨著迭代的進行能夠自適應地調整。

現在每條人工魚已處于表1所示的局部鄰域結構中，每次迭代前，第i條人工魚均要計算與其他5條鄰居人工魚的距離，取平均值后乘以限制因子K1及函數α（t）后再加上視野常量Visualmin，作為該人工魚當前的自適應視野Visuali；將Visuali乘以1/8及α（t）后再加上步長常量Stepmin，作為該人工魚當前的自適應步長Stepi。計算公式為

式（1）中，限制因子K1是在0～1之間的常數，它的取值與函數自變量搜索的范圍及維數有關。α（t）決定了視野、步長與迭代次數的變化關系［11］。Visualmin和Stepmin的主要作用是防止算法在運行后期與其他5條鄰居人工魚的平均距離無限接近0時出現停止收斂的現象。α（t）中K2為限制因子，TotalIter是一迭代總次數常量，因此α（t）是一個隨迭代次數t的增大而逐漸減小的函數。

1.3 基于局部鄰域結構的人工魚行為描述

1.3.1 聚群行為

假設當前時刻第i條人工魚的狀態為Xi＝（x1，x2，…，xn），且第i條人工魚所在鄰域結構的中心位置Centeri＝（center1，center2，…centerk，…，centern），每一分量centerk的計算公式為

式中：m——第i條人工魚鄰域結構的每條鄰居人工魚，AFNeighbori——第i條人工魚所在的鄰域結構（包括自身）。假設中心位置Xc對應的食物濃度Yc＝f（Xc），如果Yc/nf＞δ＊Yi（對應求極大問題，極小問題為 Yc/nf＜δ＊Yi），說明Centeri處食物濃度更高且可容納下自身，則第i條人工魚朝Centeri位置前進一步，下一時刻位置分量xinextk按式（3）計算，否則根據下文所述的行為選擇策略執行追尾或覓食行為

式中：rand（）—— 一個0到1之間的隨機實數，Stepi——當前迭代第i條人工魚的步長。

1.3.2 追尾行為

遍歷第i條人工魚所處的局部鄰域結構，找到本鄰域內最優人工魚，假設其狀態為AFlocalbest，這條最優人工魚對應的食物濃度為Localbest。如果Localbest/nf＞δ＊Yi（對應求極大問題，極小問題為Localbest/nf＜δ＊Yi），說明鄰域內的最優人工魚AFlocalbest處更優且可容納下自身，則第i條人工魚朝AFlocalbest的方向前進一步，下一時刻位置分量xinextk按式（4）計算，否則根據下文所述的行為選擇策略執行聚群或覓食行為

式中：AFlocalbestk——第i條人工魚所在局部鄰域內最優人工魚對應的位置分量。

1.3.3 覓食行為

當前迭代第i條人工魚的視野為Visuali，則第i條人工魚在［－Visuali，Visuali］范圍內隨機巡視得到一個狀態Xrand，設定此狀態下的食物濃度為Yrand。如果它們各自對應的食物濃度Yrand＞Yi（對應求極大問題，極小問題為Yrand＜Yi），為加快尋優速度，第i條人工魚直接移動到該位置。若將以上過程嘗試進行了try＿number次后仍未發現更高的食物濃度，則第i條人工魚在［－Stepi，Stepi］范圍內隨機選擇一值作為下一時刻游動時的位置增量。

1.3.4 行為選擇

因人工魚的行為種類較多，下一時刻具體執行哪種行為需依據具體處理問題的不同而選擇不同的行為選擇策略。本文采用的是進步即可原則［11］，即首先執行聚群行為，若未發現更高食物濃度則執行覓食行為，如果仍未發現更優值則執行追尾行為，最后若依然未發現更高食物濃度則執行覓食行為。

1.3.5 公告板

在尋優過程中，每條人工魚每次行為（如聚群、覓食、追尾或隨機行為）完畢就將自身狀態與公告板的狀態進行比較，優則替換公告板上的記錄。最后，算法根據公告板的記錄得到最終的尋優結果。

1.3.6 算法流程

步驟1 設定人工魚群規模、每條人工魚所在的局部鄰域結構AFNeighbor、擁擠度δ、覓食行為中重復嘗試次數try＿number、限制因子K1和K2、最大迭代次數等參數。

步驟2 在搜索空間內隨機初始化每條人工魚的位置，計算此時每條人工魚的食物濃度（即對應的函數值），并與公告板的狀態比較，優則替換。

步驟3 根據式（1）自適應調整此次迭代每條人工魚的視野和步長。

步驟4 每條人工魚在局部鄰域結構內按照上述進步即可原則執行各種行為，每條人工魚的位置和公告板狀態也隨之進行更新。

步驟5 判斷迭代次數是否達到預定最大迭代次數或尋找到的最優值是否滿足精度要求。若條件滿足，則輸出最優值，算法終止；否則返回步驟3，繼續下一次迭代。

2 收斂分析

一種算法具備全局收斂性的充要條件是：

（1）具備局部收斂性；

（2）提供從局部最優解狀態向其他未被搜索空間轉移的方法；

（3）提供搜索整個狀態空間的策略［12］。以下討論LNAFSA算法滿足這樣3個條件：

對于條件（1）：第i條人工魚在執行聚群或追尾行為時，如果在AFNeighbori的中心位置或在AFNeighbori內最優人工魚處發現更優值并且不太擁擠，則朝其前進一步，這種策略可以保證經過一定次數的迭代后第i條人工魚在本鄰域內找到局部最優值，顯然具備局部收斂性。如果第i條人工魚執行覓食行為，由覓食行為的定義可知，第i條人工魚總要朝更優方向前進，保證了局部收斂。因此，滿足條件（1）。

對于條件（2）：每條人工魚的生存環境位于自身和5條鄰居人工魚組成的局部鄰域結構中，每條人工魚只能與其鄰域交換信息。這種全新的局部鄰域結構可以有效提升人工魚群算法的性能。如果某條人工魚陷入了局部極值，影響的范圍也僅僅是本鄰域結構，可以依靠本鄰域內其它5條人工魚發現的更優值吸引其快速“逃離”陷入的局部極值，向其他未被搜索的空間游動。如果某條人工魚發現了更優值，既可以直接將這一信息與本鄰域內的其余5條人工魚分享，又可以通過鄰域結構的重疊性逐漸傳播到整個群體。因此，LNAFSA算法采用的這種局部鄰域結構既具有局部性又具有全局性，滿足條件（2）。

對于條件（3）：LNAFSA算法初始化時，所有人工魚隨機地均勻分布在函數的搜索空間中，對應局部鄰域結構內與其他5條人工魚的距離平均值較大，按照式（1）每條人工魚均具有較大的視野和步長，可以搜索整個狀態空間，從而加強了全局搜索能力。隨著迭代次數的增加，每條人工魚都有向最優值方向游動的趨勢，對應所在鄰域內與其他5條人工魚的平均距離逐漸減小，按式（1）逐漸減小它的視野和步長。在迭代后期，當人工魚游動至最優值附近時，其視野和步長將降低至非常小便于實現局部區域的精細搜索。每次迭代時每條人工魚通過平均距離計算得到的視野和步長均不同，賦予了人工魚更多的智能。因此，這種方法實現了視野和步長的自適應調整，兼顧了收斂速度和尋優精度，在加強局部搜索能力的同時又提高了目標精度，滿足條件（3）。

因此，LNAFSA算法具備全局收斂性。

3 實驗結果分析

3.1 實驗設計

在Matlab R2006b環境下，機器主頻為Intel Core2 2GHz，內存為1GB。選取6個經典測試函數進行實驗：

（5）Rotated hyper－ellipsoid Function：f5（x）＝，它是一個病態的高維單峰函數，在xi＝0i＝1，2，…n時達到全局最小值，最優值為0。

3.2 實驗結果及分析

人工魚群規模為20，覓食行為中重復嘗試次數try＿number＝5。其余參數設置見表2。

表2 算法的參數設置

設定f1～f4的維數均為30維，f5為5維，f6為2維，對于每一測試函數算法均獨立運行50次，其中每次迭代循環2000次，記錄這50次運行所得結果的最好值、最劣值、均值、標準差、達到目標精度時所用的最大、最小及平均迭代次數以及每次迭代的平均運行時間，以這些數據作為衡量算法性能的指標［8－9，11，14］。實驗結果如表3和圖2～圖7所示。

表3中“—”表示迭代次數超過了最大迭代次數2000，意味著算法尋優的最終結果沒有達到規定的目標精度［9，14］。由表3可以看出，LNAFSA的尋優結果明顯好于AFSA，并且這種算法的穩定性更好。以表2規定的目標優化精度作為衡量指標，由測試結果可知：AFSA對于函數f650次內有27次優化至目標精度內，具有一定的優化能力，對于函數f1～f5則完全不能優化；而LNAFSA對6個測試函數均能尋優至目標精度內，都成功實現了優化，平均迭代次數最多是1194次，并且它的平均運行時間更短，大約為AFSA的1/3。

圖2～圖7是分別采用LNAFSA和AFSA對函數f1～f6運行50次后得到的每次迭代平均最優值的進化曲線。為方便對比，f1～f5的全局最優值分別取自然對數，f6每次的尋優結果均為負值，故圖7采用了f6每次迭代后的全局最優值。從圖2～圖7可以看出，LNAFSA具有很強的克服局部極值的能力，收斂速度快，尋優精度更高，明顯優于AFSA。

表3 AFSA與LNAFSA算法優化結果

3.3 與參考文獻中改進算法的優化性能比較

選取文獻［9，13，14］共有的測試函數f1與f3，設定f1與f3的維數分別為10、20和30，相應迭代循環次數分別設置為1000次、1500次和2000次，LNAFSA在f110維時K1取1/10，20維時K1取1/15，對于f310維和20維的K1均取1/20，其他參數同上。每個函數進行50次實驗，取全局最優值的平均值，與文獻［13］中改進型粒子群算法優化結果、文獻［9］全局版人工魚群算法及文獻［14］基于馮諾依曼結構的人工魚群算法結果進行比較，實驗結果見表4。

表4 與參考文獻中改進算法的優化結果比較

通過表4可以看出，LNAFSA對于函數f1和f3的優化結果全面優于IPSO、GAFSA和AFSAVNN。因此，這種算法的優化性能更好。

3.4 實例測試

本文利用LNAFSA進行40Gb/s光纖通信系統二階偏振模色散（PMD）補償，并與文獻［15］中應用單純形算法和遺傳算法的結果進行了比較，進一步檢驗算法的優化性能。

LNAFSA的參數設置為視野最小值Visualmin＝0.001，步長最小值Stepmin＝0.0002，重復嘗試次數try＿number＝5，擁擠度因子δ＝0.5，最大迭代次數TotalIter＝50。該實例測試以光纖鏈路偏振度（DOP）作為目標函數值，理論上完全進行二階PMD補償后DOP值應為1，測試結果見表5。

表5 與單純形算法和遺傳算法的二階PMD補償結果比較

由表5可以看出，LNAFSA得到的最小、最大和平均目標函數值均優于單純形算法和遺傳算法，該算法可有效解決此類工程問題。

4 結束語

針對AFSA尋優精度差、易陷入局部極值和過早收斂的問題，提出了基于自適應視野和步長的局部鄰域人工魚群算法。該算法具有兩個主要的優點：一是采用了全新的局部鄰域結構，使得人工魚能夠快速逃離局部極值，克服了基本人工魚群算法容易過早收斂的缺陷，提高了算法的全局尋優能力；二是每條人工魚采用了基于本鄰域結構內平均距離的自適應視野和步長，達到了視野和步長自適應調整的目的，使算法具備了更多的人工智能，實現了收斂速度和尋優精度的雙贏。仿真結果表明，這是一種簡單、高效的人工魚群算法。

［1］LI Xiao－lei，LU Fei，TIAN Guo－hui，et al.Applications of artificial fish school algorithm in combinatorial optimization problems［J］.Journal of Shandong University：Engineering Science，2004，34（5）：64－67（in Chinese）.［李曉磊，路飛，田國會，等.組合優化問題的人工魚群算法應用［J］.山東大學學報，2004，34（5）：64－67.］

［2］LIAO Can－xing，ZHANG Ping，LI Xing－shan，et al.Optimal deployment in sensor networks based on hybrid artificial fish school algorithm［J］.Journal of Beijing University of Aeronautics and Astronautics，2010，36（3）：373－377（in Chinese）.［廖燦星，張平，李行善，等.基于混合人工魚群算法的傳感器網絡優化［J］.北京航空航天大學學報，2010，36（3）：373－377.］

［3］GAO Yufang，CHEN Yaodeng.The optimization of water utilization based on artificial fish－swarm algorithm［C］.Yantai：Sixth International Conference on Natural Computation，2010：4415.

［4］YU Yang，YIN Zhi－feng，TIAN Ya－fei.Multiuser detector based on adaptive artificial fish school algorithm［J］.Journal of Electronics ＆ Information Technology，2007，29（1）：121－124（in Chinese）.［俞洋，殷志鋒，田亞菲.基于自適應人工魚群算法的多用戶檢測器［J］.電子與信息學報，2007，29（1）：121－124.］

［5］BAN Xiao－juan，YANG Yun－mei，NING Shu－rong，et al.A self－adaptive control algorithm of the artificial fish formation［C］.Korea：IEEE International Conference on Fuzzy systems，2009：1903－1908.

［6］ WANG Xing－wei，QIN Pei－yu， HUANG Min.ABC supporting QoS unicast routing scheme based on the artificial fish swarm［J］.Chinese Journal of Computers，2010，33（4）：718－725（in Chinese）.［王興偉，秦培玉，黃敏.基于人工魚群的ABC支持型QoS單播路由機制［J］.計算機學報，2010，33（4）：718－725.］

［7］ZHANG Mei－feng，SHAO Cheng.Niche artificial fish swarm algorithm for multimodai function optimization［J］.Control Theory ＆ Applications，2008，25（4）：773－776（in Chinese）.［張梅鳳，邵誠.多峰函數優化的生境人工魚群算法［J］.控制理論與應用，2008，25（4）：773－776.］

［8］LIU Yan－jun，JIANG Ming－yan.Improved artificial fish swarm algorithm based on adaptive visual and step length［J］.Computer Engineering and Applications，2009，45（25）：35－47（in Chinese）.［劉彥君，江銘炎.自適應視野和步長的改進人工魚群算法［J］.計算機工程與應用，2009，45（25）：35－47.］

［9］WANG Lian－guo，HONG Yi，SHI Qiu－hong.Global edition artificial fish swarm algorithm［J］.Journal of System Simulation，2009，21（23）：7483－7502（in Chinese）.［王聯國，洪毅，施秋紅.全局版人工魚群算法［J］.系統仿真學報，2009，21（23）：7483－7502.］

［10］James Kennedy，Rui Mendes.Neighborhood topologies in fully informed and best－of－neighborhood particle swarms［J］.IEEE Trans on Systems，Man，and Cybernetics，Part C：Applications and Reviews，2006，36（4）：515－519.

［11］WANG Lian－guo，HONG Yi，ZHAO Fu－qing，et al.Improved artificial fish swarm algorithm［J］.Computer Engineering，2008，34（19）：192－194（in Chinese）.［王聯國，洪毅，趙付青，等.一種改進的人工魚群算法［J］.計算機工程，2008，34（19）：192－194.］

［12］ZHU Xi－lu，WANG Bai.Niche genetic algorithm based on cluster division［J］.Control and Decision，2010，25（7）：1113－1116（in Chinese）.［祝希路，王柏.一種基于社團劃分的小生境遺傳算法［J］.控制與決策，2010，25（7）：1113－1116.］

［13］JIANG Yan，HU Tie－song，HUANG Chong－chao，et al.An improved particle swarm optimization algorithm［J］.Applied Mathematics and Computation，2007，193（1）：231－239.

［14］WANG Lian－guo，HONG Yi.Artificial fish－swarm algorithm based on Von Neuman neighborhood［J］.Control Theory ＆Applications，2010，27（6）：775－780（in Chinese）.［王聯國，洪毅.基于馮·諾依曼鄰域結構的人工魚群算法［J］.控制理論與應用，2010，27（6）：775－780.］

［15］WANG Xian－qing，WANG Hong－xiang，JI Yue－feng，et al.Control Algorithms In Adaptive PMD Compensation System［J］.Journal of Beijing University of Posts and Telecommunications，2007，30（1）：110－113（in Chinese）.［王先慶，王洪祥，紀越峰，等.自適應偏振模色散補償系統中的控制算法［J］.北京郵電大學學報，2007，30（1）：110－113.］