基于Pareto支配的高維多目標(biāo)優(yōu)化算法的分析與研究

操心慧，許麗娟

（廣州華商學(xué)院數(shù)據(jù)科學(xué)學(xué)院，廣州 511300）

0 引言

多目標(biāo)優(yōu)化問題（multi?objective optimization problems，MOPs）是指具有多個目標(biāo)且在本質(zhì)上存在沖突，需要同時進(jìn)行優(yōu)化的問題。多目標(biāo)優(yōu)化的概念在實(shí)際應(yīng)用中經(jīng)常被研究，如軟件工程、配電網(wǎng)絡(luò)和工業(yè)調(diào)度［1］。多目標(biāo)優(yōu)化方案中各目標(biāo)的沖突行為，導(dǎo)致獲得一組非支配解，稱為Pareto最優(yōu)集，即目標(biāo)空間［2］。多目標(biāo)優(yōu)化算法（MOEAs）在求解多目標(biāo)優(yōu)化問題時是有效的，因?yàn)樗鼈兡軌蛟趩未芜\(yùn)行中獲得Pareto 最優(yōu)集。MOEAs 在求解MOPs 時的主要目的是在收斂性（得到的Pareto前沿與真實(shí)Pareto前沿的接近程度）和多樣性［3］（得到的Pareto前沿中種群的均勻分布）之間取得平衡。MOEAs能否在收斂性和多樣性之間進(jìn)行權(quán)衡，主要取決于所采用的選擇策略。按照機(jī)制將其大致分為：Pareto支配型MOEAs（PD?MOEAs）、分解型MOEAs、指標(biāo)型MOEAs［4］，而其中Pareto支配型MOEAs最為流行。

然而，大多數(shù)經(jīng)典的基于Pareto 支配的MOEAs（PDMOEAs）在多目標(biāo)優(yōu)化問題上表現(xiàn)較好，但在處理超過三個目標(biāo)的問題，也就是高維多目標(biāo)優(yōu)化問題（MaOPs）時，效果大大折扣。PDMOEAs 在解決多目標(biāo)優(yōu)化問題時，由于難以在收斂性和多樣性之間取得平衡，其性能急劇下降。導(dǎo)致PDMOEAs 性能下降的主要原因是Pareto支配關(guān)系的失效，后續(xù)多樣性的維護(hù)操作占據(jù)了主導(dǎo)位置，這種現(xiàn)象降低了選擇壓力，不能引導(dǎo)搜索過程向收斂方向發(fā)展。也可以理解為由于目標(biāo)空間維度的增加，MOEAs 的行為采用了隨機(jī)搜索，大多數(shù)個體變得無法比較，而解集無法收斂到Pareto最優(yōu)前沿［5］。

此外，隨著目標(biāo)數(shù)量的增加，在多樣性和收斂性之間取得平衡成為一項(xiàng)艱巨的任務(wù)。由于計(jì)算復(fù)雜度的問題，MOEAs 中使用的種群規(guī)模有限，個體最終會在高維空間中彼此遠(yuǎn)離，導(dǎo)致進(jìn)化效率低下。因此，對于MaOPs 來說，設(shè)計(jì)一種算法使其穩(wěn)定有效地找到收斂性和分布性都不錯的Pareto最優(yōu)解集仍有一定難度。目前進(jìn)化計(jì)算的權(quán)威期刊《IEEE Transactions on Evolutionary Computation》和《Evolutionary Com?putation》每年都發(fā)表一系列關(guān)于高維多目標(biāo)優(yōu)化的研究成果，并呈逐年遞增趨勢。在國內(nèi)，該領(lǐng)域的研究始于2010 年，迄今為止不僅論文發(fā)表數(shù)量不多而且研究成果遠(yuǎn)滯后于國外，屬于起步階段，亟待加大研究投入，所以在國內(nèi)開展MaOEAs的研究具有十分迫切的需求。

1 高維多目標(biāo)優(yōu)化問題概述

1.1 高維多目標(biāo)優(yōu)化問題（MaOPs）

