基于反向?qū)W習(xí)和種群引導(dǎo)的多目標(biāo)蝗蟲優(yōu)化算法*

邵鴻南,梁 倩,王李森,馬云鵬,項賢鵬

(1.東北財經(jīng)大學(xué)統(tǒng)計學(xué)院,遼寧 大連 116000;2.哈爾濱商業(yè)大學(xué)經(jīng)濟(jì)學(xué)院，黑龍江 哈爾濱 150000)

1 引言

多目標(biāo)優(yōu)化是多準(zhǔn)則決策的分支領(lǐng)域，它是涉及多個目標(biāo)函數(shù)同時優(yōu)化的數(shù)學(xué)問題。多目標(biāo)優(yōu)化不可能使所有的目標(biāo)都達(dá)到最優(yōu)值，需要在多個相互沖突的目標(biāo)之間進(jìn)行權(quán)衡，做出最優(yōu)決策。因此，對于多目標(biāo)的研究十分重要，應(yīng)該設(shè)計更多的優(yōu)化算法以解決實際問題。

國內(nèi)對于蝗蟲優(yōu)化算法GOA(Grasshopper Optimization Algorithm)的研究主要是將算法與其他模型結(jié)合并應(yīng)用在工程問題當(dāng)中。張伍等[1]采用了二進(jìn)制版本的蝗蟲特征選擇法，將蝗蟲優(yōu)化算法與多核模糊粗糙集模型相結(jié)合，提出了模糊粗糙集蝗蟲優(yōu)化算法FRSGOA (Fuzzy Rough Set Grasshopper Optimization Algorithm)。陳冬[2]在標(biāo)準(zhǔn)蝗蟲優(yōu)化算法的基礎(chǔ)上提出了一種正余弦混沌蝗蟲優(yōu)化算法SCCGOA (Sine Cosine Chaotic Grasshopper Optimization Algorithm)。該算法先由GOA算法搜尋到當(dāng)前最優(yōu)位置，之后在該位置進(jìn)行混沌局部搜索，將正余弦搜索機(jī)制引入到混沌變量的波仔映射中。趙然等[3]將Levy隨機(jī)飛行引入蝗蟲優(yōu)化算法，提高了局部搜索的能力，又加入了線性遞減參數(shù)的隨機(jī)突變策略，提出了一種基于 Levy飛行的改進(jìn)蝗蟲優(yōu)化算法 LBGOA (Grasshopper Optimization Algorithm Based on Levy flight)。

國外對于蝗蟲優(yōu)化算法的研究開始得比較早。Mirjalili等[4]提出了多目標(biāo)蝗蟲優(yōu)化算法MOGOA(Multi-Objective Grasshopper Optimization Algorithm)，用外部檔案來保存帕累托最優(yōu)解，然后利用輪盤賭選擇引導(dǎo)者，在多種測試函數(shù)上都表現(xiàn)優(yōu)異。Talaat等[5]結(jié)合多層前饋神經(jīng)網(wǎng)絡(luò)和蝗蟲優(yōu)化算法，使用組合模型進(jìn)行高精度的負(fù)荷預(yù)測，實驗結(jié)果表明GOA的引入能夠大幅度提升模型的準(zhǔn)確性。Gampa等[6]提出了一種基于兩階段蝗蟲優(yōu)化算法的模糊多目標(biāo)方法，利用該方法可以優(yōu)化分布式發(fā)電和并聯(lián)電容器的大小和分配，確定電動汽車充電站的最佳位置和充電站的車輛數(shù)量。由以上文獻(xiàn)可以看出，目前關(guān)于多目標(biāo)蝗蟲優(yōu)化算法的研究比較少，應(yīng)用也不夠廣泛，學(xué)者們都致力于算法的應(yīng)用，而忽略了算法本身的改進(jìn)。蝗蟲優(yōu)化算法位置的更新公式仍具有潛在價值，平衡開發(fā)與探索之間協(xié)作還有很大的改進(jìn)空間?；认x優(yōu)化算法在各方面都展現(xiàn)出了巨大的研究價值，因此對于多目標(biāo)蝗蟲優(yōu)化算法的研究仍需要投入大量時間。

