兩階段三存檔集約束優(yōu)化算法(TSDA)

李二超， 李 進

(蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州 730000)

0 引言

近些年，用多目標優(yōu)化技術來解決約束問題是個熱點[1-2].首先要找到全局內(nèi)的可行解集，其次才能考慮解集的分布性和收斂性，其中設計有效的約束處理技術是關鍵所在.因此，將進化算法引入到約束多目標優(yōu)化問題中是必須的.除了要解決多目標優(yōu)化過程中面臨的提高進化算法搜索能力、避免陷入局部最優(yōu)、合理設置參數(shù)等多個問題外，還必須保證算法獲得可靠的求解性能和全局的優(yōu)化效果.因此，約束多目標優(yōu)化算法的研究內(nèi)容較多，不僅需要重點研究約束處理技術，還必須研究與之相適應的進化策略、多樣性維護策略以及精英選擇策略等多項關鍵技術.

孟紅云等[3]提出一種用于約束多目標優(yōu)化問題的雙群體差分進化算法.該算法同時使用兩個群體，一個群體用于保存搜索過程中找到的可行解； 另一個用于記錄在搜索過程中得到的部分具有某些優(yōu)良特性的不可行解, 避免了構造罰函數(shù)和直接刪除不可行解.但是，該方法在更新可行解集時會存在丟失邊界解和不利于保持種群的整體多樣性的缺陷；而在更新不可行解集時會出現(xiàn)目標函數(shù)較差的個體，從而影響種群的收斂.Deb提出了一種可行性法則[4]來比較個體, 但Deb準則認為可行解優(yōu)于不可行解，沒有利用較優(yōu)不可行解所攜帶的信息,不利于保持種群的多樣性.最近，一些學者基于精英保留機制提出了雙檔案集方法，將進化過程產(chǎn)生的可行解和不可行解個體分別存入可行解檔案和不可行檔案.例如，文獻[5]提出了基于遺傳算法的雙檔案集機制；文獻[6-9]提出了基于差分算法的雙檔案方法.然而這些方法僅粗略地以約束違反度值作為依據(jù)，優(yōu)先選擇靠近可行邊界的不可行解，沒有區(qū)分出最優(yōu)不可行解，將直接影響算法的尋優(yōu)能力.

基于此，筆者提出一種兩階段三存檔集約束優(yōu)化算法，主要創(chuàng)新點包括：①提出新的三存檔集處理約束條件，避免了處于Pareto邊緣的解與函數(shù)值較差的解采用同樣的進化策略；②對非支配解存檔集和支配解存檔集采用側(cè)重點不同的搜索方式.非支配解存檔集采用混合策略進化，既進行局部搜索又進行全局搜索，保證在Pareto前沿附近的解快速收斂，又不會陷入局部最優(yōu)；支配解存檔集采用自適應變異，將變異率和個體信息聯(lián)系起來，引導種群進化.

1 約束優(yōu)化問題及相關定義

不失一般性，一個約束的多目標優(yōu)化問題可定義如下[1]：

(1)

式中:x=[x1,x2,…,xn]∈S是決策變量，S表示n維搜索空間，它滿足如下邊界約束條件：li≤xi≤ui，1≤i≤n;F(x)是目標函數(shù)；q表示不等式約束條件的個數(shù)；m表示總約束條件的個數(shù)；gj(x)為第j個不等式約束條件;hj(x)為第j-q個等式約束條件；ui和li分別為分量xi的上界和下界.

滿足所有約束條件的解是可行解，而所有的可行解組成可行域Ω∈S；不滿足任意一個約束條件的解被稱為不可行解，所有的不可行解組成不可行域.如果gj(x)=0(j=1,2,…,q)在一個可行解處成立，則稱該不等式約束條件在該可行解處是活躍的.

個體x在第j個約束條件上的約束違反度表示為：

(2)

2 兩階段三存檔集約束優(yōu)化算法(TSDA)

