一種改進(jìn)的多目標(biāo)正余弦優(yōu)化算法

王萬良，李偉琨，王宇樂，王 錚

(浙江工業(yè)大學(xué) 計算機(jī)學(xué)院視覺研究所，大數(shù)據(jù)重點實驗室，杭州 310023)E-mail：lwk@zjut.edu.cn

1 引 言

隨著技術(shù)的不斷革新，工業(yè)生產(chǎn)的迅速發(fā)展，優(yōu)化問題已逐漸成為現(xiàn)行科學(xué)與工程領(lǐng)域的研究熱點.在這其中，元啟發(fā)算法(Metaheuristic Algorithm，MA)扮演了極其重要的角色.其核心思想為通過每種算法的不同運算符，搜索并不斷更新位置，使得找到最優(yōu)解的概率增加.在過去的十幾年間，元啟發(fā)算法不斷被開發(fā)與延伸，如遺傳算法(Genetic Algorithm，GA)[1]，差分進(jìn)化算法(Differential Evolution，DE)[2]，進(jìn)化策略(Evolution Strategy，ES)[3]，蟻群算法(Ant Colony Algorithm，ACO)[4]，粒子群算法(Particle Swarm Algorithm)[5]等等.但隨著設(shè)備的不斷更新，信息的不斷多元化發(fā)展，優(yōu)化問題也從傳統(tǒng)的單目標(biāo)優(yōu)化問題逐漸向復(fù)雜的多目標(biāo)問題轉(zhuǎn)化.區(qū)別于傳統(tǒng)的單目標(biāo)優(yōu)化問題，多目標(biāo)優(yōu)化問題往往含有兩個或三個相互矛盾的目標(biāo)，且無法找到單一的最優(yōu)方案來滿足所有的目標(biāo)，其最終結(jié)果為一組多個目標(biāo)相互權(quán)衡后的結(jié)果集合，也被稱為帕累托最優(yōu)解集(Pareto Optimial Set，PS)[6]或非支配解集，非劣解集等.而這也使得多目標(biāo)優(yōu)化算法(Multi-Objective Evolutionary Algorithms，MOEAs) 獲得了極大的關(guān)注.從早期的強化帕累托算法(Strength Pareto Evolutionary Algorithm，SPEA)[7]，基于非支配排序的遺傳算法2(Non-dominated Sorting Genetic Algorithm version 2，NSGA-II)[8]，基于分解的多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D)[9]到近些年來涌現(xiàn)出的許多新的多目標(biāo)優(yōu)化算法，如改進(jìn)的多目標(biāo)粒子群算法[10]，多目標(biāo)分解算法[11]，基于偏好的多目標(biāo)優(yōu)化算法[12].正余弦算法(Sine-Cosine algorithm，SCA)[13]是近年來提出的一種非常有效的單目標(biāo)優(yōu)化算法，他通過采用正弦與余弦函數(shù)來有效的搜索空間，已經(jīng)被應(yīng)用到很多方面如手寫體輸入、圖像檢測、能源生產(chǎn)等[14].盡管如此.受限于其設(shè)計機(jī)理與篩選機(jī)制，這些算法仍難以滿足現(xiàn)行的需求.鑒于此，本文提出一種改進(jìn)的多目標(biāo)正余弦優(yōu)化算法(Improved Multi-Objective Sine Cosine Algorithm，IMSCA)，該算法繼承了原有SCA算法的優(yōu)良性能，并引入了兩種新的機(jī)制：反向?qū)W習(xí)機(jī)制與網(wǎng)格密度篩選機(jī)制.通過結(jié)合反向?qū)W習(xí)本文提出一種全新的初始化方法來來增強可行解的獲得的幾率，并通過引入網(wǎng)格坐標(biāo)提出一種基于密度篩選的新機(jī)制來更新和保存非劣解集，最終使得算法在具有良好收斂能力的同時使獲得的解具有良好的分布性，進(jìn)而強化算法的性能.