與之前學(xué)者的研究成果相比較，本文所提出的基于反向?qū)W習(xí)和種群引導(dǎo)的多目標(biāo)蝗蟲優(yōu)化算法OPMOGOA(Multi-Objective Grasshopper Optimization Algorithm based on Opposition-based learning and Population guidance)的創(chuàng)新點有以下幾點：

(1)種群引導(dǎo)機(jī)制的使用。單一的最優(yōu)解引導(dǎo)機(jī)制在算法的后期不能全面引導(dǎo)種群向著更好的分布進(jìn)化，而種群引導(dǎo)機(jī)制[7]的使用能夠較好地利用一部分最優(yōu)解所包含的信息引導(dǎo)種群的演化，這對于多目標(biāo)優(yōu)化算法所求解的分布性有著巨大的提升作用。

(2)反向?qū)W習(xí)機(jī)制[8]的使用。反向?qū)W習(xí)機(jī)制的應(yīng)用能夠使種群搜索的范圍更加廣泛，種群初始化時使用反向?qū)W習(xí)機(jī)制會使得初始種群分布更加合理。

(3)高斯突變[9]的使用。高斯突變較高概率下會圍繞中心周圍進(jìn)行突變，這就使得迭代后期能夠更加細(xì)致地搜索最優(yōu)解的附近。

2 基本知識

2.1 多目標(biāo)優(yōu)化問題

一個具有N個維度的決策變量和M個維度的目標(biāo)函數(shù)的問題可以描述為式(1)所示:

minY=[f1(Xi),f2(Xi),…,fM(Xi)]

(1)

決策變量解A優(yōu)于解B，則A在所有的目標(biāo)函數(shù)都小于或等于B，并且至少在一個目標(biāo)函數(shù)中，A是嚴(yán)格優(yōu)于B的，記為AB。在解集合中，不存在任何一個解嚴(yán)格優(yōu)于當(dāng)前解，這樣的解稱為最優(yōu)解。由帕累托最優(yōu)解構(gòu)成的集合被稱為帕累托最優(yōu)解集。所有的帕累托最優(yōu)解集所對應(yīng)的目標(biāo)向量就是帕累托前沿。

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

蝗蟲優(yōu)化算法[10]的核心思想是蝗蟲根據(jù)食物的位置和蝗蟲群其他個體的位置進(jìn)行跳躍移動，蝗蟲之間有排斥區(qū)、舒適區(qū)和吸引區(qū)，蝗蟲根據(jù)數(shù)學(xué)模型所提供的位置更新公式更新所在位置。所有的蝗蟲進(jìn)行移動后，更新所有蝗蟲的適應(yīng)度值，食物的位置由最優(yōu)的適應(yīng)度值確定，當(dāng)所有的蝗蟲都移動到舒適區(qū)，蝗蟲將不再移動。

蝗蟲種群中各個蝗蟲的位置更新模型表示為Xi=Si+Gi+Ai,其中Xi代表第i個蝗蟲的位置，即決策變量，Si代表社會影響因素，Gi代表重力影響因素，Ai代表風(fēng)向影響因素。Si的定義如式(2)所示：

(2)

(3)

其中，f代表吸引力強(qiáng)度，通常設(shè)置為0.5，l代表吸引力長度比例參數(shù)，通常設(shè)置為1.5。r代表2個個體間的距離，當(dāng)S(r)>0時,2只蝗蟲處于吸引狀態(tài)；當(dāng)S(r)=0時,2只蝗蟲處于舒適狀態(tài)；當(dāng)S(r)<0時，2只蝗蟲處于排斥狀態(tài)。

Gi的計算公式如式(4)所示：

(4)

Ai的計算公式如式(5)所示：

(5)

將上述公式整合后得到：

(6)

但是這一模型并不能直接應(yīng)用于求解問題，因此對它進(jìn)行如下改進(jìn)：

(7)

3 反向?qū)W習(xí)和種群引導(dǎo)的多目標(biāo)蝗蟲優(yōu)化算法