通過對三存檔集進行搜索機制不同的進化方式，來引導種群向真實Pareto前沿進行進化.利用非支配解存檔集雙重尋優(yōu)，一方面使得靠近Pareto前沿的解加速向前沿靠近；另一方面使存檔集避免陷入局部收斂.支配解存檔集利用自適應的變異概率，將目標函數(shù)值與種群個體的信息聯(lián)系起來，提高了算法的搜索效率.最后通過非支配可行解存檔集保留種群當中的精英個體，提高了算法約束優(yōu)化性能.

2.1 最優(yōu)不可行解

在非支配解存檔集中讓最優(yōu)不可行解進入存檔集參與進化，不僅能加快算法的收斂速度，同時也增強了可行域邊界附近的尋優(yōu)能力.判定一個不可行解是否位于可行域附近，具體如下：若一個不可行解的約束違反度小于等于當代的ε(t)值(可行閾值)，則其為靠近可行域邊界的不可行解.

定義1ε值(可行閾值)：

(3)

式中：t是當前代數(shù)；T為進化總代數(shù)；ε(0)是種群中個體根據(jù)約束違反度升序排序后第0.05·N個個體，N為種群的規(guī)模.

定義2最優(yōu)不可行解：靠近可行域邊界，且在可行域中找不到能支配該不可行解的可行解，則稱該不可行解為最優(yōu)不可行解，如圖1所示.

圖1 最優(yōu)不可行解Fig.1 The optimal infeasible solution

圖1中點i及k皆為靠近可行域邊界(圖中的陰影部分為可行域)的不可行解，不可行解i雖然靠近可行域邊界，但其遠離Pareto前沿，對種群進化沒有引導作用，因此，在選擇最優(yōu)不可行解時，需要跳過這種不可行解.而不可行解k既滿足靠近可行域邊界又滿足在可行域中找不到能支配k的可行解，則k為最優(yōu)不可行解，讓其參與進化.

2.2 三存檔集模型

筆者基于NSGA-Ⅱ的基礎上加入了兩階段三存檔模型，該算法將進化過程劃分為兩個階段.首先，將種群利用快速非支配排序法進行分層.根據(jù)Pareto等級、約束違反度及ε(t)值劃分為非支配解(包括可行解及不可行解)、支配解及非支配可行解，分別存入3個存檔集：非支配解存檔集、支配解存檔集以及非支配可行解存檔集.然后,種群進行兩階段進化操作.第一階段：非支配解存檔集及支配解存檔集采取不同的策略分別進行進化；第二階段：判斷非支配可行解存檔集中解的個數(shù)是否超過種群數(shù)量，如果超過則將其進行快速非支配排序，計算出非支配可行解存檔集中個體的rank值及擁擠度距離值，選出種群規(guī)模大小的優(yōu)秀個體.

2.3 非支配解存檔集進化

定義3非支配解存檔集(NDA)：根據(jù)2.1節(jié)所計算出當代的ε(t)值區(qū)分出種群中約束違反度小于等于ε(t)值的解，其中既包括可行解，也包括不可行解.若該解rank值等級為1，則為非支配解，非支配解的集合稱為非支配解存檔集.