在解決多目標(biāo)優(yōu)化問題時，有些問題是難以解決的。這是因?yàn)槎嗄繕?biāo)優(yōu)化問題（MOPs）不同于單目標(biāo)優(yōu)化（SOPs），在最優(yōu)解上多目標(biāo)優(yōu)化問題具有多個最優(yōu)解，而高維多目標(biāo)問題是普通多目標(biāo)問題的復(fù)雜情況。

對于一個具有k個目標(biāo)，n維決策變量的MOPs，其數(shù)學(xué)模型［6］為

其中，x=(x1,x2,…,xk)∈Ω 被稱為k維決策向量，為一組個體。當(dāng)k≥4 時為高維多目標(biāo)優(yōu)化問題，在目標(biāo)進(jìn)化中優(yōu)化函數(shù)向量k是目標(biāo)函數(shù)的個數(shù)。求解高維多目標(biāo)優(yōu)化問題的最終目的是得到一組無限收斂于真實(shí)Pareto前沿，并且均勻分布的Pareto解集。

1.2 解決高維多目標(biāo)優(yōu)化問題面臨的問題

常規(guī)多目標(biāo)優(yōu)化算法能夠有效解決兩個或三個目標(biāo)的多目標(biāo)優(yōu)化問題，但將算法拓展到MaOPs（高維多目標(biāo)優(yōu)化問題）時，其求解過程將主要面臨以下三個問題：

（1）隨著目標(biāo)維數(shù)的增加，對于給定的種群，該種群中非支配解的數(shù)量占其種群規(guī)模的比例接近于1。因此，Pareto 支配關(guān)系不適合在這類問題的解之間進(jìn)行區(qū)分。MaOPs 面臨的另一個問題是，近似整個Pareto 前沿所需解的數(shù)量，正常情況下會隨著目標(biāo)函數(shù)的數(shù)量呈指數(shù)增長。因此，需要更大的種群規(guī)模來獲得適當(dāng)?shù)腜areto集近似，這又需要更長的執(zhí)行時間。

（2）隨著目標(biāo)維數(shù)的增加，如果MaOPs 的大多數(shù)目標(biāo)高度相關(guān)，則其Pareto前沿不太可能在高維目標(biāo)空間的廣泛范圍內(nèi)擴(kuò)散。此外，如果它們依賴于少數(shù)相互矛盾的目標(biāo)，則目標(biāo)空間中Pareto 沿的維數(shù)可能遠(yuǎn)遠(yuǎn)小于目標(biāo)的數(shù)量。除了目標(biāo)的數(shù)量及其相互關(guān)系之外，實(shí)驗(yàn)表明當(dāng)每個目標(biāo)的目標(biāo)值范圍不同時，一些專門設(shè)計(jì)用于處理MaOPs 的MOEAs 可能無法獲得預(yù)期的性能。因此，需要進(jìn)行目標(biāo)歸一化。然而，MaOPs 缺乏一種有效的、魯棒的歸一化方法。此外，觀察表明，歸一化在性能上的影響具有很強(qiáng)的問題依賴性。

（3）多樣性是另一個需要考慮的方面。雖然非支配解會影響收斂性，但保留合理數(shù)量的解可能有利于種群多樣性。目標(biāo)數(shù)量不斷增加所帶來的巨大目標(biāo)空間，為在MaOPs上保持解集均勻分布帶來了幾個挑戰(zhàn)。在這些挑戰(zhàn)和研究機(jī)會中，仍然需要開發(fā)適當(dāng)?shù)亩鄻有员４鏅C(jī)制、適當(dāng)?shù)膿頂D距離機(jī)制和最優(yōu)解集的最終評估方法。

2 PDMOEAs的改進(jìn)方法

針對PDMOEAs 在處理高維多目標(biāo)優(yōu)化問題時所出現(xiàn)的性能缺陷，專家學(xué)者們對其進(jìn)行改進(jìn)，改進(jìn)的方向大致分為以下三類。

2.1 優(yōu)勢關(guān)系的松弛

這一類思想側(cè)重于放松支配關(guān)系，即通過引入新的支配關(guān)系來修改傳統(tǒng)Pareto支配關(guān)系的定義。引入改良顯性關(guān)系的主要目的是提高兩個體在MaOPs上的可比性。

