王學(xué)武， 魏建斌， 周 昕， 顧幸生

（華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

多目標(biāo)優(yōu)化問(wèn)題通常是指具有多個(gè)目標(biāo)同時(shí)具有多個(gè)最優(yōu)解的一類問(wèn)題，解決這類問(wèn)題需要同時(shí)對(duì)相互作用、相互沖突的多個(gè)目標(biāo)進(jìn)行優(yōu)化和綜合考慮，因此多目標(biāo)優(yōu)化已經(jīng)被廣泛應(yīng)用于電力調(diào)度[1]、網(wǎng)絡(luò)優(yōu)化[2]、化工過(guò)程[3]、結(jié)構(gòu)設(shè)計(jì)[4]、數(shù)據(jù)挖掘[5]等領(lǐng)域。

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

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

上述基于超體積指標(biāo)的算法具有計(jì)算復(fù)雜度高、程序運(yùn)行效率低的缺點(diǎn)，因此選擇有效計(jì)算超體積的方法來(lái)提升算法的運(yùn)行效率并且獲得較好的綜合性能對(duì)基于超體積指標(biāo)的進(jìn)化算法來(lái)說(shuō)具有重要意義。

1 相關(guān)工作

通過(guò)超體積指標(biāo)來(lái)指導(dǎo)算法搜索，其HV 性能指標(biāo)普遍較高，但仍然存在運(yùn)行效率低、分布性不好的缺點(diǎn)，而基于參考點(diǎn)的NSGA-Ⅲ搜索的解分布均勻，因此本文提出了一種基于超體積指標(biāo)的多目標(biāo)進(jìn)化算法（MOEA-HV），針對(duì)二維和三維的多目標(biāo)優(yōu)化問(wèn)題，采用分治遞歸思想的切片法來(lái)精確計(jì)算超體積，同時(shí)在基于指標(biāo)的進(jìn)化算法（IBEA）[11]前對(duì)所有種群個(gè)體進(jìn)行非支配排序提前刪除被支配的個(gè)體，從而減少個(gè)體獨(dú)立貢獻(xiàn)超體積的計(jì)算量，提升運(yùn)行效率，通過(guò)與NSGA-Ⅲ結(jié)合來(lái)優(yōu)化算法的分布性。

2 MOEA-HV 算法

2.1 IBEA

IBEA 主要包括兩個(gè)部分：一是將超體積指標(biāo)與適應(yīng)度評(píng)價(jià)函數(shù)進(jìn)行結(jié)合，計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，公式如下：

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

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

圖 2 在支配關(guān)系下BHV ＞ AHV = 0Fig. 2 BHV ＞ AHV = 0 in dominated relationship

在圖 1、2 中，A 和 B 均表示一個(gè)個(gè)體，H 表示計(jì)算超體積的參考點(diǎn)，陰影部分AHV和BHV表示個(gè)體A 和B 的獨(dú)立支配區(qū)域面積，其中圖1 表示個(gè)體A 和B 在互不支配時(shí)的獨(dú)立支配區(qū)域面積，圖2 表示個(gè)體B 支配個(gè)體A 時(shí)的獨(dú)立支配區(qū)域面積，均有BHV＞AHV，因此不論是根據(jù)個(gè)體的支配關(guān)系還是個(gè)體對(duì)總的超體積的獨(dú)立貢獻(xiàn)，更應(yīng)該淘汰個(gè)體A。事實(shí)上，超體積指標(biāo)在Pareto 支配關(guān)系上是嚴(yán)格單調(diào)的，因此能夠作為指導(dǎo)種群進(jìn)化的有效度量指標(biāo)[9]。

重新計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，其更新公式為

通過(guò)二元錦標(biāo)選擇父代進(jìn)行交配從而產(chǎn)生新的個(gè)體，與原種群一起構(gòu)成新的種群，繼續(xù)進(jìn)行迭代。

