基于參考向量的自適應(yīng)約束多目標進化算法

史非凡，史旭華

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江寧波 315211）

0 引言

目前，多目標進化算法（Multi-Objective Evolutionary Algorithm，MOEA）在工程優(yōu)化領(lǐng)域中的應(yīng)用展現(xiàn)出了其高效的計算能力及優(yōu)異的算法性能。它大致分為三類：第一類是基于帕累托支配關(guān)系的算法。在該類型的多目標優(yōu)化算法中，解的選擇策略是基于帕累托（Pareto）支配關(guān)系，同時采用特殊的環(huán)境選擇策略（小生境策略，聚類算法等）來同時保證解的收斂性及分布性。典型算法是由Deb 等［1］改進的NSGA-II（Non-dominated Sorting Genetic Algorithm II）。此外Hua 等［2］提出了一種結(jié)合聚類方法的多目標優(yōu)化算法CA-MOEA（Clustering-based Adaptive MOEA），該算法對當(dāng)前最優(yōu)種群進行聚類，通過聚類中心來選擇進入下一代的解，以保證解的分布性，在不規(guī)則的前沿面上展示出了良好的效果。第二類是基于性能指標的算法，為了對比MOEA 的性能，一些性能指標被提出用于定量地評價算法得到的種群質(zhì)量，通過對其性能指標的評估來選擇進入下一代的解。AR-MOEA（MOEA with Reference point Adaptation）采用一種改進的反向世代距離（Inverted Generational Distance，IGD）指標及自適應(yīng)的參考點來進行環(huán)境選擇［3］。第三類是基于目標分解的算法。該類算法的核心思想是生成一組均勻分布的權(quán)重向量，通過聚合函數(shù)將多目標問題轉(zhuǎn)化為多個標量子問題，并且權(quán)值向量本身的均勻分布保證了解分布性。基于分解的多目標進化算法（MOEA based on Decomposition，MOEA/D）［4］中給出了三種聚集函數(shù)，即權(quán)重和方法（Weighted Sum）、切比雪夫方法（Tchebycheff）和基于懲罰的邊界交叉（Penalty-based Boundary Intersection，PBI）方法。PBI 方法的參數(shù)可以通過設(shè)置近似于前兩種方法，目前一般都采用PBI 方法。在此基礎(chǔ)上Jain 等［5］結(jié)合非支配排序及可行性法則提出了C-MOEA/D（Constraint-MOEA/D）來處理約束多目標優(yōu)化問題（Constrained Multi-objective Optimization Problem，CMOP）。MOEA/D-AWA（MOEA/D with Adaptive Weight vector Adjustment）［6］中通過權(quán)值向量的轉(zhuǎn)換改進了Tchebycheff 方法，它能獲得和PBI 方法同樣好的分布性。進一步地，RVEA（Reference Vector guided Evolutionary Algorithm）是為了解決高維多目標優(yōu)化問題而提出來的，該算法提出了一種全新的聚集函數(shù)APD（Angle Penalized Distance），并且能在種群迭代過程中重建參考向量，計算速度及求得解的精度都很出色［7］。

在過去的20 年中，多目標進化算法在解決無約束的多目標優(yōu)化問題上非常成功，但是當(dāng)使用其處理CMOP 時需要合適的約束處理技術(shù)來處理等式約束及不等式約束。常用的約束處理技術(shù)可以大致分為兩類：第一類方法同時處理目標及約束，例如罰函數(shù)法［8］和多目標優(yōu)化方法［9］等。罰函數(shù)法通過懲罰因子的方法將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題。這類方法的主要問題就是懲罰因子的設(shè)置，然而對于不同的CMOP，調(diào)整懲罰因子是比較困難的。多目標優(yōu)化方法是將約束轉(zhuǎn)化為問題的一個目標，是原本m個目標的n個約束優(yōu)化問題轉(zhuǎn)化成m+n個無約束優(yōu)化問題。第二類方法分別處理目標及約束，代表性的方法是Deb［10］提出可行性法則。此外還有一種ε約束處理方法［11］，該方法在解的約束違規(guī)小于閾值ε時，將其視為可行解。當(dāng)ε=0 時，該方法等同于可行性法則。

