自適應重生魚群優化算法

易正俊　韋磊鵬　袁玉興

1(重慶大學數學與統計學院　重慶 401331)2(重慶科技學院數理學院　重慶 401331)

?

自適應重生魚群優化算法

易正俊1韋磊鵬1袁玉興2

1(重慶大學數學與統計學院重慶 401331)2(重慶科技學院數理學院重慶 401331)

摘要針對傳統人工魚群算法求解高維優化問題收斂速度較慢，易于陷入局部最優，提出自適應重生魚群優化算法。首先在每次迭代過程中，不斷地給魚群注入“新生命”使魚群得以重生；然后采用正態分布動態調整擁擠度因子的上限值使得算法更貼近于魚群搜索食物的過程。實驗結果表明，改進后的算法既保證收斂速度、增加算法獲得全局最優的可能性，又適用于求解大規模的優化問題。其中的兩個算例采用改進的魚群算法進行優化，優化結果與實際具有良好的一致性，說明了改進算法的有效性和實用性。

關鍵詞人工魚群算法魚群重生正態分布動態擁擠度因子優化

0引言

人工魚群算法[1]是李曉磊等人于2002年提出的一種基于動物自治體的新型尋優策略。該算法模擬了自然界中魚群的覓食、聚群和追尾行為。為了突出人工魚群算法的全局尋優能力，李曉磊等[2]將人工魚群算法與遺傳算法進行對照，測試后得到其效果更佳，且人工魚群算法具有集群智能、良好的并行性、參數和初值的魯棒性強等優點，在工程上已得到廣泛使用[3-8]。李亮等[4]于2006年構造了一種兩點禁忌尋優算子以避免尋優過程中的迂回搜索，并將其應用到兩個復雜土坡的最小安全系數搜索中；方金城等[5]于2011年引入實數編碼對魚群算法進行改進，并將其應用于配送決策問題中;陳安華等[7]于2012年通過定義相似度因子和聚類判別因子，建立了模擬人工魚群追尾行為的機械故障聚類診斷模型，并將之應用于機械故障特征信息的聚類分析。

通過反復實驗發現人工魚群算法設計思路簡單，求解低維優化函數時能夠保持較高的精度，且能夠較快地獲取全局最優解。但我們在實際中遇到的往往是龐大的工程問題，決策變量的維數較高，導致搜索范圍的空間復雜度大大增加。這時應用傳統的人工魚群算法很容易陷入局部最優，算法的精度和收斂速度也隨之下降。針對以上的不足，本文對人工魚群算法進行改進，給魚群注入“新生命”和引入動態擁擠度因子，使其在處理高維優化函數時仍能保持較高的精度。主要思想是在算法迭代過程中，一方面給種群注入“新生命”，豐富了種群的多樣性；另一方面通過控制擁擠度因子的值及時地調整魚群的行為，這樣擴大了魚群的搜索范圍，有效地避免算法陷入局部最優。同時，利用仿真實驗研究了該方法的有效性。

1自適應重生魚群優化算法

1.1優化問題的描述

一個優化問題描述如下：

minf(X)X∈S

式中，f(X)表示目標函數，X表示決策變量，S表示可行域。

1.2傳統人工魚群算法的描述

魚群搜索食物的過程主要包括覓食、聚群和追尾三種行為。覓食表現在當魚在它的視野范圍內發現食物時，則朝該方向游動；聚群是每條魚在游動過程中盡量地朝鄰近伙伴的中心游動，并避免過分擁擠；追尾是指當某條魚發現該處食物豐富時，其他魚會快速尾隨至此。

在一片水域中，魚往往能自行或尾隨其他魚找到營養物質比較豐富的地方，因而魚聚集數目最多的地方往往是水域中營養豐富的地方。人工魚群智能算法求解最優化問題就是模擬魚群搜索食物過程的特點，把可行解域看成一片水域，函數在可行解域中的極值點視為水域中魚群的食物源，函數值視為食物源的食物濃度。然后從構造單條人工魚開始，通過模擬魚的覓食、聚群和追尾行為，實現所有人工魚聚集在食物源中心的附近，再比較相應食物源的濃度值，得出最優食物源，其對應位置的坐標就是最優化問題的解。