IBEA 通過(guò)將超體積指標(biāo)和適應(yīng)度評(píng)價(jià)方法相結(jié)合來(lái)指導(dǎo)種群進(jìn)化，與基于超體積指標(biāo)的其他典型算法 HypE[9]、MO-CMA-ES[12]和 SMS-EMOA[13]相比，在保證綜合性能最優(yōu)或次優(yōu)的前提下，其運(yùn)行效率是最高的，這也是本文選擇IBEA 作為算法基礎(chǔ)框架的主要原因。

2.2 NSGA-Ⅲ

NSGA-II[32]是基于擁擠度距離建立偏序集來(lái)篩選個(gè)體指導(dǎo)種群進(jìn)化，能夠有效處理多目標(biāo)優(yōu)化問(wèn)題。NSGA-Ⅲ[33]在NSGA-II 的基礎(chǔ)上通過(guò)使用一組預(yù)定義的參考點(diǎn)在臨界層選擇個(gè)體來(lái)確保種群良好的分布性，該算法在最壞情況下的時(shí)間復(fù)雜度為O（N2lgM-2N）或 O（N2M）。

基于參考點(diǎn)方法的NSGA-Ⅲ能夠維持種群個(gè)體分布的多樣性和均勻性，因此將NSGA-Ⅲ整合到IBEA 框架中，獲得的解能夠同時(shí)具有良好的收斂性和分布性，使得程序的運(yùn)行效率更高，同時(shí)解也能夠均勻分布在整個(gè)Pareto 前沿面。有兩種方法可以將NSGA-Ⅲ和IBEA 結(jié)合：一是在IBEA 運(yùn)行完成的基礎(chǔ)上再運(yùn)行NSGA-Ⅲ，也就是IBEA 先迭代更新完成，獲得收斂性較好的種群，然后將獲得的種群作為NSGA-Ⅲ的初始種群繼續(xù)進(jìn)行迭代優(yōu)化，以期獲得分布性也較好的解；二是先運(yùn)行NSGA-Ⅲ，然后將獲得的分布均勻的種群作為IBEA 的初始種群、利用超體積指標(biāo)指導(dǎo)種群進(jìn)化來(lái)繼續(xù)對(duì)選擇過(guò)程增壓，以期獲得綜合性能均較好的解。

本文選擇第1 種結(jié)合方式。因?yàn)樵诨诔w積指標(biāo)的算法中，IBEA 的收斂速度較快，分布性較差，因此重點(diǎn)在于改善IBEA 的分布性，在IBEA 運(yùn)行的基礎(chǔ)上再運(yùn)行NSGA-Ⅲ能夠?qū)崿F(xiàn)此目的。而對(duì)于第2 種方式，先利用NSGA-Ⅲ獲得分布性較好的解，然后在此基礎(chǔ)上通過(guò)IBEA 繼續(xù)進(jìn)行個(gè)體的迭代選擇，很可能會(huì)破壞之前已經(jīng)均勻分布的解，反而降低了算法的綜合性能。

2.3 非支配排序

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

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

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

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

2.4 MOEA-HV 算法步驟

通過(guò)精確計(jì)算種群中個(gè)體的獨(dú)立貢獻(xiàn)超體積來(lái)指導(dǎo)種群進(jìn)化，在IBEA 前對(duì)所有種群個(gè)體進(jìn)行非支配排序并與NSGA-Ⅲ結(jié)合，共同組成了MOEAHV 算法。算法步驟如下：

輸入：種群數(shù)量、組合迭代次數(shù)、參數(shù)k、參考點(diǎn)輸出：Pareto 前沿面

（1）初始化。獲得初始種群，并生成參考點(diǎn)。

（2）非支配排序。對(duì)種群進(jìn)行非支配排序，提前刪除被支配的個(gè)體，減少超體積的計(jì)算量。

（3）計(jì)算非支配排序后種群中每個(gè)個(gè)體的適應(yīng)度值，并淘汰適應(yīng)度值最小的個(gè)體。

