融合正弦余弦和變異選擇的蝗蟲優化算法

林 杰，何 慶

(貴州大學 大數據與信息工程學院，貴陽 550025) (貴州大學 貴州省公共大數據重點實驗室，貴陽 550025)

1 引 言

蝗蟲優化算法(Grasshopper Optimization Algorithm，GOA)[1]是由Mirjalili等人于2017年1月提出的一種元啟發式智能算法.跟現有的群智能優化算法相似，GOA具有原理簡單、參數較少、易于實現等優勢.研究發現，在對基準函數優化時，GOA的收斂精度和收斂速度均優于粒子群優化算法(PSO)和引力搜索算法(GSA)以及蝙蝠算法(BA)等算法[1].并且在工程應用中取得不錯的成果.比如黃超等[2]對GOA引入曲線自適應策略，加快算法的收斂速度，將其應用到靜態障礙物環境下的移動機器人路徑規劃問題中，提高機器人路徑規劃精度；程澤新等[3]將GOA引入無人機三維航跡規劃，有效規劃出合理航跡，與其他算法相比具有更優的性能；閆旭等[4]提出一種混合蝗蟲優化算法(HGOA)，并應用到作業車間調度問題中.

然而GOA雖具有較強的局部開發能力，但對全局探索不足，易陷入局部最優，導致算法收斂精度較差[5].針對這些問題，Arora 等[6]提出全局優化的混沌GOA，將10種混沌映射分別取代線性變化參數c，混沌映射用于在優化過程中有效地平衡探索和開發，同時減少蝗蟲之間的排斥或吸引力，但是從實驗結果看，即使是實驗效果最佳的Circle映射，也早早的陷入局部最優，證明對算法開發不夠.Zakeri等[7]提出GOFS算法，在迭代過程中通過統計分析以最優值替換重復出現的解，以避免陷入局部最優值；文獻[8]提出一種混沌橋接機制，并引入混沌算子，利用交叉機制產生新解，并成功應用到生物信息學的蛋白質結果預測(PSP)和調頻聲波參數估計問題.文獻[9]提出一種基于曲線自適應和模擬退火的蝗蟲優化算法(SA-CAGOA)，首先對參數c提出兩種曲線自適應改進策略，提高算法的全局搜索能力，其次引入模擬退火算法，對算法的劣質解以一定概率的接收，使算法具有跳出局部最優的能力.

上述研究方法對GOA的收斂速度和精度均有改善，但由于提出GOA的時間不久，現在對GOA及其應用的研究還較少，為進一步推進GOA尋優性能的快速改進，本文提出融合正弦余弦和變異選擇的蝗蟲優化算法，首先，為了增加種群多樣性，根據轉換概率，選擇不同更新方式更新蝗蟲個體位置；其次，對引入的正弦余弦算法進行改進，使算法的全局探索和局部最優得到更好的平衡；最后，依據變異概率對更新后的目標位置進行變異，并通過貪婪法則保存最優，使算法跳出局部最優，確保算法的每一次迭代在目標值的影響下，找到更優解，加快算法的收斂速度和收斂精度.

2 算法基本原理

2.1 蝗蟲優化算法

蝗蟲優化算法[1]通過模擬自然界蝗蟲幼蟲時期小范圍移動和成蟲時期隨機性大范圍移動的特征，構成GOA算法的局部開發和全局探索過程.在不考慮重力因素，并假定風向總是指向目標位置的情況下，蝗蟲群的行為可以用式(1)的數學模型來描述：

(1)

(2)

式(2)為線性遞減函數，其中t為當前迭代次數，Tmax為最大迭代次數，cmax、cmin分別是參數c的最大值和最小值.系數c用于平衡算法的全局探索和局部開發，式(1)中外側的系數c與PSO算法中的慣性權重類似，隨著迭代次數的增加而減少個體的搜索范圍，用于控制算法的探索與開發；內側的系數c用于控制蝗蟲間的吸引區、舒適區和排斥區.