非支配解存檔集(NDA)既進行局部搜索又進行全局搜索.NDA存檔集中的解雖然皆為Pareto等級為1的解，但這些解有靠近真實Pareto前沿的、也有遠離Pareto前沿的.若只進行局部搜索，很可能陷入局部最優(yōu)當中，因此，筆者采用非支配解存檔集局部搜索和全局搜索同時進行.因為非支配解存檔集中的不可行解為靠近可行域且在可行域當中沒有能支配它的可行解，所以非支配不可行解只進行局部搜索可以更好地引導種群向Pareto前沿進化.非支配解存檔集當中的可行解分為兩種情況：一種情況為該可行解位于Pareto前沿附近，采用局部搜索策略可以使其盡快收斂；另外一種情況為該可行解遠離Pareto前沿，采用全局搜索策略可以擴大搜索的空間，避免陷入局部最優(yōu).鑒于以上兩種情況，非支配解存檔集當中的可行解為不確定因素，故筆者采用兩種不同交叉變異概率對其進行進化.首先將可行解復制一份放入集合CNDFA中，然后非支配解存檔集整體進行局部搜索，而復制的可行解集CNDFA進行全局搜索.非支配解存檔集進化過程中，交叉算子取0.5，變異算子取0.05，在進化過程中生成一個隨機數(shù)，若隨機數(shù)u≤0.5，u為[0,1]上均勻分布的隨機數(shù)，則進行SBX交叉操作；若隨機數(shù)u≥0.95，則進行多項式變異操作；0.5<若隨機數(shù)u<0.95，則按照約束違反度值從小到大，從非支配解存檔集合中依次選擇兩個個體進入下一代.CNDFA集合仍采用原NSGA-Ⅱ的SBX交叉和多項式變異操作.

2.4 支配解存檔集進化

定義4支配解存檔集(DA)：若該解不為非支配解，則其為支配解，支配解的集合稱為支配解存檔集.

支配解存檔集進行全局搜索，具體操作如下.

(1)交叉操作：為了跳出局部最優(yōu)以及加強空間搜索能力，筆者將正態(tài)分布引入到SBX算子中.由于正態(tài)分布的引入，算法可搜索到的空間更為廣闊，因此更容易跳出局部最優(yōu)，從而使Pareto前沿更具延展性，均勻地分布在Pareto域上，保證種群的多樣性.NDX算子的產(chǎn)生方式如下：

如果u≤0.5，則

(4)

如果u>0.5，則

(5)

式中:c1/2,k為子代染色體上對應的第k個變量；p1,k、p2,k分別為父代兩個染色體上對應的第k個變量；|N(0,1)|為正態(tài)分布隨機變量.

(2)變異操作：經(jīng)典NSGA-Ⅱ算法中多項式變異算子與種群個體的信息并沒有聯(lián)系，無論種群進化到何種程度，變異概率都為固定值，種群沒有特定的方向進行進化.因此，將種群個體當前信息與變異算子結(jié)合起來時，才能使種群向著真實的Pareto前沿進化.自適應變異算子[10]產(chǎn)生方式如下：

pm=

(6)

式中：fmax、fmin分別為當前種群中目標函數(shù)的最大值、最小值；favg為當前種群所有個體平均目標函數(shù)值.

在進化的初期，個體的最大目標函數(shù)值fmax與最小目標函數(shù)值fmin差異較大，目標函數(shù)值較大和較小的個體數(shù)目大致相同，此時favg近似等于fmax與fmin的平均值.由式(6)知，(fmax-favg)/(fmax-fmin)的值大致為0.5，此時求得的變異概率較大，有助于算法初期進行全局搜索，尋找最優(yōu)解集.算法進化到后期，大部分種群個體求得的目標函數(shù)值大致相同，此時favg是一個略大于fmin的值.當所有個體都進化到最優(yōu)解時，達到一種極限條件，即fmin=favg，這時公式中(fmax-favg)/(fmax-fmin)的值接近1，交叉變異概率相對調(diào)整為較小的數(shù)，增進局部尋優(yōu)的能力，與種群個體尋優(yōu)的方向相一致，有利于最優(yōu)解集的搜索.

2.5 非支配可行解存檔集

筆者使用非支配可行解存檔集來保存進化過程中產(chǎn)生的所有可行非劣解.首先，在種群每次迭代過程中，將非支配存檔集中約束違反度為0的解提取出來，加入到非支配可行解集當中；然后，通過快速非支配排序，選出的N個優(yōu)秀個體進行輸出，此時輸出的解全部為最優(yōu)的可行解.

2.6 算法流程

兩階段三存檔集約束優(yōu)化算法流程：

Step1開始gen=1.

Step2初始化種群.從決策空間S隨機產(chǎn)生N個個體的初代種群P(t)={x1,t,…,xN,t}，并根據(jù)目標函數(shù)計算每個個體的目標函數(shù)值.