魚的視野范圍(記為Visual)是有限的。它在水域中隨機游動，若在其視野范圍內發現某點的食物濃度大于當前位置的食物濃度，則它會朝食物濃度大的點方向進行移動，移動的步長用step表示。游動到一定的程度，魚在它的視野范圍內可能有多條魚，此時會產生聚群現象。若每一條魚當前位置的食物濃度低于視野范圍內魚群的中心位置的濃度，魚群的擁擠度不是太大，則魚會朝中心位置移動；同時魚群中的魚還會有追尾現象發生，每一條魚會探索其視野范圍內最大食物濃度位置中的魚，若擁擠度還沒有達到極限位置，則魚會朝最大食物濃度位置游動。

傳統的人工魚群算法經反復實驗發現：決策變量X的維數增多時，算法的精度和收斂速度大大地降低了，無法得到全局最優解。實際問題中的許多待優化問題往往是高維的，如資源配送問題、線路設計問題等。因此本文在傳統的魚群算法基礎上不斷地給魚群注入新的“生命”，動態修訂魚群擁擠度因子的上限值，更加符合自然界中魚群的搜索食物的過程。改進后的魚群算法稱為自適應重生魚群優化算法，適合大規模的優化問題的求解。

1.3反向學習的基本概念

反向學習是智能搜索中的一種方法，已經被證明是隨機搜索算法中的一種有效方法[14,15]。下面介紹反向學習中幾個基本的概念。

1.3.1反向數

定義1若x∈[a,b]是一維實空間R1中的點，則x的反向數x*=a+b-x。

1.3.1反向點

1.4自適應重生魚群優化算法

1.4.1魚群重生

魚群重生是指每次迭代的開始根據上輪迭代所得的N個位置，生成這N個位置分別對應的反向點，重新得到N條人工魚，給人工魚注入新的生命，相當于產生新的N個位置。然后把N個位置與上輪迭代所得N個位置的食物濃度進行比較，選取食物濃度最大的前N個位置作為人工魚的現處位置來參與進化，是對人工魚的一種更佳的估計。每次迭代通過不斷地給人工魚注入“新生命”，豐富了種群的多樣性，人工魚的搜索范圍擴大，跳出局部最優的機會增大，提高了算法獲得全局最優的可能性。

1.4.2動態擁擠度因子

擁擠度因子是用來刻畫人工魚群聚集的規模，擁擠度因子δ的設定是避免人工魚過分地聚集在某個極值點的周圍，使得人工魚能夠更廣泛的尋優。傳統的人工魚群算法中把δ設定為一個常數，這樣設計會影響算法的性能。若δ選取偏小，人工魚在逼近極值的同時會避免過分擁擠而隨機走開，或者受其他人工魚的排斥作用，不能精確逼近極值點，且導致收斂速度很慢；若δ選取過大，容易陷入局部最優，致使算法出現停滯現象。

現引入動態擁擠度因δk來更加確切地模擬魚搜索食物的過程。事實上，魚群在尋找食物開始時，每條魚在其視野范圍內并不擁擠，為更廣泛地搜索，避免魚群過度集中，擁擠度因子δ應該取較小的值；隨著魚群搜索過程的繼續，魚群就會進行聚群和追尾行為，這時魚的周圍變得越來越擁擠，這時為保證最優食物源的周圍有更多的魚，避免因擁擠限制魚群的聚集，δ應隨著搜索的進行而增加。但是迭代后期，魚群趨于成熟和穩定，魚群容易陷入局部最優，致使算法停滯不前。這時為了提高人工魚跳出局部最優的能力，我們應抑制魚群的聚群和追尾行為，鼓勵其進行覓食行為和隨機游動，這時我們就要抑制δ的值并適當地降低。鑒于此，隨著迭代次數k的不同，擁擠度因子δ也不同，即魚群算法的擁擠度因子δ應該是迭代次數k的函數δk=δ(k)(δk稱為動態擁擠度因子)，且兩者的函數關系大致如圖1所示。

