基于全局最優(yōu)值的群搜索優(yōu)化算法

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

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

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

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

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

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

1 群搜索優(yōu)化算法

群搜索優(yōu)化(group search optimizer，GSO)算法，根據(jù)群居動(dòng)物搜索食物行為而設(shè)計(jì)的一種仿真模擬算法.該算法的原型是“發(fā)現(xiàn)者–加入者”(producerscrounger，PS)模型.在GSO算法中將研究對(duì)象按照在種群中的功能分為3類：搜索資源并共享其信息的發(fā)現(xiàn)者、對(duì)發(fā)現(xiàn)者搜索到的資源進(jìn)行掠奪的加入者、執(zhí)行隨機(jī)搜索的游蕩者.群搜索優(yōu)化算法是基于動(dòng)物種群之間信息共享和相互合作的特性而建立的一種智能優(yōu)化算法[1].該算法模仿了動(dòng)物的視覺搜索機(jī)制，在其搜索過程中，適應(yīng)度值最好的個(gè)體作為發(fā)現(xiàn)者帶頭搜索，發(fā)現(xiàn)者按照既定的搜索角度和方向?qū)ふ腋玫馁Y源，加入者跟隨發(fā)現(xiàn)者進(jìn)行局部搜索，剩余的個(gè)體作為游蕩者，根據(jù)搜索角度在當(dāng)前的范圍內(nèi)調(diào)整自己的位置.群體中的3類個(gè)體相互協(xié)同協(xié)作完成搜索的任務(wù)，從而使所找到的資源為最優(yōu).

1.1 發(fā)現(xiàn)者

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

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

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

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

其中αmax∈R1為最大的搜索轉(zhuǎn)換角度.

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

其中α∈R1為實(shí)驗(yàn)人員自行確定的常數(shù).

1.2 加入者

隨機(jī)選擇剩余個(gè)體的80%作為加入者(scrounger)，加入者一直跟隨共享由發(fā)現(xiàn)者搜索到的位置資源信息，如果加入者找到比當(dāng)前發(fā)現(xiàn)者更好的資源時(shí)，在下一次迭代中按照式(10)加入者會(huì)轉(zhuǎn)換為發(fā)現(xiàn)者角色進(jìn)行搜索.

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

1.3 游蕩者

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

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

1.4 GSO算法整體框架

標(biāo)準(zhǔn)GSO算法流程圖如圖1所示.

圖1 標(biāo)準(zhǔn)GSO算法流程圖Fig. 1 Standard GSO algorithm flow chart

標(biāo)準(zhǔn)GSO算法(算法1)如下：

1. 輸入：隨機(jī)向量Xi.

2. 輸出：當(dāng)前最優(yōu)個(gè)體位置信息.

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

4. 計(jì)算種群個(gè)體的適應(yīng)度值fvalue.

5. WHILE(iter＜MaxIter).

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

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

9. 計(jì)算種群的適應(yīng)度值fvalue.

10. END WHILE.

1.5 GSO參數(shù)選擇

2 改進(jìn)的群搜索優(yōu)化算法

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

2.1 GGSO算法的實(shí)現(xiàn)過程

(1)在前期時(shí)，算法采用標(biāo)準(zhǔn)GSO算法流程進(jìn)行進(jìn)化和迭代.

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

(3)在發(fā)現(xiàn)者搜索過程中，每一輪迭代在發(fā)現(xiàn)者適應(yīng)度值中都加入之前保存的全局最優(yōu)值fbestval.

(4)與此同時(shí)，發(fā)現(xiàn)者、加入者和游蕩者均按照GSO算法的搜索方式進(jìn)行搜索.

2.2 GGSO算法偽代碼

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

1. 輸入：隨機(jī)向量Xi.

2. 輸出：當(dāng)前最優(yōu)個(gè)體位置信息.

3. BEGIN.

4. 隨機(jī)初始化種群種個(gè)體的位置和角度信息.

5. 計(jì)算種群個(gè)體的適應(yīng)度值fvalue.

6. 選取適應(yīng)度值最好的點(diǎn)作為發(fā)現(xiàn)者.

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

8. 將全局最優(yōu)值加入發(fā)現(xiàn)者群體.

9. 選擇發(fā)現(xiàn)者，由式(4)—式(9)執(zhí)行發(fā)現(xiàn)者操作.

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

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

12. 再次計(jì)算種群的適應(yīng)度值fvalue，得到當(dāng)前最優(yōu)適應(yīng)度值.

13. END WHILE.

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

圖2 局部最優(yōu)值與全局最優(yōu)值示意圖Fig. 2 Diagram of local optimum and global optimum

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

如果存在 X*∈S，使得對(duì)?X∈S，存在

其中 S?Rn為函數(shù)的搜索空間，則稱 X*為f (X)的全局最優(yōu)值點(diǎn)，f (X*)為其全局最優(yōu)值.

2.3 全局最優(yōu)策略

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

算法3：根據(jù)適應(yīng)度值對(duì)種群中最優(yōu)個(gè)體進(jìn)行記錄.

1. 輸入：每輪迭代中的最小適應(yīng)度值.

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