Step3非支配排序.對Step 2產(chǎn)生的種群進行非支配排序，按照非支配等級由小到大排序，并計算每個個體的約束違反度.

Step4存檔集劃分.將種群中每個個體的約束違反度值與可行閾值ε(t)值相比，再根據(jù)rank值大小，分類到非支配解存檔集(NDA)、支配解存檔集(DA)及非支配可行解存檔集(NDFA)當中.

Step5基因操作.對非支配解存檔集和支配解存檔集采取不同的進化策略.

Step5.1非支配解存檔集采用混合搜索策略.根據(jù)2.3節(jié)中的內(nèi)容分別對NDA和CNDFA兩個集合進行局部搜索和全局搜索，合并進化后的兩個集合，記作U(t).

Step5.2支配解存檔集采用全局搜索.利用正態(tài)分布算子和自適應變異算子對DA進行交叉變異操作，從而生成子種群Q(t).

Step6合并子父代種群.將U(t)，Q(t)及父代種群P(t)進行合并，記作Y(t).

Step7選擇操作.將Y(t)進行快速非支配排序，根據(jù)rank值及擁擠度距離值大小從Y(t)中選擇出N個個體作為下一代種群P(t+1).

Step8判斷當前代數(shù)是否大于設定代數(shù)，如滿足則跳轉(zhuǎn)至Step 9，進行第二階段的操作；否則，gen=gen+1，并跳轉(zhuǎn)至Step 3.

Step9對非支配可行解存檔集(NDFA)進行快速非支配排序，根據(jù)rank值及擁擠度距離選擇出N個個體，輸出最終的Pareto最優(yōu)解，算法終止.

2.7 計算復雜度分析

假設非支配解存檔集規(guī)模為N1，支配解存檔集規(guī)模為N2，非支配可行解存檔集規(guī)模為N3.則計算非支配解存檔集、支配解存檔集和非支配可行解存檔集目標函數(shù)和約束違反度的時間復雜度為O(m(N1+N2+N3)).其中，m為目標函數(shù)個數(shù)；N為種群規(guī)模；非支配解存檔集變異和交叉操作的時間復雜度為O(mN1)；支配解存檔集變異和交叉操作的時間復雜度為O(mN2)；選擇操作的時間復雜度為O(m(N1+N2+N3)2).綜上，TSDA算法迭代一次的最壞時間復雜度為O(m(N1+N2+N3))+O(mN1)+O(mN2)+O(m(N1+N2+N3)2)，所以本文算法時間復雜度為O(mN2).

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

3.1 測試函數(shù)與參數(shù)設置

所有實驗在硬件配置為Intel Pentium、G2030 CPU、4G內(nèi)存、主頻3.0 GHz、Win10系統(tǒng)的計算機上進行，程序采用Matlab R 2010 編寫.

為了驗證TSDA算法的性能，選擇了SRN、TNK、OSY作為測試函數(shù)，其函數(shù)表達式見表1.并與運用可行性規(guī)則的NSGA-Ⅱ算法(FRNSGA-Ⅱ)進行比較.

TSDA算法參數(shù)設置：隨機生成的種群規(guī)模為N=200，進化代數(shù)為2 000代，交叉算子為NDX(正態(tài)分布)交叉算子，采用自適應變異算子，交叉變異概率詳見2.4節(jié).

FRNSGA-Ⅱ算法參數(shù)設置：隨機生成的種群規(guī)模為N=200，進化代數(shù)為2 000代，交叉算子為SBX算子，交叉概率為0.95，變異算子為多項式變異，變異概率為0.05.

測試函數(shù)特點：SRN函數(shù)的Pareto前沿連續(xù)；TNK函數(shù)為非線性約束函數(shù)，且其Pareto前沿不連續(xù)；OSY函數(shù)共有6個不等式約束條件，既有線性約束又有非線性約束;Pareto前沿由三段折線組成.約束測試函數(shù)的真實Pareto前沿源自參考文獻[11].

