基于分解和向量的多目標(biāo)鯊魚優(yōu)化算法

李宏偉

(太原城市職業(yè)技術(shù)學(xué)院信息工程系,山西 太原 030001)

0 引 言

多目標(biāo)優(yōu)化問題[1-2](Multi-objective Optimization Problem, MOP)是指在一個系統(tǒng)中使多個目標(biāo)在一定約束條件下能夠同時達(dá)到最優(yōu)的問題。求解多目標(biāo)優(yōu)化問題時，得到的不是一個唯一解，而是一組由非劣解構(gòu)成的解集，即Pareto解集[3-5]。智能優(yōu)化算法具有較好的全局搜索能力，且具有一次運(yùn)行可以得到多個解的特性，因此，多目標(biāo)智能優(yōu)化算法已被廣泛應(yīng)用于解決多目標(biāo)優(yōu)化問題[6-8]。

鯊魚優(yōu)化算法(Shark Smell Optimization, SSO)是由Abedinia等人[9]提出的一類啟發(fā)式智能優(yōu)化算法。算法收斂精度較高，易于實(shí)現(xiàn)。在處理單目標(biāo)優(yōu)化問題上，鯊魚優(yōu)化算法已經(jīng)展現(xiàn)出較強(qiáng)的優(yōu)化能力。但在求解MOP問題優(yōu)化中，基本鯊魚算法面臨容易陷入局部最優(yōu)、收斂性差、通用性不好和計(jì)算復(fù)雜度高等缺點(diǎn)，導(dǎo)致鯊魚優(yōu)化算法在多目標(biāo)優(yōu)化問題上還未取得有效的成果，因此，基本鯊魚優(yōu)化算法還存在大量的待改進(jìn)之處。Kumar等人[10]提出了MOSLPSO算法，該算法基于自學(xué)習(xí)思想，將種群的速度及位置更新策略進(jìn)行改進(jìn)，對于不同粒子采用不同的學(xué)習(xí)方式，使得每個粒子搜索的有效性增強(qiáng)。文獻(xiàn)[11]提出多策略變異方法作用于粒子位置更新，將種群劃分區(qū)域，根據(jù)粒子在不同區(qū)域的性能選擇不同的變異方法，從而避免種群的早熟收斂現(xiàn)象。NSGAII-DS[12]中提出的快速非支配排序和擁擠距離策略在解決多目標(biāo)優(yōu)化問題上表現(xiàn)出了良好的性能。文獻(xiàn)[13]將粒子群算法與非劣排序相結(jié)合，提出了非劣排序的多目標(biāo)粒子群優(yōu)化算法(NSPSO)。該算法基于Pareto支配關(guān)系比較候選解之間的優(yōu)劣關(guān)系，然后在外部存檔集中保存搜索過程中的最優(yōu)解。除此之外，采用自適應(yīng)變異策略維護(hù)種群的多樣性。文獻(xiàn)[14]提出了一種高效的協(xié)同進(jìn)化多目標(biāo)粒子群優(yōu)化算法(ECMPSO)，該算法利用動態(tài)多群處理多個目標(biāo)，考慮每個群對一個目標(biāo)進(jìn)行優(yōu)化，并通過采用3級粒子群優(yōu)化(PSO)更新規(guī)則保持新發(fā)現(xiàn)的非支配解的多樣性。在Pareto支配關(guān)系基礎(chǔ)上提出的多目標(biāo)粒子群算法能夠保證算法的收斂性，但在解集分布性上仍需要密度策略維護(hù)解集的分布性。