（4）選擇、交叉、變異，產(chǎn)生新的種群。利用二元錦標(biāo)法選擇最優(yōu)的兩個(gè)個(gè)體到交配池進(jìn)行交叉變異，產(chǎn)生新的個(gè)體與原種群合并為新的種群。

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

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

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

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

圖 5 三維情況下個(gè)體獨(dú)立貢獻(xiàn)超體積的計(jì)算Fig. 5 Calculation of the individuals’ exclusive hypervolume contributions in three dimension

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

表 1 各算法運(yùn)行時(shí)間均值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 算法在部分測(cè)試函數(shù)上的Pareto 前沿面Fig. 6 Pareto fronts of MOEA-HV on some test functions

從表2 和表3 中各算法的IGDm和HVm可以看出，MOEA-HV 的收斂性和分布性要明顯優(yōu)于IBEA，同時(shí)與NSGA-Ⅲ結(jié)合后算法綜合性能與NSGA-Ⅲ相比也更優(yōu)，與其他算法相比能夠取得最優(yōu)或次優(yōu)的綜合性能，且性能穩(wěn)定。總體來(lái)看，MOEA-HV 在DTLZ 系列測(cè)試函數(shù)上的性能要優(yōu)于在ZDT 系列測(cè)試函數(shù)上的性能，因?yàn)榧尤敕侵渑判蚝突趨⒖键c(diǎn)的NSGA-Ⅲ算法后，三維解集中的非支配個(gè)體要比二維的多，因此MOEA-HV 的解集在Pareto 前沿面上分布會(huì)更加均勻。具體來(lái)說(shuō)，MOEA-HV 在測(cè)試函數(shù) ZDT1、ZDT2、ZDT5、ZDT6 和 DTLZ1～DTLZ7上的綜合性能最優(yōu)或次優(yōu)，說(shuō)明該算法能夠較好地處理具有凹性、多模態(tài)、偏好的問(wèn)題，但在測(cè)試函數(shù)ZDT3、ZDT4 上性能表現(xiàn)不佳，算法在處理不連續(xù)以及多模態(tài)混合問(wèn)題時(shí)尚且有待改進(jìn)，同時(shí)測(cè)試函數(shù)ZDT5 具有欺騙性，導(dǎo)致算法容易陷入局部最優(yōu)，解的分布性較差，測(cè)試函數(shù)DTLZ5 和DTLZ6 具有退化性，比較難收斂，因此測(cè)試的所有算法在這兩個(gè)測(cè)試函數(shù)上表現(xiàn)的收斂性均較差。與其他基于超體積的典型算法相比，MOEA-HV 的運(yùn)行效率更高，且能夠保持較好的收斂性和分布性。

3.1 參數(shù) k 的影響

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

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

圖 7 不同參數(shù) k 對(duì)IBEA 運(yùn)行時(shí)間、IGDm 值和HVm 值的影響Fig. 7 Influence of different k on runtime, IGDm and HVm of IBEA

3.2 非支配排序的影響

IBEA 的計(jì)算復(fù)雜度高，主要原因是需要計(jì)算每個(gè)個(gè)體的獨(dú)立貢獻(xiàn)超體積，而通過(guò)Pareto 支配關(guān)系對(duì)個(gè)體進(jìn)行篩選能夠提前刪除質(zhì)量不好的個(gè)體從而降低了整個(gè)解集中個(gè)體的超體積計(jì)算量，能夠有效提高程序的運(yùn)行效率。設(shè)置種群大小為100，迭代次數(shù)為500，在相同條件下獨(dú)立運(yùn)行10 次，對(duì)在IBEA中是否加入非支配排序進(jìn)行對(duì)比實(shí)驗(yàn)以探究非支配排序?qū)λ惴ǖ挠绊?。?shí)驗(yàn)的測(cè)試函數(shù)為ZDT1～ZDT6和DTLZ1～DTLZ7，分別比較IBEA 中是否加入非支配排序的運(yùn)行時(shí)間均值、IGDm值和HVm值，如圖8所示，其中NDSort+IBEA(Mean)和NDSort+IBEA(Sd)分別表示算法IBEA 加入非支配排序后所獲得的平均值以及標(biāo)準(zhǔn)差，而IBEA(Mean)和IBEA(Sd)則表示沒(méi)有加入非支配排序得到的平均值和標(biāo)準(zhǔn)差。