本文其余章節(jié)安排如下，第二節(jié)介紹算法相關(guān)背景，第三節(jié)陳述算法設(shè)計與其具體機(jī)制.第四節(jié)通過將IMSCA與其他五個多目標(biāo)優(yōu)化算法在一系列標(biāo)準(zhǔn)測試函數(shù)上進(jìn)行仿真實驗來驗證算法的良好性能，第五節(jié)通過將IMSCA與其他多目標(biāo)算法在真實工程設(shè)計優(yōu)化問題上進(jìn)行對比分析，驗證所提算法在解決實際問題中的性能.最后第六節(jié)總結(jié)全文.

2 背景知識

2.1 反向?qū)W習(xí)

反向?qū)W習(xí)(opposition-based learning，OBL)[15]的出現(xiàn)為算法的搜索提供了一種新的思路，通過反向?qū)W習(xí)策略，算法在搜索最優(yōu)解的同時，還會對其相反方向的解進(jìn)行評價，從而增大最優(yōu)解的獲得概率，進(jìn)而提升算法收斂速度.其基礎(chǔ)概念如下所示：

(1)

2.2 網(wǎng)格坐標(biāo)

網(wǎng)格坐標(biāo)是一種非常有效的空間劃分機(jī)制，在這種機(jī)制中，一個網(wǎng)格被用作框架來確定個體在客觀空間中的位置.它具有同時反映收斂性和多樣性信息的內(nèi)在屬性.下面給出了網(wǎng)格的基礎(chǔ)定義[16].

定義3.(網(wǎng)格邊界)給定個體x在第dth個目標(biāo)下的最小值和最大值為minfd(x)與maxfd(x).則其上邊界與下邊界為ud，ld，其具體公式如下：

(2)

(3)

其中h∈Z，h≥2為固定參數(shù)，表示在目標(biāo)空間每一維度下的劃分.

定義4.(網(wǎng)格坐標(biāo))給定個體x，第dth目標(biāo)下的網(wǎng)格坐標(biāo)可表示為：

(4)

算法1.Improved Multi-Objective Sine Cosine Algorithm

Data:population siszN. external archive sizeN,objective numberM.

Result:optimal front.

begin

3 IMSCA算法框架

本文所提出的IMCSA算法偽代碼如算法1所示.該算法由四個主要階段組成.首先在初始化階段，初始個體通過反向?qū)W習(xí)進(jìn)行初始化.隨后通過應(yīng)用正余弦函數(shù)與反向?qū)W習(xí)獲得子代解決方案.最后，通過在網(wǎng)格機(jī)制更新和保存外部解集，最終生成解決方案.在下面的段落中，將詳細(xì)解釋IMCSA中各個環(huán)節(jié).

3.1 反向?qū)W習(xí)初始化

傳統(tǒng)采用隨機(jī)初始化的算法由于缺乏先驗知識，大大降低了算法中較好區(qū)域的搜索幾率.但利用OBL可以在沒有先驗知識的情況下，獲得更適合的初始化候選解，從而提升探索到更好區(qū)域的概率.本文通過結(jié)合OBL，提出一種全新的方法來初始化IMSCA算法.其具體流程如下：

Step1.首先將初始種群PN分為兩個部分，第一個部分PN1通過隨機(jī)分布來產(chǎn)生.

Step2.第二個部分PN2通過2.1節(jié)中的反向?qū)W習(xí)方法來產(chǎn)生：

PN2=ai+bi-PN1

(5)

Step3.所產(chǎn)生的集合{PN1∪PN2}將作為初始種群NP帶入算法的后續(xù)流程.

3.2 正余弦操作

正弦余弦算法(SCA)是一種基于種群的算法，在SCA中，為了高效探索并有效的更新位置，它使用了兩種不同的數(shù)學(xué)表達(dá)式來更新每一代的解決方案.這些表達(dá)式如下[13]：

(6)

(7)

(8)

3.3 基于網(wǎng)格密度的篩選機(jī)制

