基于4VA信息素的蝗蟲優(yōu)化算法*

趙艷玲，王 勇,2,3**，袁 磊

(1.廣西民族大學(xué)人工智能學(xué)院，廣西南寧 530006；2.廣西混雜計算與集成電路設(shè)計分析重點實驗室，廣西南寧 530006；3.廣西高校復(fù)雜系統(tǒng)與智能計算重點實驗室，廣西南寧 530006)

群智能優(yōu)化算法是人們通過對自然界中某些生物體的功能、特點和作用機理的觀察和理解，或者對自然界中某些自然或物理現(xiàn)象的分析和研究，從中挖掘出其中蘊含的運行規(guī)律或機制，并基于對其運行規(guī)律或機制的模擬而構(gòu)建的隨機搜索算法。迄今，國內(nèi)外學(xué)者先后提出了諸如遺傳算法(GA)[1]、粒子群算法(PSO)[2]、蟻群算法(ACO)[3,4]、人工蜂群算法(ABC)[5]、蝗蟲優(yōu)化算法(Grasshopper Optimization Algorithm,GOA)[6]、正弦余弦算法(SCA)[7]、鯨魚算法(WOA)[8]、蝴蝶優(yōu)化算法(BOA)[9]等群智能優(yōu)化算法。這些群智能優(yōu)化算法的提出為解決工程等的優(yōu)化問題提供了新的技術(shù)支持。

GOA是Saremi等[6]基于對蝗蟲覓食行為的模擬而提出的一種新的群智能隨機優(yōu)化算法。GOA分為勘探和開發(fā)兩個步驟，局部搜索能力較強，但全局搜索能力偏弱，故該算法規(guī)避陷入局部最優(yōu)的能力不強。針對GOA的不足，Yildiz等[10]提出一種改進GOA，通過與精英對立學(xué)習(xí)機制雜交來提高算法的全局搜索能力，并利用工程中的具體優(yōu)化實例來驗證該算法的優(yōu)化性能。Reddy等[11]利用遺傳算子來改善勘探和開發(fā)之間的平衡，利用差分進化策略來指導(dǎo)算法搜索，以提高算法搜索效率。與標(biāo)準(zhǔn)GOA相比較，其改進的GOA在一定程度上提升了優(yōu)化精度和收斂速度，然而提升的程度比較有限，仍有待進一步提高。尹德鑫等[12]利用Fuch初始化種群，通過引入正余弦因子和非線性慣性權(quán)重來提高算法的全局搜索能力，但在一定程度上增加了算法的時間復(fù)雜度。劉奇等[13]利用反向?qū)W習(xí)機制與混沌映射來加快算法的收斂速度，以增強算法的搜索能力，并利用紅細(xì)胞供應(yīng)預(yù)測實例來驗證其改進算法的有效性。李洋州等[14]利用曲線自適應(yīng)和模擬退火算法來提高算法的優(yōu)化性能，其改進GOA的優(yōu)化性能相較于標(biāo)準(zhǔn)GOA有一定的提高，但在收斂精度和優(yōu)化精度方面仍有待進一步提升。何慶等[15]采用分段位置更新方式和利用柯西變異算子與反向?qū)W習(xí)策略對當(dāng)前最優(yōu)位置進行變異更新，提高算法跳出局部最優(yōu)能力，將均勻分布函數(shù)引入非線性控制參數(shù)，平衡算法全局探索與局部開發(fā)，但對當(dāng)前最優(yōu)位置進行變異更新會增加算法的迭代次數(shù)，從而增加算法的時間復(fù)雜度。Luo等[16]通過引入高斯變異、列維飛行策略和反向?qū)W習(xí)策略來提高算法的收斂速度，但這樣處理會增加算法的時間復(fù)雜度。林杰等[17]根據(jù)概率轉(zhuǎn)換采用不同的位置更新方式，利用正弦余弦來平衡全局探索和局部開發(fā)，通過變異選擇對最優(yōu)解進行變異，提高算法的優(yōu)化精度。然而采用變異選擇對最優(yōu)解進行變異會增加算法的迭代次數(shù)，從而增加算法的時間復(fù)雜度。楊文珍等[18]利用非線性曲線函數(shù)去平衡算法的局部開發(fā)和全局探索，引入擾動因子并利用高斯分布增加種群多樣性，提高算法的收斂速度，但采用擾動因子和高斯分布增加種群多樣性策略會增加算法的時間復(fù)雜度。上述文獻(xiàn)[10-18]提出的各種版本的改進GOA相較于標(biāo)準(zhǔn)GOA，雖然在優(yōu)化精度方面有一定的改善，但是仍存在早熟收斂問題，跳出局部極值的能力仍有待提高。本研究針對這些問題，提出一種基于4-乙烯基苯甲醚(4-vinylanisole,4VA)信息素的蝗蟲優(yōu)化算法(Grasshopper Optimization Algorithm Based on 4-vinylanisole Pheromone,VAGOA)。根據(jù)蝗蟲生活習(xí)性和行為特征的最新研究發(fā)現(xiàn)[19,20]，結(jié)合標(biāo)準(zhǔn)GOA模型，基于4VA是蝗蟲聚集信息素，設(shè)計4VA信息素表達(dá)式，對于不同蝗蟲群體(群居型蝗蟲和散居型蝗蟲)分別采用不同的搜索策略，以平衡全局探索和局部開發(fā)，使算法的全局探索能力和局部開發(fā)能力均得到提升，并通過數(shù)值實例仿真驗證本研究算法的優(yōu)化性能。

