文章目錄

• 1 INTRODUCTION
• 2 PRELIMINARIES
• • 2.1 文獻綜述
  • 2.2 對現(xiàn)有的約束處理方法的挑戰(zhàn)
• 3 PROPOSED ALGORITHM
• • 3.1 密度估計方法
  • 3.2 CA的更新機制
  • 3.3 DA的更新機制
  • 3.4 后代繁殖
• 4 EXPERIMENTAL SETUP
• • 4.1 基準函數(shù)
  • 4.2 指標
• 5 EMPIRICAL STUDIES
• 6 CONCLUSION
• 7 REFERENCES

摘要 在求解約束多目標優(yōu)化問題時，一個重要的問題是如何同時兼顧收斂、多樣性和可行性。針對這一問題，提出了一種無參數(shù)約束處理技術(shù)–兩檔案進化算法，用于有約束的多目標優(yōu)化問題。它同時維護兩個協(xié)同檔案：一個是推動種群走向帕累托前沿的驅(qū)動力，稱為收斂導向檔案（convergence-oriented archive）；另一個是主要傾向于維持種群多樣性的多樣性導向檔案(diversity-oriented archive)。特別是，為了補充CA的行為并提供盡可能多的多樣化信息，DA旨在探索CA未充分開發(fā)的區(qū)域，包括不可行的區(qū)域。為了利用這兩種檔案的互補作用，我們開發(fā)了一種受限的交配選擇機制，根據(jù)它們的進化狀態(tài)自適應地從它們中選擇合適的交配親本。在一系列測試函數(shù)上的復雜實驗和一個真實世界的案例研究充分證明了我們提出的算法相對于五種最先進的約束進化多目標優(yōu)化器的競爭力。

1 INTRODUCTION