為方便從子種群中篩選出優(yōu)秀個體來構(gòu)成新的種群，本文提出一種基于網(wǎng)格密度的新機(jī)制來輔助算法對較好的個體進(jìn)行優(yōu)先篩選，根據(jù)2.2節(jié)構(gòu)建網(wǎng)格坐標(biāo)后，每一個個體都有自己對應(yīng)的網(wǎng)格坐標(biāo)，首先采用全局網(wǎng)格排序進(jìn)行篩選：

定義5.(全局網(wǎng)格排序)對于給定兩個體x，y，個體x的全局網(wǎng)格排序(Global Grid Ranking，GGR)為：

(9)

其中M為目標(biāo)個數(shù)，Gm(x)，Gm(y)表示個體x，y在目標(biāo)m上的網(wǎng)格坐標(biāo).GGR反映了個體的全局支配程度，換言之，一個個體其支配其他個體越多，其GGR值也就越大，則其被優(yōu)先選擇的幾率也就越大.通過GGR的排序篩選，可以輔助算法快速篩選優(yōu)秀個體，但個體仍可能存在GGR值相同的情況，針對此類情況，我們綜合考慮其個體分布多樣性提出一種基于網(wǎng)格密度排序(Grid Density Ranking，GDR)的新機(jī)制來進(jìn)行進(jìn)一步篩選最優(yōu)個體，其定義如下：

定義6.(網(wǎng)格密度排序) 對于給定兩個體x，y，個體x的網(wǎng)格密度排序為：

GDR(x)=find(GD(x，y)

(10)

(11)

全局網(wǎng)格密度排序GDR反映了個體周邊的擁擠程度，換言之，一個個體與其他個體的密集程度越小，其GDR值也就越小，則其被優(yōu)先選擇的幾率也就越大.

圖1 網(wǎng)格密度排序Fig.1 Grid density ranking

如圖1 所示為雙目標(biāo)最小化問題，個體p1，p2，p3，p4，p5，p6，p7的網(wǎng)格坐標(biāo)分別為(3，5)，(3，4)，(2，4)，(2，3)，(1，3)，(2，2)，(3，2).從圖中可以看出，個體p5，p6的GGR 值最大，支配的個體最多，但由于兩個個體的GGR值均為13，此時我們采用GDR排序?qū)ζ溥M(jìn)行進(jìn)一步篩選.對于個體p5，其與p6，p4，p3的GD 值分別為2，1，2，所以其GDR 值為1. 而對于個體p6，其與p5，p4，p7的GD 值分別為2，1，1，所以其GDR 值為2.p5的GDR 值更小，所以優(yōu)先選擇p5(從個體的密度來看，相比p6，p5周圍擁擠度較低，多樣性更好，則優(yōu)先選擇p5).

3.4 外部解集更新

維護(hù)和更新非支配解集是算法中重要的一環(huán).傳統(tǒng)多目標(biāo)優(yōu)化算法大多采用建立一個外部檔案來存儲非支配解.當(dāng)非支配解個數(shù)達(dá)到預(yù)定值時，需要對其進(jìn)行刪減，以提高算法的搜索效率，從而保持解的多樣性.在這里，我們將外部存檔的大小設(shè)置為N，與種群的大小相同，并使用3.3節(jié)中的GGR和GDR策略將前50% 的解決方案按升序存放到外部存檔中.由于整個種群的分布在外部存檔中發(fā)生了變化，因此需要重新計算網(wǎng)格排序來獲得最優(yōu)的帕累托前沿.

4 實驗設(shè)計

在本節(jié)，IMSCA算法將與5種優(yōu)秀的多目標(biāo)優(yōu)化算法(NSGA-II，MOEA/D，AGE-II[17]，IM-MOEA[18]，NSLS[19])在一系列標(biāo)準(zhǔn)測試函數(shù)上進(jìn)行對比，在這里，我們采用ZDT{1，2，3，4，6}、UF{4，5，6，7，8，9}與 DTLZ{1，2}測試函數(shù)[20]進(jìn)行驗證.此外，本文采用兩個經(jīng)典評價指標(biāo)反轉(zhuǎn)世代距離(Inverted Generational Distance，IGD)[16]與空間指標(biāo)(Spacing，SP)[22]來對各個算法的結(jié)果進(jìn)行評估，最后，為了客觀的顯示對比結(jié)果，本節(jié)還引入了秩序檢驗來對結(jié)果的差異性進(jìn)行客觀評估，從而驗證所提算法的性能與表現(xiàn).