1 蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法(GOA)[6]的基本思想：將蝗蟲的生命周期分為幼蟲和成蟲兩個階段。在幼蟲階段，蝗蟲具有跳躍步幅小、移動緩慢、小范圍覓食活動的特征，傾向于局部搜索；在成蟲階段，蝗蟲具有跳躍步幅大、移動快速、大范圍覓食活動的特征，傾向于全局搜索。

GOA模型及步驟如下。

Input：蝗蟲種群規(guī)模N，搜索空間維數(shù)dim，最大迭代次數(shù)Tmax，參數(shù)cmax和cmin。

①初始化種群Xi，i=1，…，N。

③依公式(1)更新參數(shù)c：

c=cmax-t(cmax-cmin)/Tmax，

(1)

其中，cmax和cmin分別表示參數(shù)c的最大值和最小值，t為當(dāng)前迭代次數(shù)。

④蝗蟲個體依公式(4)更新位置：

(2)

(3)

(4)

其中：s(r)表示種群社交影響強度，f為吸引力強度，l為吸引力范圍(GOA在仿真實驗中取f=0.5，l=1.5)；ubd和lbd分別表示第d維度的上下界，dij=

⑥判斷是否滿足終止條件，如果是，則轉(zhuǎn)步驟⑦；否則,重復(fù)步驟③-⑤。

2 采用4VA信息素的蝗蟲優(yōu)化算法

2.1 構(gòu)建算法模型的主要依據(jù)

根據(jù)Guo等[19]和Chen等[20]的最新研究，蝗蟲除具有前面已提及的特征外，還具有以下活動習(xí)性和生物行為特征：①4VA是蝗蟲的聚集信息素。②3′-磷酸腺苷-5′-磷酰硫酸(PAPS)生物合成過程能有效誘導(dǎo)蝗蟲的行為轉(zhuǎn)變。抑制PAPS的合成可以促使蝗蟲行為從群居狀態(tài)轉(zhuǎn)變?yōu)楠毦訝顟B(tài)。③根據(jù)活動行為狀態(tài)，蝗蟲分為群居型蝗蟲和散居型蝗蟲兩種。④群居型蝗蟲行為的亢奮是源于4VA信息素的分泌，4VA信息素專門由群居蝗蟲釋放，4-5只孤立蝗蟲的聚集就會觸發(fā)4VA信息素的產(chǎn)生，而且4VA信息素對蝗蟲的吸引力極強。⑤釋放4VA信息素的濃度與群居蝗蟲發(fā)育密度有關(guān)，4VA信息素生物合成對于調(diào)節(jié)遷徙蝗蟲的嗅覺吸引力和移動性至關(guān)重要。⑥4VA信息素對群居型蝗蟲和散居型蝗蟲的不同發(fā)育階段都有很強的吸引力，能夠響應(yīng)蝗蟲種群密度的變化，隨著種群密度增加而增加。⑦根據(jù)種群密度顯示出兩個不同的行為階段，即獨居階段和蜂擁而至的群居階段，低密度發(fā)育的獨居期蝗蟲(散居型蝗蟲)具有嗜睡和同種排斥的特征，而高密度發(fā)育的群居期蝗蟲(群居型蝗蟲)具有高流動性和同種吸引的特征。⑧散居蝗蟲背部是綠色的，蝗蟲從散居變成群居一段時間后，背部就會從綠色轉(zhuǎn)換為黑色，行為也會變得亢奮起來。此時的蝗蟲胃口很大，所過之處食物全被一掃而空。