文獻(xiàn)［7］提出了一種新的控制個體優(yōu)勢區(qū)域（CDAS）的方法，以提高M(jìn)OEAs 的性能。CDAS算法通過控制優(yōu)勢區(qū)域，誘導(dǎo)出合適的個體排序，增強(qiáng)了選擇過程。文獻(xiàn)［10］提出了一種自適應(yīng)外部參數(shù)S 和自控制個體優(yōu)勢區(qū)（S?CDAS）的CDAS 方法來解決MaOPs 問題。在S?CDAS 算法中提出的主要改進(jìn)是，S?CDAS 采用了細(xì)粒度排序，將極限解始終包含在隊(duì)列的最前面。文獻(xiàn)［8］提出了一個廣義Pareto 最優(yōu)（GPO）來處理PDMOEAs 的可擴(kuò)展性問題。GPO 的主要思想是，隨著問題維度的增加，解決方案的主導(dǎo)區(qū)域逐漸擴(kuò)大。廣義Pareto最優(yōu)方法與控制優(yōu)勢區(qū)域擴(kuò)張程度的擴(kuò)展角參數(shù)相關(guān)聯(lián)。文獻(xiàn)［9］提出了Pareto支配關(guān)系的模糊化方法，并分析了該方法在MOEAs 設(shè)計(jì)中的適用性。同時，描述了一種通用排序方案，該方案以集合依賴、非對稱和尺度無關(guān)的方式分配具有支配度的任意向量集。文獻(xiàn)［10］引入了一種新的適應(yīng)度評價(jià)機(jī)制，將解連續(xù)劃分為不同程度的最優(yōu)解。在適應(yīng)度評價(jià)機(jī)制的基礎(chǔ)上，基于模糊邏輯提出了一種模糊Pareto?dominance（FD），并將其整合到流行的NSGA-II和SPEA2中，增加解決MaOPs上的性能。文獻(xiàn)［11］提出了一種對傳統(tǒng)Pareto?dominance的修正，稱為g?dominance，可以被納入到任何MOEA 的設(shè)計(jì)中。g?dominance 利用了納入?yún)?考點(diǎn)的信息，沒有任何縮放函數(shù)的幫助，逼近最優(yōu)區(qū)域周圍的有效集。文獻(xiàn)［12］提出了ε-MOEA，該ε-MOEA 采用了一種新的Pareto 優(yōu)勢變體—ε-優(yōu)勢與存檔和選擇策略相結(jié)合，以提高對Pa?reto最優(yōu)集的搜索。文獻(xiàn)［13］提出了強(qiáng)化優(yōu)勢關(guān)系（SDR），它是對Pareto 優(yōu)勢關(guān)系的一種新的加強(qiáng)方式。然而，改良優(yōu)勢度關(guān)系的PDMOEAs 處理MaOPs 的性能有所提高，但往往會出現(xiàn)局部最優(yōu)情況。

2.2 使用附加指標(biāo)結(jié)合Pareto優(yōu)勢

這類思想集中于將附加的指標(biāo)與Pareto優(yōu)勢相結(jié)合，以促進(jìn)PDMOEAs 的融合。許多工作集中在發(fā)展有效的額外指標(biāo)，以提供適當(dāng)?shù)木庵g的收斂性和多樣性。

