基于禁忌搜索的自適應(yīng)人工魚群優(yōu)化算法

陳靜靜，劉 升

(上海工程技術(shù)大學(xué)，上海 201620)

0 引 言

人工魚群算法(artificial fish swarm algorithm，AFSA)[1]是一種智能的仿生優(yōu)化算法，基于魚群及其覓食習(xí)慣而衍生出來的算法，該算法具有對初值不敏感、魯棒性高、全局搜索能力強(qiáng)且易與其他方法結(jié)合等優(yōu)點(diǎn)，目前在傳感器網(wǎng)絡(luò)優(yōu)化[2]、水質(zhì)參數(shù)識別[3]、參數(shù)優(yōu)化[4]以及組合優(yōu)化[5]等多個工程領(lǐng)域取得了良好效果。 但AFSA算法也存在前期收斂速度快、 后期盲目性強(qiáng)且易陷入局部極值、解精度低等問題。針對上述人工魚群算法的缺點(diǎn)，目前許多學(xué)者提出了改進(jìn)策略，主要包括三類：自適應(yīng)策略、變異策略和混合算法策略[6]。自適應(yīng)策略主要是對參數(shù)的調(diào)整，例如文獻(xiàn)[7-9]自適應(yīng)調(diào)整人工魚的參數(shù)，保證算法前期有較強(qiáng)的全局探索能力，迭代后期有較好的局部尋優(yōu)能力，但當(dāng)魚群尋優(yōu)停滯不前，很難擺脫局部困境。為了增加魚群的多樣性，降低人工魚陷入早熟的可能性，文獻(xiàn)[10]提出了一種最優(yōu)解引導(dǎo)的高斯變異機(jī)制。人工魚群算法除了可以從自身方面進(jìn)行改進(jìn)外，還可以借助其他算法的優(yōu)點(diǎn)來彌補(bǔ)自身的不足，文獻(xiàn)[11]利用模擬退火較強(qiáng)的局部尋優(yōu)能力來改善人工魚群迭代后期盲目搜索、尋優(yōu)精度低等問題。文獻(xiàn)[12]將人工魚群算法與和聲搜索算法進(jìn)行融合，提出了一種新的混合算法，相比單一算法，混合算法明顯提高了尋優(yōu)精度、降低了算法復(fù)雜度，全局搜索能力也有所增強(qiáng)。文獻(xiàn)[13-14]提出了人工魚群算法與粒子群算法結(jié)合的混合優(yōu)化算法，該混合算法綜合利用人工魚群算法較好的全局搜索能力和粒子群算法的局部快速收斂性、易實(shí)現(xiàn)性等優(yōu)點(diǎn)，彌補(bǔ)人工魚群算法和粒子群算法在后期尋優(yōu)過程中存在的不足。雖然這些改進(jìn)算法都不同程度地增強(qiáng)了AFSA的尋優(yōu)性能，但是隨著待優(yōu)化問題復(fù)雜程度和規(guī)模的不斷擴(kuò)大，對AFSA及其改進(jìn)算法尋優(yōu)能力的要求越來越高。

為了能在一定程度上提升AFSA求解復(fù)雜優(yōu)化問題的能力，該文試圖提出一種基于禁忌搜索的自適應(yīng)人工魚優(yōu)化算法(Taboo search based adaptive artificial fish swarm optimization algorithm，TSAFSA)。該算法首先對魚群行為的視野和步長進(jìn)行了改進(jìn)。在迭代尋優(yōu)過程中，視野和步長按照各自設(shè)定的衰減函數(shù)進(jìn)行遞減，既提高了算法的全局搜索能力，也降低了算法后期陷入局部極值的概率；為了改善隨機(jī)行為具有盲目性這一狀況，該文引入了更符合魚群自由游動的levy飛行機(jī)制；當(dāng)AFSA尋優(yōu)停滯不前時，就以當(dāng)前最優(yōu)個體為初始值，建立禁忌區(qū)域，產(chǎn)生領(lǐng)域解，幫助魚群跳出“困境”。最后通過經(jīng)典測試函數(shù)進(jìn)行驗證，實(shí)驗結(jié)果表明TSAFSA算法具有較好的尋優(yōu)性能。