??有約束的多目標問題（CMOP）可以描述為：
$$\begin{array}{rl}minimize& \mathbf{F}(\mathbf{x})=(f_1(\mathbf{x}),f_2(\mathbf{x}),...,f_m(\mathbf{x}){)}^T\\ subjectto& g_i(\mathbf{x})\ge a_j,j=1,2,...,q\\ & h_i(\mathbf{x})=b_j,j=q+1,...,?\\ & \mathbf{x}\in \Omega \end{array}$$ $\mathbf{x}$對第$j$個約束條件的違反程度計算方法為：
$$c_j\left(\mathbf{x}\right)=\{\begin{array}{ll}?g_i\left(\mathbf{x}\right)/a_j?1?,& j=1,...,q\\ ?\left|h_j\left(\mathbf{x}\right)/b_j?1\right|???,& j=q+1,...,?\end{array}$$ $?$是一個容忍項，可以將等式約束放松為不等式約束。$???$表示當括號內(nèi)大于等于零時函數(shù)值為0，否則函數(shù)值為負數(shù)。因此$\mathbf{x}$整體的違反程度為：
$$CV(\mathbf{x})=\sum _{j=1}^{?}{c}_j\left(\mathbf{x}\right)$$當 $CV(\mathbf{x})=0$ 時說明$\mathbf{x}$是可行的，否則$\mathbf{x}$不可行。
??給定兩個可行解${\mathbf{x}}^1,{\mathbf{x}}^2\in \Omega$，若在任一目標函數(shù)上$F({\mathbf{x}}^1)$都不差于$F({\mathbf{x}}^2)$，且至少在一個目標上完全優(yōu)于$F({\mathbf{x}}^2)$，則稱${\mathbf{x}}^1$支配${\mathbf{x}}^2$（${\mathbf{x}}^1?{\mathbf{x}}^2$）。若$?\mathbf{x}\in \Omega$ 使得$\mathbf{x}?{\mathbf{x}}^{?}$，則稱${\mathbf{x}}^{?}$是帕累托最優(yōu)解（Pareto-optimal），所有帕累托最優(yōu)解的集合稱為帕累托解集（Pareto set;PS）,帕累托前沿面（Pareto front;PF）定義為：$PF=\left\{\mathbf{F}(\mathbf{x})|\mathbf{x}\in PS\right\}$。
??一般而言，收斂性、多樣性和可行性是CMOP的三個基本問題。大多數(shù)現(xiàn)有的約束處理技術(shù)在考慮可行域內(nèi)的收斂和多樣性之間的平衡之前，首先傾向于將種群盡可能地留在可行域。但這可能會導致種群陷入局部最優(yōu)或局部可行域，特別是當可行域很窄或在搜索空間中分布不均勻時。
??在本文中我們提出了一種兩階段進化算法（C-TAEA）,同時維持兩個協(xié)作互補的檔案：一個是收斂導向檔案（CA），一個是多樣性導向檔案（DA）。C-TAEA主要的特點如下：
1）正如名字所示，CA是進化過程中保證解的收斂性和可行性的主導力量，它能夠使解接近PF。
2）相比之下，DA在沒有考慮可行性的情況下，主要傾向于保持進化過程的收斂性和多樣性。特別是，DA探索了CA尚未開發(fā)的領(lǐng)域。這不僅提高了CA在當前搜索的可行域內(nèi)的種群多樣性，而且有助于跳出局部最優(yōu)或局部可行域。
3）為了利用這兩個協(xié)作檔案的互補效應和精英信息，我們提出了一種受限的交配選擇機制，根據(jù)CA和DA的進化狀態(tài)分別從CA和DA中選擇合適的交配親本。
??本文的其余部分組織如下：第二節(jié)簡要概述了為解決CMOP的最新的進化算法，然后引出了我們的動機。第三節(jié)介紹了所提出算法的技術(shù)細節(jié)。在第四節(jié)和第五節(jié)中，對所提出的算法的有效性和競爭力進行了實證研究，并在不同的基準問題上與五種最新的約束EMO算法進行了比較。最后，第六節(jié)對全文進行了總結(jié)，并對今后的發(fā)展方向提出了設(shè)想。

2 PRELIMINARIES

2.1 文獻綜述

??多目標優(yōu)化中現(xiàn)有的約束處理技術(shù)的思想可以分為以下三類：
??第一類主要是由可行性主導的，其中可行方案總是被賦予更高的優(yōu)先級以生存到下一次迭代。在1990年的算法[13]中對約束的重視程度高于對目標函數(shù)的重視程度，這導致了對可行解決方案的搜索優(yōu)先于最佳解決方案。還有一些算法[14]直接忽視不可行解，這樣的算法在遇到狹窄的可行域時會產(chǎn)生很多問題。后來Deb[2]等人提出了一種帶約束的支配關(guān)系。即只要滿足以下條件就稱${\mathbf{x}}^1$支配${\mathbf{x}}^2$：1）${\mathbf{x}}^1$可行而${\mathbf{x}}^2$不可行；2）二者都不可行但$CV({\mathbf{x}}^1)<CV({\mathbf{x}}^2)$；3）二者都可行且${\mathbf{x}}^1?{\mathbf{x}}^2$。在現(xiàn)有的NSGA-II和NSGA-III的基礎(chǔ)上使用該支配關(guān)系接可以解決CMOP問題。借用此想法，幾個MOEA/D變體[15]-[17]在子問題更新過程中使用CV作為替代標準。與文獻[2]不同，Oyama et al[18]提出了一種改進的支配關(guān)系，根據(jù)該關(guān)系，優(yōu)先選擇違反較少約束的解。為了改善不可行解的可解釋性，Takahama和Sakai[19]以及Martínez和Coello[20]提出了一種$??constrained$支配關(guān)系，其中當兩個解的CV之差小于閾值$?$時，兩個解違反約束的程度相同，特別的是，該閾值可以根據(jù)種群中可行解的比例自適應地調(diào)整。Asafuddoula等人[21]提出了一種自適應約束處理方法：當不可行解的CV值小于閾值時，將不可行解視為可行解。同樣，Fan等人[22]也提出了類似的觀點：基于角度的約束支配原理，即當兩個不可行解的角度大于某一閾值時，兩個不可行解被認為是彼此非支配的。
??第二類是在搜索過程中平衡收斂和可行性。Jiménez等人[23]提出了一個最小-最大公式，該公式驅(qū)動可行解向最優(yōu)解進化，并驅(qū)動不可行解向可行性進化。Ray等人[24]提出了一種Ray-Tai-Seow算法，該算法使用三種不同的方法對非支配解進行比較和排序。具體地說，第一排序過程是根據(jù)對目標函數(shù)的排序，第二種是根據(jù)不同的約束條件進行的；第三種是基于目標值和約束條件的組合。基于同樣的嚴密性，Young[25]提出了一種約束優(yōu)勢關(guān)系，該關(guān)系根據(jù)目標空間和約束空間的混合排序來比較解。Angantyr等人[26]也提出了類似的方法，使用目標空間和約束空間中的等級的加權(quán)平均排名。[5]提出了一種新的CMO約束處理技術(shù)：將CMOP的每個原始目標函數(shù)轉(zhuǎn)換為距離度量和懲罰函數(shù)的和。特別地，將改進的目標函數(shù)用于NSGA-II的非支配排序過程中，可以在可行域和不可行域中搜索最優(yōu)解。為了提高種群的多樣性，Li et al.[27]提出了一種方法：保留孤立的不可行解。為了利用包含在不可行解中的有用信息，Peng et al.[28]提出使用一組分布在不可行域中的不可行權(quán)重來保留大量多樣性較高的不可行解。Ning et al.[29]提出了一種約束非支配排序方法，該方法根據(jù)解的Pareto排序和約束的排序得到解的約束非支配排序.。在[30]中，提出了一種對偶進化，其中不可行粒子向可行粒子進化，可行粒子向PF進化。
??最后一類試圖將不可行解修復為可行解。例如，Harada等人[31]提出了一種所謂的Pareto下降修復算子，它在約束空間中探索不可行解附近可能的可行解。然而，在實際應用中，梯度信息通常是不可用的。Singh等人[32]建議使用模擬退火法來加快從不可行解向可行解的移動過程。焦立中等人[33]提出了一種可行引導策略，其中可行方向被定義為從一個不可行解開始到其最近可行解的一個向量。然后，通過利用可行方向提供的信息，將不可行解引導到可行域。

2.2 對現(xiàn)有的約束處理方法的挑戰(zhàn)

??通過對上述文獻的回顧，我們發(fā)現(xiàn)大多數(shù)多目標優(yōu)化中的約束處理技術(shù)過于強調(diào)可行性的重要性，而很少同時考慮收斂、多樣性和可行性之間的平衡。當遇到復雜的約束時，這可能會導致搜索無效。
??以文獻[15]中的測試問題C1-DTLZ3為例，它的目標函數(shù)與[34]的DTLZ3相同，約束條件為：
$$\text{c}\left(\mathbf{x}\right)=\left(\sum _{i=1}^m{f}_i{\left(\mathbf{x}\right)}^2?16\right)\left(\sum _{i=1}^m{f}_i{\left(\mathbf{x}\right)}^2?r^2\right)$$下圖顯示了當$r=6$時MOEA/D和NSGA-III的運算結(jié)果。由于可行域與不可行域交織在一起，所喲當解離開可行邊界，CV值就會增大。因此可行性主導的結(jié)果就是解只能停留在外層可行邊界。

??文獻[15]中的測試問題C2-DTLZ2為例，它的目標函數(shù)與[34]的DTLZ2相同，約束條件為：
$$\begin{array}{r}\text{c}\left(\mathbf{x}\right)=\max ?\underset{i=1}{\stackrel{m}{\max }}?{\left(f_i\left(\mathbf{x}\right)?1\right)}^2+\sum _{j=1,j=i}^m{f}_j^2?r^2?\left[\sum _{i=1}^m{\left(f_i\left(\mathbf{x}\right)?\frac{1}{\sqrt{m}}\right)}^2?r^2\right]?\end{array}$$下圖給出了該例子的圖示，其中可行區(qū)域在PF上是不連續(xù)的。如果每個可行部分較小，則可行性驅(qū)動的策略將很容易陷入部分可行。此外，最先進的基于分解的EMO算法中使用的權(quán)重向量，例如C-MOEA/D和C-NSGA-III，如果它們的大小足夠小，則很可能沒有一個穿過這些可行段。這給基于分解的EMO算法尋找可行解帶來了很大的困難。如圖所示的結(jié)果完全驗證了我們的斷言，當我們將r設(shè)置為相對較小的值(例如0.1時)時，C-MOEA/D和C-NSGA-III都無法在所有三個可行部分上找到帕累托最優(yōu)解。

??在這些討論的基礎(chǔ)上，我們發(fā)現(xiàn)過度使用可行性信息會限制受限EMO算法的搜索能力。在第三節(jié)中，我們將演示如何使用兩個歸檔策略平衡在整個搜索空間中同時實現(xiàn)收斂、多樣性和可行性。特別是，我們發(fā)現(xiàn)，合理利用不可行信息有助于解決勘探和開采之間的兩難境地。

3 PROPOSED ALGORITHM

??我們提出的C-TAEA的總體流程圖如下圖所示。顧名思義，C-TAEA保留兩個協(xié)作檔案，CA和DA，每個檔案都有相同的固定大小$N$。具體來說，CA起主要作用，負責將種群導向可行域并接近PF；DA作為補充，主要用于探索CA開發(fā)不足的區(qū)域。值得注意的是，為了提供盡可能多的多樣化信息，DA的更新不考慮可行性信息。在繁殖過程中，交配親本根據(jù)其進化狀態(tài)分別從CA和DA中選擇，如第III-D節(jié)所述。然后，根據(jù)第III-B節(jié)和第III-C節(jié)分別描述的機制，使用子代來更新CA和DA。

3.1 密度估計方法

??在解釋C-TAEA中CA和DA的更新機制之前，我們首先介紹了對這兩種情況都有用的密度估計方法。為了便于密度估計，我們借鑒了MOEA/D-M2M[35]的思想，將目標空間劃分為$N$個子區(qū)域，每個子區(qū)域由標準單純形上唯一權(quán)向量表示。特別地，我們使用我們先前提出的可擴展到多目標場景的權(quán)重向量生成方法[27]來采樣一組均勻分布的權(quán)重向量，即$\text{W}=\left\{{\text{w}}^1,...,{\text{w}}^N\right\}$。具體地說，一個子區(qū)域${\Delta }^i$，其中$i\in \left\{1,...,N\right\}$，它的定義為：
$${\Delta }^i=\left\{\mathbf{F}\left(\mathbf{x}\right)\in {\mathbb{R}}^m|?\mathbf{F}\left(\mathbf{x}\right),{\text{w}}^i?\le ?\mathbf{F}\left(\mathbf{x}\right),{\text{w}}^j?\right\}$$ 其中$j\in \left\{1,...,N\right\}$，$?\mathbf{F}\left(\mathbf{x}\right),\text{w}?$表示$\mathbf{F}\left(\mathbf{x}\right)$與$\text{w}$之間的銳角。建立子區(qū)域后，種群中的每個解$\mathbf{x}$都與下指標如下的子區(qū)域?qū)?lián)系：
$$k=\underset{i\in \left\{1,...,N\right\}}{\mathrm{argmin}}?\bar{\mathbf{F}}\left(\mathbf{x}\right),{\mathbf{w}}^i?$$這里$\bar{\mathbf{F}}\left(\mathbf{x},t\right)$是歸一化的$\mathbf{x}$的目標向量，其第$i$個目標函數(shù)的計算方法為：
$$\overline{f_i}\left(\mathbf{x}\right)=\frac{f_i\left(\mathbf{x}\right)?z_i^{?}}{z_i^{nad}?z_i^{?}}$$其中$i\in \left\{1,...,N\right\}$，$z_i^{?}=mi{n}_{\mathbf{x}\in S}{f}_i(\mathbf{x})$，$z_i^{nad}=ma{x}_{\mathbf{x}\in S}{f}_i(\mathbf{x})$，$S$指當前解所在的解集。
??算法1給出了該關(guān)聯(lián)過程的偽代碼。將解與子區(qū)域關(guān)聯(lián)后，子區(qū)域的密度被計算為與其關(guān)聯(lián)的解的個數(shù)。
Algorithm 1:關(guān)聯(lián)過程
Input：解集$S$，權(quán)重向量集$W$
Output：子區(qū)域${\Delta }^1,...,{\Delta }^N$
Step 1) ${\Delta }^1\leftarrow ?$,…,${\Delta }^N\leftarrow ?$
Step 2) 對每一個$\mathbf{x}\in S$，以及每一個$\mathbf{w}\in W$都計算：
$$d^{\perp }\left(\mathbf{x},\mathbf{w}\right)=\mathbf{x}?{\mathbf{w}}^{\mathbf{T}}\mathbf{x}/\Vert \mathbf{w}\Vert$$Step 3) 令$k\leftarrow \underset{\mathbf{w}\in W}{\mathrm{argmin}}{d}^{\perp }\left(\mathbf{x},\mathbf{w}\right)$
Step 4) ${\Delta }^k\leftarrow {\Delta }^k\cup \left\{\mathbf{x}\right\}$
Step 5) 最后輸出${\Delta }^1,...,{\Delta }^N$
注意：偽代碼中的$\mathbf{x}$實際指目標空間中的解，也就是上文中的$\mathbf{F}\left(\mathbf{x}\right)$。
簡述版：用[35]MOEA/D-M2M中的方法將目標空間分為 $N$個子空間${\Delta }^1,...,{\Delta }^N$，再用[2]中的方法生成均勻分布的權(quán)重向量集$W$，對解集中的每個解$\mathbf{F}\left(\mathbf{x}\right)$求出與其夾角最小的權(quán)重向量${\mathbf{w}}^k$，將該解分配到${\Delta }^k$。