3. BEGIN.

4. WHILE(Iter＜MaxIter).

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

6. Min(fvalue)→index.

7. END WHILE.

8. 根據(jù)index更新發(fā)現(xiàn)者群體信息.

9. END.

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

在對(duì)具體優(yōu)化問題求解時(shí)，主要思路就是找到當(dāng)前空間內(nèi)的局部最優(yōu)值，或者說通過迭代計(jì)算找到目標(biāo)函數(shù)的解，直到找到兩個(gè)解沒有變化為止，此時(shí)即為該目標(biāo)函數(shù)的局部最優(yōu)值.如果目標(biāo)函數(shù)及其約束條件均為凸函數(shù)，通過算法找到的解即為全局最優(yōu)值.如果目標(biāo)函數(shù)不是凸函數(shù)，通過算法找到的最優(yōu)值，有可能是全局最優(yōu)值，也有可能為局部最優(yōu)值.

3 實(shí)驗(yàn)仿真與結(jié)果分析

3.1 國際標(biāo)準(zhǔn)測(cè)試函數(shù)

測(cè)試過程中選取了11個(gè)國際標(biāo)準(zhǔn)函數(shù)(見表1)，主要分為兩大類，單峰函數(shù)f1—f6和多峰函數(shù)f7—f11.

表1 11個(gè)測(cè)試函數(shù)Tab. 1 Eleven benchmark functions

3.2 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

實(shí)驗(yàn)所用到的環(huán)境為：操作系統(tǒng)Win10，軟件Matlab2017a，運(yùn)行內(nèi)存8GB.實(shí)驗(yàn)中算法所用到的參數(shù)與初始GSO算法參數(shù)均保持一致，種群規(guī)模設(shè)置為48，種群個(gè)體維數(shù)設(shè)置為30，最大迭代次數(shù)設(shè)置為5000次，測(cè)試函數(shù)運(yùn)行次數(shù)設(shè)置為50次.

3.3 實(shí)驗(yàn)結(jié)果及算法比較分析

通過對(duì)比標(biāo)準(zhǔn)GSO算法和GGSO算法在11個(gè)國際標(biāo)準(zhǔn)測(cè)試函數(shù)上的平均值和標(biāo)準(zhǔn)差(表2)，評(píng)價(jià)兩種算法的性能.其中，平均值和標(biāo)準(zhǔn)差是同一個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上運(yùn)行50次的實(shí)驗(yàn)平均結(jié)果的統(tǒng)計(jì).同時(shí)，黑色加粗字體表示兩個(gè)算法在同一個(gè)測(cè)試函數(shù)上所取得的平均值的最優(yōu)值.

表2 兩種算法在11個(gè)測(cè)試函數(shù)上的比較結(jié)果Tab. 2 Compared results of the two algorithms on 11 benchmark functions

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

為了更好地展示測(cè)試改進(jìn)的算法在測(cè)試函數(shù)上的表現(xiàn)，實(shí)驗(yàn)中測(cè)試了迭代次數(shù)從500到5000次的表現(xiàn)，以測(cè)試函數(shù)f6和f11的結(jié)果對(duì)比為例，結(jié)果如圖3和圖4所示.從圖3中可看出，改進(jìn)的群搜索優(yōu)化算法在測(cè)試函數(shù)f6上在3000次迭代之前得到的平均適應(yīng)度均優(yōu)于標(biāo)準(zhǔn)GSO算法，在3500次迭代后收斂速度明顯優(yōu)于標(biāo)準(zhǔn)GSO算法的收斂速度，且得到更好的平均適應(yīng)度.由圖4可知，雖然GGSO算法的收斂速度與標(biāo)準(zhǔn)GSO算法中收斂速度一致，但是可以得到比標(biāo)準(zhǔn)GSO算法更好的平均適應(yīng)度.

圖3 測(cè)試函數(shù)f6結(jié)果對(duì)比Fig. 3 Comparison of benchmark function f6 results

圖4 測(cè)試函數(shù)f11結(jié)果對(duì)比Fig. 4 Comparison of benchmark function f11 results

4 結(jié) 論

在標(biāo)準(zhǔn)GSO算法基礎(chǔ)上，通過對(duì)算法中發(fā)現(xiàn)者的搜索策略進(jìn)行改進(jìn)，以達(dá)到提高算法的收斂速度和精度的效果.針對(duì)標(biāo)準(zhǔn)GSO算法未考慮全局最優(yōu)值的影響，通過在發(fā)現(xiàn)者搜索過程中加入全局最優(yōu)值，一定程度增加了種群的多樣性，算法的收斂速度和精度相比之前有所提高，避免了發(fā)現(xiàn)者在搜索時(shí)陷入局部最優(yōu).實(shí)驗(yàn)結(jié)果表明，標(biāo)準(zhǔn)GSO算法的不足之處在GGSO算法上有一定的改進(jìn)和彌補(bǔ).未來工作尚需在發(fā)現(xiàn)者和加入者搜索過程中加入更多優(yōu)化策略，把改進(jìn)過的群搜索優(yōu)化算法具體應(yīng)用實(shí)現(xiàn).