一種基于超體積指標的多目標進化算法

王學武， 魏建斌， 周 昕， 顧幸生

（華東理工大學化工過程先進控制和優化技術教育部重點實驗室，上海 200237）

多目標優化問題通常是指具有多個目標同時具有多個最優解的一類問題，解決這類問題需要同時對相互作用、相互沖突的多個目標進行優化和綜合考慮，因此多目標優化已經被廣泛應用于電力調度[1]、網絡優化[2]、化工過程[3]、結構設計[4]、數據挖掘[5]等領域。

以焊接機器人路徑規劃問題為例，衡量焊接路徑好壞的指標往往不止一個，通常有路徑長度、焊接用時、能量消耗、焊接變形量等，因此可將焊接機器人路徑規劃問題看作一個多目標優化問題。進化算法是一類模擬生物自然選擇與自然進化的隨機搜索算法[6]，通過種群迭代來協調局部與全局搜索能力，從而獲得收斂性和分布性均較好的解集，能夠有效地解決多目標優化問題。王學武等[7]通過將基于分解的多目標進化算法與自適應鄰域相結合，以焊接路徑長度和能量消耗為優化目標，較好地解決了弧焊機器人路徑規劃問題。Mac 等[8]基于Pareto 支配關系提出了改進的多目標粒子群優化算法，以焊接路徑長度和路徑平滑度為優化目標求解移動機器人路徑規劃問題，在不同種類的環境中均得到了較好的仿真結果。

多目標優化算法是解決多目標優化問題的核心，關鍵在于如何設計算法以獲得較好的綜合性能，而超體積（Hypervolume，HV）指標是唯一一個在Pareto 支配關系上嚴格單調的度量指標[9]，超體積值越大，對應算法的綜合性能越好，因此超體積可以作為歸檔策略、多樣性機制或選擇標準來指導算法搜索[10]，從而考慮將評價算法性能的超體積指標整合到算法中來解決多目標優化問題[11]。Bader 等[9]提出的HypE 算法通過蒙特卡洛模擬來近似精確的超體積，能夠大大降低算法的時間復雜度、平衡估計的準確性和算法的計算復雜度。Igel 等[12]提出的MO-CMAES 算法將具有協方差矩陣自適應的精英進化策略與基于非支配排序的多目標選擇相結合，實驗結果表明基于超體積貢獻的s-MO-CMA 比基于擁擠距離的c-MO-CMA 具有更好的性能。Beume 等[13]提出的SMS-EMOA 算法采用在每次迭代中只產生和淘汰一個個體的穩態進化策略，在二維和三維的測試問題上表現出較好的綜合性能。

上述基于超體積指標的算法具有計算復雜度高、程序運行效率低的缺點，因此選擇有效計算超體積的方法來提升算法的運行效率并且獲得較好的綜合性能對基于超體積指標的進化算法來說具有重要意義。

1 相關工作

通過超體積指標來指導算法搜索，其HV 性能指標普遍較高，但仍然存在運行效率低、分布性不好的缺點，而基于參考點的NSGA-Ⅲ搜索的解分布均勻，因此本文提出了一種基于超體積指標的多目標進化算法（MOEA-HV），針對二維和三維的多目標優化問題，采用分治遞歸思想的切片法來精確計算超體積，同時在基于指標的進化算法（IBEA）[11]前對所有種群個體進行非支配排序提前刪除被支配的個體，從而減少個體獨立貢獻超體積的計算量，提升運行效率，通過與NSGA-Ⅲ結合來優化算法的分布性。

2 MOEA-HV 算法

2.1 IBEA

IBEA 主要包括兩個部分：一是將超體積指標與適應度評價函數進行結合，計算種群中每個個體的適應度值，公式如下：

其中： I ({x2},{x1}) 表示計算個體的獨立貢獻超體積；k是一個大于0 的比例縮放因子[31]，用于淘汰適應度值小的個體，即在原種群中刪除對總的超體積的獨立貢獻最小的個體，如圖1 和圖2 所示（以二維為例）。

圖 1 在非支配關系下 BHV ＞ AHV ＞ 0Fig. 1 BHV ＞ AHV ＞ 0 in non-dominated relationship

圖 2 在支配關系下BHV ＞ AHV = 0Fig. 2 BHV ＞ AHV = 0 in dominated relationship