本研究基于以上蝗蟲活動習(xí)性和生物行為特征，設(shè)計一種新的采用4VA信息素的蝗蟲優(yōu)化算法。

2.2 構(gòu)建算法模型

2.2.1 4VA信息素表達(dá)式的設(shè)計

4VA是蝗蟲聚集信息素，能夠響應(yīng)蝗蟲種群密度的變化，其濃度隨著種群密度的增加而增加。因此，某處(蝗蟲愛吃的)食物越豐富，該處引來的蝗蟲就越多，從而該處蝗蟲釋放出的4VA信息素濃度也就越高。即哪里的食物越豐富，哪里的4VA信息素濃度就越高。基于此，設(shè)群體于t時刻找到最優(yōu)位置，即食物最豐富、4VA信息素濃度最大位置是xbest(t)，i個體于t時刻位于xi(t)。由于i個體嗅覺受體在t時刻聞到4VA信息素的強弱與位置xbest(t)的4VA信息素濃度、距離有關(guān)，也與其嗅覺受體感應(yīng)能力有關(guān)，故設(shè)計4VA信息素表達(dá)式如下：

(5)

其中，β0=2，qi=|f(xbest(t))-f(xi(t))|，

f(xbest(t))表示位置xbest(t)的適應(yīng)度值(即此處4VA信息素濃度)，f(xi(t))表示i個體的嗅覺受體感應(yīng)能力(以適應(yīng)度值表示)；hi=‖xbest(t)-xi(t)‖為xbest(t)與xi(t)的距離，Tmax為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。

公式(5)說明i個體嗅覺感應(yīng)到4VA信息素的強弱，不僅跟其與xbest(t)的距離、與其嗅覺受體感應(yīng)能力和位置xbest(t)的4VA信息素濃度有關(guān)，還跟時間有關(guān)，4VA信息素隨時間的增加而逐漸變?nèi)酢?/p>

2.2.2 不同蝗蟲群體搜索方法的設(shè)計

①群居型蝗蟲搜索方法設(shè)計。由于4VA信息素由群居型蝗蟲釋放，群居型蝗蟲具有同種吸引特征，故群居型蝗蟲釋放的4VA信息素會誘惑其他蝗蟲前來聚集(圖1)。因此，本研究結(jié)合GOA的公式(4)，將4VA信息素與高斯分布相結(jié)合，設(shè)計群居型蝗蟲搜索方法如下。

首先利用正態(tài)分布選取數(shù)a：

a～N(0,σ2)。

(6)

在仿真實驗中，取σ=t/Tmax。然后按公式(7)更新位置。

(7)

設(shè)xbest(t)=[xbest,1(t),…，xbest,D(t)]為群體于t時刻找到的最優(yōu)位置，此時xbest(t)的4VA信息素濃度最大，故有一部分群居型蝗蟲被誘惑到xbest(t)的周圍覓食。針對這部分蝗蟲，本研究設(shè)計其位置更新公式如下：

圖1 4VA信息素誘惑蝗蟲聚集[19]Fig.1 Locusts being lured by 4VA pheromone to gather

xi,j(t+1)=ξi,j，

(8)

其中，ξi,j為[xbest,j(t)-ε,xbest,j(t)+ε]中的隨機數(shù)，0<ε?1，j=1,…,D。在仿真實驗中，取ε=

1/t2。

②散居型蝗蟲搜索方法設(shè)計。盡管處于獨居狀態(tài)的蝗蟲的覓食活動具有隨意性，但4VA信息素對散居型蝗蟲的不同發(fā)育階段都有很強的吸引力。因此，當(dāng)散居型蝗蟲聞到其他蝗蟲釋放的4VA氣味時，就會朝4VA散發(fā)地進發(fā)。針對散居型蝗蟲，本研究設(shè)計其位置更新公式如下：

(9)

2.3 群居型蝗蟲與散居型蝗蟲的區(qū)分方法