1 基本AFSA算法

1.1 相關(guān)定義

人工魚群算法是基于動物行為的一種新型仿生優(yōu)化算法，魚群密度較大的地方，大多是食物較為充足的水域，以這一點(diǎn)為依據(jù)來模擬魚群覓食、聚群、追尾等行為，以期實(shí)現(xiàn)尋優(yōu)的目的。假設(shè)第i條人工魚可表示為Xi={x1,x2,…,xn}，適應(yīng)度函數(shù)Y=f(x)(食物濃度)，視野范圍用Visual表示，Step表示移動步長，δ表示擁擠度因子，最大嘗試次數(shù)為try-number，魚群規(guī)模為np，人工魚之間的距離用dij=‖Xj-Xi‖表示，Rand函數(shù)為(0,1)范圍內(nèi)的隨機(jī)數(shù)。

1.2 描述行為

1.2.1 覓食行為

設(shè)某條人工魚目前狀態(tài)為Xi，隨機(jī)的在其視野范圍內(nèi)選擇一條魚Xj，如式(1)所示。針對求最大值的問題，若Yj≥Yi，則向Xj的方向前進(jìn)一步，用式(2)所示；否則，繼續(xù)尋找，如果嘗試次數(shù)m等于try-number次后，仍未找到較優(yōu)狀態(tài)，則隨機(jī)移動一步。可以用式(3)表示。

Xj=Xi+visual×Rand

(1)

(2)

nextX=Xi+step×Rand

(3)

1.2.2 聚群行為

(4)

1.2.3 追尾行為

(5)

2 基于禁忌搜索的自適應(yīng)人工魚群優(yōu)化算法(TSAFSA)

2.1 自適應(yīng)視野和步長

在基本AFSA中，視野visual和步長step都是提前設(shè)定好的固定值。這是兩個非常重要的參數(shù)，直接影響了尋優(yōu)結(jié)果的精度。視野較大時，有利于魚群進(jìn)行全局的探索，加快尋優(yōu)速度；較小的視野范圍，有利于人工魚進(jìn)行局部搜索提高解精度；但是視野過小，不僅影響收斂速度還可能導(dǎo)致算法陷入局部極值。綜合考慮上述條件，該文利用分段函數(shù)對視野進(jìn)行了改進(jìn)，保證了魚群在不同階段具有合適的視域，如式(6)所示。

(6)

為了進(jìn)一步協(xié)調(diào)算法尋優(yōu)速度與解精度的之間的平衡，對魚群的各個行為的步長也進(jìn)行了改進(jìn)，如式(7)所示：

(7)

若滿足覓食行為條件，nextX表示下一較優(yōu)狀態(tài)Xj，如果是執(zhí)行聚群行為，nextX則代表魚群中心Xc，若條件適合追尾行為，那么nextX即為人工魚當(dāng)前視野范圍內(nèi)的最優(yōu)值Xbest， ‖nextX-Xi‖表示當(dāng)前魚Xi與下一狀態(tài)魚間的距離，Rand函數(shù)是為了防止算法收斂過快，降低其陷入局部極值的風(fēng)險。在迭代尋優(yōu)過程，逐漸減少的步長有助于提高算法的尋優(yōu)的穩(wěn)定性及尋優(yōu)精度，但尋優(yōu)速度可能會受到負(fù)面影響。為了提高算法的綜合性能，該文對步長的改進(jìn)不僅加入了衰減因子還在此基礎(chǔ)上考慮了魚間距離，若當(dāng)前魚Xi距離下一狀態(tài)較遠(yuǎn)，則賦給Xi較大的步長，否則移動較小的步長。這種對步長的改進(jìn)，不僅有利于人工魚群跳出局部極值，在對求解精度、尋優(yōu)穩(wěn)定性及迭代周期方面也有一定的積極作用。

2.2 對覓食行為的改進(jìn)