3.2 CA的更新機制

??CA的作用與參考文獻中其他有約束的EMO算法相似。它首先將種群盡可能地推向可行域，然后試圖在可行域內(nèi)平衡收斂性和多樣性。算法2給出了CA更新機制的偽代碼。具體來說，我們首先形成混合種群$H_C$，即 CA 和子代$Q$的組合。$H_C$中的可行解被儲存到臨時檔案$S_C$中(算法2的第3-5行)。之后，后續(xù)的程序取決于$S_C$的大小。

1）若$S_C$的大小等于$N$，即提前設(shè)定的CA的大小，則$S_C$就是新的CA，此次更新程序終止。
2）若$\left|S_C\right|>N$，我們使用[2]中的快速非支配排序方法，將$S_C$分為不同的非支配等級：$F_1$、$F_2$等。從$F_1$開始，依次選擇每個非支配等級構(gòu)成臨時檔案$S$直至檔案大小等于$N$或超過$N$。如果我們將最后一個可接受的非支配水平表示為$F_l$，則屬于$F_{l+1}$以后的解不再被考慮。需要注意的是，如果$S$的大小等于$N$，則$S$可以用作新的CA；否則，我們將S中的每個解與其對應的子區(qū)域相關(guān)聯(lián)，并計算$S$的密度信息，依次刪去最擁擠區(qū)域的最差解，直到$S$的大小等于$N$(算法2的第11-21行)。值得注意的是，為了改善一個分區(qū)域內(nèi)的人口多樣性，我們提出了以下過程來確定最差解${\mathbf{x}}^w$。首先，我們計算${\Delta }^i$內(nèi)每個個體$\mathbf{x}$與其最近點的距離：
$$dist(\mathbf{x})=\underset{{\mathbf{x}}^{\prime }\in {\mathbf{\Delta }}^i,\mathbf{x}={\mathbf{x}}^{\prime }}{\min }\Vert \mathbf{x}?{\mathbf{x}}^{\prime }\Vert$$具有最小距離的解被儲存在臨時檔案$S_t$中，而${\mathbf{x}}^w$的定義如下：
$${\mathbf{x}}^w=\underset{\mathbf{x}\in S_t}{\mathrm{argmax}}\left\{g^{tch}(\mathbf{x}|{\mathbf{w}}^i,{\mathbf{z}}^{?})\right\}$$這里，
$$g^{tch}(\mathbf{x}|{\mathbf{w}}^i,{\mathbf{z}}^{?})=\underset{1\le j\le m}{\max }\left\{\left|f_j(\mathbf{x})?z_j^{?}\right|/w_j^i\right\}$$
3）若$\left|S_C\right|<N$，我們求解如下雙目標優(yōu)化問題：
$$\begin{gathered} minimize\mathbf{F}(\mathbf{x})={\left(f_1(\mathbf{x}),f_2(\mathbf{x})\right)}^T \\ where\{\begin{array}{l}{f}_1(\mathbf{x})=CV(\mathbf{x})\\ f_2(\mathbf{x})=g^{tch}(\mathbf{x}|{\mathbf{w}}^i,{\mathbf{z}}^{?})\end{array} \end{gathered}$$
??在上述問題的基礎(chǔ)上，用快速非支配排序的方法將$H_C$中的不可行解劃分為幾個非支配等級，前幾個級別的解在CA中有更高的優(yōu)先級，多余的解根據(jù)其CV進行刪除，CV值較大的優(yōu)先刪除。這些操作都是為了進一步平更收斂性、多樣性和可行性。
簡述版：每次迭代都從上一代CA和本次生成的子代Q形成$H_C$中選擇。首先選出$H_C$中可行的解放入$S_C$，接下來討論$S_C$與N大小不同時的情況：$\left|S_C\right|=N$時，CA$\leftarrow S_C$；$\left|S_C\right|>N$時，首先對$S_C$中的解進行非支配排序得到$\left\{F_1,F_2,...\right\}$，依次將其放入一個暫時的集合$S$直至$\left|S\right|=N$，若出現(xiàn)了$\left|S\right|>N$的情況，則對此時$S$中的$\mathbf{x}$對應的$\mathbf{F}\left(\mathbf{x}\right)$進行歸一化后分到不同的子空間（3.1中的方法），選出最擁擠的子空間并計算其中每個解與最近鄰的距離，距離最小的稱之為最差解，優(yōu)先刪除，每刪除一個解后重新檢查此時$\left|S\right|>N$是否仍成立，若仍成立，則繼續(xù)判斷最擁擠的子空間是否發(fā)生變化，再計算該子空間中每個解計算最近鄰，循環(huán)直至$\left|S\right|=N$。$\left|S_C\right|<N$時，從$H_C$中不可行解中選擇非支配解排序靠前的補全CA，如果在非支配解排序過程中又出現(xiàn)$\left|S\right|>N$的情況，仍是依次刪除最差解，此時最差解的評判標準是CV值的大小，CV越大則解越差。

3.3 DA的更新機制

??與CA不同，DA的目的是維持解的多樣性。它的更新機制有兩個特點：1)它沒有考慮約束；2)它以最新的CA作為參考集，探索CA的未開發(fā)區(qū)域來補充CA。算法3給出了這種更新過程的偽代碼。

