基于全局最優值的群搜索優化算法

熊聰聰，李俊偉，楊曉藝，王 丹

(天津科技大學人工智能學院，天津300457)

在20世紀60年代早期，人們創造了許多工具來模擬生物的行為，仿生學就此誕生.在這樣的前提下，自然界有很多動物群體(蟻群、鳥群等)成為研究者關注的焦點，對動物的群體行為進行數學建模，并在計算機軟件上進行模擬仿真實驗，群智能(swarm intelligence，SI)算法[1-4]應運而生.其中，比較經典的群智能算法有：Colorni等[3]根據螞蟻在尋找食物時的行為而提出的蟻群(ant colony optimizer，ACO)算法、Kenndy等[4]根據鳥群在尋找食物時的行為從而提出的粒子群(particle swarm optimizer，PSO)算法、He等[1,5]提出的群搜索優化(group search optimizer，GSO)算法.

He等[1]系統地闡述了群搜索優化算法的基本原理，解釋了相關的數學模型，并將其與遺傳算法(GA)、快速演化規劃(FEP)[6]、快速演化策略(FES)[7]、粒子群(PSO)算法等群智能算法進行了比較和仿真實驗，對比討論該算法中的初始化參數對最終實驗結果的影響.

雖然GSO在一些優化問題中顯示出了比較顯著的優越性，但其仍然存在部分不足之處，例如在處理一些優化問題時出現易陷入局部最優，造成收斂速度較慢、精度較低的問題.因此，許多研究者都提出了相應的改進方法.安曉偉等[8]提出了保留發現者的搜索策略和由加入者執行魚群算法的搜索策略，通過引入魚群算法，可以避免種群搜索陷入局部最優.在標準GSO算法的基礎上，李麗娟等[9]提出了取消按角度搜索的策略，增加了控制變量隨迭代次數減少而變化的概率，在一定程度上解決了標準GSO算法收斂速度慢的缺點.楊文璐等[10]提出了一種基于交叉因子的改進群搜索優化算法，通過將交叉因子和模擬退火算法結合，使得群體中粒子多樣性增加，從而避免使GSO算法陷入局部最優值的可能性.景書杰等[11]提出一種群搜索優化算法，該算法通過對發現者搜索方式中加入最大下降方向，把游蕩者生成策略改變為基因突變策略，從而提高了標準GSO算法的收斂速度.郝璐萌[12]提出在發現者搜索過程中引入不同的差分變異策略，提高收斂精度.王娟等[13]提出了基于改進Tent混沌映射的種群初始化和基于Levy飛行特征的跟隨者更新策略，提高了解決高維復雜問題的收斂速度和求解精度.

針對GSO算法存在的問題，本文提出了一種基于全局最優值的群搜索優化(global optimal valuebased group search optimizer，GGSO)算法，該算法針對在標準群搜索優化算法發現者搜索過程中收斂速度慢，引入全局最優值，從而加速算法收斂速度.選取11組標準測試函數進行測試，并與GSO算法的測試結果比較，GGSO算法整體上相比GSO算法具有更好的收斂速度和精度.

1 群搜索優化算法

群搜索優化(group search optimizer，GSO)算法，根據群居動物搜索食物行為而設計的一種仿真模擬算法.該算法的原型是“發現者–加入者”(producerscrounger，PS)模型.在GSO算法中將研究對象按照在種群中的功能分為3類：搜索資源并共享其信息的發現者、對發現者搜索到的資源進行掠奪的加入者、執行隨機搜索的游蕩者.群搜索優化算法是基于動物種群之間信息共享和相互合作的特性而建立的一種智能優化算法[1].該算法模仿了動物的視覺搜索機制，在其搜索過程中，適應度值最好的個體作為發現者帶頭搜索，發現者按照既定的搜索角度和方向尋找更好的資源，加入者跟隨發現者進行局部搜索，剩余的個體作為游蕩者，根據搜索角度在當前的范圍內調整自己的位置.群體中的3類個體相互協同協作完成搜索的任務，從而使所找到的資源為最優.

1.1 發現者

在每次迭代過程中，均選擇適應度值最好的個體作為本次迭代過程中的發現者(producer)，發現者在共享資源的同時繼續搜索資源.搜索策略是在當前位置沿著3個不同的角度進行掃描搜索，找到3個方向上不同的位置，通過式(4)—式(6)分別在其前方、左方以及右方進行掃描查找.

其中：r1∈R1為服從均值為0、方差為1的正態分布隨機數；r2∈ Rn?1為[0，1)間均勻分布的隨機數；lmax為搜索的最大距離，并能夠通過式(7)計算得到；θmax為搜索的最大角度.

其中Ui和Li分別是取值范圍的上界和下界.

如果3個隨機位置中某一個要好于當前發現者的位置，就將發現者的位置和角度更新為隨機位置中較好的位置和角度；反之，發現者則不改變其當前位置信息，并通過式(8)更新搜索角度，進行下一次迭代.