(3)

式(3)是表蝗蟲與其他蝗蟲的交互力影響函數s函數，式中，s(r)>0時，r的取值范圍稱為吸引區，此時蝗蟲間相互吸引；s(r)<0時，r的取值范圍稱為排斥區，蝗蟲間相互排斥；s(r)=0時，既不吸引也不排斥，r的取值稱為舒適區.另外，f與l為吸引強度參數與吸引尺度參數，本文取值f=0.5，l=1.5.

由上述分析可知GOA算法的基本實現步驟如下：

Step 1.初始化種群大小N，參數cmin，cmax和最大迭代次數Tmax，初始化種群位置，并計算每個蝗蟲的適應度值，選擇最優值作為目標位置；

Step 2.進入主循環，根據公式(2)更新參數c；

Step 3.根據公式(1)更新蝗蟲個體位置，計算每個蝗蟲的適應度值并擇優更新目標位置；

Step 4.判斷是否滿足停止循環條件，若滿足，算法跳出循環并返回目標值，否則算法重復Step 2和Step 3.

2.2 正余弦算法

正余弦算法(Sine Cosine Algorithm，SCA)[10]是 2016年由Mirjalili等人提出的基于數學性質的變化的正余弦函數的新型元啟發式優化算法.該算法通過迭代利用正弦余弦的變化對算法進行全局搜索和局部開發.在SCA中個體的位置更新公式如下所示：

(4)

(5)

其中a是常數，t是當前迭代次數，Tmax是最大迭代次數.

SCA的基本思想是：初始化種群位置以及相關參數，并計算個體適應度值，擇優保存；其次在主循環中根據公式(5)更新參數R1，并在切換概率R4的控制下決定個體是選擇更新位置的方式：正弦方式或余弦方式，隨后計算個體適應度值并更新全局最優，迭代到最大迭代次數時退出循環并返回最優值.個體進行的位置更新方式是逐維更新，并且SCA具有較強的全局探索和局部開發能力，這是與GOA不同的地方，SCA通過正弦余弦的轉換機制使得算法在求解優化函數時具有更好的尋優能力.

3 SC-MGOA算法

3.1 融入正弦余弦算法

根據2.1節的闡述，可知蝗蟲優化算法位置更新由蝗蟲自身位置、與其他所有蝗蟲之間影響力和目標位置控制，蝗蟲個體之間的信息交互能力很強，所以GOA具有較強的局部開發能力，而全局尋優能力較差，導致算法易出現搜索停止，即算法缺乏種群多樣性.而SCA與基于蝗蟲個體的GOA相比，全局搜索和局部開發得到更好的平衡.因此，在GOA中融入SCA的思想，改變GOA單一的位置更新方式.通過引入正余弦機制，增加種群多樣性同時降低個體尋優的盲目性.利用正余弦機制同時具備局部開發和全局搜索的特點，增強算法全局搜索力度.

本文的兩種位置更新方式通過轉換概率控制.當轉換概率設置為一個常數時，并不利于平衡算法的全局搜索和局部開發，因此本文將轉換概率設置為一個隨著迭代自適應調整的函數，有利于算法通過動態控制轉換概率的大小，進一步調控全局搜索和局部開發的平衡，轉換概率的定義如下：

(6)

其中t是當前迭代次數，Tmax是最大迭代次數，μ為轉換因子，取值為μ=0.01.因為算法應在迭代前期盡可能的進行全局搜索，在后期進行開發，所以在轉換的概率的控制下，當rand

3.2 對正弦余弦算法進行改進

為了更好的協調算法的全局搜索和局部開發，對融入正弦余弦機制的算法進行改進.首先，由2.2節可以看出，R1是SCA算法的關鍵參數，控制著算法的探索和開發，但是R1是線性變化的，這不利于算法在迭代前期進行充分的全局探索，也可能導致算法后期開發不足，因此，對融進GOA算法的SCA部分的參數R1的收斂方式進行改進，改進后的表達式如下：

