基于遞減反饋視野的人工魚群算法改進與應用

王 麗 宮建平

(晉中學院信息技術與工程學院 山西 晉中 030619)

?

基于遞減反饋視野的人工魚群算法改進與應用

王 麗 宮建平

(晉中學院信息技術與工程學院 山西 晉中 030619)

基本人工魚群算法的覓食行為是算法收斂的基礎，覓食視野固定會導致尋優(yōu)效率低、易陷入局部極值等弊端。引入視野遞減反饋策略，視野隨著迭代次數和尋優(yōu)的反饋信息適時變化，旨在平衡算法的全局搜索和局部搜索能力。通過五個TSP實例測試，結果表明該算法在保證收斂速度的基礎上提高了計算精度。最后將改進算法應用于求解山西省國家AAAA級風景區(qū)(含5A)最短遍歷路徑問題。

魚群算法 遞減視野 反饋策略 最優(yōu)路徑

0 引 言

水域中魚類生存數目最多的地方意味著食物最多，人工魚群算法AFSA(artificial fish swarm algorithm)就是模仿魚類群體行為方式提出的一種基于動物自治體的優(yōu)化方法[1]。該算法通過模擬魚類的覓食、聚群、追尾和隨機等行為在搜索區(qū)域內進行尋優(yōu)，每條人工魚通過感知外界環(huán)境和其他人工魚的狀態(tài)調整自身的行為。它對初值參數選擇不敏感，對目標函數的要求極低，對待求問題的適應能力很強，可以解決經典優(yōu)化方法不能求解的帶有絕對值且不可導二元函數的極值問題。但隨著優(yōu)化問題復雜程度和搜索空間維度的增加，后期的收斂速度明顯減小，只能找到較優(yōu)解域，很難得出精確的最優(yōu)解。近年來許多學者從多方面對算法進行改進，大致可以分成三類：與待求實際問題結合對算法行為改進[2,3]、與其他算法結合進行分段優(yōu)化或者混合優(yōu)化[4-6]、對算法相關參數進行改進[7,8]。例如文獻[2]將速度引力場與人工魚群算法結合，在多變的復雜環(huán)境中追蹤動態(tài)目標，對所生成路徑進行評估和修正，從而獲得最優(yōu)路徑；文獻[3]求解旅行商問題時將城市間距離作為啟發(fā)式信息來加快人工魚尋優(yōu)的速度；文獻[4]和文獻[5]分別將和聲搜索算法和微粒群算法與人工魚群算法進行融合；文獻[6]對基本人工魚群算法的移動條件進行改進，并且采用分段優(yōu)化的方法；文獻[7]和文獻[8]分別針對人工魚群算法視野和步長進行自適應調整；為了使算法在迭代初期具有良好的全局探索性，而在迭代后期具有較優(yōu)的局部搜優(yōu)性，文獻[9]將高斯變異和柯西變異的優(yōu)點結合，形成一種新的自適應t變異機制，并將變異機制應用于種群中的非最優(yōu)個體，同時針對種群中的最優(yōu)個體執(zhí)行高斯最優(yōu)調教變異。大量文獻經實驗發(fā)現(xiàn)，如果視野較大，那么算法前期收斂速度很快。但在算法后期，人工魚個體在較優(yōu)解域附近仍以此視野覓食就無法搜索到全局最優(yōu)解或者陷入局部極值點。視野較小又會導致尋優(yōu)迭代次數太大，很難找到一個折中的視野參數來兼顧整個迭代過程的搜優(yōu)效率。為了提高算法后期的求解精度，文獻[10]使魚群個體的步長和視野逐漸遞減到一個固定值，提出了一種基于Logistic模型的變步長和變視野機制的改進人工魚群算法。本文受文獻[7]的啟發(fā)在AFSA的基礎上引入遞減指數和迭代閾值，提出一種基于視野遞減反饋策略的改進人工魚群算法，旨在保證算法前期的收斂速度和算法后期的收斂精度，同時也能避免算法后期陷入局部最優(yōu)，有利于提高搜索效率和準確性。最后將其應用于解決最短遍歷路徑問題。

1 改進的人工魚群算法

1.1 基本人工魚群算法求解TSP的思想

人工魚群算法模仿魚類的覓食行為、聚群行為、追尾行為和隨機行為構造人工魚群，通過四種行為使得幾個局部極值甚至全局最優(yōu)值周圍可以聚集大量人工魚。每條人工魚對應一個優(yōu)化解，食物濃度對應目標函數。假設有N條人工魚，每條人工魚的狀態(tài)為向量X=(x1,x2,…,xn)，人工魚當前位置的食物濃度為Y=f(X)，人工魚個體之間的距離為di,j=‖Xi-Xj‖。