在覓食過程中倘若嘗試了try-number次后仍沒有合適的新解，則執(zhí)行具有l(wèi)evy飛行機(jī)制的自由游動。在解空間的范圍內(nèi)，若人工魚經(jīng)自由游動后依舊沒有探尋到合適的下一狀態(tài)魚，就隨機(jī)移動一步，如式(8)所示。將levy飛行機(jī)制加入到自由游動算子中，既符合生物覓食的本能行為，也加強(qiáng)了算法的全局搜索能力。

nextX=

(8)

2.3 禁忌搜索算法的融合

禁忌算法又稱禁忌搜索算法(Tabu search，TS)，是一種啟發(fā)式算法，最早由美國工程院士Ferd W.Glover在1986年提出[15]。禁忌搜索算法是一種模擬人的思維的智能算法，即人們在尋找東西時，對搜索過的地方短時不會進(jìn)行第二次尋找，而是去其他未搜索過地方尋找，若仍然沒有結(jié)果，可能會再搜索已去過的地方。為了避免陷入局部極值，禁忌搜索加入了一種靈活的“記憶”技術(shù)，即記錄已執(zhí)行過的優(yōu)化過程，并對下一步的搜索方向做出指導(dǎo)，建立禁忌表。表中保存了最近若干次迭代過程中所實(shí)現(xiàn)的移動，凡是處于表中的移動，在當(dāng)前迭代過程中是禁忌進(jìn)行的，這樣可以避免算法重新訪問在最近若干次迭代過程中已經(jīng)訪問過的解，從而防止了循環(huán)，幫助算法擺脫局部最優(yōu)解，當(dāng)禁忌對象滿足一定禁忌長度之后，將被釋放出來重新尋優(yōu)，為了盡可能不錯過產(chǎn)生最優(yōu)解的“移動”，還采用“特赦準(zhǔn)則”的策略[16]。

因AFSA在求解高維且具有多個局部極值點(diǎn)的問題時，容易陷入局部最優(yōu)。為此，該文將禁忌搜索算法融入到了AFSA中，提出了一種基于禁忌搜索的AFSA算法(Tabu search based artificial fish swarm algorithm，TSAFSA)，當(dāng)AFSA尋優(yōu)過程停滯時，以當(dāng)前最優(yōu)值作為禁忌搜索的初值，建立禁忌區(qū)域，并在禁忌區(qū)域內(nèi)生成一個小規(guī)模子群繼續(xù)尋優(yōu)，實(shí)現(xiàn)跳出局部極值的目的。算法基本思路如下：

首先，設(shè)立一個公告板，計算所有人工魚的食物濃度，將最大的食物濃度值Ymax及其對應(yīng)的BestX更新至公告板上。將每次AFSA迭代尋優(yōu)尋得的Ymax與公告板中的數(shù)值進(jìn)行比較，若大于公告板中的數(shù)值，則更新公告板，否則公告板中數(shù)值保持不變。記錄每次迭代尋得的Ymax于BestY中，若BestY中數(shù)據(jù)連續(xù)0.05*maxgen次沒有發(fā)生變化或者變化非常小時，表明算法陷入了停滯，此時魚群很難跳出局部極值，這就需要建立禁忌區(qū)域來改善這一狀況。把當(dāng)前公告板中數(shù)據(jù)對應(yīng)的BestX作為禁忌搜索的初值X0，并記為目前最優(yōu)解Xbest和當(dāng)前解Xnow，將其對應(yīng)的函數(shù)值賦給當(dāng)前解的函數(shù)值Ynow和best so far，設(shè)立禁忌區(qū)域，在禁忌區(qū)域內(nèi)按照levy機(jī)制生成鄰域解，第i個鄰域解的第j維數(shù)據(jù)可表示為Xnear(i,j)=Xi+levyrand(beta)*w*(ub(j)-lb(j))，其中w是權(quán)重，初值為1，按照w=w*0.998進(jìn)行自適應(yīng)更新，ub和lb代表X的邊界限定值。計算領(lǐng)域解的適應(yīng)度，將其中最優(yōu)的作為候選解Xcandidate，對應(yīng)的函數(shù)值為Ycandidate，計算Ycandidate與Ynow的差值β1以及Ycandidate與best so far的差值β2。若候選解沒有改進(jìn)(即β1<0)，就把候選解賦給下一次迭代的當(dāng)前解，更新禁忌表；若β1>0且β2>0時，就把候選解賦給下一次迭代的當(dāng)前解Xnow和目前最優(yōu)解Xbest，并將相應(yīng)對象加入禁忌表，更改禁忌表中各對象的任期；若β1>0但β2<0，判斷Xcandidate是否在禁忌表中：若不在，則把候選解賦給下一次迭代的當(dāng)前解Xnow，并更新禁忌表；若在，則用當(dāng)前Xnow重新產(chǎn)生新的鄰域解。