3.1 反向?qū)W習(xí)機(jī)制

為了更好地學(xué)習(xí)反向?qū)W習(xí)機(jī)制，首先來解釋反向點的概念，以一維標(biāo)量為例，圖1所示a的反向點為z。

Figure 1 Reverse point圖1 反向點

a的上下限分別是lower和upper，則lower+upper-a稱為a的反向點。明確反向點的定義之后，在每次位置更新后，求出每個解的反向點，比較當(dāng)前解和反向點的目標(biāo)函數(shù)值，如果反向點有更優(yōu)的目標(biāo)值，則用反向點代替當(dāng)前解，否則保持不變。本文將反向?qū)W習(xí)機(jī)制應(yīng)用于種群初始化策略和迭代更新過程。

3.2 高斯變異

為了解決多目標(biāo)算法陷入局部最優(yōu)解的問題，本文在位置更新時加入了高斯變異算子。高斯變異算子相比于其他的變異算子，在均值附近變異的概率最大，而產(chǎn)生變異是以上代位置為中心的變異，這就使得算法在局部的開發(fā)更加有效。在算法運(yùn)行過程中，每個個體決策變量的每個維度都有一定幾率發(fā)生標(biāo)準(zhǔn)差為σ的高斯變異，其數(shù)學(xué)模型如式(8)～式(10)所示：

(8)

(9)

σ=(ubk-lbk)/6

(10)

3.3 種群引導(dǎo)

由于蝗蟲優(yōu)化算法需要最優(yōu)解作為引導(dǎo)，引導(dǎo)其他的蝗蟲向最優(yōu)解移動，因此，最優(yōu)解的選取至關(guān)重要。但是，由于偶然性的存在，有時選擇的最優(yōu)解不夠合理。并且全局最優(yōu)解不應(yīng)該只局限于一個固定的解，應(yīng)該是較為優(yōu)秀的解的集合。本文所提到的種群引導(dǎo)正是基于這樣的目的，每次從帕累托等級為1的個體中隨機(jī)選取10%作為最優(yōu)解的集合，每個蝗蟲個體從最優(yōu)的10%的解中隨機(jī)選取一個向其移動，經(jīng)過這種引導(dǎo)方式的解有更好的分布。

3.4 帕累托等級排序

通過非支配排序?qū)⒎N群數(shù)為n的種群分類為分級的帕累托前沿。首先將種群中所有的帕累托前沿求出，標(biāo)記帕累托前沿等級為1。之后將帕累托等級為1的個體忽略，在剩下的個體中求帕累托前沿，并記錄帕累托等級為2，之后循環(huán)進(jìn)行，直至將所有的解都分類。通過引入帕累托等級[11]和擁擠度的計算，能夠?qū)⑺械慕膺M(jìn)行排序，以便在種群混合時能夠選擇出比較好的前N個解。

3.5 擁擠距離

擁擠距離用來描述非支配解分布的特征，以便選出帕累托最優(yōu)集中10%的優(yōu)質(zhì)解。在帕累托解集中，每個非支配解都有一個擁擠距離，用于表示離它最近的非支配解在各個目標(biāo)函數(shù)維度上的距離之和。擁擠距離值越大，說明離當(dāng)前解最近的解位置較遠(yuǎn)，即帕累托解比較稀疏。相反，擁擠距離越小，說明離當(dāng)前解最近的解位置較近，即帕累托解越密集。引入擁擠距離的目的是通過當(dāng)前帕累托最優(yōu)解的分布情況來選擇最優(yōu)帕累托解，以引導(dǎo)種群發(fā)現(xiàn)使得帕累托前沿更均勻的解。而在帕累托前沿中的邊界解中，擁擠距離被設(shè)定為inf，其他解的擁擠距離的計算公式如式(11)所示:

(11)

3.6 算法流程

本文算法首先通過反向?qū)W習(xí)機(jī)制來初始化種群，利用最優(yōu)解的10%作為引導(dǎo)者進(jìn)行位置更新，更新位置后結(jié)合反向?qū)W習(xí)機(jī)制，選擇較優(yōu)解作為子代，并以一定的概率產(chǎn)生高斯突變，將最終產(chǎn)生的子代與父代混合，根據(jù)精英保留策略篩選出較優(yōu)解進(jìn)入下一代。該過程不斷迭代直至達(dá)到最大迭代次數(shù)。具體流程如算法1所示。