自文獻(xiàn)[15]提出基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)以來，打破了對Pareto支配關(guān)系的局面。MOEA/D算法通過將一個MOP轉(zhuǎn)換成一組單目標(biāo)優(yōu)化問題，在一次運(yùn)行后同時優(yōu)化得到最優(yōu)解集。文獻(xiàn)[16]提出了基于分解的多目標(biāo)粒子群算法(MOPSO/D),該算法將粒子群算法替換進(jìn)化算法，并采用分解方法計(jì)算領(lǐng)導(dǎo)粒子的聚合函數(shù)值進(jìn)行更新。為了提高多目標(biāo)粒子群算法的收斂性和解集的分布性。文獻(xiàn)[17]提出了采用2種方法結(jié)合的策略，基于分解和支配的多目標(biāo)粒子群算法(DDMOPSO)的提出改進(jìn)了算法收斂性和分布性。文獻(xiàn)[18]提出了一種基于Pareto支配和分解的多目標(biāo)粒子群算法，在支配方法的基礎(chǔ)上，利用分解方法為種群選擇全局最優(yōu)粒子，在一定程度上降低了領(lǐng)導(dǎo)個體選擇過程中的計(jì)算負(fù)載。文獻(xiàn)[19]在分解方法的思想基礎(chǔ)上，提出了一種參考向量引導(dǎo)的進(jìn)化算法，使用一組在目標(biāo)空間中均勻分布的參考向量對種群進(jìn)行優(yōu)化，改善種群的收斂性和多樣性。

通過以上算法的研究，同時為了提高SSO在處理復(fù)雜的多目標(biāo)優(yōu)化問題時的性能，本文提出一種基于分解和向量的多目標(biāo)鯊魚優(yōu)化算法(DVMOSSO)。本文在精英解集中采用參考向量計(jì)算角度懲罰距離標(biāo)量值來平衡目標(biāo)空間中解的收斂性和多樣性，并采用高斯變異策略重新初始化鯊魚個體，避免陷入局部最優(yōu)，采用多項(xiàng)式變異維護(hù)種群的多樣性。

1 背景知識

1.1 分解方法

分解方法是將一個多目標(biāo)優(yōu)化問題轉(zhuǎn)化成一組單目標(biāo)優(yōu)化問題，通常分解方法分為Weighted Sum、Tchebycheff和PBI。本文采用的是Tchebycheff分解方法，即：

(1)

1.2 參考向量

(2)

其中，ui=(u1,u2,…,ul)，‖·‖為計(jì)算范數(shù)，即矢量的長度。2個向量之間的角度關(guān)系，可以通過計(jì)算余弦值來表示，公式為：

(3)

其中，w1、w2為2個向量。計(jì)算2個向量之間的余弦值可以測量目標(biāo)空間和參考向量之間的關(guān)系。

1.3 基本鯊魚優(yōu)化算法

鯊魚優(yōu)化算法在迭代過程中會不斷向最優(yōu)解進(jìn)行靠攏，同時由于鯊魚在游動過程中具有慣性，導(dǎo)致鯊魚粒子在向最優(yōu)解靠攏的過程中，游動速度不斷增加。此外，鯊魚優(yōu)化算法在進(jìn)行速度更新的過程中，每一個階段的速度均受上一個階段的速度大小的影響，因此鯊魚粒子的速度是有限定范圍的。鯊魚粒子更新公式為：

(4)

(5)

值得注意的是，與傳統(tǒng)智能優(yōu)化算法位置更新方法不同的是，鯊魚算法在更新過程中不只考慮全局最優(yōu)解對種群中鯊魚粒子的吸引，同時也會在尋優(yōu)路徑上進(jìn)行小范圍旋轉(zhuǎn)運(yùn)動，這是鯊魚在捕獵時的一種真實(shí)方式，這種鄰域隨機(jī)搜索方式，使得鯊魚粒子可以更好地進(jìn)行全局搜索，提高搜索精度，這種位置更新方式的數(shù)學(xué)表達(dá)式為：

(6)

最后，鯊魚在進(jìn)行捕獵時，會不斷向氣味更濃的獵物發(fā)起攻擊，這一特點(diǎn)在SSO中可用式(7)進(jìn)行實(shí)現(xiàn)。

(7)

2 DVMOSSO算法

下面分別從基于向量的精英解集選擇、基于分解的領(lǐng)導(dǎo)粒子更新、重新初始化、以及算法整體流程4個方面詳細(xì)介紹本文提出的DVMOSSO算法。

2.1 基于分解和向量進(jìn)行精英解集選擇

本文使用參考向量將精英解集的目標(biāo)空間劃分為多個子空間，并且在每個子空間內(nèi)單獨(dú)執(zhí)行選擇。目標(biāo)空間分區(qū)相當(dāng)于為每個參考向量指定的子問題添加約束，這顯示出能夠幫助平衡基于分解的方法中的收斂和多樣性，更新過程如算法1所示。

