一種改進的多目標正余弦優化算法

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

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

1 引 言

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

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

2 背景知識

2.1 反向學習

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

(1)

2.2 網格坐標

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

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

(2)

(3)

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

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

(4)

算法1.Improved Multi-Objective Sine Cosine Algorithm

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

Result:optimal front.

begin

3 IMSCA算法框架

本文所提出的IMCSA算法偽代碼如算法1所示.該算法由四個主要階段組成.首先在初始化階段，初始個體通過反向學習進行初始化.隨后通過應用正余弦函數與反向學習獲得子代解決方案.最后，通過在網格機制更新和保存外部解集，最終生成解決方案.在下面的段落中，將詳細解釋IMCSA中各個環節.

3.1 反向學習初始化

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

Step1.首先將初始種群PN分為兩個部分，第一個部分PN1通過隨機分布來產生.

Step2.第二個部分PN2通過2.1節中的反向學習方法來產生：

PN2=ai+bi-PN1

(5)

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

3.2 正余弦操作

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

(6)

(7)

(8)

3.3 基于網格密度的篩選機制

為方便從子種群中篩選出優秀個體來構成新的種群，本文提出一種基于網格密度的新機制來輔助算法對較好的個體進行優先篩選，根據2.2節構建網格坐標后，每一個個體都有自己對應的網格坐標，首先采用全局網格排序進行篩選：

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

(9)

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

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

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

(10)

(11)

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

圖1 網格密度排序Fig.1 Grid density ranking

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

3.4 外部解集更新

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

4 實驗設計

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

4.1 參數設定

本文引入了5種算法與IMSCA進行對比試驗，其中各算法的參數設置如表1所示，為避免算法結果的偶然性，每個算法實驗都獨立運行30次進行統計.

表1 各算法參數設定Table 1 Parameters for each algorithms

4.2 結果分析

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

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

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

表2 各算法在IGD指標下的統計結果，其中灰色標記部分為最優值Table 2 IGD metric results obtained by each algorithms

表3 各算法在SP指標下的統計結果，其中灰色標記部分為最優值Table 3 SP metric results obtained by each algorithms

4.3 參數分析

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

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

5 工程實例應用

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

減速器優化設計問題是工程領域中一個較為突出的優化設計問題，該問題主要包含兩個目標最小化：減速器的重量f1

與應力f2.此外該問題還包含7個設計變量即齒輪面寬度x1、 齒模x2、 小齒輪的齒數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.

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

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

6 總 結

為了進一步提升算法的收斂性并一定程度的保持解得多樣性，本文提出了一種改進的正余弦多目標優化算法IMSCA.算法繼承了原有單目標SCA算法在目標空間的良好收斂能力，并通過采用基于反向學習的機制重新設計了算法初始化階段，此外，結合我們之前的工作，本算法還提出了一種基于網格密度的新機制，通過計算全局網格排序與網格密度排序進一步篩選出優良個體，從而強化和鞏固算法的收斂性和多樣性.

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