??具體而言，類似于3.2節(jié)，我們首先將DA與子代種群$Q$相結(jié)合，以形成混合種群$H_d$。然后，按照3.1節(jié)(算法3的第1-3行)中介紹的方法，將$H_d$中的每個解和最新的CA分別與其對應的子區(qū)域相關(guān)聯(lián)。然后，我們依次研究每個子區(qū)域，并決定$H_d$中的解是否保留在DA中。每個子區(qū)域在第$itr$次迭代中最多保留$itr$個解，對于當前子區(qū)域${\Delta }^i$，$i\in \left\{1,...,N\right\}$，如果在${\Delta }^i$的CA中已經(jīng)存在$itr$個解，則在此迭代過程中，$H_d$中的解將不會留在${\Delta }^i$中。否則，將選擇與${\Delta }^i$相關(guān)的$H_d$中最好的非支配解，表示為${\mathbf{O}}^i$，并將其選入新的DA(算法3的第10-12行)。這里，最優(yōu)解${\mathbf{x}}^b$被定義為：
$${\mathbf{x}}^b=\underset{\mathbf{x}\in O_i}{\mathrm{argmin}}\left\{g^{tch}(\mathbf{x}|{\mathbf{w}}^i,{\mathbf{z}}^{?})\right\}$$直至DA被填滿。