算法1 基于向量的精英解集選擇

Input:當(dāng)代父代種群Pt和當(dāng)代子代種群Qt,最小參考點(diǎn)zmin，參考向量wi,種群規(guī)模NP

Output:下一代種群Pt+1

1:Rt=Pt∪Qt

2: 根據(jù)公式(8)對Rt進(jìn)行目標(biāo)函數(shù)值轉(zhuǎn)換

3: 使用公式(10)計(jì)算解和向量之間的角度懲罰距離

4: fori=1 to NP

5:k=argmin(di)

6:Pt+1=Pt+1∪{Rt(i,k)}

7: end for

8: ReturnPt+1

本文提出的參考向量指導(dǎo)精英解集選擇的策略主要從以下4個步驟展開：

1)目標(biāo)函數(shù)值轉(zhuǎn)換。這是為確保所有轉(zhuǎn)換的目標(biāo)函數(shù)值都在第一象限內(nèi)，并且每個目標(biāo)函數(shù)值得極值點(diǎn)都在坐標(biāo)軸上，從而最大化參考向量的覆蓋范圍。轉(zhuǎn)化公式為：

f′i=fi-zmin

(8)

其中，f′i和fi分別為轉(zhuǎn)換前后的目標(biāo)函數(shù)值，zmin為每個目標(biāo)函數(shù)值上的最小值。

2)種群劃分。這是為將每個子問題都劃分到其最近的參考向量，劃分標(biāo)準(zhǔn)則是根據(jù)子問題的目標(biāo)函數(shù)值fi與參考向量ci之間的余弦值，其計(jì)算公式為：

(9)

由式(9)可以知道，余弦值越大表明子問題距離參考向量越近。

3)計(jì)算角度懲罰距離。這是為具有選擇收斂性和分布性的雙重標(biāo)準(zhǔn)，子問題到最小參考點(diǎn)的距離‖f′i‖代表收斂性標(biāo)準(zhǔn)，子問題與參考向量之間的角度代表了分布性標(biāo)準(zhǔn)[19]。計(jì)算角度懲罰距離的公式為：

di=(1+P(θi))·‖f′i‖

(10)

4)精英選擇。通過計(jì)算角度懲罰距離公式可以知道，子問題與參考向量之間的角度越小代表該粒子的分布性越好，而‖f′i‖越小則代表距離收斂前沿越小，也就是收斂性越好。所以在存檔集中選擇角度懲罰距離更小的粒子作為進(jìn)入下一代的精英解。

2.2 領(lǐng)導(dǎo)粒子更新

個體最優(yōu)粒子的選擇影響粒子的收斂速度，本文采用分解方法Tchebycheff聚合函數(shù)值進(jìn)行更新。更新過程如算法2所示。

算法2 基于分解的個體最優(yōu)粒子更新

1: Tchebycheff聚合方法

3:xk=xk+1

4:a=0

5: else

6:a=a+1

7: End

如果候選解粒子被更新，粒子年齡則重置為0，否則粒子年齡需要加1。全局最優(yōu)粒子的選擇則是從精英解集中隨機(jī)選擇，增加全局搜索的概率。

2.3 變異操作

為了避免DVMOSSO算法陷入局部最優(yōu)狀態(tài)，本文算法采用高斯變異策略重置鯊魚粒子。當(dāng)鯊魚粒子在預(yù)設(shè)粒子年齡內(nèi)的聚合函數(shù)值一直優(yōu)于新鯊魚粒子，鯊魚粒子可能陷入局部最優(yōu)，需要重置。重置公式為：

(11)

其中，xk+1為k+1代的鯊魚粒子位置，xg為全局最優(yōu)粒子位置，x為個體粒子位置。

2.4 算法實(shí)現(xiàn)

本文提出的基于分解和向量進(jìn)化的多目標(biāo)鯊魚優(yōu)化算法流程如算法3所示。

算法3 DVMOSSO算法整體流程

1: 初始化種群，精英解集archive

2: Fori=1:NP

3: ifa

4: 根據(jù)公式(4)更新鯊魚個體速度

5: 根據(jù)公式(5)更新鯊魚個體位置