算法1OPMOGOA

輸入:種群數(shù)量，最大迭代次數(shù)。

輸出:帕累托最優(yōu)解。

步驟1初始化種群并計算反向點及其適應(yīng)度值。

步驟2將種群合并后計算帕累托等級和擁擠距離。優(yōu)先選擇較低的帕累托等級，當(dāng)帕累托等級相同時選擇擁擠距離較大的解。根據(jù)此規(guī)則選取前N個個體作為初始種群。

步驟3從帕累托等級為1的個體中隨機(jī)選擇10%作為種群引導(dǎo)。

步驟4每個個體從已選取的10%的解中隨機(jī)選取一個作為引導(dǎo)者，對所有的蝗蟲位置進(jìn)行更新。

步驟5計算反向點與當(dāng)前候選解，選擇更優(yōu)解進(jìn)入下一代，如果反向點與當(dāng)前候選解互不支配，以0.5的概率進(jìn)行選擇。

步驟6對種群中每個蝗蟲產(chǎn)生一個隨機(jī)數(shù)，當(dāng)隨機(jī)數(shù)小于p時對該蝗蟲位置進(jìn)行高斯突變。

步驟7將子代與父代進(jìn)行合并，重新計算帕累托等級和擁擠距離，根據(jù)步驟2的篩選規(guī)則選擇前N個個體進(jìn)入下一代，以保證種群數(shù)量維持不變。

步驟8判斷是否滿足最大迭代次數(shù)，不滿足最大迭代次數(shù)則重新執(zhí)行步驟3～步驟8。

4 實驗

4.1 實驗設(shè)置

為了進(jìn)一步驗證改進(jìn)的算法具有良好的表現(xiàn)，本文選取了4種算法與改進(jìn)的算法進(jìn)行比較，分別是多目標(biāo)粒子群優(yōu)化MOPSO(Multiple Objective Particle Swarm Optimization)算法[12]、多目標(biāo)布谷鳥搜索MOCS(Multi-Objective Cuckoo Search)算法[13]、經(jīng)典多目標(biāo)蝗蟲優(yōu)化算法MOGOA(Multi-Objective Grasshopper Optimization Algorithm)[14]和多目標(biāo)鯨魚優(yōu)化算法MOWOA(Multi-Objective Whale Optimization Algorithm)[15],測試函數(shù)選擇2個目標(biāo)的測試函數(shù)ZDT1和ZDT2[16]，以及3個目標(biāo)函數(shù)的VNT2和VNT3[17]。在測試函數(shù)中分為有約束條件和沒有約束條件，這就給帕累托前沿的求解帶來了巨大的困難，但是OPMOGOA的表現(xiàn)依舊出色。實驗環(huán)境為64位Windows 10系統(tǒng)，CPU為AMD R5 3500U 2.10 GHz，內(nèi)存為8 GB，編程語言為Matlab。每個算法獨立運(yùn)行30次然后計算出反轉(zhuǎn)世代距離IGD(Inverted Generational Distance)[18]和超體積指標(biāo)HV(Hyper Volume)[19]的均值與方差。

4.2 性能指標(biāo)

4.2.1 反轉(zhuǎn)世代距離

反轉(zhuǎn)世代距離IGD是每個真實帕累托前沿上的參考點與算法所求解的最近距離的平均值，如式(12)所示：

(12)

其中，P為分布在真實帕累托前沿上的點的集合，|P|為集合P中的點的個數(shù)，Q為算法獲取的帕累托最優(yōu)解的集合，v代表測試函數(shù)中真實帕累托前沿上的參考點集合。d(v,Q)代表v與集合Q中的點的最小歐氏距離。當(dāng)算法獲得的解比較集中時，d(v,Q)的值較大，導(dǎo)致IGD值較大。當(dāng)獲得的解離帕累托真實前沿比較遠(yuǎn)時，參考點與獲得的解之間的距離之和則會相對較大。因此，IGD能夠同時評價多樣性和收斂性。IGD值越小，說明算法所求的解離真實帕累托前沿越近或者解的分布越均勻。