基于對工程優(yōu)化領(lǐng)域上解的不確定性和約束的復(fù)雜性，本文提出一種基于參考向量的自適應(yīng)約束多目標進化算法（Adaptive Reference Vector based Constrained MOEA，ARVCMOEA），通過分階段分類別的混合計算意圖在各種形態(tài)的CMOP 上均獲得較好的搜索性能。算法初始階段對種群進行分類：一類不考慮約束條件，使種群可以跨越約束范圍較大或約束值大的區(qū)間，也能加快收斂速度；另一類考慮約束并且對分布性提出更為嚴格的要求，使種群保持良好的分布性。算法在最后階段進行局部搜索，根據(jù)當(dāng)前支配解比例及對應(yīng)的參考向量構(gòu)建局部分布性強化區(qū)域。通過降低非支配解對應(yīng)參考向量的分布性要求構(gòu)建強化搜索區(qū)域，增強算法的搜索能力；同時，動態(tài)地更新參考向量所屬區(qū)域，從而在保證種群分布性的前提下提高算法的搜索能力。

1 相關(guān)背景

1.1 約束多目標優(yōu)化

一個約束多目標優(yōu)化問題（CMOP）可以描述為：

其中：F(x)是決策空間到目標空間的映射，是m維向量，m為目標個數(shù)；gi(x)和hj(x)分別為第i個不等式約束和第j個等式約束；p為不等式約束數(shù)量；q為等式約束數(shù)量；x=(x1，x2，…，xn)T是決策變量，是一個n維向量，n是決策變量個數(shù)。

一般解的約束違反值由式（2）計算：

其中：ε是無窮小值，一般ε=1×10-6用來將等式約束轉(zhuǎn)化為不等式約束。

1.2 聚合函數(shù)

聚合函數(shù)通過對解相較于參考向量的幾何關(guān)系來評價其優(yōu)劣。MOEA/D 中包含三種聚合函數(shù)，分別是Weighted Sum、Tchebycheff 與PBI 方法。本文采用的是RVEA 中一種基于角度的聚合函數(shù)的思想，該函數(shù)通過當(dāng)前解與參考向量的夾角進行適應(yīng)度懲罰，并在此基礎(chǔ)上進行一些微調(diào)，其標量子問題可以描述為：

其中：

進一步地標量的子問題的適應(yīng)度函數(shù)結(jié)合約束的懲罰項可以概括成：

1.3 CMOP的困難點

1）分布性的困難。通常這類的帕累托最優(yōu)前沿（Pareto Front，PF）是不連續(xù)的或者因較大的不可行域造成一小部分比其余部分PF 難以被搜索到。

2）可行區(qū)間的困難。通常是因為極小的可行域難以被搜索到或者極大的不可行域阻擋了搜索方向因而陷入局部最優(yōu)。

3）收斂性的困難。CMOP 阻礙了MOEA 向PF 的收斂，即約束阻擋了算法的收斂，在進化過程中很難實現(xiàn)最小化。

2 參考向量自適應(yīng)的多目標約束進化算法

圖1（a）為算法C-MOEA/D 在測試函數(shù)DASCMOP5［12］上的局部種群分布情況。常規(guī)的基于分解的算法采用單一聚合函數(shù)，這樣會因為標量化問題的收斂性、分布性及約束違反值的權(quán)重分配問題導(dǎo)致部分個體在約束邊緣聚集，無法對種群進化提供有效幫助。圖1（b）為NSGA-II 在測試函數(shù)C1-DTLZ1 上的種群分布情況，種群因一個較大的不可行域而無法收斂至最優(yōu)。這兩類難點在解空間上存在于不同的位置，極大的不可行域存在于種群的收斂過程中，而PF 的不連續(xù)是集中在PF 附近。即可以在算法起始優(yōu)先使種群跨越約束快速收斂至PF 附近，然后再優(yōu)化種群分布性。