3.4 后代繁殖

??兩個檔案之間的互動和合作是C-TAEA中至關(guān)重要的一步。除了CA和DA的更新機制的互補行為外，促成這種合作的另一個因素是受限制的交配選擇。一般來說，它的主要目的是利用這兩個檔案的精英信息進行后代繁殖。算法4提供了該受限交配選擇過程的偽代碼。

具體地說，我們首先將CA和DA組合成復合集$H_m$。然后，我們分別評估CA和DA的非支配解在$H_m$中的比例(算法4的第2行和第3行)。如果${\rho }_c>{\rho }_d$，則CA的收斂狀態(tài)好于DA。因此，第一個交配親本是從CA中選擇的；否則，它來自DA(算法4的第4-7行)。至于另一個交配親本，它是從CA還是DA中選擇，取決于非支配解在CA中的比例。CA擁有的非支配解越多，它被選為交配池的機會就越大。如算法4的第5-11行所示，我們使用二進制錦標賽選擇來選擇交配親本。

如算法5所示，與[2]中提出的算法相同，該錦標賽選擇過程是可行性驅(qū)動的。具體來說，如果隨機選擇的候選者都是可行的，則根據(jù)帕累托優(yōu)勢進行選擇；如果只有一個可行，則選擇可行的；否則，以隨機的方式選擇交配親本。一旦選擇了交配的雙親，我們就使用流行的模擬二進制交叉[36]和多項式突變[37]來繁殖后代。原則上，只需稍加修改即可應用任何其他復制操作符。