2.4 算法描述

TSAFSA具體步驟如下：

(a)初始化TSAFSA魚群及各參數(shù)。

(b)AFSA執(zhí)行覓食、追尾、聚群、隨機(jī)行為，視野更新如式(6)，步長更新如式(7)，覓食行為更新如式(8)，進(jìn)入自適應(yīng)迭代尋優(yōu)。

(c)判斷BestY中的數(shù)據(jù)是否滿足2.3所示條件，若滿足，就將此時公告板中的bestX作為禁忌搜索的初值，建立禁忌區(qū)域和禁忌表，進(jìn)入禁忌搜索程序。若不滿足，直接跳到(d)。

(d)輸出TSAFSA尋得的最優(yōu)解及其對應(yīng)目標(biāo)函數(shù)值。

圖1 TSAFSA算法流程

3 實(shí)驗仿真與實(shí)驗結(jié)果

3.1 仿真實(shí)驗環(huán)境

該仿真測試環(huán)境：操作系統(tǒng)為Windows10，CPU為Intel(R)Core(TM)i7-8565U，主頻1.99 GHz,內(nèi)存為8 GB，仿真軟件為Matlab2018b。

3.2 實(shí)驗參數(shù)初始化設(shè)置

該文對基本人工魚群(AFSA)、基于禁忌搜索的自適應(yīng)人工魚(TSAFSA)和基于量子遺傳算法(GQA)三種算法的函數(shù)尋優(yōu)結(jié)果進(jìn)行了對比。統(tǒng)一設(shè)置所有算法的共有參數(shù)，visualmin=0.1，stepmin=0.02，maxgen=200，try-number=50，δ=0.618,禁忌搜索中的候選集個數(shù)為Ca=6，禁忌長度L為5到11之間的隨機(jī)整數(shù)。

3.3 測試函數(shù)

為了驗證TSAFSA的性能，該文選擇以下3個典型的測試函數(shù)進(jìn)行了對比實(shí)驗分析。

F2：f(x,y)=xsin(4πx)+ysin(20πy)，該非線性函數(shù)在給定范圍內(nèi)分布著許多局部極值，在尋優(yōu)過程中易陷入局部區(qū)域或在各局部極值間震蕩；

F3：f(x,y)=cos(x)cos(y)e[-((x-π)2+(y-π)2)]，在[-2π,2π]的范圍內(nèi)取得全局極大值1。

3.4 實(shí)驗結(jié)果及分析

該文選取AFSA、TSAFSA和量子遺傳算法(GQA)三種算法對函數(shù)F1、F2及F3進(jìn)行求解，為了減少隨機(jī)性對實(shí)驗結(jié)果的影響，算法在每個函數(shù)上運(yùn)行30次，記錄其最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差，如表1所示。

表1 各個測試函數(shù)的實(shí)驗結(jié)果

由表1可知，TSAFSA在這三個測試函數(shù)尋優(yōu)過程中，都可以找到或接近最優(yōu)值，尋優(yōu)性能和穩(wěn)定性均較優(yōu)；AFSA在對函數(shù)F2尋優(yōu)時，未搜索到全局最優(yōu)值，其他尋優(yōu)性能參數(shù)也較差；雖然GQA能全部找到三個函數(shù)的全局最大值，但其尋優(yōu)穩(wěn)定性和精度較差。以上結(jié)果表明TSAFSA的尋優(yōu)性能優(yōu)于AFSA、GQA。