(7)

式中引入了余弦函數，利用余弦函數的數學特點，讓R1在一定范圍內來回震蕩，使算法的全局探索和局部開發得到進一步的平衡.

其次，為了在位置更新處充分利用個體位置信息，使個體位置對新位置的影響權重隨迭代發生變化，引入動態權重系數，權重系數β的表達式如下：

(8)

其中b為服從指數分布的優化因子，即b～E(λ)，本文中λ取值為種群數N.在算法迭代前期，β較大且下降緩慢，即個體位置對算法有較大的影響力，以充分進行全局探索，在算法后期，β急速減小以減少個體位置的影響力，讓算法進行充分的局部開發.改進后的正弦余弦機制更新方式如下：

(9)

3.3 目標位置的變異選擇

由GOA基本算法原理可知，GOA算法在位置更新后，計算適應度，然后更新目標值，接著直接進入下一次的循環，故導致算法在目標值陷入局部最優而算法不自知.因此，本文對目標位置進行變異更新，使算法具有跳出局部最優的概率，提升算法的收斂精度和收斂速度.

本文在GOA算法的目標位置更新后，以一定概率對目標位置進行變異，提高每次迭代后蝗蟲解的質量，使算法能夠避免陷入局部最優.其中變異概率Pm定義如下：

(10)

其中fitness是目標位置的適應度，式(10)中充分利用了每一代的目標值，隨著算法的迭代，Pm與目標值以及迭代次數緊密結合，動態調整變異概率的大小.當rand

(11)

對目標位置進行變異操作雖然能讓算法跳出局部最優，但是不能保證新位置優于原目標位置，所以本文在變異操作后面加入了貪婪原則，通過比較適應度之后再決定是否更新目標位置：

(12)

利用貪婪選擇策略使算法在迭代過程中能夠充分利用目標位置信息，提升算法收斂速度和精度，促進算法的尋優性能.

圖1 改進算法流程圖Fig.1 Improved algorithm pipeline

3.4 SC-MGOA算法的實現

綜上所述，將SCA算法和GOA算法各自的優勢融合，并對目標位置進行變異更新，使SC-MGOA算法不僅具備強大的全局探索能力和局部開發能力，同時也具有跳出局部最優的能力，其算法實現的流程如圖1所示，具體實現步驟描述如下：

Step 1.初始化種群位置及各項參數；

Step 2.計算蝗蟲適應度，找到當前最優作為目標位置及目標值；

Step 3.進入主循環，更新參數Pv、Pc、R1和β.

當rand>Pv時，根據基本GOA算法的位置更新公式(1)更新蝗蟲位置；

當rand

Step 4.計算蝗蟲適應度并判斷是否更新目標位置及目標值；

Step 5.更新參數Pc，當rand

Step 6.判斷算法是否滿足停止條件，若滿足則跳出主循環，輸出目標位置和目標值，否則返回Step 3.

4 實驗仿真與分析

4.1 實驗環境和參數設置

本文采用MATLAB R2014a進行試驗，運行環境為64 位 Windows 10操作系統，處理器類型為 Intel Core i5-7500.仿真程序中算法的共有參數設置：種群規模N=30，最大迭代次數Tmax=500，空間維度dim=30.

實驗引入10個經典測試函數，如表1所示.其中F1-F5為單峰函數，局部最優即為全局最優，常用來測試算法的收斂速度和尋優精度；F6-F10為多峰函數，具有多個局部極值，常用來檢測算法跳出局部最優的能力和全局探索的能力.為降低實驗偶然性，對每個測試函數均進行50次獨立實驗.

表1 測試函數Table 1 Test function

本文實驗仿真分為3個部分進行：