由于“群居型蝗蟲胃口大，所過之處食物全被一掃而空”，故認(rèn)為群居型蝗蟲的搜索(覓食)能力相對較強；“散居型蝗蟲具有嗜睡和同種排斥特征”，故認(rèn)為散居型蝗蟲的搜索(覓食)能力相對較弱。因此，本研究根據(jù)蝗蟲個體覓食能力強弱來區(qū)分其是群居型蝗蟲還是散居型蝗蟲。

區(qū)分方法如下：設(shè)至t時刻群體找到的最優(yōu)位置為xbest(t)，相應(yīng)的適應(yīng)度值為f(xbest(t))。首先給定閾值ρ>1(本研究在實驗中取ρ=1.4)。

Rule 1：若f(xi(t))≤2f(xbest(t))，則認(rèn)為i蝗蟲為群居蝗蟲。此時，若ρ·f(xbest(t))

Rule 2：若2f(xbest(t))≤f(xi(t))，則認(rèn)為i蝗蟲為散居蝗蟲，并按公式(9)更新位置。

2.4 算法實現(xiàn)步驟

本研究算法步驟和流程如下。

輸入：種群規(guī)模N，搜索空間維數(shù)D，最大迭代次數(shù)Tmax。

步驟 1：初始化種群Xi，i=1，…，N。

步驟 3：按群居蝗蟲與散居蝗蟲的區(qū)分方法將種群分為群居蝗蟲與散居蝗蟲兩個子群。

步驟 4：群居蝗蟲按“Rule 1”選擇公式(6)、(7)或公式(8)更新位置；散居蝗蟲按公式(9)更新位置。

步驟 6：判斷是否滿足停止條件，若滿足，則轉(zhuǎn)Step 7；否則重復(fù)Step 3-Step 5。

3 實驗仿真與結(jié)果分析

3.1 測試函數(shù)

為了測試本研究算法(VAGOA)的優(yōu)化性能，將VAGOA與標(biāo)準(zhǔn)GOA[6]、PSO[2]，以及從各種改進版本GOA當(dāng)中選擇的比較有代表性的SA_CAGOA[14]和HCUGOA[15]進行算法數(shù)值實驗對比分析。選取12個典型的基準(zhǔn)測試函數(shù)(表1)作為本次算法性能測試分析(均為求最小值問題)。

表1 基準(zhǔn)測試函數(shù)Table 1 Benchmark function

續(xù)表

Continued table

3.2 結(jié)果與分析

為保證實驗結(jié)果的對照與比較的客觀和公平，5種算法統(tǒng)一設(shè)置群體規(guī)模為30，最大迭代次數(shù)為200。對于GOA、HCUGOA、SA_CAGOA 3種算法，其參數(shù)設(shè)置與相應(yīng)的文獻(xiàn)保持一致，即cmax=0.1，cmin=0.000 04。對于SA_CAGOA，設(shè)置初始溫度T0=100，結(jié)束溫度T=1，退火系數(shù)r=0.95。

為了驗證本研究算法(VAGOA)的性能，對表1中的12個基準(zhǔn)測試函數(shù)進行求解。表1中既有單峰函數(shù)，也有多峰函數(shù)。單峰函數(shù)主要用來測試算法的收斂速度，多峰函數(shù)主要用來測試算法的全局搜索能力(探索和開發(fā)能力)和規(guī)避陷入局部最優(yōu)的能力。本研究以最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差作為算法性能評價指標(biāo)，這些評價指標(biāo)總體上反映了算法優(yōu)化能力的強弱和算法穩(wěn)定性的優(yōu)劣。為了避免隨機性對實驗結(jié)果的影響，本研究在數(shù)值實驗中將5種算法對每個測試函數(shù)均獨立進行30次實驗，并記錄最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差等實驗數(shù)據(jù)。高維測試函數(shù)(F1-F10)實驗結(jié)果比較數(shù)據(jù)見表2，低維測試函數(shù)(F11-F12)實驗結(jié)果比較數(shù)據(jù)見表3。

表2 高維測試函數(shù)(F1-F10)實驗結(jié)果比較Table 2 Comparison of experimental results of high dimensional test function (F1-F10)

續(xù)表

Continued table

續(xù)表

Continued table

表3 低維測試函數(shù)(F11-F12)實驗結(jié)果比較Table 3 Comparison of experimental results of low dimensional test function (F11-F12)