圖1 C-MOEA/D及NSGA-II算法在兩種特殊的測試函數(shù)上種群的分布情況Fig.1 Population distribution of C-MOEA/D and NSGA-II algorithms on two special test functions

MOEA 對于CMOP 的難點主要集中在極大的不可行域造成的算法陷入局部最優(yōu)及PF 不連續(xù)造成的分布性差。

本文算法將參考向量分為兩類：一類在算法全局采用同一聚合函數(shù)以保證算法穩(wěn)定性；另一類參考向量根據(jù)階段不同變化聚合函數(shù)及約束處理方法以指導(dǎo)種群進化。在算法初始通過部分無約束計算的種群指導(dǎo)種群跨越不可行區(qū)間，有效地搜索可行域，提高種群收斂速度；在算法后期采用弱分布性的聚合函數(shù)，通過擴大對種群進化沒有幫助的參考向量的搜索范圍，為種群分布性提供幫助，增強算法搜索能力。

2.1 參考向量的分類及更新

基于分解的多目標優(yōu)化算法首先要生成均勻分布的與種群數(shù)量N相同數(shù)量的參考向量。本文將參考向量等分成主參考向量及輔助參考向量兩類，并采用均勻分布方式，見圖2。主參考向量主要為了保證算法穩(wěn)定性，全局保持同一聚合函數(shù)，并且側(cè)重分布性。

圖2 主參考向量及輔助參考向量分布示意圖Fig.2 Schematic diagram of distribution of main reference vectors and auxiliary reference vectors

在第一階段，輔助參考向量在計算適應(yīng)值函數(shù)時不考慮約束，主要作用是指導(dǎo)種群越過較大的不可行域，并且能夠加速算法收斂；而主參考向量考慮約束且強調(diào)分布性使種群可以盡可能地保存分布性的信息。當(dāng)主參考向量在無約束的情況下近似收斂時，算法進入第二階段。第二階段是柔性過渡階段，全部參考向量均考慮約束。由于當(dāng)前輔助參考向量有可能存在于不可行域中，突然增加約束會造成該部分解直接被可行域中解取代，不利于算法收斂，影響算法搜索能力。本文對約束進行適當(dāng)降權(quán)，適應(yīng)值函數(shù)自適應(yīng)調(diào)整權(quán)重，使輔助參考向量有一個反向的搜索能力。當(dāng)全部解均是可行解或一定代數(shù)后算法進入第三階段，該階段試圖解決因約束導(dǎo)致的PF 不連續(xù)造成的部分參考向量對應(yīng)的解始終是遠離PF 的非支配解，無法對最終的收斂及分布性提供幫助的問題。所以在第三階段將當(dāng)前種群中非支配解所對應(yīng)的參考向量記為非支配參考向量即主參考向量，其他向量記為支配參考向量即輔助參考向量，區(qū)別在于輔助參考向量在適應(yīng)度計算時減少其角度的懲罰項，使搜索范圍增大，提高算法搜索能力。

三個階段的參考向量分類用邏輯矩陣mark進行二分類。主參考向量邏輯值始終為1，本文要注意的是在第二階段的過渡開始時重置全部參考向量的邏輯值為1。第三階段設(shè)置當(dāng)前支配解所對應(yīng)參考向量為主參考向量，其他向量為輔助參考向量，并進行動態(tài)更新。整體更新規(guī)則詳見算法1。

2.2 適應(yīng)值計算及約束處理