4.2.2 超體積指標(biāo)

超體積指標(biāo)HV是度量非支配解集所支配區(qū)域的大小。

(13)

其中，δ表示 Lebesgue 測度，用來測量體積。 |S|表示非支配解集中解的數(shù)目，vi表示參照點與解集中第i個解構(gòu)成的超體積。HV值越大，表示算法的綜合性能越好。

4.3 實驗結(jié)果與分析

4.3.1 種群引導(dǎo)、高斯變異、反向?qū)W習(xí)機(jī)制的驗證

為了進(jìn)一步體現(xiàn)算法中引入種群引導(dǎo)、高斯變異算子和反向?qū)W習(xí)機(jī)制的作用，本文將所提出的算法在ZDT1函數(shù)上進(jìn)行了實驗，采用控制變量法，在種群數(shù)量和迭代次數(shù)相同的情況下對比了引入改進(jìn)和未引入改進(jìn)時的實驗指標(biāo)。鑒于各部分改進(jìn)對于算法收斂速度的提升效果的影響各不相同，因此各對比實驗的迭代次數(shù)分別設(shè)置為60次、80次和90次。實驗分別運(yùn)行30次，同樣取均值作為比較，記引入種群引導(dǎo)的算法為PG-MOGOA，引入高斯變異的算法為GS-MOGOA，引入反向?qū)W習(xí)的算法為OBL-MOGOA，未引入相應(yīng)改進(jìn)的算法記為MOGOA。各實驗結(jié)果對比圖如圖2～圖4所示，其中橫坐標(biāo)和縱坐標(biāo)分別表示測試函數(shù)ZDT1的目標(biāo)函數(shù)維度。

Figure 2 Comparison of population guidance圖2 種群引導(dǎo)的對比圖

Figure 3 Comparison of Gaussian mutation圖3 高斯變異的對比圖

Figure 4 Comparison of back learning mechanism圖4 反向?qū)W習(xí)機(jī)制的對比圖

未引入種群引導(dǎo)的MOGOA 30次實驗的IGD和HV均值分別是3.192E-01，3.081E-01，PG-MOGOA的IGD和HV均值分別是1.361E-02，7.054E-01，可見種群引導(dǎo)對算法的提升效果十分明顯。結(jié)合圖2可以看出，未引入種群引導(dǎo)時，算法所求的帕累托最優(yōu)解集中在右下角，并且解的分布并不均勻。這是由于算法在選擇最優(yōu)解時不能全面地引導(dǎo)種群的進(jìn)化，若算法每次僅選擇單個最優(yōu)解進(jìn)行引導(dǎo)會讓解的分布比較集中。因此，種群引導(dǎo)的引入能夠讓解的分布性得到明顯的提升。

未引入高斯變異的MOGOA的IGD和HV均值分別是3.447E-02，6.844E-01，引入后的均值分別是1.4121E-02，7.0476E-01，高斯變異的引入使得各指標(biāo)值都有了改善。結(jié)合圖3可以看出，未引入高斯變異時的解均勻且光滑，已經(jīng)陷入局部最優(yōu)，而高斯變異的引入能使算法跳出局部最優(yōu)解，從而使收斂性得到提升。

未引入反向?qū)W習(xí)機(jī)制的MOGOA的IGD和HV均值分別是1.400E-02，7.049E-01，引入后的均值分別是8.5442E-03,7.129E-01。從圖4中可以看出，反向?qū)W習(xí)機(jī)制的引入對算法有著相對較小的提升作用。在算法中，反向?qū)W習(xí)機(jī)制不僅應(yīng)用在種群初始化中，也應(yīng)用在種群的位置更新過程中。初始化時反向?qū)W習(xí)機(jī)制的引入使得算法的初始分布更加全面，迭代更新過程中的應(yīng)用使算法的搜索范圍更為廣泛，使算法的性能有了良好的改善。