針對30，100和200維，本研究算法(VAGOA)找到F1-F9的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差均與理論最優(yōu)值相同，HCUGOA找到F1-F8的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差也與理論最優(yōu)值相同。VAGOA與HCUGOA找到F10的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差相同，其他3種算法均沒有找到這10個測試函數(shù)的理論最優(yōu)值(表2)。基于以上分析，不論是求解單峰還是多峰優(yōu)化問題，相較于其他4種算法，VAGOA全局尋優(yōu)能力和規(guī)避陷入局部最優(yōu)能力最強、優(yōu)化精度最高、穩(wěn)定性更好。

本研究算法(VAGOA)與HCUGOA找到F11和F12的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差均與理論最優(yōu)值相等，但VAGOA至41次迭代就已經(jīng)找到理論最優(yōu)解，而HCUGOA至175次迭代才找到理論最優(yōu)解，其他3種算法均沒有找到理論最優(yōu)解(表3)。基于此，針對低維度優(yōu)化問題，說明VAGOA相較于4種對比算法具有更快的全局收斂速度，收斂精度更高，穩(wěn)定性更好。

為了更直觀地對比本研究算法(VAGOA)、GOA、PSO、HCUGOA和SA_CAGOA 5種算法各自的全局收斂速度和全局搜索能力，給出5種算法求解以上12個基準(zhǔn)測試函數(shù)的適應(yīng)度進化曲線對比圖(圖2)。相較于GOA、PSO、HCUGOA、SA_CAGOA 4種算法，VAGOA的進化曲線均位于最下方位置，且下降趨勢為5種算法中最快，沒有出現(xiàn)停滯狀態(tài)；VAGOA的F1-F9收斂曲線均到達(dá)理論最優(yōu)位置，F(xiàn)10收斂曲線非常接近理論最優(yōu)位置(圖2)。說明本研究算法(VAGOA)在搜索后期沒有陷入局部最優(yōu)。基于以上分析，相較于GOA、PSO、HCUGOA、SA_CAGOA 4種算法，VAGOA的全局收斂速度明顯更快，規(guī)避陷入局部最優(yōu)的能力更強。

圖2 5種算法進化曲線對比Fig.2 Comparison of evolution curves of five algorithms

4 結(jié)論

本研究從以下方面對GOA進行了優(yōu)化：①根據(jù)確定的搜索方法規(guī)則，群體中位置較優(yōu)者采用聚集搜索方法，而位置較劣者則采用分散搜索方法。②從確定的搜索方法規(guī)則上看，蝗蟲個體可根據(jù)自身當(dāng)前位置的優(yōu)劣來確定下一步的搜索方法，使其能更快地搜尋到食物源，以增強個體的搜索能力。③對群居型蝗蟲和散居型蝗蟲分別采用不同的搜索方法，使得算法能基于群體信息反饋，及時分配群居型蝗蟲個體數(shù)和散居型蝗蟲個體數(shù)，使群體中從事探索活動的個體數(shù)與從事開發(fā)活動的個體數(shù)得到適當(dāng)分配，也使種群的多樣性得到有效保持，從而提升算法的全局搜索能力。④利用4VA信息素隨時間增加而逐漸變?nèi)踹@一特征，確保群體中時刻都有部分個體開展隨機游走(搜索)活動，在保持種群多樣性的同時，又增強算法規(guī)避陷入局部最優(yōu)的能力。

本研究針對GOA存在的不足，基于蝗蟲活動習(xí)性和生物行為特征，提出基于4VA信息素的蝗蟲優(yōu)化算法(VAGOA)。對不同蝗蟲群體(群居型蝗蟲和散居型蝗蟲)分別采用不同的搜索策略，以平衡全局探索和局部開發(fā)，使算法全局探索能力和局部開發(fā)能力均得到有效提升,增強了算法的全局尋優(yōu)能力和規(guī)避陷入局部最優(yōu)的能力。通過求解12個基準(zhǔn)測試函數(shù)，驗證了VAGOA明顯比GOA、PSO、HCUGOA、SA_CAGOA 4種算法具有更快的全局收斂速度、更強的規(guī)避陷入局部最優(yōu)的能力、更好的全局搜索能力和穩(wěn)定性。在后續(xù)研究中，將考慮把VAGOA應(yīng)用于求解TSP優(yōu)化問題,進一步驗證VAGOA的性能。