4 EXPERIMENTAL SETUP

??在討論實證結(jié)果之前，這一部分簡要介紹了我們的實證研究中用于同行比較的基準問題、性能指標和最新的約束EMO算法。

4.1 基準函數(shù)

??從文獻[15]中選取了5個約束測試問題(即C1-DTLZ1/DTLZ3、C2-DTLZ2和C3-DTLZ1/DTLZ4)和6個新提出的測試問題(DC1-DTLZ1/DTLZ3、DC2DTLZ2/DTLZ4和DC3-DTLZ1/DTLZ4)組成了基準測試集。所有這些測試問題都可以擴展到任意數(shù)量的目標，其中我們在這里設(shè)置了$m\in \left\{3,5,8,10,15\right\}$。補充材料的第一節(jié)給出了這些測試問題的詳細描述，包括數(shù)學定義和性質(zhì)。

4.2 指標

??選擇了兩個廣泛使用的度量來評估不同算法的性能。
1）Inverted Generational Distance（IGD）：設(shè) $P^{?}$是在PF上均勻采樣的一組點，$P$是EMO算法求得的解集，則$P$的IGD值為：
$$IGD(P,P^{?})=\frac{{\sum }_{\mathbf{z}\in P^{?}}dist\left(\mathbf{z},P\right)}{\left|P^{?}\right|}$$
其中，$dist\left(\mathbf{z},P\right)$表示$\mathbf{z}$與$P$中最近點的歐氏距離。
2）Hypervolume (HV)：設(shè)${\mathbf{z}}^r={\left(z_1^r,...,z_m^r\right)}^T$是可以被所有帕累托最優(yōu)目標向量支配的最差解，$P$的HV值為目標空間中由$P$和${\mathbf{z}}^r$圍成的體積：
$$HV(P)=VOL(\underset{z\in P}{?}\left[z_1,z_1^r\right]\times ...\times \left[z_m,z_m^r\right])$$
其中，VOL表示勒貝格測度。
??較小的IGD和較大的HV表示解更接近PF。