4.3.2 與其他算法的比較

從表1來看，OPMOGOA在ZDT1，ZDT2上的IGD值分別為1.367E-02，5.775E-03，相比于另外4種算法本文所提算法均值最小,且方差也最小，分別為8.760E-03，1.360E-03，可以看出OPMOGOA求得的解在收斂性和均勻性上的表現(xiàn)都十分出色。由于ZDT2函數(shù)的特殊性，MOCS、MOPSO、MOWOA和MOGOA都出現(xiàn)過收斂于一點，該點在帕累托最優(yōu)前沿上，這會導(dǎo)致IGD值為0，使總體均值偏小，因此在這里將所有IGD為0的實驗結(jié)果去掉后求平均。在ZDT2上運(yùn)行的30次中，MOWOA、MOGOA、MOPSO、OPMOGOA和MOCS分別有11次、3次、11次、1次和0次IGD值為0的情況?？梢奜PMOGOA跳出局部最優(yōu)的能力較強(qiáng)。雖然MOCS沒有出現(xiàn)一次這種情況，但是其IGD值為3.377E-01，相對表現(xiàn)比較差。從表2來看，OPMOGOA在ZDT1和ZDT2上的HV值最大，分別為7.056E-01，4.426E-01，并且方差均為最小，表現(xiàn)十分穩(wěn)定，在2個目標(biāo)的ZDT系列函數(shù)上，MOGOA能夠較好地收斂到帕累托前沿。

Table 1 Comparsion of IGD value of algorithms表1 各算法的IGD值比較

表1和表2中所示分別為各算法的IGD和HV均值mean和方差std。從表1來看，在VNT2上OPMOGOA的IGD值僅次于MOCS的IGD值，MOGOA的表現(xiàn)最差。在VNT3上MOGOA的IGD值最小，為4.477E-02，改進(jìn)后的OPMOGOA反而略差，但是比另3種算法更好。從表2來看，在VNT2上，OPMOGOA的HV值為2.041E-00，位于第1位，相比經(jīng)典的MOGOA算法性能有所提升。在VNT3上，OPMOGOA的HV值仍然最大，為1.840E-01。除MOGOA的性能較差之外，其他3種算法之間相差不大?？偟膩碚f，5種算法在3個目標(biāo)的VNT系列上的表現(xiàn)相差不大，但MOGOA的算法有著一定的優(yōu)勢。

5 結(jié)束語

隨著信息化技術(shù)越來越發(fā)達(dá)，產(chǎn)生的信息越來越多樣化，多目標(biāo)算法優(yōu)化對象的規(guī)模越來越大，約束條件也越來越多，因此學(xué)者們對于多目標(biāo)算法性能的要求也越來越高，這給多目標(biāo)優(yōu)化帶來了更大的挑戰(zhàn) 。本文所提出的多目標(biāo)蝗蟲優(yōu)化算法將反向?qū)W習(xí)機(jī)制應(yīng)用到產(chǎn)生初始解和迭代進(jìn)化的過程中，在蝗蟲移動過程中增加高斯變異算子，并加入帕累托最優(yōu)集中的隨機(jī)解集引導(dǎo)種群的移動，最后根據(jù)帕累托等級和擁擠度距離篩選精英個體進(jìn)行保留。實驗結(jié)果表明，3種改進(jìn)機(jī)制的引入在一定程度上提升了算法的性能。此外，本文的OPMOGOA算法相對于其他4種算法在IGD和HV上都有著明顯的優(yōu)勢，表明了多目標(biāo)蝗蟲優(yōu)化算法有著較大的研究價值。未來的研究工作將從以下2個方面進(jìn)行：(1)研究OPMOGOA的應(yīng)用領(lǐng)域，應(yīng)用多目標(biāo)蝗蟲優(yōu)化算法解決更多的實際問題；(2)改進(jìn)多目標(biāo)蝗蟲優(yōu)化算法，使其適應(yīng)更難更復(fù)雜的多目標(biāo)問題。

Table 2 Comparsion of HV value of algorithms表2 各算法HV值比較