王 麗 宮建平

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

?

基于遞減反饋視野的人工魚群算法改進(jìn)與應(yīng)用

王 麗 宮建平

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

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

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

0 引 言

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

1 改進(jìn)的人工魚群算法

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

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

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

(1)

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

1.2 遞減反饋策略

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

(2)

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

(3)

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

1.3 改進(jìn)算法流程

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

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

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

(4)

若Yc

(5)

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

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

(6)

步驟5判斷是否達(dá)到終止條件(迭代次數(shù)達(dá)到M或?qū)?yōu)結(jié)果滿足精度要求)，若是，則更新公告板，輸出最優(yōu)結(jié)果，算法終止；若否，則進(jìn)入下一次迭代過程。

2 仿真實驗及應(yīng)用

2.1 算例及參數(shù)選取

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

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

表1 五個TSP實例求解結(jié)果

五個TSP問題的最優(yōu)解巡回路徑分別如圖1-圖5所示，圖中橫坐標(biāo)和縱坐標(biāo)分別表示城市的經(jīng)度和緯度，單位為弧度(下同)。五個TSP問題的最優(yōu)解收斂曲線分別如圖6-圖10所示，橫坐標(biāo)和縱坐標(biāo)分別表示迭代次數(shù)和最優(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)解收斂曲線

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

3 改進(jìn)算法求解最短遍歷路徑

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

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

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

圖13 圖12的局部放大圖

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

4 結(jié) 語

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

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

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

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

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

[5] 孫偉,朱正禮,鄭磊,等.基于人工魚群和微粒群混合算法的WSN節(jié)點部署策略[J].計算機科學(xué),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] 朱旭輝,倪志偉,程美英.變步長自適應(yīng)的改進(jìn)人工魚群算法[J].計算機科學(xué),2015,42(2):210-216,246.

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

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

[11] 宋錦娟,白艷萍.一種改進(jìn)的蟻群算法及其在TSP中的應(yīng)用[J].數(shù)學(xué)的實踐與認(rèn)識,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。教育部高等學(xué)校專業(yè)教學(xué)指導(dǎo)委員會項目(JZW-14-JW-09)；山西省高等學(xué)校教學(xué)改革項目(J2014108)；晉中學(xué)院教學(xué)改革創(chuàng)新項目(ZL2016jg04)。王麗，講師，主研領(lǐng)域：智能優(yōu)化算法，計算物理。宮建平，教授。

TP18

A

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