TSP一直是組合優(yōu)化領域研究的經典熱點問題之一，常常被用來驗證智能啟發(fā)式算法的有效性。一個旅行商人從某城市出發(fā)，選擇一條遍歷所有城市節(jié)點最短的路徑，最終返回出發(fā)城市，限制路徑中每個城市只能拜訪一次。其數學模型為：假設有n個城市C=(C1,C2,…,Cn),城市之間的兩兩距離為di,j=(Ci,Cj)。設路徑距離為F,則目標函數為：

(1)

基于此，人工魚群算法是求解TSP問題的一個有效方法。

1.2 遞減反饋策略

本文經多次實驗發(fā)現(xiàn)，覓食行為的視野對收斂速度影響較大，而且大視野可使人工魚的全局搜索能力強，覓食行為較頻繁；小視野可使局部搜索能力強，覓食行為減弱而追尾行為相對頻繁。故本文以最大迭代次數M的一半為界，將整個迭代過程分為前期和后期，在迭代前期將覓食行為的初始視野V0設置為較大值。為了減小算法陷入局部極值點鄰域無法跳出的概率，視野隨著迭代數的增加呈指數式遞減，當迭代次數達到閾值K時將視野范圍限定為終止視野Vf。視野遞減策略公式為：

(2)

其中k為當前迭代數，λ為遞減指數。因為人工魚只和視野內的其他個體交流信息，所以隨著視野逐漸減小，會形成幾個孤立的子魚群。為了防止算法陷入局部極值，繼而設置反饋策略：若從K+1代開始至M/2代時無更優(yōu)解，則迭代后期將視野重新設定回初始值V0，V(M/2)+1=V0依次按照式(3)變化；反之，視野仍限定為Vf。

(3)

另外，人工魚行為方式的選擇采用目標函數最小的準則?；爵~群算法中的缺省行為為隨機行為，存在迂回搜索的弊端，降低尋優(yōu)速度，本文將隨機行為改進為停止行為。

1.3 改進算法流程

步驟1魚群初始化。設置魚群規(guī)模為N、最大迭代次數M、人工魚的移動步長Step、覓食行為的最大試探次數try_number和擁擠度因子δ。當迭代次數從k=0開始計數時，生成N條人工魚個體，即初始魚群，每條人工魚代表待優(yōu)化問題的路徑，是在給定范圍內產生的隨機實數數組。設待優(yōu)化問題為n元參數，則要產生一個n行N列的初始序列，每列表示每條人工魚的n個參數。

步驟2公告板初始化。計算人工魚群的目標函數值，并將最優(yōu)魚狀態(tài)寫入公告板。

步驟3追尾行為和群聚行為。設人工魚的當前狀態(tài)為Xi，在其視野范圍內探測鄰居數目n以及狀態(tài)最優(yōu)的鄰居Xj、中心位置Xc。若此鄰居的食物濃度較高且周圍不太擁擠，即Yj

(4)

若Yc

(5)

比較兩種行為的尋優(yōu)結果，擇優(yōu)而行。若兩種行為都沒有使食物濃度提高，則執(zhí)行覓食行為(其中Y表示食物濃度，即目標函數)否則執(zhí)行覓食行為。

步驟4覓食行為。設人工魚當前狀態(tài)Xi，在視野內隨機選擇狀態(tài)Xl=Xi+rand()·Visual，視野初始值設為V0，隨著迭代次數按照式(2)和式(3)變化。若Yl>Yi,則向該方向前進一步，否則維持當前狀態(tài)不動。判斷是否滿足前進條件，若嘗試次數達到try_number仍不能前行，則隨機移動一步。

(6)

步驟5判斷是否達到終止條件(迭代次數達到M或尋優(yōu)結果滿足精度要求)，若是，則更新公告板，輸出最優(yōu)結果，算法終止；若否，則進入下一次迭代過程。

2 仿真實驗及應用

2.1 算例及參數選取

為了驗證引入遞減反饋策略人工魚群算法的有效性和先進性，本文從TSPLIB選取Ulysses22、Oliver30、Att48、eil76和Pr136五個標準TSP實例進行測試(http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsp/)。TSP問題所選擇的路徑數目與城市規(guī)模呈指數式增長的關系，當城市規(guī)模較小時用最簡單的枚舉法即可獲得最短路徑；當城市數目較大時，多數算法無法獲得全局最優(yōu)解，往往以算法的最優(yōu)解與TSPLIB給出的最優(yōu)解之接近程度作為算法計算精度之考量。本文采用Matlab 7.1為編程工具實現(xiàn)算法，實驗分別用基本魚群算法AFSA和改進算法各自進行20次測試，并將求解結果與文獻進行對比。參數設置為：人工魚數目N=10，Ulysses22的最大迭代次數M設為500，Oliver30、Att48、eil76和Pr136的最大迭代次數M設為1000，最多試探次數try_number=15，擁擠度因子δ=0.618。本文引入的反饋遞減策略參數包括初始視野V0、終止視野Vf、迭代閾值K、遞減指數λ、步長step。經過多次實驗對比，五個TSP實例對應的最優(yōu)參數集{V0,Vf,K,λ,step}分別設置為：{1.5,0.3,80,2,Vk/3}{2.5,0.5,300,2.2,Vk/5}{2.8,0.6,600,2.8,Vk/20}{5,1,630,1.5,Vk/2}{20,2,280,1.5,Vk/4}。