5 EMPIRICAL STUDIES

6 CONCLUSION

??本文針對約束多目標優(yōu)化問題，提出了一種無參數(shù)約束處理技術(shù)C-TAEA。在C-TAEA中，我們同時維護兩個協(xié)作檔案。具體地說，一種被稱為CA，主要關(guān)注于推動人口向PF靠攏；另一種，被稱為DA，主要傾向于探索CA未被開發(fā)的區(qū)域(即使是那些不可行的區(qū)域)，從而提供更多樣化的信息。在這種情況下，CA和DA具有不同的行為和互補的作用。特別是，它們通過一種有限的交配選擇機制相互補充，該機制為后代繁殖選擇互補的交配親本。C-TAEA的性能已經(jīng)在一系列基準問題上進行了調(diào)查，這些問題具有各種類型的約束和多達15個目標。實驗結(jié)果充分證明了該算法在CMOP上的競爭力，并與五種最新的約束EMO算法進行了比較。除了人工基準問題外，C-TAEA的有效性也已在WDN設(shè)計優(yōu)化的真實案例研究中得到驗證。
??約束多目標優(yōu)化問題在實際應用中普遍存在。本文考慮的CMOP并不包含現(xiàn)實世界中的所有類型的約束。希望本文能啟發(fā)更多關(guān)于約束多目標優(yōu)化的研究，包括其他約束公式的研究以及在現(xiàn)實世界優(yōu)化場景中的應用。正如前面在[6]-[8]中所證明的，我們認為C-TAEA不僅僅是一個特定的算法。相反，它的基本思想，即同時維護多個互補和協(xié)同的檔案，可以廣泛應用于一般的EMO算法設(shè)計。在未來，從算法設(shè)計和理論基礎(chǔ)兩個角度對其潛在機制進行深入研究是值得探討的。此外，我們計劃研究這一雙檔案協(xié)作框架在更廣泛的問題上的有效性，例如無約束的MOP，包括那些具有復雜屬性的MOP(例如，具有復雜PSS的問題[43]以及不平衡的收斂和多樣性[44])、動態(tài)優(yōu)化(例如，具有變化的目標或約束的問題[45])。

7 REFERENCES

