基于4VA信息素的蝗蟲優化算法*

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

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

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

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

1 蝗蟲優化算法

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

GOA模型及步驟如下。

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

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

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

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

(1)

其中，cmax和cmin分別表示參數c的最大值和最小值，t為當前迭代次數。

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

(2)

(3)

(4)

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

⑥判斷是否滿足終止條件，如果是，則轉步驟⑦；否則,重復步驟③-⑤。

2 采用4VA信息素的蝗蟲優化算法

2.1 構建算法模型的主要依據

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

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

2.2 構建算法模型

2.2.1 4VA信息素表達式的設計

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

(5)

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

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

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

2.2.2 不同蝗蟲群體搜索方法的設計

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

首先利用正態分布選取數a：

a～N(0,σ2)。

(6)

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

(7)

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

圖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)+ε]中的隨機數，0<ε?1，j=1,…,D。在仿真實驗中，取ε=

1/t2。

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

(9)

2.3 群居型蝗蟲與散居型蝗蟲的區分方法

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

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

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

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

2.4 算法實現步驟

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

輸入：種群規模N，搜索空間維數D，最大迭代次數Tmax。

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

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

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

步驟 6：判斷是否滿足停止條件，若滿足，則轉Step 7；否則重復Step 3-Step 5。

3 實驗仿真與結果分析

3.1 測試函數

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

表1 基準測試函數Table 1 Benchmark function

續表

Continued table

3.2 結果與分析

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

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

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

續表

Continued table

續表

Continued table

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

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

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

為了更直觀地對比本研究算法(VAGOA)、GOA、PSO、HCUGOA和SA_CAGOA 5種算法各自的全局收斂速度和全局搜索能力，給出5種算法求解以上12個基準測試函數的適應度進化曲線對比圖(圖2)。相較于GOA、PSO、HCUGOA、SA_CAGOA 4種算法，VAGOA的進化曲線均位于最下方位置，且下降趨勢為5種算法中最快，沒有出現停滯狀態；VAGOA的F1-F9收斂曲線均到達理論最優位置，F10收斂曲線非常接近理論最優位置(圖2)。說明本研究算法(VAGOA)在搜索后期沒有陷入局部最優?；谝陨戏治?，相較于GOA、PSO、HCUGOA、SA_CAGOA 4種算法，VAGOA的全局收斂速度明顯更快，規避陷入局部最優的能力更強。

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

4 結論

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

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