圖1　動態擁擠度因子

由此，魚群算法中擁擠度因子的上限值δ修正為動態值δk。利用Matlab軟件進行擬合，得到其變化規律可以利用正態分布來刻畫，且擬合函數為：

其中m代表最大迭代次數。

魚群算法經過上面兩個方面的改進就稱為自適應重生魚群算法，其算法步驟為：

步驟1設定每條人工魚的視野范圍為Visual，移動步長恒定為step，擁擠度因子為δ，最大迭代次數為m。

步驟2初始化魚群。在可行域S內隨機生成N條人工魚。第i條人工魚的當前位置為Xi，其對應的食物濃度Yi(=-f(Xi))(i=1,2,…,N)。

步驟3測定N條人工魚在當前位置下的食物濃度Yi(1≤i≤N),記錄食物濃度最大值Ymax和相應的位置Xmax，即作為公告板的初始記錄(Xmax,Ymax)。

步驟5動態擁擠度因子δk：

(1)

步驟8覓食。在人工魚Xi的視野范圍內隨機選擇一個位置Xj。若Yj>Yi，則朝Xj的方向按照式(1)中的方法前進一步，否則重新隨機選擇位置Xj，判斷是否滿足前進條件。若嘗試Try_number次后仍不滿足前進條件，則執行步驟9。

步驟9隨機移動。人工魚在其可行域S內按照式(2)隨機移動一步，產生一個新的位置Xnext。

Xnext=Xi+Rand()×step

(2)

步驟11用新確定的人工魚位置，從步驟4開始重新搜索，直到迭代結束。

2實驗與仿真

2.1高維優化函數極值問題

選擇以下非線性優化函數來驗證自適應重生魚群優化算法的性能：

(3)

該非線性優化函數的全局最優解的周圍分布著很多局部最優解。且容易看出，對任意的自然數n，該優化問題的最優解為X=0，最優值為1。

下面的仿真實驗中，算法參數設置如下：人工魚的數量為50，視野范圍為1，移動步長為0.05，最大試探次數為50，最大迭代次數的設定:實驗1為500次，實驗2和3為50次。

實驗1圖2為采用傳統人工魚群算法求解式(3)所得的最優值隨維數n的變化曲線；圖3為維數n=11時傳統人工魚群算法的尋優曲線。從圖2可以看出隨著維數n的增大，傳統人工魚群算法的最優值越來越偏離1，精度大大地降低。當維數n>5時，傳統人工魚群算法的求解誤差≥0.25，所以其適用范圍受到一定的局限性。且從圖3中可以看出當維數n=11時，傳統人工魚群算法在迭代初期就陷入局部最優，始終無法跳出，所得的最優值0.366與1相差很大。

圖2　傳統人工魚群算法隨優化函數維數的變化曲線

圖3　維數n=11

通過實驗1可以得出：如果問題(3)要求求解誤差≤0.25，則傳統人工魚群算法的適用范圍為維數n≤5。但是實際的工程問題很復雜，所對應的優化問題的維數往往不止5。

實驗2圖4-圖6為自適應重生魚群優化算法與傳統的人工魚群算法維數不同比較的仿真結果。圖4表示當維數為2時,兩種算法尋優曲線的比較。從圖4可以看出雖然兩種算法都能得到最優值，但改進后的人工魚群算法比傳統的人工魚群算法的收斂速度快。圖5表示當維數為5時，兩種算法尋優曲線的比較。從圖5可以看出當迭代次數為40次時，傳統的人工魚群算法已經陷入局部最優，并且所得的最優值0.87。但是自適應重生魚群算法所得的最優值仍能逼近于1，求解精度比傳統的人工魚群算法高，且收斂速度快。圖6表示當維數為11時，兩種算法尋優曲線的比較。從圖6可以看出傳統的人工魚群算法所求的最優值在0.4左右，與式(3)的最優值偏離很大，已經無法適用。但是自適應重生魚群算法所得最優值仍保持在0.75以上，求解精度仍比傳統的人工魚群算法高。