a)將本文算法與其它一些新的群智能算法——樽海鞘算法[11](SSA)(1)http：//kns.cnki.net/kcms/detail/11.2127.TP.20190815.1534.017.html.、蟻獅算法(ALO)[12]和正弦余弦算法(SCA)[13]比較，驗證本文算法的有效性；其中本文算法的常量參數取值為：a=2、cmax=1、cmin=0.00004，3種對比算法的參數設置與其對應的原文獻保持一致；

b)對3個改進策略算法分別進行運行測試，根據測試結果分析不同改進策略對算法尋優的影響；

c)通過與其他蝗蟲改進算法作比較，說明本文改進算法相對于其他最新的改進GOA算法仍具有優越性.

4.2 驗證本文算法的有效性

為驗證本文算法的有效性和可行性，4種算法在dim=30的條件下對10個基準測試函數進行尋優，通過4個性能指標評估仿真結果，算法獨立運行50次的數據如表2和表3所示.

從表2可知，SCA算法的尋優結果相較于SSA和ALO要好，但是SC-MGOA的尋優結果最好.對于5個單峰函數，SC-MGOA均尋優到了理論最優值，而3個對比算法均沒有找到理論值，且尋優精度較低，例如函數F1，SSA的最優值是1.79E-10，ALO的最優值是2.15E-09，SCA的最優值是2.03E-18，而SC-MGOA的最優值為0，尋優精度明顯高于對比的3種算法，證明了本文算法具有較好的尋優速度和收斂精度.

表2 不同算法尋優結果對比(單峰)Table 2 Comparison of results of algorithms(single peak)

從表3可知，對于多峰函數，SC-MGOA算法相對于SSA、ALO和SCA 3個對比算法，尋優的結果相對較好，具有更明顯的競爭優勢，例如函數F6和F8，SC-MGOA的4個評價均尋到了理論值0，而3個對比算法的尋優精度明顯沒有SC-MGOA的好；對于函數F7、F9和F10，4種算法均沒有尋到理論最優值，但是SC-MGOA的尋優精度明顯高于其他3種算法，例如函數F10，SC-MGOA與SCA的尋優精度最大相差46個數量級.

表3 不同算法尋優結果對比(多峰)Table 3 Comparison of results of algorithms(multi-peak)

算法的收斂曲線圖可以直觀的體現算法的收斂趨勢的一種表達方式[14]，為了更直觀的了解本文算法的有效性，圖2給出了SC-MGOA算法和SSA算法、ALO算法和SCA算法的收斂曲線對比圖.

圖2 測試函數平均收斂曲線Fig.2 Average convergence curve of test function

通過圖2(a)-圖2(d)可直觀看出，SSA算法和ALO算法的解在算法迭代前期下降緩慢，說明這兩種算法全局探索能力不強，在算法后期，解的分布范圍相對集中，表明SSA和ALO后期陷入局部最優；從圖2(a)和圖2(b)可知，SCA的尋優精度優于SSA和ALO，但尋優能力也沒有SC-MGOA算法強；從圖2(d)-圖2(g)可看出SC-MGOA算法的收斂速度具備明顯優勢；從圖2(a)-圖2(j)整體可以看出，在100次迭代內，SC-MGOA算法的收斂曲線均位于其他算法的收斂曲線左下方，表明在迭代次數一樣的條件下，SC-MGOA算法具有更高的收斂精度，在收斂精度一樣的條件下，SC-MGOA算法具有更快的收斂速度.例如在單峰函數F2和F3中，SC-MGOA算法分別在47代和31代收斂，在多峰函數F7和F8中，SC-MGOA算法尋到理論最優值，并在30代左右迅速收斂，對于沒有尋到的理論值的F9和F10，相較于其它3種對比算法會較早的出現尋優停滯，SC-MGOA算法即使沒有尋到最優，且最后陷入局部最優后難以跳出，但SC-MGOA算法的尋優精度明顯高于3種對比算法.