在適應(yīng)值計算方面，主參考向量作為保證算法穩(wěn)定性的基礎(chǔ)，全局采用同一適應(yīng)值函數(shù)，側(cè)重于對分布性的要求。而輔助參考向量作為輔助指引，本文則側(cè)重其收斂性，并且放寬其多樣性要求，從而提高收斂速度及搜索范圍。本文通過式（5）中的α參數(shù)控制，主參考向量對分布性要求高，α默認取2，在幾何意義上近似于PBI 聚合函數(shù)。輔助參考向量加速收斂以及放寬搜索區(qū)間α默認取10。以主參考向量為例，當(dāng)前解與當(dāng)前參考向量的夾角是當(dāng)前參考向量與最鄰近參考向量夾角的2 倍時懲罰值為2。基本上可以使個體在參考向量左右4 個角度附近進化，從而保留其分布性信息。

同樣在不同階段算法采用不同的約束處理方法：第一階段中輔助參考向量計算時不考慮約束來指導(dǎo)種群跨越不可行域。主參考向量計算采用罰函數(shù)法，在保證分布性的前提下盡可能地在空間中進行搜索。第二階段中所有向量均增加約束要求，并且整個種群要向著可行域進化來為第三階段中支配向量的局部搜索準備。值得注意的是當(dāng)算法進入第二階段時突然增加的約束會導(dǎo)致大量在約束空間的解會被鄰近參考向量的可行解直接取代，會降低算法的搜索能力及穩(wěn)定性。所以第二階段的適應(yīng)值函數(shù)對約束進行了限制：

其中：fr為可行解占比，當(dāng)種群不可行解占比大時約束懲罰值占主導(dǎo)地位，使個體快速向可行域進化。當(dāng)可行解占比高時，適應(yīng)值計算主要取決于聚合函數(shù)值。在第三階段中對于約束的處理變更為可行性規(guī)則，使種群充分地在可行域內(nèi)搜索。

2.3 主參考向量指導(dǎo)的父代選擇

一般多目標優(yōu)化算法會使用標準的遺傳算法（Generic Algorithm，GA）作為搜索算法，基于分解的多目標優(yōu)化算法會在相鄰區(qū)間內(nèi)隨機選擇兩個個體作為父代，通過GA 生成一個子代進行比較。本文對父代的選擇進行了改進，設(shè)置了概率Pm通過主參考向量占比來決定。

算法2 通過rand隨機一個0 到1 的隨機數(shù)，在第一階段時主參考向量占比為0.5，則pm為0.5，則有一半的概率子代會從主參考向量對應(yīng)的子代中選取，而另一半概率從全部個體中隨機選取，那么子代均為輔助參考向量對應(yīng)個體概率為0.25。在第二階段中pm為1，這里則均勻隨機產(chǎn)生父代。第三階段中若主參考向量占比高則pm小，父代大概率在主參考向量對應(yīng)的解中產(chǎn)生；若主參考向量占比低則在種群中隨機產(chǎn)生。這樣兩個父代均是輔助參考向量對應(yīng)解的概率為（1-pm）2，即降低了父代均為輔助參考向量對應(yīng)個體的概率，增強了算法穩(wěn)定性。

2.4 算法整體流程

整個算法流程基于MOEA/D 框架，結(jié)合算法1 參考向量跟新機制及算法2 的主向量指導(dǎo)的父代選擇機制，算法的整體框架如下：

初始化種群P，初始化標記矩陣mark，鄰居索引矩陣B及一些相關(guān)參數(shù)。可調(diào)參數(shù)NI代表每次判斷是否更新mark的代數(shù)間隔，可以根據(jù)設(shè)置的最大進化代數(shù)來設(shè)置，過小的NI可能造成第一階段的提前收斂，過大的NI則會導(dǎo)致階段轉(zhuǎn)換困難造成計算浪費，本文默認NI=50。算法第7）～15）行是解的更新過程，第9）行為算法2 父代的選擇策略，采用了標準GA 的交叉及多項式變異來產(chǎn)生子代。第10）～13）行是計算個體適應(yīng)度的過程，根據(jù)mark的不同使用不同的適應(yīng)度函數(shù)及約束處理方法。第16）～17）行更新mark。當(dāng)達到最大代數(shù)后算法返回最終的種群P。