(僅列出了本文中所提到的文獻)
[2] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan,“A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002.
[5] Y. G. Woldesenbet, G. G. Yen, and B. G. Tessema,“Constraint han- dling in multiobjective evolutionary optimization,” IEEE Trans. Evol. Comput., vol. 13, no. 3, pp. 514–525, Jun. 2009.
[15] H. Jain and K. Deb,“An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: Handling constraints and extending to an adaptive approach,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 602–622, Aug. 2014.
[16] M. A. Jan and Q. Zhang,“MOEA/D for constrained multiobjective optimization: Some preliminary experimental results,” in Proc. U.K. Workshop Comput. Intell. (UKCI), 2010, pp. 1–6.
[17] R. Cheng, Y. Jin, M. Olhofer, and B. Sendhoff, “A reference vector guided evolutionary algorithm for many-objective optimization,” IEEE Trans. Evol. Comput., vol. 20, no. 5, pp. 773–791, Oct. 2016.
[18] A. Oyama, K. Shimoyama, and K. Fujii, “New constraint- handling method for multi-objective and multi-constraint evolutionary optimization,” Jpn. Soc. Aeronaut. Space Sci. Trans., vol. 50, no. 167, pp. 56–62, 2007.
[19] T. Takahama and S. Sakai,“Efficient constrained optimization by the $?$ constrained rank-based differential evolution,” in Proc. IEEE Congr.Evol. Comput. (CEC), 2012, pp. 1–8.
[21] M. Asafuddoula, T. Ray, and R. A. Sarker, “A decomposition-based evolutionary algorithm for many objective optimization,” IEEE Trans. Evol. Comput., vol. 19, no. 3, pp. 445–460, Jun. 2015.
[22] Z. Fan et al.,“Angle-based constrained dominance principle in MOEA/D for constrained multi-objective optimization problems,” in Proc. IEEE Congr. Evol. Comput. (CEC), 2016, pp. 460–467.
[23] F. Jiménez, A. F. Gómez-Skarmeta, G. Sánchez, and K. Deb,“An evolutionary algorithm for constrained multi-objective optimization,” in Proc. IEEE Congr. Evol. Comput. (CEC), 2002, pp. 1133–1138.
[24] T. Ray, K. Tai, and K.-C. Seow,“Multiobjective design optimization by an evolutionary algorithm,” Eng. Optim., vol. 33, no. 4, pp. 399–424, 2001.
[26] A. Angantyr, J. Andersson, and J.-O. Aidanpaa, “Constrained optimization based on a multiobjective evolutionary algorithm,” in Proc. IEEE Congr. Evol. Comput. (CEC), 2003, pp. 1560–1567.
[27] K. Li, K. Deb, Q. Zhang, and S. Kwong,“An evolutionary many objective optimization algorithm based on dominance and decomposition,” IEEE Trans. Evol. Comput., vol. 19, no. 5, pp. 694–716, Oct. 2015.
[28] C. Peng, H.-L. Liu, and F. Gu, “An evolutionary algorithm with directed weights for constrained multi-objective optimization,” Appl. Soft Comput., vol. 60, pp. 613–622, Nov. 2017.
[29] W. Ning et al.,“Constrained multi-objective optimization using constrained non-dominated sorting combined with an improved hybrid multi-objective evolutionary algorithm,” Eng. Optim., vol. 49, no. 10, pp. 1645–1664, 2017.
[30] A. E. Sorkhabi, M. D. Amiri, and A. R. Khanteymoori,“Duality evolution: An efficient approach to constraint handling in multi-objective particle swarm optimization,” Soft Comput., vol. 21, no. 24, pp. 7251–7267, 2017.
[31] K. Harada, J. Sakuma, I. Ono, and S. Kobayashi,“Constraint-handling method for multi-objective function optimization: Pareto descent repair operator,” in Proc. 4th Int. Conf. Evol. Multi Criterion Optim. (EMO), 2006, pp. 156–170.
[32] H. K. Singh, T. Ray, and W. Smith,“C-PSA: Constrained Pareto simulated annealing for constrained multi-objective optimization,” Inf. Sci., vol. 180, no. 13, pp. 2499–2513, 2010.
[33] L. Jiao, J. Luo, R. Shang, and F. Liu, “A modified objective function method with feasible-guiding strategy to solve constrained multi-objective optimization problems,” Appl. Soft Comput., vol. 14, pp. 363–380, Jan. 2014.
[35] H. Liu, F. Gu, and Q. Zhang,“Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems,” IEEE Trans. Evol. Comput., vol. 18, no. 3, pp. 450–455, Jun. 2014.
[36] K. Deb and R. B. Agrawal,“Simulated binary crossover for continuous search space,” Complex Syst., vol. 9, no. 2, pp. 115–148, 1994.
[37] K. Deb and M. Goyal,“A combined genetic adaptive search (GeneAS) for engineering design,” Comput. Sci. Informat., vol. 26, no. 4, pp. 30–45, 1996.

總結(jié)

以上是生活随笔為你收集整理的《Two-Archive Evolutionary Algorithm for Constrained Multiobjective Optimization》阅读笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。