4.3 驗證不同改進策略的有效性

將融入正弦余弦機制的SCGOA1算法、改進正弦余弦機制參數的SCGOA2算法和對目標位置進行變異產生新解的MGOA算法與基本GOA算法對比，證明不同改進策略的有效性，同時再與SC-MGOA算法作對比，證明不同策略的算法對SC-MGOA算法的影響.為方便比較，算法的參數設置均與4.2節的一樣.測試結果如表4和表5所示.

表4 不同改進策略算法測試結果(單峰)Table 4 Test results of different improved strategies(single peak)

首先，最優值和平均值可以反映出算法的尋優精度和尋優能力，從表4可知在5個單峰函數中，SCGOA2、MGOA和SC-MGOA的最優值和平均值均為0，說明3個算法尋到理論值不是偶然性，而是算法的尋優能力增強；SCGOA1算法盡管沒有尋到最優，但與GOA算法相比，尋優精度也得到改善，例如函數F1，其尋優精度最大提升9個數量級，說明了融入SCA機制對算法改進的有效性.從表5測試結果可以看出，對于函數F6和F8，SCGOA2、MGOA和SC-MGOA尋到了理論最優值0，SCGOA1在對F6進行尋優時，最優值尋到理論值0，對F8尋優時，SCGOA1相較于GOA算法最大相差14個數量級；Ackley函數是一種具有山峰形態的多峰函數，其理論最優值很難找到，因此3個策略算法均未找到理論值，但提升了尋優精度；從F9和F10的尋優結果中可以看出，3種策略相對于GOA算法均有改進，但是最終尋優結果均不如SC-MGOA算法的好，說明在不同策略的共同影響下，算法的尋優精度得到最大程度的提升.

表5 不同改進策略算法測試結果(多峰)Table 5 Test results of different improved strategies(multi-peak)

其次，測試結果的標準差可以反映出算法的穩定性，從表4和表5可以看出，改進算法對10個測試函數尋優結果的標準差大部分均為0，對于標準差不是0的測試函數，改進算法的標準差精度也比GOA算法的要高，例如函數F10，MGOA和SC-MGOA的標準差與GOA的標準差相差46個數量級，說明MGOA算法和SC-MGOA算法在未尋到最優值的情況下，尋優精度更高且尋優結果更穩定.

最后，從圖3(a)和圖3(c)-圖3(d)可看出SCGOA2比其他兩種改進策略具有更快的尋優速度和更高的收斂精度.從圖3(f)-圖3(h)可以看出，在多峰函數中MGOA算法相較于其它兩種策略具有更好的收斂精度，體現出MGOA算法避免陷入局部最優的能力.從圖3(a)-圖3(j)可知，SC-MGOA整體的收斂曲線均居于其他曲線的左下方，而且下降速度更快，說明SC-MGOA算法在迭代次數一樣的條件下具有更高的收斂精度，在收斂精度一樣的條件下具備更快的收斂速度；SCAGOA1算法明顯是3個改進策略里面效果最不好的，如圖3(g)和圖3(h)，但可以看出其尋優精度也比基本GOA算法高，說明即使是尋優結果最不好的策略，相對于GOA算法其尋優能力也得到改善.

圖3 不同策略算法的平均收斂曲線圖Fig.3 Average convergence curves of different strategy

4.4 與其他改進GOA算法性能對比

為了進一步體現SC-MGOA算法的優越性，本文將最新的改進蝗蟲算法文獻[5]中的CGOA算法(這里采用了10個混沌映射，產生的10個算法對應為CGOA1-CGOA10，本文采用收斂精度最高的CGOA6)和文獻[8]的SA-CGOA算法(這里采用引入圓映射的SA-CGOA2算法)的數據引入，與SC-MGOA算法進行比較.參數設置與4.1節一致，N=30，dim=30，Tmax=500，對10個基準函數進行測試，并獨立運行50次，為方便比較，3種算法的參數設置統一，數據比較結果如表6所示.