文獻(xiàn)［14］提出了一種MOEA（NSGA-III），該MOEA 生成一組均勻分布的參考點(diǎn)，并優(yōu)先考慮與參考點(diǎn)垂直距離最小的非支配解，以保持多樣性。換句話說，在NSGA-III 中，多樣性的保存機(jī)制借助于一組分布良好的參考點(diǎn)。在NSGA-III 的環(huán)境選擇中，合并種群中的每個個體都與一個參考點(diǎn)關(guān)聯(lián)，與參考點(diǎn)距離最小的解將被選擇。文獻(xiàn)［15］引入了一種多樣性機(jī)制，基于移位的密度估計(jì)（SDE）指標(biāo)，旨在保持多樣性而不失去收斂性。SDE 的基本思想是通過相對于每個目標(biāo)的收斂性比較，移動其他個體的位置來估計(jì)候選解的密度。因此，收斂性能較差的個體會有高密度值。文獻(xiàn)［16］提出了基于Pareto?dominance 和排序方法的MOEA，在總體中給每個候選解分配一個優(yōu)先級排序。根據(jù)①非支配排序得到的解的Pareto 排序給每個候選解分配優(yōu)先級排序；②歸一化目標(biāo)和；③改變生態(tài)位半徑。優(yōu)先級最低的個體在交配和環(huán)境選擇中更受青睞，因?yàn)樗鼈兗铀倭讼騊areto前沿的收斂，同時保持了多樣性。文獻(xiàn)［13］提出了一種基于矢量角度的MaOPs-EA，它采用了Pareto 優(yōu)勢與最大矢量角度優(yōu)先原則相結(jié)合。除了這些指標(biāo)，還采用了劣解消除原則。文獻(xiàn)［17］基于有利收斂（FC）和方向多樣性（DD）提出了一種多目標(biāo)進(jìn)化算法（MOEA-DDFC）。在MOEA?DDFC 算法中，引入了良好的收斂性和方向多樣性，使算法的收斂性和多樣性同時提高。

2.3 以支配與分解相結(jié)合為基礎(chǔ)

最后一類是將基于支配的方法與基于分解的算法相結(jié)合。文獻(xiàn)［18］提出了一個統(tǒng)一的范式，采用基于優(yōu)勢的方法與基于分解的方法相結(jié)合來解決MaOPs（MOEA-DD）。在MOEA-DD中，利用一組權(quán)值將目標(biāo)空間劃分為不同的子區(qū)域，每個權(quán)值向量定義一個適合度評估子問題。文獻(xiàn)［19］提出了一種雙準(zhǔn)則進(jìn)化（BCE）框架，將Pareto 準(zhǔn)則（PC）方法與非Pareto 準(zhǔn)則（NPC）方法相結(jié)合，增強(qiáng)了收斂性和多樣性。雙標(biāo)準(zhǔn)方法試圖通過充分交換信息的協(xié)作方式將PC 和NPC 方法的優(yōu)勢結(jié)合起來，以促進(jìn)彼此的進(jìn)化。另一方面，雙標(biāo)準(zhǔn)進(jìn)化試圖彌補(bǔ)彼此的弱點(diǎn)。

3 ad?MOEA

上節(jié)提到對于PDMOEAs 算法的改進(jìn)，最終的目的都是想要均衡算法的收斂性和多樣性?；诖耍竟?jié)詳細(xì)介紹一種具有自適應(yīng)交配和環(huán)境選擇的多目標(biāo)優(yōu)化進(jìn)化算法（ad?MOEA），利用自適應(yīng)交配和環(huán)境選擇的策略自適應(yīng)地平衡算法的收斂性和多樣性。

3.1 ad?MOEA的總體框架

該算法的總體框架類似于經(jīng)典的NSGA-II。在該方法中，隨機(jī)生成一個大小為N 的初始種群，并對其初始化。初始化后，得到歸一化目標(biāo)（SoNB）和擁擠距離（CWD）的Pareto 最優(yōu)解集。根據(jù)這些準(zhǔn)則計(jì)算每個候選解的加權(quán)級，然后進(jìn)行交配選擇，隨機(jī)選擇兩個親本解，并根據(jù)權(quán)重進(jìn)行比較，選擇一個權(quán)重最小的解作為后代的親本。在交配選擇后，通過突變和重組操作生成大小為N的后代種群。

將子代種群與父代種群合并，對合并種群中的每個個體，得到每個候選解的Pareto 排序和歸一化目標(biāo)之和（SoNB）。環(huán)境選擇過程中，在Pareto 優(yōu)勢之后，個體的選擇一直持續(xù)到臨界前沿。