在圖 1、2 中，A 和 B 均表示一個個體，H 表示計算超體積的參考點，陰影部分AHV和BHV表示個體A 和B 的獨立支配區域面積，其中圖1 表示個體A 和B 在互不支配時的獨立支配區域面積，圖2 表示個體B 支配個體A 時的獨立支配區域面積，均有BHV＞AHV，因此不論是根據個體的支配關系還是個體對總的超體積的獨立貢獻，更應該淘汰個體A。事實上，超體積指標在Pareto 支配關系上是嚴格單調的，因此能夠作為指導種群進化的有效度量指標[9]。

重新計算種群中每個個體的適應度值，其更新公式為

通過二元錦標選擇父代進行交配從而產生新的個體，與原種群一起構成新的種群，繼續進行迭代。

IBEA 通過將超體積指標和適應度評價方法相結合來指導種群進化，與基于超體積指標的其他典型算法 HypE[9]、MO-CMA-ES[12]和 SMS-EMOA[13]相比，在保證綜合性能最優或次優的前提下，其運行效率是最高的，這也是本文選擇IBEA 作為算法基礎框架的主要原因。

2.2 NSGA-Ⅲ

NSGA-II[32]是基于擁擠度距離建立偏序集來篩選個體指導種群進化，能夠有效處理多目標優化問題。NSGA-Ⅲ[33]在NSGA-II 的基礎上通過使用一組預定義的參考點在臨界層選擇個體來確保種群良好的分布性，該算法在最壞情況下的時間復雜度為O（N2lgM-2N）或 O（N2M）。

基于參考點方法的NSGA-Ⅲ能夠維持種群個體分布的多樣性和均勻性，因此將NSGA-Ⅲ整合到IBEA 框架中，獲得的解能夠同時具有良好的收斂性和分布性，使得程序的運行效率更高，同時解也能夠均勻分布在整個Pareto 前沿面。有兩種方法可以將NSGA-Ⅲ和IBEA 結合：一是在IBEA 運行完成的基礎上再運行NSGA-Ⅲ，也就是IBEA 先迭代更新完成，獲得收斂性較好的種群，然后將獲得的種群作為NSGA-Ⅲ的初始種群繼續進行迭代優化，以期獲得分布性也較好的解；二是先運行NSGA-Ⅲ，然后將獲得的分布均勻的種群作為IBEA 的初始種群、利用超體積指標指導種群進化來繼續對選擇過程增壓，以期獲得綜合性能均較好的解。

本文選擇第1 種結合方式。因為在基于超體積指標的算法中，IBEA 的收斂速度較快，分布性較差，因此重點在于改善IBEA 的分布性，在IBEA 運行的基礎上再運行NSGA-Ⅲ能夠實現此目的。而對于第2 種方式，先利用NSGA-Ⅲ獲得分布性較好的解，然后在此基礎上通過IBEA 繼續進行個體的迭代選擇，很可能會破壞之前已經均勻分布的解，反而降低了算法的綜合性能。

2.3 非支配排序

IBEA 通過計算種群中每個個體的獨立貢獻超體積及其適應度值淘汰適應度值最小的個體，并依次進行迭代，使得算法最終能獲得一個較好的解集，但計算復雜度高，主要原因在于IBEA 計算了每個個體的獨立貢獻超體積。本文的改進之處是先通過Pareto 支配關系對個體進行篩選，得到一組非支配解集，然后計算非支配解集中每個個體的獨立貢獻超體積，淘汰貢獻值最小的個體并依次迭代。通過提前刪除質量不好的個體而避免計算其獨立貢獻超體積，能夠有效節約個體的超體積計算量，而且減小了計算復雜度，提升運行效率。以二維為例，圖3 示出了非支配排序后的解集分布情況，很容易計算出每個個體的獨立貢獻超體積（即面積）。圖4 示出了經過初始化后產生的種群個體分布情況，處于亂序狀態，此時要淘汰獨立貢獻超體積最小的個體仍然需要計算每個個體的貢獻值，浪費了部分計算資源，因此本文考慮在IBEA 前引入非支配排序來提升算法的運行效率。

圖 3 非支配排序后的解集Fig. 3 Solution set after non-dominated sort

圖 4 亂序下的解集Fig. 4 Solution set in chaos

