操心慧，許麗娟

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

0 引言

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

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

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

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

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

在解決多目標優(yōu)化問題時，有些問題是難以解決的。這是因為多目標優(yōu)化問題（MOPs）不同于單目標優(yōu)化（SOPs），在最優(yōu)解上多目標優(yōu)化問題具有多個最優(yōu)解，而高維多目標問題是普通多目標問題的復雜情況。

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

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

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

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

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

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

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

2 PDMOEAs的改進方法

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

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

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

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

2.2 使用附加指標結合Pareto優(yōu)勢

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

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

2.3 以支配與分解相結合為基礎

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

3 ad?MOEA

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

3.1 ad?MOEA的總體框架

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

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

在臨界前沿，一定概率下基于目標之和選擇候選解，根據(jù)擁擠距離選擇剩余的候選解。選擇候選解的概率由一個自適應參數(shù)w決定。最初，參數(shù)“w”的值設置為1，因為在初始代中需要收斂。然后根據(jù)問題的特點，自適應參數(shù)w的值。但隨著進化到需要增強多樣性的最后階段，“w”的值預計會下降。圖1 描述了所提方法的框架，在NSGA-II 框架的基礎上結合歸一化目標之和SoNB 以及擁擠距離CWD 得到ad?MOEA算法的總體框架。

圖1 ad?MOEA總體框架

3.2 交配選擇

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

3.3 環(huán)境選擇

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

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

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

4 結語

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