其中αmax∈R1為最大的搜索轉換角度.

發現者如果在α次迭代后無法找到更好的資源時，通過式(9)回到0°位置.

其中α∈R1為實驗人員自行確定的常數.

1.2 加入者

隨機選擇剩余個體的80%作為加入者(scrounger)，加入者一直跟隨共享由發現者搜索到的位置資源信息，如果加入者找到比當前發現者更好的資源時，在下一次迭代中按照式(10)加入者會轉換為發現者角色進行搜索.

其中r3∈Rn為服從[0，1)均勻分布的隨機數.

1.3 游蕩者

剩余個體作為游蕩者(ranger)在搜索空間中隨機分布并且進行資源搜索.在第k次迭代中，游蕩者通過式(8)產生隨機角度，并通過式(11)得出隨機距離li，通過式(12)更新位置.

通過3種角色個體間的相互合作，更新種群信息，最終收斂得到種群中的最優個體.但是為了在搜索資源時更加方便，所以在一定程度上限制了個體的搜索界限，如果某個個體在搜索時跳出該搜索界限，會判斷其是否越界，并讓該個體返回到之前的搜索位置.

1.4 GSO算法整體框架

標準GSO算法流程圖如圖1所示.

圖1 標準GSO算法流程圖Fig. 1 Standard GSO algorithm flow chart

標準GSO算法(算法1)如下：

1. 輸入：隨機向量Xi.

2. 輸出：當前最優個體位置信息.

3. 初始化種群中所有個體的角度和位置信息.

4. 計算種群個體的適應度值fvalue.

5. WHILE(iter＜MaxIter).

6. 選取發現者，按照式(4)—式(9)執行發現者操作.7. 選擇剩余成員80%作為加入者，按照式(10)執行加入者操作.

8. 選擇剩余成員20%作為游蕩者，按照公式(11)和公式(12)執行游蕩者操作.

9. 計算種群的適應度值fvalue.

10. END WHILE.

1.5 GSO參數選擇

2 改進的群搜索優化算法

為了提升算法在搜索空間內的資源尋優能力，提出一種基于全局最優值的群搜索優化(global optimal value-based group search optimizer，GGSO)算法.該算法以標準GSO算法的PS模型為基礎，并在搜索時加入全局最優值作為發現者，提高了算法的搜索性能和收斂精度.在該算法中，先求得所有群體的適應度值，然后得到其中的最優值，在發現者的搜索過程中，加入全局最優值.在不斷的迭代過程中，每一次迭代加入全局最優值以后，使得全局最優值有機會參與到發現者的搜索過程中，進而使算法可以跳出局部最優值，提升算法收斂精度，從而提高算法的全局搜索能力.

2.1 GGSO算法的實現過程

(1)在前期時，算法采用標準GSO算法流程進行進化和迭代.

(2)保存所有成員適應度值的最小值，即在迭代開始之前保存某個成員i當前位置及其適應度作為全局最優值fbestval.

(3)在發現者搜索過程中，每一輪迭代在發現者適應度值中都加入之前保存的全局最優值fbestval.

(4)與此同時，發現者、加入者和游蕩者均按照GSO算法的搜索方式進行搜索.

2.2 GGSO算法偽代碼

GGSO算法偽代碼(算法2)如下：

1. 輸入：隨機向量Xi.

2. 輸出：當前最優個體位置信息.

3. BEGIN.

4. 隨機初始化種群種個體的位置和角度信息.

5. 計算種群個體的適應度值fvalue.

6. 選取適應度值最好的點作為發現者.

7. WHILE(迭代是否滿足).

8. 將全局最優值加入發現者群體.

9. 選擇發現者，由式(4)—式(9)執行發現者操作.

10. 選擇剩余成員80%作為加入者，由式(10)執行加入者策略.

11. 選擇剩余成員20%作為游蕩者，由式(11)和式(12)執行游蕩者策略.

12. 再次計算種群的適應度值fvalue，得到當前最優適應度值.

13. END WHILE.

全局最優值即在優化問題的全值域范圍內得到的最優值.局部最優值即在優化問題的解在一定范圍或者區域內的最優值，或者優化問題在一定的限制條件內最優值.從圖2即可明顯看出兩者的區別.

圖2 局部最優值與全局最優值示意圖Fig. 2 Diagram of local optimum and global optimum

其中：B ?S?Rn，S為函數的搜索空間，則稱為f (X)的局部最小值點，f ()為局部最小值.

如果存在 X*∈S，使得對?X∈S，存在

其中 S?Rn為函數的搜索空間，則稱 X*為f (X)的全局最優值點，f (X*)為其全局最優值.

2.3 全局最優策略