三維的非支配排序情況與二維類似，但個體獨立貢獻超體積的計算更加復雜。本文采用切片法來精確計算三維個體的獨立貢獻超體積，基本思想是計算整個解集的超體積與去除該個體后的超體積之差。具體來說，先利用某一維度（本文選擇第一維度）對整個超體積進行切片以達到降維的目的，通過計算切割面的面積與切片在第一維度上的深度的乘積得到整個解集的超體積，然后用同樣的方法計算去除該個體后的超體積，兩個超體積之差即為三維情況下的個體獨立貢獻超體積（即體積）。假設解集中有 4 個個體 P1、P2、P3、P4，圖 5（a）、（b）、（c）和（d）分別示出了整個解集的超體積、經過切片后的子超體積、個體P1和P2的獨立貢獻超體積。通過精確計算每個個體的獨立貢獻超體積，淘汰獨立貢獻超體積最小的個體來指導種群進化。

2.4 MOEA-HV 算法步驟

通過精確計算種群中個體的獨立貢獻超體積來指導種群進化，在IBEA 前對所有種群個體進行非支配排序并與NSGA-Ⅲ結合，共同組成了MOEAHV 算法。算法步驟如下：

輸入：種群數量、組合迭代次數、參數k、參考點輸出：Pareto 前沿面

（1）初始化。獲得初始種群，并生成參考點。

（2）非支配排序。對種群進行非支配排序，提前刪除被支配的個體，減少超體積的計算量。

（3）計算非支配排序后種群中每個個體的適應度值，并淘汰適應度值最小的個體。

（4）選擇、交叉、變異，產生新的種群。利用二元錦標法選擇最優的兩個個體到交配池進行交叉變異，產生新的個體與原種群合并為新的種群。

（5）嵌入 NSGA-Ⅲ。將新得到的種群作為NSGA-Ⅲ的初始種群繼續進行迭代，滿足迭代要求則停止迭代并輸出。

3 實驗結果及分析

仿真實驗使用Lenovo-PC 計算機，處理器為Intel(R) Core(TM) i5-4200M CPU @ 2.50 GHz，內存為4.00 GB，操作系統為基于x64 處理器的64 位操作系統Windows 8.1 中文版，軟件版本為 MATLAB R2018a，程序運行均在PlatEMO[34]平臺實現。

為檢驗MOEA-HV 的運行效率和綜合性能，與其他典型的基于超體積的算法IBEA[11]、HypE[9]、MO-CMA-ES[12]、SMS-EMOA[13]以 及 NSGA-Ⅲ[33]進行對比實驗，選擇2 個目標的ZDT 和3 個目標的DTLZ 系列中具有代表性的典型測試函數ZDT1～ZDT6 和 DTLZ1～DTLZ7 進行實驗，通過運行時間評價算法的運行效率，通過IGD[35]和HV[36]指標評價算法的綜合性能，其中IGD 值越小說明算法的綜合性能越好，HV 值越大說明算法的綜合性能越好，這兩個評價指標都能夠綜合評價算法的收斂性和分布性。設置種群大小為100，迭代次數為500，所有算法在相同條件下獨立運行10 次，k=0.03。表1～3 分別列出了各算法的運行時間、IGD 均值（IGDm）和HV 均值（HVm），其中黑體數字為最優值。圖6 示出了MOEA-HV 算法在測試函數ZDT2、ZDT3、DTLZ2和DTLZ7 上的Pareto 前沿面。

圖 5 三維情況下個體獨立貢獻超體積的計算Fig. 5 Calculation of the individuals’ exclusive hypervolume contributions in three dimension

從表1 中各算法的運行時間均值來看，MOEAHV 的運行效率要遠遠高于其他基于超體積的典型算法，在IBEA 的基礎上提升近兩倍，但比NSGA-Ⅲ要慢，究其原因在于NSGA-Ⅲ不需要計算超體積，而對于基于超體積的算法來說，不論采用何種策略、何種計算方法，超體積的時間計算成本仍然非常大。對于基于超體積的算法來說，計算復雜度高是制約算法性能最重要的因素，因此MOEA-HV 最大的突破就是在保持良好收斂性和分布性的同時能有效降低計算復雜度，節約計算超體積的時間成本，提高算法的運行效率。

表 1 各算法運行時間均值Table 1 Mean runtime of each algorithm

表 2 各算法 IGD 均值Table 2 Mean IGD of each algorithm

表 3 各算法 HV 均值Table 3 Mean HV of each algorithm

圖 6 MOEA-HV 算法在部分測試函數上的Pareto 前沿面Fig. 6 Pareto fronts of MOEA-HV on some test functions

