李二超， 李 進(jìn)

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

0 引言

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

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

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

1 約束優(yōu)化問(wèn)題及相關(guān)定義

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

(1)

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

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

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

(2)

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

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

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

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

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

(3)

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

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

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

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

2.2 三存檔集模型

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

2.3 非支配解存檔集進(jìn)化

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

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

2.4 支配解存檔集進(jìn)化

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

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

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

如果u≤0.5，則

(4)

如果u>0.5，則

(5)

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

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

pm=

(6)

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

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

2.5 非支配可行解存檔集

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

2.6 算法流程

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

Step1開(kāi)始gen=1.

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

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

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

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

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

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

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

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

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

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

2.7 計(jì)算復(fù)雜度分析

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

3 TSDA算法實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

3.2 評(píng)價(jià)指標(biāo)

3.2.1 GD指標(biāo)

世代距離(generational distance，GD)[12]，用于評(píng)價(jià)所求得的近似Pareto前沿Pknow相對(duì)于真實(shí)Pareto前沿Ptrue的逼近程度，該指標(biāo)的定義如下：

(7)

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

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

3.2.2 SP指標(biāo)

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

(8)

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

3.3 仿真結(jié)果

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

4 結(jié)論

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

表2 2種進(jìn)化算法求解標(biāo)準(zhǔn)測(cè)試函數(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

然而，必須承認(rèn)，本文算法TSDA在計(jì)算量上要高于FRNSGA-Ⅱ算法.接下來(lái)的研究將致力于如何降低算法的時(shí)間復(fù)雜度及本文算法的實(shí)際應(yīng)用.