雖然GSO算法在部分問題的解決上有優越的表現，但其仍然面臨在發現者搜索效果不為顯著的問題.受到“適者生存”的規律啟發，優秀的個體較為容易生存.因此，將全局最優策略應用到GSO算法的發現者個體選擇中.算法3詳細描述了該操作.

算法3：根據適應度值對種群中最優個體進行記錄.

1. 輸入：每輪迭代中的最小適應度值.

2. 輸出：所有迭代中的最小適應度值位置信息.

3. BEGIN.

4. WHILE(Iter＜MaxIter).

5. 得到迭代中的最小適應度值fvalue及其位置信息.

6. Min(fvalue)→index.

7. END WHILE.

8. 根據index更新發現者群體信息.

9. END.

在該策略中雖然體現出了與粒子群算法較為相似之處，粒子群算法初始化得到隨機粒子群，然后再通過迭代找到最優解.在之后的每次迭代中，其中的粒子通過查找局部最優值和全局最優值更新其本身的位置.當初始化粒子群后，得到其適應度值并找到全局最優值.但是，上述算法3中提到的策略與粒子群算法不同之處在于，在得到每次迭代中的最優值之后將其記錄下來，最終將所有最優值均作為發現者群體進行搜索，對發現者種群產生影響，進而可以進一步得到其全局最優值.

在對具體優化問題求解時，主要思路就是找到當前空間內的局部最優值，或者說通過迭代計算找到目標函數的解，直到找到兩個解沒有變化為止，此時即為該目標函數的局部最優值.如果目標函數及其約束條件均為凸函數，通過算法找到的解即為全局最優值.如果目標函數不是凸函數，通過算法找到的最優值，有可能是全局最優值，也有可能為局部最優值.

3 實驗仿真與結果分析

3.1 國際標準測試函數

測試過程中選取了11個國際標準函數(見表1)，主要分為兩大類，單峰函數f1—f6和多峰函數f7—f11.

表1 11個測試函數Tab. 1 Eleven benchmark functions

3.2 實驗環境與參數設置

實驗所用到的環境為：操作系統Win10，軟件Matlab2017a，運行內存8GB.實驗中算法所用到的參數與初始GSO算法參數均保持一致，種群規模設置為48，種群個體維數設置為30，最大迭代次數設置為5000次，測試函數運行次數設置為50次.

3.3 實驗結果及算法比較分析

通過對比標準GSO算法和GGSO算法在11個國際標準測試函數上的平均值和標準差(表2)，評價兩種算法的性能.其中，平均值和標準差是同一個標準測試函數上運行50次的實驗平均結果的統計.同時，黑色加粗字體表示兩個算法在同一個測試函數上所取得的平均值的最優值.

表2 兩種算法在11個測試函數上的比較結果Tab. 2 Compared results of the two algorithms on 11 benchmark functions

由表2可知：對于單峰函數(f1—f6)，GGSO算法收斂進度與GSO算法相差不大，f1、f2、f3、f4、f6在GGSO算法上得到的最優值優于標準GSO上的最優值，但其離散程度比標準GSO的離散程度要高.對于多峰函數(f7—f11)，除f7外，其余4個測試函數在GGSO算法上的表現均優于在標準GSO算法上的表現，且其離散程度表現不一，f9、f11的離散程度低于在標準GSO上的離散程度.在11個標準測試函數上，有9個標準測試函數在GGSO算法上的表現優于在標準GSO算法上的表現，僅有1個標準測試函數結果的精度稍遜于標準GSO算法，另有1個測試函數在兩個算法上表現一致.總體表明，GGSO算法性能優于標準GSO算法.

為了更好地展示測試改進的算法在測試函數上的表現，實驗中測試了迭代次數從500到5000次的表現，以測試函數f6和f11的結果對比為例，結果如圖3和圖4所示.從圖3中可看出，改進的群搜索優化算法在測試函數f6上在3000次迭代之前得到的平均適應度均優于標準GSO算法，在3500次迭代后收斂速度明顯優于標準GSO算法的收斂速度，且得到更好的平均適應度.由圖4可知，雖然GGSO算法的收斂速度與標準GSO算法中收斂速度一致，但是可以得到比標準GSO算法更好的平均適應度.

圖3 測試函數f6結果對比Fig. 3 Comparison of benchmark function f6 results

圖4 測試函數f11結果對比Fig. 4 Comparison of benchmark function f11 results

4 結 論

在標準GSO算法基礎上，通過對算法中發現者的搜索策略進行改進，以達到提高算法的收斂速度和精度的效果.針對標準GSO算法未考慮全局最優值的影響，通過在發現者搜索過程中加入全局最優值，一定程度增加了種群的多樣性，算法的收斂速度和精度相比之前有所提高，避免了發現者在搜索時陷入局部最優.實驗結果表明，標準GSO算法的不足之處在GGSO算法上有一定的改進和彌補.未來工作尚需在發現者和加入者搜索過程中加入更多優化策略，把改進過的群搜索優化算法具體應用實現.