從表2 和表3 中各算法的IGDm和HVm可以看出，MOEA-HV 的收斂性和分布性要明顯優于IBEA，同時與NSGA-Ⅲ結合后算法綜合性能與NSGA-Ⅲ相比也更優，與其他算法相比能夠取得最優或次優的綜合性能，且性能穩定?？傮w來看，MOEA-HV 在DTLZ 系列測試函數上的性能要優于在ZDT 系列測試函數上的性能，因為加入非支配排序和基于參考點的NSGA-Ⅲ算法后，三維解集中的非支配個體要比二維的多，因此MOEA-HV 的解集在Pareto 前沿面上分布會更加均勻。具體來說，MOEA-HV 在測試函數 ZDT1、ZDT2、ZDT5、ZDT6 和 DTLZ1～DTLZ7上的綜合性能最優或次優，說明該算法能夠較好地處理具有凹性、多模態、偏好的問題，但在測試函數ZDT3、ZDT4 上性能表現不佳，算法在處理不連續以及多模態混合問題時尚且有待改進，同時測試函數ZDT5 具有欺騙性，導致算法容易陷入局部最優，解的分布性較差，測試函數DTLZ5 和DTLZ6 具有退化性，比較難收斂，因此測試的所有算法在這兩個測試函數上表現的收斂性均較差。與其他基于超體積的典型算法相比，MOEA-HV 的運行效率更高，且能夠保持較好的收斂性和分布性。

3.1 參數 k 的影響

MOEA-HV 算法是基于IBEA 的框架，其中，適應度值計算函數中的參數k 對算法的綜合性能有一定影響，因此有必要對k 的選擇進行獨立的對比實驗，選擇使算法表現出最好性能的參數值。設置種群大小為100，迭代次數為500，IBEA 在相同條件下獨立運行 10 次，參數 k 分別為 0.030、0.035、0.040、0.045、0.050、0.055、0.060，進行 7 組對比實驗，測試函數為 ZDT1～ZDT6和 DTLZ1～DTLZ7，分別比較不同參數下算法IBEA 的運行時間均值、IGDm和HVm，結果如圖7 所示。

相同條件下程序的運行時間越短說明算法的運行效率越高。從圖7（a）中可以看出參數 k 取0.030時，在 ZDT3、DTLZ1～DTLZ4、DTLZ6 上能夠得到最小值， k 取0.035 時運行時間均值也較短，說明參數設置得較小能夠在一定程度上節約算法的時間成本，且對于ZDT 系列測試函數來說，運行時間受參數設置影響較小，而對于DTLZ 系列測試函數來說，k取0.030 具有較大優勢。從圖7（b）可以看出，測試函數ZDT5 的分布性較差，不論參數取何值，其IGDm值都遠遠超過其他測試函數的IGDm值，因此考慮去掉ZDT5 測試函數來比較不同參數對算法IGDm值的影響。如圖 7（c）所示， k 取 0.030 時在 DTLZ1、DTLZ7 上的IGDm值明顯小于其他參數的IGDm值，且比較穩定，說明 k 取 0.030 時算法的解集在Pareto 前沿面上分布更加均勻。從圖7（d）可以看出k 取 0.030時，算法在測試函數 ZDT3 和 DTLZ1 上的HVm值最大，在其他測試函數上也好于其他參數，且性能穩定，收斂性更好，綜上可認為在比較的7 個參數中， k 取0.030時IBEA 的運行效率更高，且具有良好的綜合性能，因此為了獲得最好的算法性能，MOEA-HV中的參數 k 也取為0.030。

圖 7 不同參數 k 對IBEA 運行時間、IGDm 值和HVm 值的影響Fig. 7 Influence of different k on runtime, IGDm and HVm of IBEA

3.2 非支配排序的影響

IBEA 的計算復雜度高，主要原因是需要計算每個個體的獨立貢獻超體積，而通過Pareto 支配關系對個體進行篩選能夠提前刪除質量不好的個體從而降低了整個解集中個體的超體積計算量，能夠有效提高程序的運行效率。設置種群大小為100，迭代次數為500，在相同條件下獨立運行10 次，對在IBEA中是否加入非支配排序進行對比實驗以探究非支配排序對算法的影響。實驗的測試函數為ZDT1～ZDT6和DTLZ1～DTLZ7，分別比較IBEA 中是否加入非支配排序的運行時間均值、IGDm值和HVm值，如圖8所示，其中NDSort+IBEA(Mean)和NDSort+IBEA(Sd)分別表示算法IBEA 加入非支配排序后所獲得的平均值以及標準差，而IBEA(Mean)和IBEA(Sd)則表示沒有加入非支配排序得到的平均值和標準差。