對(duì)于2 個(gè)目標(biāo)的ZDT 系列測(cè)試函數(shù)來(lái)說(shuō)，計(jì)算的超體積為二維的（即面積），比較簡(jiǎn)單，使得加入非支配排序程序的算法運(yùn)行時(shí)間與IBEA 相近甚至更長(zhǎng)。因?yàn)榧尤敕侵渑判蚝笏惴ǖ倪\(yùn)行效率更高，但同時(shí)算法的程序也更長(zhǎng)，導(dǎo)致前者節(jié)約的時(shí)間與后者所消耗的時(shí)間剛好抵消，因此在迭代之后兩者的運(yùn)行時(shí)間相近。從圖8（a）中可以看出，對(duì)于3 個(gè)目標(biāo)的DTLZ 系列測(cè)試函數(shù)來(lái)說(shuō)，加入非支配排序后算法的運(yùn)行時(shí)間顯著降低，是因?yàn)槿S的超體積更難計(jì)算，經(jīng)過(guò)非支配排序之后能有效刪除不好的個(gè)體，從而大大減少超體積的計(jì)算量。同時(shí)，從圖8（b）、（c）中可以看出，加入非支配排序后算法的性能更加穩(wěn)定，且能在一定程度上提高算法的綜合性能。

圖 8 非支配排序?qū)?IBEA 運(yùn)行時(shí)間均值、IGDm 值和HVm 值的影響Fig. 8 Influence of non-dominated sort on runtime, IGDm and HVm of IBEA

3.3 NSGA-Ⅲ的影響

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

從圖9（a）中可以看出，與NSGA-III 結(jié)合后算法的運(yùn)行時(shí)間大幅下降，且IBEA+NSGA-III 比其他兩者的綜合運(yùn)行時(shí)間更短，但從圖9（b）的標(biāo)準(zhǔn)差數(shù)據(jù)來(lái)看，NSGA-III+IBEA 比 IBEA+NSGA-III 的運(yùn)行時(shí)間更加穩(wěn)定，因?yàn)樗惴∟SGA-III 的運(yùn)行速度快，且分布性好，所獲得的初始種群較好，因此第2 種結(jié)合方式（NSGA-Ⅲ+IBEA）的運(yùn)行時(shí)間浮動(dòng)更小、更穩(wěn)定。圖 9（c）～（f）表明 IBEA+NSGA-III 在所有測(cè)試函數(shù)上的IGDm值最小、HVm值最大，性能最穩(wěn)定，且在ZDT5、DTLZ1 和 DTLZ3 測(cè)試函數(shù)上要明顯優(yōu)于NSGA-III+IBEA，因此本文的組合算法選擇IBEA+NSGA-III 結(jié)合方式。

圖 9 NSGA-Ⅲ對(duì)IBEA 運(yùn)行時(shí)間、IGDm 值和HVm 值的影響Fig. 9 Influence of NSGA-Ⅲ on runtime, IGDm and HVm of NSGA-Ⅲ

4 結(jié) 論

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

在今后的研究中，考慮將算法MOEA-HV 應(yīng)用于解決焊接機(jī)器人多目標(biāo)路徑規(guī)劃問(wèn)題和更高維的問(wèn)題，并會(huì)繼續(xù)研究精確計(jì)算和近似估計(jì)超體積的方法，更加有效地提升算法的運(yùn)行效率，同時(shí)結(jié)合其他的優(yōu)化策略持續(xù)改善算法的綜合性能。