圖4　維數n=2

圖5　維數n=5

圖6　維數n=11

通過實驗2可以得出：本文自適應重生魚群優化算法在收斂速度和全局尋優能力上都比傳統的人工魚群算法更佳，大大拓寬了人工魚群算法的適用范圍，在解決復雜的工程問題上更勝一籌。

實驗3圖7為兩種算法運行時間的比較結果。從圖7可以看出在相同的迭代次數內，當維數n≥6時，兩種算法的運行時間相當，也就是說，與傳統人工魚群算法相比，本文算法的復雜度并沒有增加，說明本文提出的算法不僅復雜度沒有增加，且各項性能都有大幅度的提高，在工程上適用范圍廣。

圖7　兩種算法運行時間的比較

由此可以得出結論：處理高維優化函數問題時，自適應重生魚群優化算法與傳統人工魚群算法相比，具有尋優速度快、精度高、復雜度相當等優點，成功地拓寬了其在工程上的應用。

2.2旅行線路的優化

旅游線路的優化的問題是旅行商(TSP)問題的一種典型代表。近幾年來對于TSP問題的求解提出了許多優化算法，其中仿生算法是研究的熱點[9-12]。它具有傳統算法不可替代的優勢,如：非線性性、自組織性和并行性等。本文引用文獻[13]中設計旅行線路為例，來直觀地反映自適應重生魚群優化算法與其他算法的優劣。

按照實數編碼的原理，對各個城市進行重新編號。為驗證本文算法的性能，同時引入遺傳算法和傳統的人工魚群算法進行求解。此時的優化函數為城市之間的歐氏距離之和。相關參數設置如下：人工魚數目為10;最大迭代次數：遺傳算法為1500，傳統和改進后的人工魚群算法為500;最多試探次數為100；視野范圍為6;移動步長為2；擁擠度因子為0.8(遺傳算法與文獻[13]的參數設置一致)。現設置出發點都為重慶，且必須經過每一個城市且僅一次，最后回到重慶。

由文獻[13]可知，利用遺傳算法得出的最優路線，所對應的最優值為18 997.8km。采用傳統的人工魚群算法設計旅行路徑的結果，其對應的最優值為18 596.9km。從優化效果來看，傳統人工魚群算法的尋優效果比遺傳算法的效果更好些。采用自適應重生魚群優化算法設計旅行路徑的結果。對應的線路安排如下：重慶—>貴州—>南寧—>海口—>澳門—>香港—>廣州—>長沙—>合肥—>南京—>上海—>杭州—>臺北—>福州—>南昌—>武漢—>鄭州—>太原—>石家莊—>濟南—>哈爾濱—>長春—>沈陽—>天津—>北京—>呼和浩特—>西安—>銀川—>蘭州—>西寧—>烏魯木齊—>拉薩—>昆明—>成都—>重慶；所對應的最優值為17 595.3km。從優化效果來看，自適應重生魚群優化算法的尋優效果比遺傳算法和傳統的人工魚群算法的效果都更佳。圖8為自適應重生魚群算法的尋優效果圖。從尋優的速度來看，本文算法能夠快速地找到較優路徑，并且運行時間短。

圖8　自適應重生魚群優化算法的尋優效果圖

通過三種算法的比較可以得出：本文在迭代過程中采用魚群重生和利用正態分布調整擁擠度因子的思想設計所得的自適應重生魚群優化算法，在實際的應用中能夠得到更佳的效果，并且求解精度高，收斂速度快，成功地拓寬了傳統的人工魚群算法在工程上的應用。

3結語

本文針對人工魚群算法在處理高維優化函數時的缺點，提出了自適應重生魚群算法。通過魚群重生和利用正態分布動態調整擁擠度因子的結合，不僅每次迭代都給魚群注入“新生命”，使魚群得以重生，而且能自適應地調整魚群的行為。實驗表明：經自適應重生魚群優化算法提高了求解高維優化函數的收斂速度和精度。最后為驗證本文算法的有效性，將其用于34個城市旅游線路的優化，并與傳統的人工魚群算法和遺傳算法相比。結果表明：本文算法尋優精度高，得到的線路最優，成功地拓寬了其在工程上的應用。