4.1 參數(shù)設(shè)定

本文引入了5種算法與IMSCA進(jìn)行對比試驗，其中各算法的參數(shù)設(shè)置如表1所示，為避免算法結(jié)果的偶然性，每個算法實驗都獨立運行30次進(jìn)行統(tǒng)計.

表1 各算法參數(shù)設(shè)定Table 1 Parameters for each algorithms

4.2 結(jié)果分析

采用IGD指標(biāo)與SP指標(biāo)的實驗統(tǒng)計結(jié)果已經(jīng)如表2，表3所示.表格中高亮部分的值為該行中的最優(yōu)結(jié)果.為了方便對比，本節(jié)引入了秩序檢驗來評價各個算法所獲得結(jié)果間的差異性，其統(tǒng)計結(jié)果以“w/t/l” 的形式被記錄在各表格最后一行，其中w表示本文提出的IMSCA算法所獲得結(jié)果優(yōu)于該對比算法的結(jié)果；l表示本文提出的IMSCA所獲得結(jié)果差于該對比算法；t表示該對比算法的結(jié)果與本文提出的IMSCA 所獲得結(jié)果無明顯的差異.

如表2所示，6個算法在IGD指標(biāo)下的統(tǒng)計結(jié)果已經(jīng)列在表中.從結(jié)果可以看出，IMSCA算法、NSGA-II算法，AGE-II與IM-MOEA算法包攬了所有13個測試函數(shù)在IGD指標(biāo)下的最優(yōu)值(最小值).對于ZDT系列測試函數(shù)，IMSCA 在ZDT1，ZDT2，ZDT3，ZFT4與ZDT6五個測試函數(shù)上都獲得良好的表現(xiàn)，此外圖2中第1、2、3行6個算法在ZDT4.ZDT6上所獲得結(jié)果圖也進(jìn)一步驗證了IMSCA算法的良好性能.對于UF系列測試函數(shù)，IMSCA在UF4，UF5，UF7與UF9上取得了最優(yōu)值，NSGA-II包攬了UF6與UF8上的最優(yōu)值.而MOEA/D算法、IM-MOEA算法、NSLS算法在UF測試函數(shù)上的表現(xiàn)較在ZDT上的表現(xiàn)略遜一籌，特別是在UF5測試函數(shù)上.對于UF6測試函數(shù)，盡管IMSCA的表現(xiàn)稍遜于NSGA-II與AGE-II算法，但仍優(yōu)于其他算法的結(jié)果.對于UF7測試函數(shù)，IMSCA表現(xiàn)出了優(yōu)良的性能，如圖2中所示，IMSCA算法在UF7上的表現(xiàn)明顯優(yōu)于其他算法.此外，從圖2第6行可以看出，IMSCA在UF9上的表現(xiàn)也較為出色.最后，對于DTLZ測試函數(shù)，IMSCA 與AGE-II兩個算法分別取得了DTLZ1和DTLZ2上的最優(yōu)值，但根據(jù)秩序檢驗結(jié)果，IMSCA 所獲得結(jié)果仍優(yōu)于其他算法.而從圖2中的最后兩行也可以看出，IMSCA在DTLZ1 測試函數(shù)的表現(xiàn)較為良好.表3統(tǒng)計了各算法在13個測試函數(shù)上采用SP指標(biāo)的統(tǒng)計結(jié)果.對于SP指標(biāo)，其值越小，表示算法解得分布越均勻，如果SP值為0，則表示所有解都是等距排列的.從表3可以看出，IMSCA算法包攬了大部分測試函數(shù)的最優(yōu)值，MOEA/D算法表現(xiàn)也比其在IGD指標(biāo)下的表現(xiàn)更為優(yōu)秀.對于ZDT測試函數(shù)，IMSCA，MOEA/D與IM-MOEA包攬了全部的最優(yōu)值，對于ZDT1和ZDT6，IMSCA表現(xiàn)良好并包攬了兩個測試函數(shù)在SP指標(biāo)下最優(yōu)值.而對于ZDT2，ZDT3與ZDT4測試函數(shù)，盡管SP指標(biāo)下的最優(yōu)值為MOEA/D與IM-MOEA所獲得，但根據(jù)秩序檢驗的結(jié)果，他們所獲得的結(jié)果與IMSCA所獲得的結(jié)果無明顯差異.對于UF4測試函數(shù)，盡管NSGA-II獲得了最優(yōu)值，但I(xiàn)MSCA仍然優(yōu)于大部分算法如MOEA/D，AGE-II等.而對于UF5和UF6測試函數(shù)，IMSCA在SP指標(biāo)下的表現(xiàn)稍遜于MOEA/D，但仍然優(yōu)于其他算法如NSGA-II 等.對于UF7-9測試函數(shù)，IMSCA的表現(xiàn)明顯優(yōu)于大部分算法，由表3 可以看出，三個測試函數(shù)在SP指標(biāo)下的最優(yōu)值全部為IMSCA算法所獲得.最后對于DTLZ1和DTLZ2測試函數(shù)，盡管NSLS與NSGA-II的表現(xiàn)良好，但I(xiàn)MSCA算法依然優(yōu)于大部分算法.總體來講，IMSCA算法通過采用正余弦函數(shù)來不斷更新位置，并通過采用了OBL和GGR機(jī)制來進(jìn)一步強化算法的收斂性，從而提升了算法的性能.