2.2 實驗結果分析

五個TSP實例求解結果如表1所示。TSPLIB給出的五個標準TSP問題全局最優(yōu)解分別為74、420、33 522、538和96 772。前三個TSP實例求解結果與文獻[3]的改進魚群算法對比，后兩個TSP實例與文獻[11]的改進蟻群算法對比。收斂率定義為：20次實驗中收斂次數與實驗次數之比，每次運行的最終解和全局最優(yōu)解誤差在3.5%之內則認為算法收斂。由表1計算結果可看出：對于同一TSP問題，利用本文改進算法求解的最優(yōu)值最接近TSPLIB所給結果，相對誤差分別為1.7699%、0.8906%、0.1966%、0.0318%和0.0041%，說明本文算法在計算精度方面有所提高?？v向對比五個TSP問題的城市數目與其平均相對誤差之關系，利用基本魚群算法兩者關系為近似正比，而文獻[3，11]和本文改進算法為近似反比，并且本文改進算法的平均相對誤差更小，分別為2.0657%、0.9758%、1.3825%、0.3183%和0.3154%，說明本文改進算法具有較高的求解精度，尤其在求解較大規(guī)模TSP問題中更能體現(xiàn)出先進性?；爵~群算法的收斂率隨著TSP問題復雜程度增加而迅速減小為0，當城市數目達到48時，文獻[9]的改進算法收斂率急劇降低至25%，而利用本文改進魚群算法求解結果全部滿足收斂條件(表1中，——表示該數據該文獻未提及)。

表1 五個TSP實例求解結果

五個TSP問題的最優(yōu)解巡回路徑分別如圖1-圖5所示，圖中橫坐標和縱坐標分別表示城市的經度和緯度，單位為弧度(下同)。五個TSP問題的最優(yōu)解收斂曲線分別如圖6-圖10所示，橫坐標和縱坐標分別表示迭代次數和最優(yōu)值。

圖1 Ulysses22的最優(yōu)解巡回路徑

圖2 Oliver30的最優(yōu)解巡回路徑

圖3 Att48的最優(yōu)解巡回路徑

圖4 eil76的最優(yōu)解巡回路徑

圖5 Pr136的最優(yōu)解巡回路徑

圖6 Ulysses22的最優(yōu)解收斂曲線

圖7 Oliver30的最優(yōu)解收斂曲線

圖9 Eil76的最優(yōu)解收斂曲線

圖10 Pr136的最優(yōu)解收斂曲線

由改進算法的收斂曲線圖可看出，視野遞減策略使算法初期的迭代曲線非常陡峭，算法可以很快找到局部最優(yōu)解，意味著改進算法保證了初期具有較好的搜優(yōu)速度，而且并未出現(xiàn)明顯的振蕩現(xiàn)象。另外，五個TSP實例運行20次的迭代次數范圍不大，分別為[338,408]、[296,364]、[756,818]、[749，803]和[754,815]，說明改進算法具備穩(wěn)定的全局搜優(yōu)性能。

3 改進算法求解最短遍歷路徑

本文改進算法研究目的是為了更好地應用于實際問題求解。截止2014年12月底，國家旅游局評定出山西省4A(含5A)級旅游景區(qū)共47處，其中4A級旅游區(qū)42處，5A級旅游景區(qū)5處，位置分布及局部放大圖如圖11所示。這些風景區(qū)分布在山西省各地，是全省旅游資源的精華所在。假設一個外地旅行者，從山西省任一處4A級景點出發(fā)，每個景點去一次且僅去一次，游覽完所有景點返回出發(fā)點，希望路線總長度最短，需要在最短的時間內規(guī)劃一條最佳出行路線。本文改進算法可以很好地解決山西省國家4A級以上風景區(qū)為地點構成的TSP問題。設置人工魚數目N=10，最大迭代次數M=500，最多試探次數try_number=15，擁擠度因子δ=0.618，經過多次實驗對比，最優(yōu)參數集設置為{4,1.5,100,1.8,Vk/10}，最優(yōu)解的巡回路徑和收斂曲線分別如圖12和圖14所示。因晉中市4A級景區(qū)分布較為集中，利用Matlab放大鏡功能需要將圖11中經度[111.5,113]和緯度[36.5,38]區(qū)域、經度[112.175,112.187]和緯度[37.2,37.212]區(qū)域進行局部放大，如圖13所示。計算結果如下：20次運算過程迭代次數范圍為[243,378]，平均迭代次數329.18，最優(yōu)解為18.1314，最差解為21.7717，平均值為19.0816；按照巡回路徑最優(yōu)解輸入各景點的經緯度，在Matlab中調用distance 函數計算出最短遍歷路徑長度為 1658.12798 km。