6: 根據(jù)公式(6)對鯊魚個體進(jìn)行鄰域搜索

7: else

8: 根據(jù)公式(11)重置鯊魚粒子位置

9: end

10: 計(jì)算新鯊魚粒子的函數(shù)值并更新參考點(diǎn)

11: 根據(jù)算法2更新最優(yōu)鯊魚粒子

12: 根據(jù)算法1更新精英解集

13: 采用多項(xiàng)式變異并再次更新archive集

14: 從archive集中更新全局最優(yōu)粒子

15: end For

16: 滿足終止條件

14: 輸出archive解集

由算法3可以看出，根據(jù)公式(4)～公式(6)得到新的粒子。產(chǎn)生新粒子的過程中，為了避免粒子陷入局部最優(yōu)，采用公式(11)重新初始化粒子。根據(jù)算法2更新鯊魚粒子得到子代種群，然后將父代種群與子代種群合并后，根據(jù)算法1更新精英解集(archive)。另外，在archive解集中采用多項(xiàng)式變異策略增加種群的多樣性，然后從archive解集中選擇全局最優(yōu)粒子。最后滿足終止條件時，輸出archive解集。

3 性能測試與分析

3.1 測試函數(shù)

本文選擇ZDT系列測試函數(shù)[20]和DTLZ系列測試函數(shù)[21]，將本文提出的DVMOSSO算法的性能與NSGAII-DS[12]、dMOSSO、MOEA/D[22]、MOSSO和MMOPSO[23]算法的性能進(jìn)行對比仿真實(shí)驗(yàn)。其中MOSSO算法為基本多目標(biāo)鯊魚算法，dMOSSO算法為基于分解的多目標(biāo)鯊魚算法。為了驗(yàn)證該算法在不同特征的測試函數(shù)上表現(xiàn)出良好的性能，表1中列出了測試函數(shù)的特性、決策變量和目標(biāo)個數(shù)。

表1 測試函數(shù)特征表

3.2 評價指標(biāo)

評價一個算法的性能主要從算法的收斂性和分布性上進(jìn)行評價，IGD是綜合性指標(biāo)[24]，既能評價收斂性又能評價分布性。IGD函數(shù)定義為：

(12)

其中，di是目標(biāo)空間中向量與真實(shí)前沿上所有點(diǎn)的最短歐氏距離，n是目標(biāo)空間中解的個數(shù)。

3.3 實(shí)驗(yàn)參數(shù)設(shè)置

為了確保實(shí)驗(yàn)數(shù)據(jù)對比過程的公平性，本文提出的算法和對比算法在每個測試函數(shù)上獨(dú)立運(yùn)行30次。對于2個目標(biāo)個數(shù)的測試函數(shù)，種群規(guī)模為100，評價次數(shù)為100000次；對于3個目標(biāo)個數(shù)的測試函數(shù)，種群規(guī)模為200，評價次數(shù)為200000次。在DVMOSSO算法中，ηk=1,R1=0.25,R2=0.3，R3=0.2，個體的最大年齡Ta=2，精英解集規(guī)模等于種群規(guī)模。對比算法的參數(shù)參考相應(yīng)的文獻(xiàn)。

3.4 實(shí)驗(yàn)結(jié)果分析

1)實(shí)驗(yàn)數(shù)據(jù)分析。

本文提出的DVMOSSO算法與對比算法在每個測試函數(shù)上獨(dú)立運(yùn)行中的20次的IGD性能指標(biāo)的平均值和標(biāo)準(zhǔn)差統(tǒng)計(jì)如表2所示。通過表2可以看出，DVMOSSO算法在ZDT1、ZDT2、ZDT3、ZDT4、DTLZ1、DTLZ2和DTLZ7上的IGD的平均值(mean)取得了最小值，在表中用黑色加粗字體表示。下面從每個函數(shù)的特點(diǎn)進(jìn)行分析。

表2 DVMOSSO算法與對比算法IGD性能指標(biāo)的平均值和標(biāo)準(zhǔn)差統(tǒng)計(jì)