3.2 評價指標

3.2.1 GD指標

世代距離(generational distance，GD)[12]，用于評價所求得的近似Pareto前沿Pknow相對于真實Pareto前沿Ptrue的逼近程度，該指標的定義如下：

(7)

式中：NPF為Pknow中個體的數(shù)量；di為Pknow中第i個個體的目標向量到Ptrue中最近個體的歐式距離;GD越小，表明Pknow越逼近Ptrue，收斂性越好.

表1 測試函數(shù)表達式Tab.1 Description of test functions

3.2.2 SP指標

Schott在1995年提出了Spacing指標[13],用來計算所求得的解集在目標空間上的分布均勻性，其計算公式如下所示：

(8)

表2為2種算法對上述3種測試函數(shù)的SP、GD的統(tǒng)計結(jié)果.可以看出，本文算法TSDA在測試函數(shù)TNK、OSY上的GD值明顯小于對比算法——FRNSGA-Ⅱ算法，說明筆者所提算法采用的策略避免了種群陷入局部最優(yōu)，對種群收斂到Pareto前沿起著重要的作用.在SP值方面，算法也有著明顯的優(yōu)勢，這說明所提算法的分布性更好，保證了種群的多樣性.

3.3 仿真結(jié)果

圖2、圖4、圖6為本文算法TSDA所求得的Pareto前沿，圖3、圖5、圖7為基于可行性規(guī)則的NSGA-Ⅱ算法所求得的Pareto前沿.通過以上的對比可以看出:對于SRN函數(shù)，兩種算法雖然都找到了真實的Pareto前沿，但FRNSGA-Ⅱ算法的分布性和收斂性較差；對于TNK測試函數(shù)，本文算法TSDA有更好的收斂性，并保持良好的分布性；對于OSY測試函數(shù)，F(xiàn)RNSGA-Ⅱ算法所得到的解集明顯偏離真實前沿.由此可以得出，筆者提出的TSDA算法在3個約束測試問題上，其最優(yōu)Pareto前沿在逼近性和分布性上都明顯優(yōu)于FRNSGA-Ⅱ.

4 結(jié)論

針對約束優(yōu)化算法處理位于Pareto邊緣的解與函數(shù)值較差的解采用相同的進化策略使得尋優(yōu)結(jié)果較差的問題，提出兩階段三存檔集約束優(yōu)化算法.利用兩個存檔集不同的尋優(yōu)方式，很好地兼顧了探索開發(fā)和收斂的平衡.并且通過與其他算法在3種測試函數(shù)上的對比表明，本文算法在處理約束多目標優(yōu)化問題時，分布性及收斂性均具有一定優(yōu)勢.

表2 2種進化算法求解標準測試函數(shù)所得的GD、SP值Tab.2 GD and SP values obtained by two evolutionary algorithms for solving standard test functions

圖2 TSDA算法SRN函數(shù)仿真結(jié)果Fig.2 Simulation result of TSDA algorithm on SRN function

圖3 FRNSGA-Ⅱ算法SRN函數(shù)仿真結(jié)果Fig.3 Simulation result of FRNSGA-Ⅱ on SRN function

圖4 TSDA算法TNK函數(shù)仿真結(jié)果Fig.4 Simulation result of TSDA algorithm on TNK function

圖5 FRNSGA-Ⅱ算法TNK函數(shù)仿真結(jié)果Fig.5 Simulation result of FRNSGA-Ⅱ on TNK function

圖6 TSDA算法OSY函數(shù)仿真結(jié)果Fig.6 Simulation result of TSDA algorithm on OSY function

圖7 FRNSGA-Ⅱ算法OSY函數(shù)仿真結(jié)果Fig.7 Simulation result of FRNSGA-Ⅱ on OSY function

然而，必須承認，本文算法TSDA在計算量上要高于FRNSGA-Ⅱ算法.接下來的研究將致力于如何降低算法的時間復雜度及本文算法的實際應用.