圖11 山西省4A(含5A)級旅游景區(qū)分布圖

圖12 山西省4A(含5A)級風景區(qū)最優(yōu)解巡回路徑

圖13 圖12的局部放大圖

圖14 山西省4A(含5A)級風景區(qū)最優(yōu)解收斂曲線

4 結 語

本文在基本魚群算法的基礎上引入遞減指數λ和迭代閾值K，對覓食行為的視野設置遞減反饋策略：為了保證算法的尋優(yōu)速度，視野初值設置為較大值；為了提高計算精度，視野在優(yōu)化過程前期隨迭代次數遞減；為了避免陷入局部極值，在優(yōu)化過程后期設置反饋策略，視野根據反饋信息適時變化。通過對五個具有代表性的TSP實例進行仿真實驗，并與基本魚群算法以及其他文獻改進算法結果對比分析，尋優(yōu)過程和仿真結果表明：本文提出的改進魚群算法在搜優(yōu)精度、收斂速度、穩(wěn)定性等方面有明顯優(yōu)勢。最后將其應用于求解最短遍歷路徑問題。然而改進算法的視野最優(yōu)參數集直接影響算法性能，本文選取的參數只是在有限次實驗對比過程中相對最優(yōu)，所以亟需進一步研究最優(yōu)視野參數集選取的合理方法。

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

[2] 陳廷斌,張奇松,楊曉光.基于改進人工勢場—魚群算法的LBS最短路徑修正研究[J].計算機應用與軟件,2015,32(6):259-262.

[3] 朱命昊,厙向陽.求解旅行商問題的改進人工魚群算法[J].計算機應用研究,2010,27(10):3734-3736.

[4] 張洪青,卜濤.基于和聲搜索的混合人工魚群算法[J].計算機應用與軟件,2014,31(3):269-272,285.

[5] 孫偉,朱正禮,鄭磊,等.基于人工魚群和微粒群混合算法的WSN節(jié)點部署策略[J].計算機科學,2012,39(11):83-85,121.

[6] Zhou Yongquan,Huang Huajuan,Zhang Junli.Hybrid artificial fish swarm algorithm for solving Ill-Conditioned linear systems of equations[J].Intelligent Computing and Information Science,2011:656-661.

[7] Ma Xianmin,Liu Ni.Improved artificial fish swarm algorithm based on adaptive vision for solving the shortest path problem[J].Journal on Communications,2014,35(1):1-6.

[8] 朱旭輝,倪志偉,程美英.變步長自適應的改進人工魚群算法[J].計算機科學,2015,42(2):210-216,246.

[9] 王波.基于自適應t分布混合變異的人工魚群算法[J].計算機工程與科學,2013,35(4):120-124.

[10] 王培崇,李麗榮,賀毅朝,等.一種基于Logistic模型的人工魚群算法[J].中國科技論文,2013,8(7):668-671.

[11] 宋錦娟,白艷萍.一種改進的蟻群算法及其在TSP中的應用[J].數學的實踐與認識,2012,42(18):154-162.

IMPROVING ARTIFICIAL FISH SWARM ALGORITHM BASED ON DEGRESSION FEEDBACK VISION AND ITS APPLICATION

Wang li Gong Jianping

(School of Information Technology and Engineering,Jinzhong University,Jinzhong 030619,Shanxi,China)

Foraging behaviour of basic artificial fish swarm algorithm is the basis of algorithm convergence. A fixed foraging vision may lead to the disadvantages of low optimising efficiency and being prone to local extremums. To overcome such disadvantages, we introduced the vision degression feedback strategy, in which the visual field timely changes along with the times of iteration and the feedback information of optimisation aiming at balancing global and local search abilities. By testing five TSP examples, results suggested that the proposed algorithm improves the calculation accuracy while ensuring the convergence rate. At last, we applied the improved algorithm to solving the problem of the shortest path traversal of AAAA grade tourist attractions (including 5A) in Shanxi province.

Artificial fish swarm algorithm Degression of vision Feedback strategy Optimal path

2015-09-02。教育部高等學校專業(yè)教學指導委員會項目(JZW-14-JW-09)；山西省高等學校教學改革項目(J2014108)；晉中學院教學改革創(chuàng)新項目(ZL2016jg04)。王麗，講師，主研領域：智能優(yōu)化算法，計算物理。宮建平，教授。

TP18

A

10.3969/j.issn.1000-386x.2016.11.053