3.5 對比其他參考文獻(xiàn)的改進(jìn)算法

為了進(jìn)一步驗證該算法的尋優(yōu)性能，將該算法與其他參考文獻(xiàn)中的算法進(jìn)行相關(guān)的對比實(shí)驗。

F6[8]:f(x,y)=-(1+(x+y+1)2×(19-14x+3x2-14y+6xy+3y2))×(30+(2x-3y)2)×(18-32x+12x2+48y-36xy+27y2)，變量x,y的范圍為[-2，2]，全局極大值為-3；

函數(shù)F4的公共參數(shù)為：種群規(guī)模np=20，人工魚的感知范圍visual=0.1，step=0.008，擁擠因子δ=0.2函數(shù)F5的公共參數(shù)為種群規(guī)模np=20，人工魚的感知范圍visual=10，step=0.1，擁擠因子δ=0.2函數(shù)F4-F5尋優(yōu)對比結(jié)果如表2所示。函數(shù)F6的公共參數(shù)為種群規(guī)模np=50，初始視野visual=5，迭代次數(shù)為200。其中GSO-Powell為利用Powell方法局部優(yōu)化的人工螢火蟲算法，實(shí)驗結(jié)果如表3所示。函數(shù)F7的公共參數(shù)設(shè)置為：種群規(guī)模np=40，感知范圍visual=3.5，嘗試次數(shù)try-number=10，擁擠因子δ=1，最大迭代次數(shù)maxgen=1 000實(shí)驗結(jié)果如表4所示。

表2 函數(shù)F4-F5的對比實(shí)驗結(jié)果

表3 函數(shù)F6的對比實(shí)驗結(jié)果

表4 函數(shù)F7的對比試驗結(jié)果

由表2可得，在對函數(shù)F4、F5的尋優(yōu)過程中，TSAFSA不僅尋優(yōu)精度高，而且搜索速度快。對函數(shù)F6的尋優(yōu)結(jié)果如表3所示，分析實(shí)驗結(jié)果可知，TSAFSA算法的最優(yōu)值、最差值和平均值均優(yōu)于算法AFSA、GSO和GSO-Powell；TSAFSA算法的最優(yōu)值雖然沒有文獻(xiàn)[8]精確，但其他尋優(yōu)參數(shù)均優(yōu)于文獻(xiàn)[8]，整體性能較文獻(xiàn)[8]好一些。表4反映出，針對函數(shù)F7的尋優(yōu)，TSAFSA搜索到的最優(yōu)解較文獻(xiàn)[8]和文獻(xiàn)[9]更加精確。由此可見，該改進(jìn)算法的尋優(yōu)性能在一定程度上確實(shí)有了提高。

4 結(jié)束語

針對基本人工魚群算法存在的缺點(diǎn)及對復(fù)雜函數(shù)尋優(yōu)困難等問題，提出了基于禁忌搜索的自適應(yīng)人工魚優(yōu)化算法。TSAFSA算法首先對視野和步長方面的參數(shù)進(jìn)行了改進(jìn)，隨著迭代過程的進(jìn)行，自適應(yīng)地調(diào)整視野和步長，不僅加快了尋優(yōu)速度同時也提高了解精度；其次，隨機(jī)行為有利于魚群跳出局部極值，但由于其盲目性，也有引起解退化的風(fēng)險，為了改善這一狀況，加入了具有l(wèi)evy飛行機(jī)制的自由游動算子；隨后，當(dāng)尋優(yōu)過程停滯不前時，引入了禁忌搜索的思想，將魚群尋得的最優(yōu)值賦值給禁忌搜索的初始值，設(shè)立禁忌區(qū)域，在禁忌區(qū)域內(nèi)生成小種群繼續(xù)尋優(yōu)，明顯提高了人工魚群的尋優(yōu)精度。最后，通過7個標(biāo)準(zhǔn)測試函數(shù)對各個算法的性能進(jìn)行檢測，仿真結(jié)果證明了TSAFSA算法的確具有較好的尋優(yōu)性能。