對于2 個目標的ZDT 系列測試函數來說，計算的超體積為二維的（即面積），比較簡單，使得加入非支配排序程序的算法運行時間與IBEA 相近甚至更長。因為加入非支配排序后算法的運行效率更高，但同時算法的程序也更長，導致前者節約的時間與后者所消耗的時間剛好抵消，因此在迭代之后兩者的運行時間相近。從圖8（a）中可以看出，對于3 個目標的DTLZ 系列測試函數來說，加入非支配排序后算法的運行時間顯著降低，是因為三維的超體積更難計算，經過非支配排序之后能有效刪除不好的個體，從而大大減少超體積的計算量。同時，從圖8（b）、（c）中可以看出，加入非支配排序后算法的性能更加穩定，且能在一定程度上提高算法的綜合性能。

圖 8 非支配排序對 IBEA 運行時間均值、IGDm 值和HVm 值的影響Fig. 8 Influence of non-dominated sort on runtime, IGDm and HVm of IBEA

3.3 NSGA-Ⅲ的影響

將IBEA 與NSGA-III 結合能明顯改善算法的分布性，但關鍵在于如何結合，本文主要考慮兩種結合方式：一是IBEA 先迭代更新完成獲得收斂性較好的種群，然后將獲得的該種群作為NSGA-III 的初始種群繼續進行迭代優化，以期獲得分布性也較好的解（簡稱 IBEA+NSGA-III）；二是先運行 NSGA-III，然后將獲得分布均勻的種群作為IBEA 的初始種群，利用超體積指標進化繼續增壓選擇，以期獲得綜合性能均較好的解（簡稱NSGA-III+IBEA）。設置種群大小為100，兩種結合方式中IBEA 迭代次數均為100，NSGA-III 迭代次數均為500，在相同條件下獨立運行10 次，通過實驗分析決定何種方式更有利于整合到MOEA-HV 算法中。實驗的測試函數為ZDT1～ZDT6 和 DTLZ1～DTLZ7，分別比較 IBEA 與兩種不同結合方式 IBEA+NSGA-III、NSGA-III+IBEA 的運行時間均值、IGDm值、HVm值和標準差（Standard deviation，Sd），如圖 9 所示。

從圖9（a）中可以看出，與NSGA-III 結合后算法的運行時間大幅下降，且IBEA+NSGA-III 比其他兩者的綜合運行時間更短，但從圖9（b）的標準差數據來看，NSGA-III+IBEA 比 IBEA+NSGA-III 的運行時間更加穩定，因為算法NSGA-III 的運行速度快，且分布性好，所獲得的初始種群較好，因此第2 種結合方式（NSGA-Ⅲ+IBEA）的運行時間浮動更小、更穩定。圖 9（c）～（f）表明 IBEA+NSGA-III 在所有測試函數上的IGDm值最小、HVm值最大，性能最穩定，且在ZDT5、DTLZ1 和 DTLZ3 測試函數上要明顯優于NSGA-III+IBEA，因此本文的組合算法選擇IBEA+NSGA-III 結合方式。

圖 9 NSGA-Ⅲ對IBEA 運行時間、IGDm 值和HVm 值的影響Fig. 9 Influence of NSGA-Ⅲ on runtime, IGDm and HVm of NSGA-Ⅲ

4 結 論

針對二維和三維的多目標優化問題，本文提出了一種基于超體積指標的多目標進化算法(MOEAHV)。利用分治遞歸思想的切片法精確計算種群中個體的獨立貢獻超體積來指導種群進化，通過在IBEA 前對所有種群個體進行非支配排序提前刪除被支配的個體，從而減少個體獨立貢獻超體積的計算量來提升運行效率，同時通過與NSGA-Ⅲ結合來優化算法的分布性，主要有3 點改進之處：（1）設計對比實驗選擇更好的參數；（2）通過非支配排序提前刪除不好的個體，能有效節約計算超體積的時間成本；（3）與NSGA-Ⅲ結合來優化算法的分布性。

在今后的研究中，考慮將算法MOEA-HV 應用于解決焊接機器人多目標路徑規劃問題和更高維的問題，并會繼續研究精確計算和近似估計超體積的方法，更加有效地提升算法的運行效率，同時結合其他的優化策略持續改善算法的綜合性能。