3 實驗與結(jié)果分析

為了驗證算法在解決CMOP 上的性能，與算法NSGA-II［1］、C-MOEA/D［5］、MOEA/D-DAE（MOEA/D with Detect-And-Escape strategy）［13］和 CCMO（Coevolutionary Constrained Multi-objective Optimization framework）［14］在不同的測試函數(shù)DTLZ［5，15］、DASCMOP［12］和MW［16］上進行了比較。實驗在多目標優(yōu)化平臺PlatEMO［17］實現(xiàn)，其中算法所涉及到使用的GA 均采用平臺默認參數(shù)。

根據(jù)測試函數(shù)的難易程度設(shè)置終止條件，帶有約束的DTLZ 及MW 的24 個測試函數(shù)終止代數(shù)為800，DASCMOP 的6 種測試函數(shù)的終止代數(shù)為1 000。DASCMOP1～3 的參數(shù)設(shè)置為0、0.5、0.5，DASCMOP4～6 的參數(shù)設(shè)置為0.5、0.5、0.5。

表1 顯示了NSGA-II、C-MOEA/D、MOEA/D-DAE、CCMO和本文ARVCMOEA 算法在10 個帶有約束的DTLZ 測試函數(shù)、6 個DASCMOP 測試函數(shù)及14 個MW 測試函數(shù)上運行20次后計算得到的IGD 以及GD 值的平均值和標準差。IGD 通過在測試函數(shù)PF 上采樣的10 000 個參考點進行計算，可以看出本文算法在大多數(shù)測試問題上結(jié)果上更精確。其中在DTLZ 測試函數(shù)PF 相對簡單，C-DTLZ 為單一約束，DC-DTLZ為復(fù)雜約束，可以看到算法可以很好地處理單一種類約束；在DC-DTLZ 測試函數(shù)相較于其他算法結(jié)果更出色，原因在于起始階段可以快速跨越不可行域，使種群快速到達PF 附近；在部分函數(shù)上IGD 數(shù)值無法達到最優(yōu)是因為PF 不連續(xù)程度過大，算法后期大量參考向量對應(yīng)的個體仍然存在于不可行域中，即使其作為輔助參考向量得到的可行解占比仍不如通過支配關(guān)系得到解的分布性好。DASCMOP 測試函數(shù)為多種約束混合，算法仍表現(xiàn)出良好的穩(wěn)定性。MW 測試函數(shù)則是在無約束條件下收斂更為困難，一定程度上影響了算法起始階段的效果，降低了算法收斂速度。在MW4、MW8 及MW14 三個目標的測試函數(shù)下沒有達到最優(yōu)，原因在于輔助參考向量在最后搜索階段提供搜索幫助時，沒有辦法使種群均勻分布，在兩個目標時不均勻分布的效果被弱化了，目標數(shù)越多這個部分的不均勻性越高。然而這本身也是為了優(yōu)化基于分解的多目標優(yōu)化算法在不連續(xù)前沿的弊端，同時增強了搜索能力。一般IGD 指標主要衡量種群分布性，而世代距離（Generational Distance，GD）指標值主要衡量種群的收斂性。通過五種算法在不同的30 個測試函數(shù)上的GD 指標值可以看出：ARVCMOEAD 在DTLZ 及MW 問題上收斂性較好，在DASCMOP 上結(jié)果較CCMO 略差。DASCMOP 的PF 不連續(xù)且間斷多，在一定程度上影響了主參考向量的個數(shù)，這樣就導(dǎo)致算法在相同代數(shù)在收斂性上的計算次數(shù)會降低。通過對GD 及IGD 的結(jié)果與標準差比較可以展示出算法的良好的穩(wěn)定性及搜索能力。