ZDT1是凸函數(shù)，DVMOSSO算法在函數(shù)上表現(xiàn)出明顯的優(yōu)勢即最小的IGD平均值和標(biāo)準(zhǔn)方差，其次表現(xiàn)良好的則是dMOSSO、MOSSO和MOEA/D，相對于NSGAII-DS和MMOPSO算法，基于分解的方法和多目標(biāo)鯊魚算法在求解ZDT1的凸問題時更能表現(xiàn)出良好的性能。對于ZDT2凹函數(shù)和ZDT3不連續(xù)函數(shù)，DVMOSSO取得最優(yōu)的IGD值，其次則是NSGAII-DS算法表現(xiàn)出次優(yōu)。而MOSSO和MMOPSO算法相對于基于分解算法的MOEA/D和dMOSSO表現(xiàn)出細(xì)微的優(yōu)勢。這也表明單純的基于分解的方法在求解凹問題和不連續(xù)問題時沒有明顯的優(yōu)勢。對于ZDT4多峰問題，DVMOSSO算法表現(xiàn)的優(yōu)勢明顯，MOSSO和MMOPSO算法對于處理ZDT4多峰函數(shù)時略差于DVMOSSO，但優(yōu)于其他算法。ZDT6是一個非均勻函數(shù)，MOEA/D表現(xiàn)出最優(yōu)的IGD值，DVMOSSO算法雖然在ZDT6函數(shù)上劣于MOEA/D，但與NSGAII-DS、dMOSSO、MMOPSO和MOSSO算法相比有明顯的優(yōu)勢。綜上所述，對于2維的ZDT系列函數(shù)，DVMOSSO算法整體上表現(xiàn)出了良好的性能，具有一定的對比性。

DTLZ1是一個多峰平面函數(shù)，DVMOSSO算法在IGD值上表現(xiàn)出了良好的性能，其次是MMOPSO。而dMOSSO對于處理多峰問題并不理想，對于處理多峰問題，多項(xiàng)式變異策略有關(guān)鍵的作用。DTLZ2是一個凹平面函數(shù)，DVMOSSO算法取得最優(yōu)的IGD值，dMOSSO和MOSSO算法在處理DTLZ2函數(shù)時也表現(xiàn)出了不錯的性能。至于DTLZ7不連續(xù)的面函數(shù)，DVMOSSO算法取得了IGD平均值的最優(yōu)值，但標(biāo)準(zhǔn)方差劣于MMOPSO。綜上所述，對于3維的DTLZ系列函數(shù)，DVMOSSO算法取得了有競爭性的性能。

總體來看，DVMOSSO算法的均值和方差要優(yōu)于其他5種算法。IGD指標(biāo)值可以同時評估算法的收斂性和分布性，因此，通過表2數(shù)據(jù)可以得到DVMOSSO算法在處理復(fù)雜多目標(biāo)問題時具有一定的競爭力。

2)實(shí)驗(yàn)圖分析。

圖1～圖8列出了DVMOSSO算法與5種對比算法的前沿圖。圖1、圖2和圖5列出了6種算法分別在ZDT1、ZDT2和ZDT6函數(shù)上的前沿圖，可以看出6種算法都能收斂到前沿上，但明顯可以看出DVMOSSO的最優(yōu)解集不僅收斂到最優(yōu)前沿，并在前沿上分布均勻。NSGAII-DS在分布性上略差一些。圖3列出6種算法在ZDT3函數(shù)上的前沿圖，由圖3可以看出MOEA/D和dMOSSO算法在兩端的分布并不理想，其他算法都能獲得良好的分布性。圖4列出了6種算法在ZDT4上的對比前沿圖，可以看出MOEA/D和dMOSSO在ZDT4未收斂到真實(shí)前沿上。圖5可以看出6種算法在ZDT6上都能表現(xiàn)出良好的收斂性和分布性。對于圖6的DTLZ1前沿圖，dMOSSO算法為收斂到真實(shí)前沿，MOEA/D和NSGAII-DS算法在DTLZ1上的分布性略差。圖7和圖8的dMOSSO和MOEA/D算法在分布性上主要依賴參考向量的分布，而DVMOSSO算法采用基于角度懲罰距離的選擇使解集的分布性更加均勻。NSGAII-DS算法在DTLZ2上近似Pareto前沿雖收斂到真實(shí)前沿但分布性略差。MOSSO算法和MMOPSO算法雖然在8個測試函數(shù)上均可收斂到真實(shí)前沿，但在DTLZ2和DTLZ7上的分布性較差。