圖2 各算法部分測試函數(shù)所獲非支配解情況Fig.2 Pareto fronts of each algorithm on parts of hard test instances

表2 各算法在IGD指標(biāo)下的統(tǒng)計結(jié)果，其中灰色標(biāo)記部分為最優(yōu)值Table 2 IGD metric results obtained by each algorithms

表3 各算法在SP指標(biāo)下的統(tǒng)計結(jié)果，其中灰色標(biāo)記部分為最優(yōu)值Table 3 SP metric results obtained by each algorithms

4.3 參數(shù)分析

在IMSCA算法中，我們引入了全局網(wǎng)格機(jī)制，其中通過參數(shù)h來劃分網(wǎng)格，構(gòu)建網(wǎng)格坐標(biāo).因此我們將通過在ZDT3，UF4，UF9和DTLZ2上的實驗來分析參數(shù)h的影響，并試圖提供一個合適的參數(shù)設(shè)置.為了避免偶然性，我們在這里設(shè)定h∈[5，30).此外，我們首先生成一系列隨機(jī)值來設(shè)置其它控制參數(shù)，并將其在實驗中保持不變來保證實驗的客觀性.

如圖3為IMSCA算法的IGD值隨h取值變化的規(guī)律圖.從圖中可以看出，算法的IGD值從開始變化到h=5左右迅速下降，然后上升直到邊界.從圖中可以看出，IMSCA算法對雙目標(biāo)問題和三目標(biāo)問題的參數(shù)靈敏度相似，盡管算法在IGD取最好的值時參數(shù)h不完全一樣，但大體上是相似的.綜上所述，IMSCA算法在h∈[9，11]時對于雙目標(biāo)和三目標(biāo)問題較為合適.

5 工程實例應(yīng)用

本節(jié)將提出的IMSCA算法應(yīng)用到實際的減速器優(yōu)化設(shè)計問題中，并與四種已實現(xiàn)的算法(NSGA-II，MOPSO[23]，MOALO[24]，PAES)進(jìn)行了對比與分析，進(jìn)而驗證本算法的良好性能.

減速器優(yōu)化設(shè)計問題是工程領(lǐng)域中一個較為突出的優(yōu)化設(shè)計問題，該問題主要包含兩個目標(biāo)最小化：減速器的重量f1