表1 五種算法在DTLZ、MW及DASCMOP上的IGD及GDTab.1 IGD and GD of five algorithms on DTLZ，MW and DASCMOP

續(xù)表

圖3 展示了NSGA-II、CMOEA/D、MOEA/D-DAE、CCMO及ARVCMOEAD 在DC2-DTLZ3、DASCMOP6 及MW8 上的20次運算得到最優(yōu)IGD 的非支配解分布比較。在DC2-DTLZ3測試函數(shù)上可以看出ARVCMOED 在均勻分布的PF 上仍具備基于分解的MOEA 的良好的多向性分布，并且可以很好地跨越不可行區(qū)域，而在DASCMOP6 上過于分散的PF 上也能夠有較好的搜索能力并且搜索到了其他算法沒有搜索到的解，說明算法具備良好的搜索能力。

圖3 五種算法在DC2-DTLZ3、DASCMOP6及MW8上的20次運算得到最優(yōu)IGD的非支配解分布比較Fig.3 Non-dominated solution distribution comparison of optimal IGDs obtained by five algorithms after 20 runs on DC2-DTLZ3，DASCMOP6 and MW8

表2 給出算法在三個系列函數(shù)上的20 次計算的平均計算時間，結(jié)果表明NSGA-II 的耗時最短，MOEA/D-DAE 耗時最長。其中本文算法與C-MOEA/D 采用相同的搜索策略，算法時間復(fù)雜度基本一致，但是由于部分約束計算并且增加了階段及參考向量更新機制，所以計算時間會比C-MOEA/D稍長。

表2 五種算法在三個系列測試函數(shù)上的平均計算時間 單位：sTab.2 Average computing times of five algorithms on three series of test functions unit：s

圖4 給出了五種算法的GD 收斂曲線。可以看出在擁有較大不可行域的C1-DTLZ3 及MW9 測試函數(shù)上ARVCMOEA收斂性更好。在DASCMOP5 上在起始時收斂速度最快，但是中間一段階段沒有繼續(xù)收斂，是由于當(dāng)前約束處理方法導(dǎo)致的部分解可能停留存在于不可行域中，在進入最后階段時繼續(xù)收斂。在MW9 測試函數(shù)解空間中絕大部分是不可行域，這樣ARVCMOEA 在起始階段由于主參考向量對分布性信息的要求及約束處理策略，會略微影響其收斂速度。同樣由于這部分的分布性信息使算法在下一個階段可以更快地得到最優(yōu)的收斂效果。

圖4 五種算法在C1-DTLZ3、DASCMOP5及MW9上的GD收斂曲線Fig.4 GD convergence curves of five algorithms on C1-DTLZ3，DASCMOP5 and MW9

4 結(jié)語

本文針對復(fù)雜種類的CMOP 提出了基于參考向量自適應(yīng)調(diào)整的約束多目標進化優(yōu)化算法。算法將參考向量分為主參考向量和輔助參考向量，通過自適應(yīng)調(diào)整輔助參考向量來輔助算法解決不同種類的約束，而主參考向量全局不變以保證算法的合理性及穩(wěn)定性。算法通過在各個階段調(diào)整父代選擇策略及約束處理方法算法，在維持基于分解的MOEA在多樣性分布上的優(yōu)勢的前提下，提高了解決約束的能力及解的搜索能力，并且改善了基于分解的MOEA 對于不連續(xù)PF 的處理能力，結(jié)果在多個測試函數(shù)上均取得了更優(yōu)的結(jié)果。此外，若能提高算法在無約束條件下的收斂速度及搜索能力，則能進一步提高本文算法的性能。對于進化算子的選擇也能對算法在特定測試函數(shù)上的計算有較大幫助，后續(xù)可以通過結(jié)合性能優(yōu)異的MOEA 來提高算法性能。