圖1 DVMOSSO與對比算法在ZDT1測試函數(shù)上的前沿圖

圖2 DVMOSSO與對比算法在ZDT2測試函數(shù)上的前沿圖

圖3 DVMOSSO與對比算法在ZDT3測試函數(shù)上的前沿圖

圖4 DVMOSSO與對比算法在ZDT4測試函數(shù)上的前沿圖

圖5 DVMOSSO與對比算法在ZDT6測試函數(shù)上的前沿圖

圖6 DVMOSSO與對比算法在DTLZ1測試函數(shù)上的前沿圖

圖7 DVMOSSO與對比算法在DTLZ2測試函數(shù)上的前沿圖

圖8 DVMOSSO與對比算法在DTLZ7測試函數(shù)上的前沿圖

本文除了將DVMOSSO算法與對比算法進(jìn)行比較，還與該算法的子部件的功能進(jìn)行比較。本文主要從3個方面進(jìn)行說明：基于向量的精英解集選擇(A策略)、基于分解的領(lǐng)導(dǎo)粒子更新(B策略)和變異操作(C策略)。測試的IGD性能指標(biāo)如表3所示。

表3 DVMOSSO算法與該算法子部件的功能測試的IGD性能指標(biāo)的平均值和標(biāo)準(zhǔn)差統(tǒng)計(jì)

由表3中的數(shù)據(jù)可以看出，DVMOSSO算法比任何子策略單獨(dú)作用MOSSO時的性能更優(yōu)。通過數(shù)據(jù)可以看出，如果單獨(dú)采用基于向量更新精英解集(A策略)時，算法的整體性能與DVMOSSO算法最為接近，但除了在DTLZ1測試函數(shù)上。DTLZ1函數(shù)具有多峰特點(diǎn)，需要多項(xiàng)式變異操作增加種群的多樣性，從而使算法能夠收斂到真實(shí)前沿。也就是當(dāng)單獨(dú)采用變異策略(C策略)時，除了DTLZ1函數(shù)問題表現(xiàn)出相對較好的IGD值，其他的則與B策略表現(xiàn)相近，但都劣于DVMOSSO算法。從表3可以得出本文提出的策略具有一定的有效性。

另外，本文采用鯊魚算法作為優(yōu)化算子，在粒子更新的公式中，有R1、R2和R3這3個隨機(jī)參數(shù)需要人為確定。參數(shù)的確定需要一定的參考，由于參考文獻(xiàn)[25]采用R1=0.3，R2=0.4，R3=0.2，參考文獻(xiàn)[26]采用R1=0.4，R2=0.3，R3=0.25，因此本文采用R1=0.25，R2=0.3，R3=0.2。為了驗(yàn)證本文采用的參數(shù)具有一定的參考性，與另外2組參數(shù)進(jìn)行對比，得到的IGD平均值如表4所示。通過表4中IGD值的平均值可以看出，不同參數(shù)的設(shè)置對算法的總體影響并不明顯。

表4 DVMOSSO算法不同參數(shù)下的IGD性能指標(biāo)的平均值統(tǒng)計(jì)

總體而言，DVMOSSO算法在8個具有不同特性的函數(shù)上都收斂到了真實(shí)前沿，并且都表現(xiàn)出良好的分布性。說明本文提出的算法在處理復(fù)雜的多目標(biāo)問題時具有較強(qiáng)的競爭能力。

4 結(jié)束語

在處理復(fù)雜的多目標(biāo)優(yōu)化問題時，本文提出一種基于分解和向量的多目標(biāo)鯊魚優(yōu)化算法。通過在精英集采用參考向量計(jì)算角度懲罰距離標(biāo)量值來平衡目標(biāo)空間中的解的收斂性和多樣性。除此之外，為了避免粒子陷入局部最優(yōu)，采用高斯變異策略重新初始化粒子；精英解集中采用多項(xiàng)式變異增加種群的多樣性。實(shí)驗(yàn)結(jié)果表明該算法在處理復(fù)雜的多目標(biāo)優(yōu)化問題時，能夠得到收斂性和分布性更好的近似Pareto解集。