表6 與改進GOA算法對比結果Table 6 Comparison result with improved GOA algorithm

表6用尋優結果的平均值和標準差來評估算法性能，由表6可以看出，文獻[5]的CGOA算法尋優精度較差而且尋優結果不穩定，相比于CGOA，SC-MGOA算法具有更好的收斂精度和更強的魯棒性，說明了SC-MGOA算法再改進后表現的更好，在10個測試函數中，SC-MGOA算法都比CGOA算法的結果更優；與SA-CGOA算法相比，在F6和F8中，SA-CGOA算法和SC-MGOA 算法均尋到了理論值，但在其余8個測試函數中，SC-MGOA算法尋優精度更高.相對于兩種改進的GOA算法，通過10個測試函數證明SC-MGOA算法無論是平均值還是標準差大部分均能尋到理論值，對于沒有尋到理論值的，SC-MGOA算法的尋優精度也是最優的.

綜上所述，本文所提的改進算法高質量的尋優精度和穩定性使其在優化函數時仍具有一定競爭力.

4.5 Wilcoxon秩和檢驗

算法的4個評價指標在50次獨立運行的實驗中沒有獨立的比較每次的運行結果.為驗證SC-MGOA算法與其他算法的顯著性差異，采用Wilcoxon秩和檢驗進行統計分析[15].SC-MGOA算法的50次尋優結果分別與SSA、ALO、SCA、GOA、MGOA、SCGOA1和SCGOA2的50次尋優結果進行假設檢驗，并假設H0：兩種對比算法的尋優結果總體上是相同的；H1：兩種對比算法尋優結果總體上是不同的.由文獻[16]可知秩和檢驗在5%的顯著性水平下進行，當小于5%時，拒絕H0假設則，說明兩種對比算法具有顯著性差異；否則接受H0假設，說明兩種算法的尋優結果在整體上是相同的.

表7中給出了10個測試函數下SC-MGOA與其他算法的Wilcoxon秩和檢驗中計算的p值，因為最佳算法不能與自身進行比較，所以在表格中標記為‘N/A’的表示該算法與SC-MGOA算法尋優結果一致，且為最優，所以無法進行顯著性判斷.從檢驗結果來看，SCGOA2和MGOA中，大多數函數的p值均為N/A，說明在對測試函數尋優時，SCGOA2和MGOA算法與SC-MGOA的大部分表現一樣，而函數F5、F9和F10中3個函數的在SCGOA2和MGOA中的p值均小于0.05，說明SCGOA2和MGOA算法與SC-MGOA之間具有顯著性差異.SC-MGOA算法與SSA、ALO、SCA、GOA和SCGOA1比較時，尋優結果全部有顯著性差異，說明SC-MGOA算法在統計上具有優越性，即認定SC-MGOA算法相對于其他算法表現出更優的搜索能力.

表7 Wilcoxon秩和檢驗的p值Table 7 Wilcoxon rank sum test p value

5 結束語

為改善GOA的缺陷，本文提出融合正弦余弦和變異選擇的蝗蟲優化算法(SC-MGOA)，在位置更新處根據轉換概率選擇位置更新方式來增加種群的多樣性，同時彌補GOA算法全局搜索能力不足的缺陷；其次，為更好的協調算法的全局探索和局部開發，對引入的正余弦機制進行改進；最后，在一定概率下接受變異產生的新解，使算法避免陷入局部最優，提高算法的收斂精度.通過10個測試函數進行3組實驗，不僅證明了不同改進策略的有效性，還證明了SC-MGOA算法相對于其他比較算法在尋優精度、尋優速度和魯棒性等方面的優越性.在后續研究中，考慮將改進的蝗蟲優化算法應用到WSN路由能耗尋優問題中，找到能耗最小的廣播路徑，以進一步驗證算法的性能.