與應(yīng)力f2.此外該問題還包含7個設(shè)計變量即齒輪面寬度x1、 齒模x2、 小齒輪的齒數(shù)x3、軸承1的間距x3、軸承2的間距x4、軸1的直徑x5、軸2的直徑x6.其具體描述如[25]：

(12)

(13)

約束條件為：

其中，2.6≤x1≤3.6，0.7≤x2≤0.8，17≤x3≤28，7.3≤x4≤8.3，7.3≤x5≤8.3，2.9≤x6≤3.9，5.0≤x7≤5.5.

在本節(jié)中，四種算法在減速器優(yōu)化設(shè)計問題上的運行代數(shù)為1000，為避免偶然性，每個算法單獨運行30次，并做統(tǒng)計分析.此外，除去本文已介紹的SP指標(biāo)，本節(jié)還引入了世代距離GD指標(biāo)[24]來客觀的評價各算法在該真實工程問題上的表現(xiàn).其具體結(jié)果如表4所示.

如表4所示為MOPSO，NSGA-II，MOALO，PAES和IMSCA算法在減速器優(yōu)化設(shè)計問題上實驗結(jié)果，其在GD和SP指標(biāo)獨立運行30次的平均值與標(biāo)準(zhǔn)差已經(jīng)列在表中，灰色高亮標(biāo)記表示該指標(biāo)下的最優(yōu)值.從表中的數(shù)據(jù)可以看出，IMSCA在GD指標(biāo)和SP指標(biāo)上都取得了最好的解，盡管MOALO在該問題上的表現(xiàn)也較為良好，但對比本文提出的IM-SCA算法，仍有一些劣勢.這主要是由于MOPSO，NSGA-II，PAES以及MOALO算法單純使用了進(jìn)化的操作來對數(shù)據(jù)進(jìn)行優(yōu)選，但面對復(fù)雜約束問題，其很難達(dá)到較好的效果.而本文提出的IMSCA算法，一方面繼承了原有SCA算法的良好性能，另一方面兩種不同的機(jī)制：基于反向?qū)W習(xí)機(jī)制與基于網(wǎng)格密度篩選機(jī)制的引入都進(jìn)一步鞏固與強化了算法解的收斂性與多樣性，從而在實際問題中取得了較好的效果.

6 總 結(jié)

為了進(jìn)一步提升算法的收斂性并一定程度的保持解得多樣性，本文提出了一種改進(jìn)的正余弦多目標(biāo)優(yōu)化算法IMSCA.算法繼承了原有單目標(biāo)SCA算法在目標(biāo)空間的良好收斂能力，并通過采用基于反向?qū)W習(xí)的機(jī)制重新設(shè)計了算法初始化階段，此外，結(jié)合我們之前的工作，本算法還提出了一種基于網(wǎng)格密度的新機(jī)制，通過計算全局網(wǎng)格排序與網(wǎng)格密度排序進(jìn)一步篩選出優(yōu)良個體，從而強化和鞏固算法的收斂性和多樣性.

最后，本文通過對IMSCA和其他5種先進(jìn)的進(jìn)化算法進(jìn)行了廣泛的實驗比較，并選取了ZDT，UF，DTLZ的部分測試基準(zhǔn)問題來研究和評估算法的能力，最后算法還在實際的減速器優(yōu)化設(shè)計問題上進(jìn)行了實力驗證.統(tǒng)計結(jié)果顯示，本文提出的IMSCA算法在測試問題和實際優(yōu)化問題上都表現(xiàn)出了良好的性能與潛力.但是，在本文采用的實例上表現(xiàn)良好，并不代表其可在所有的實例中表現(xiàn)良好，不同的實際問題與環(huán)境更需要針對性的選擇與設(shè)計算法.在未來，我們將擴(kuò)展IMSCA，通過結(jié)合約束處理技術(shù)解決高維約束多目標(biāo)問題，以進(jìn)一步驗證其有效性.