在臨界前沿，一定概率下基于目標(biāo)之和選擇候選解，根據(jù)擁擠距離選擇剩余的候選解。選擇候選解的概率由一個自適應(yīng)參數(shù)w決定。最初，參數(shù)“w”的值設(shè)置為1，因?yàn)樵诔跏即行枰諗?。然后根?jù)問題的特點(diǎn)，自適應(yīng)參數(shù)w的值。但隨著進(jìn)化到需要增強(qiáng)多樣性的最后階段，“w”的值預(yù)計(jì)會下降。圖1 描述了所提方法的框架，在NSGA-II 框架的基礎(chǔ)上結(jié)合歸一化目標(biāo)之和SoNB 以及擁擠距離CWD 得到ad?MOEA算法的總體框架。

圖1 ad?MOEA總體框架

3.2 交配選擇

交配選擇過程在MOEAs 的進(jìn)化過程中起著重要作用。在產(chǎn)生過程中，篩選有前景子代進(jìn)化的解決方案將提高算法的性能。該算法在交配選擇中引入了加權(quán)的概念，為了得到加權(quán)排序，首先對個體進(jìn)行Pareto排序和歸一化目標(biāo)之和的升序排序，并按照排序后的順序給每個個體分配一個排序，根據(jù)排序結(jié)果，選擇有前景的子代進(jìn)化產(chǎn)生后代種群。算法1描述了交配選擇的過程。

3.3 環(huán)境選擇

環(huán)境選擇的主要目的是為下一次迭代保留作為父種群的精英。在環(huán)境選擇中，首先將交配選擇后獲得的子代種群與父種群進(jìn)行組合。然后對合并后的種群采用Pareto優(yōu)勢法，將個體分配到不同的非優(yōu)勢Pareto 前沿。根據(jù)Pareto?Dominance 算法，得到了每個候選解的歸一化目標(biāo)和擁擠距離之和。

首先，來自第一個非支配Pareto 前沿F1和判斷 |F1|>N，F(xiàn)1中的個體是基于考慮標(biāo)準(zhǔn)化目標(biāo)總和（SoNB）和擁擠距離（CWD）的自適應(yīng)方法進(jìn)行選擇。如果前面?zhèn)€體解的大小（F1）小于N，則從第二個非支配Pareto 前沿F2中選擇解；如果|F1∪F2|>N，就將Pareto前沿F2視為非支配Pareto前沿，并采用自適應(yīng)方法選擇第二非支配Pareto前沿的解。對于下一代而言，在獲得具有精英解的N大小種群之前，遵循的相同過程選擇非支配Pareto前沿的個體。本文采用了自適應(yīng)參數(shù)w，為了調(diào)整參數(shù)，利用關(guān)于組合總體中非支配解數(shù)量的信息，自適應(yīng)參數(shù)w采用如下公式計(jì)算。

其中：wt表示t代參數(shù)w的值；wt-1表示上一代中w的值；M為目標(biāo)個數(shù)；NF表示總體中非支配解的數(shù)量，N表示個體總數(shù)量。首先，基于歸一化目標(biāo)與百分比（w× 100）所需的解決方案是根據(jù)歸一化目標(biāo)的總和來選擇的。然后根據(jù)擁擠距離選擇剩余解，因此參數(shù)w在環(huán)境選擇中起著關(guān)鍵作用。

4 結(jié)語

本文對解決高維多目標(biāo)優(yōu)化問題的算法進(jìn)行了研究與分析，重點(diǎn)介紹了一種具有自適應(yīng)交配和環(huán)境選擇的多目標(biāo)進(jìn)化算法（ad?MOEA）以及處理多目標(biāo)和多目標(biāo)優(yōu)化問題的過程。該方法將歸一化目標(biāo)之和的概念引入交配選擇和環(huán)境選擇中，用以均衡收斂性和多樣性，從而得到最優(yōu)結(jié)果。環(huán)境選擇中，在臨界前沿，首先根據(jù)目標(biāo)之和選擇方案，然后根據(jù)擁擠距離選擇剩余方案。為了選擇基于歸一化目標(biāo)和的解，本文采用了由自適應(yīng)參數(shù)決定的一定概率，與現(xiàn)有的NSGA-II 算法相比，該算法的性能有所提高，與其他先進(jìn)算法相比具有競爭力。盡管如此，還無法完全解決PDMOEA 在高維多目標(biāo)優(yōu)化上遇到的問題。