參考文獻

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

[2] 李曉磊,錢積新.基于分解協調的人工魚群優化算法研究[J].電路與系統學報,2003,8(1):1-6.

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

[4] 李亮,遲世春,林皋.禁忌魚群算法及其在邊坡穩定分析中的應用[J].工程力學,2006,23(3):6-10.

[5] 方金城,張岐山.配送中心配送決策問題及其魚群算法優化求解[J].計算機應用,2011,31(6):1652-1655.

[6]ZhangK,ZhangW,DaiCYEal.Artificalfish-swarmbasedconverage-enhancingalgorithmforvisiblelightsensornetworks[J].Optoelectronicletters,2010,6(3):229-231.

[7] 陳安華,周博,張會福,等.基于改進人工魚群算法的機械故障聚類診斷方法[J].振動與沖擊,2012,31(17):145-148.

[8] 王曄,吳小俊,王士同.基于改進人工魚群算法的RBF網絡及其在人臉表情識別中的應用[J].計算機應用研究,2008,25(9):2643-2646.

[9]ZhangZhigang,LiXiaojing.BasedonTSPProblemtheResearchofImprovedAntColonyAlgorithms[J].ElectricalEngineeringandControl,2011,98(2):827-833.

[10] 鄭立平,郝忠孝.基于混合雜交的遺傳算法求解旅行商問題[J].計算機工程,2005,20(31):168-172.

[11] 黃嵐,王康平,周春光,等.粒子群優化算法求解旅行商問題[J].吉林大學學報:理學版,2003,4(41):477-480.

[12] 楊劍峰,蔣靜坪.蟻群算法及其在組合優化問題中的應用[J].科技通報,2006,4(22):553-556.

[13] 走遍全中國方案的研究[EB/OL].(2014.05.30.)http://www.docin.com/p-105402921.html.

[14]TizhooshH.opppsition_basedlearning:Anewschemeformachineintelligence[C]//ProceedingsoftheInternationalConferenceonComputationalIntelligenceforModelingControlandAutomation,2005:695-701.

[15]WangHui,LiuY,ZengSY,etal.Opposition-basedParticleSwarmAlgorithmwithCauchyMutation[C]//Proc.Congr.Evol.Comput,2007:4750-4756.

ADAPTIVE REBORN FISH SCHOOL OPTIMISATION ALGORITHM

Yi Zhengjun1Wei Leipeng1Yuan Yuxing2

1(College of Mathematics and Statistics,Chongqing University,Chongqing 401331,China)2(School of Mathematics and Science,Chongqing University of Science and Technology,Chongqing 401331,China)

AbstractTraditional artificial fish school algorithm converges slowly and is prone to falling into local optimum when solving high-dimensional optimisation problems. In light of this, we presented the adaptive reborn fish school optimisation algorithm. First, in the process of each iteration we injected the "new life" into fish school incessantly, which made the rebirth of the fish school; Then we used normal distribution to dynamically adjust the upper threshold of crowding factor, making the algorithm more close to the process of fish school’s forage. Experimental result showed that the improved algorithm ensured the convergence speed and increased the probability of the algorithm in obtaining global optimum, yet it were also suitable for solving large-scale optimisation problems. Two examples in the paper were optimised by the improved fish school algorithm, the optimisation results were in good conformity with the reality, this illustrated the effectiveness and practicability of the improved algorithm.

KeywordsArtificial fish school algorithmFish rebirthNormal distributionDynamic crowding factorOptimisation

收稿日期：2014-11-27。國家自然科學基金項目(11371384，6967 4012)；重慶市科技攻關計劃項目(CSTC2009AC3037)。易正俊，教授，主研領域：人工智能，智能算法，信息融合與處理。韋磊鵬，碩士生。袁玉興，助教。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.055