謝倩文，何利力

（浙江理工大學(xué) 信息學(xué)院，浙江 杭州 310018）

0 引言

追求多個目標同時最優(yōu)化是現(xiàn)代社會生活中經(jīng)常發(fā)生的事，而幾個優(yōu)化目標在一定程度上互相排斥的情況更是屢見不鮮。因此，多目標優(yōu)化問題（Multi-objective Optimization Problem，MOP）［1］研究發(fā)展迅速。多目標進化算法［2］可解決多目標優(yōu)化問題，在遺傳算法［3］框架下，一系列的進化算法不斷發(fā)展，如差分進化算法（Differential Evolution，DE）［4］通過改進變異向量收斂于最優(yōu)解；粒子群優(yōu)化算法［5］（Particle Swarm Optimization，PSO）通過學(xué)習(xí)鳥類捕食的群體協(xié)作行為，利用信息共享獲取最優(yōu)解；蟻群優(yōu)化算法［6］（Ant Colony Optimization，ACO）通過蟻群覓食過程中的信息素引導(dǎo)搜索方向，在組合優(yōu)化領(lǐng)域取得了較好效果。這些進化算法已經(jīng)廣泛應(yīng)用于日常生活中，如生產(chǎn)過程中的調(diào)度任務(wù)最優(yōu)化［7］，社會醫(yī)療［8］、圖像處理［9］、人工神經(jīng)網(wǎng)絡(luò)優(yōu)化、物流配送［10-11］以及網(wǎng)絡(luò)安全［12］等領(lǐng)域中的任務(wù)優(yōu)化。隨著應(yīng)用的深入，優(yōu)化進化算法逐漸成為人工智能技術(shù)中的重要一環(huán)。因此，研究多目標進化算法對可持續(xù)發(fā)展具有重大意義。單一目標優(yōu)化算法只存在單個最優(yōu)解，而多個目標的優(yōu)化問題需要盡可能地找到一組最優(yōu)解集，多個目標優(yōu)化的核心就是如何在有沖突的多個目標中找到這個最優(yōu)解集。

多目標進化算法主要包括兩部分：①原始種群生成子代種群，利用編碼操作為每個個體賦予染色體基因，對父代基因進行交叉和變異生成子代個體；②在子代種群中挑選合適的個體組成新父代進入下一次迭代，選擇算法的不同會影響最終所得個體的優(yōu)秀程度。

1 研究現(xiàn)狀

解決多目標優(yōu)化問題算法主要是基于支配關(guān)系和基于分解關(guān)系?；谥潢P(guān)系的算法主要以Deb［13］提出的帶有精英策略的非支配排序算法NSGA-II 為主導(dǎo)，在所有解中找到非支配解（Non-dominated soluitons）作為Pareto 最優(yōu)解（Pareto optimal Soluitons），利用擁擠距離在非支配解中找出一定數(shù)量的優(yōu)秀解集。NSGA-II 在低維多目標優(yōu)化問題中效果較好，但是存在搜索能力不足的問題。鄭金華等［14］提出定向搜索優(yōu)化策略，前期著重收斂性，后期著重多樣性，兼顧了兩者的平衡。為解決高維空間中擁擠距離不適用問題，NSGA-III 算法［15］利用參考點的約束支配關(guān)系找到具有更好收斂性和分布性的最優(yōu)解集。這些方法證明在一些多目標問題上都有較好性能，但是在一定程度上仍然缺乏維護種群多樣性能力。

基于分解方法的算法主要以Zhang 等［16］提出的基于分解的多目標進化算法MOEA/D 為主導(dǎo)。MOEA/D 方法初始化時先生成一組均勻分布的權(quán)重向量，將多目標問題分解成子問題，種群由每個子問題找到的最優(yōu)解組成。MOEA/D 可擴展性高、收斂快、計算復(fù)雜度低，在高維空間中處理結(jié)果更理想，但是在相對復(fù)雜的Pareto 前沿情況下，解的分布性會被破壞；Li 等［17］提出MOEA/DD，將支配和分解結(jié)合剔除最差解，得到收斂良好和分布良好的點集；Yuan 等［18］提出θ-DEA，在分解的基礎(chǔ)上利用θ支配在非支配層上選擇解來提高NSGA-III 的收斂性。但隨著目標個數(shù)的增加，以MOEA/D 算法為主要框架的進化算法會出現(xiàn)逼近Pareto前沿困難、收斂性下降、最優(yōu)解選擇不足等缺點，在非凸Pareto 前沿上的分布性還需要進一步優(yōu)化。本文研究的主要方向是在遺傳過程中通過自適應(yīng)種群來定向調(diào)整進化方向以提高收斂速度，并且在收斂過程中根據(jù)權(quán)重向量的聚類算法對種群進行選擇，以保護種群的多樣性。

在社會生活中，多目標進化算法用來解決各種問題。針對解決多目標柔性車間調(diào)度問題，呂琳［19］提出了基于均勻設(shè)計的分配方法，提高了求解最優(yōu)解的能力；周沖［20］提出基于參考點的多目標演化算法，在求解衛(wèi)星星座設(shè)計問題中平衡了收斂性和多樣性；趙雅卿［21］提出基于分解的多目標優(yōu)化算法，在陣列天線方向中得到很好應(yīng)用。

2 改進的多目標進化算法

基于分解的多目標進化算法MOEA/D 因操作執(zhí)行簡單且在處理許多目標測試函數(shù)時表現(xiàn)良好而受到青睞。在MOEA/D 算法中，有3 種分解方法可以衡量權(quán)重向量的適應(yīng)度值，分別是加權(quán)求和法（Weighted Sum Approach，WSA）、切比雪夫方法（Tchebycheff Approach，TA）和基于懲罰因子的邊界交叉方法（Penalty-based Boundary Intersection approach，PBI）。其中，切比雪夫方法和基于懲罰因子的邊界交叉方法因為能夠有效處理多目標問題而廣泛應(yīng)用。本文算法需要用到基于懲罰因子的邊界交叉聚合方法。PBI 方法根據(jù)個體到權(quán)重向量和理想點的距離，不斷收斂找到Pareto 前沿的最優(yōu)解。PBI 計算公式如下：

NSGA-ACM 算法利用NSGA-II 的快速非支配排序?qū)ΨN群進行等級排序。結(jié)合MOEA/D 的PBI 方法，加入懲罰因子θ計算gpbi值，根據(jù)gpbi選出剩余的個體。種群在迭代過程中，利用交叉變異生成子代個體，父子代合并之后根據(jù)環(huán)境選擇形成新種群；若未達到最大迭代次數(shù)則繼續(xù)進行下一次迭代，若達到次數(shù)則算法結(jié)束，輸出最優(yōu)解。算法如下：

算法1：NSGA-ACM：Frameworkofthe NSGA-ACM procedure

輸入：種群迭代大小，優(yōu)化問題MOP

輸出：Pareto 非支配解

初始化：初始化參照點{λ1,...,λN}，初始化種群N，得到初始理想點z*

whilet＜max Gendo（迭代次數(shù)未達到）

Individual=Recombination+Mutation（交叉變異進化生成新個體）

Rt=N∪Individual（合并子代種群和父代種群）

Pt=EnviromentSelection(Rt)（進行環(huán)境選擇）

t=t+ 1

end while

returnPt

2.1 初始化

根據(jù)Indraneel 等［22］提出的Systematic Approach 產(chǎn)生一組均勻的權(quán)重向量{λ1,…,λN（}N是權(quán)重向量的個數(shù)，也即種群大小），即結(jié)構(gòu)化的參考點。權(quán)重向量的個數(shù)與優(yōu)化目標個數(shù)m和分割數(shù)H有關(guān)，H表示在每個目標方向上的分割數(shù)，計算如下：

每個參考點滿足式（5）要求，即每個參考點的各分量之和為1。從幾何角度看所有參考點都落在一個平面上，即參考點是基于單位超平面產(chǎn)生的，且總的個數(shù)為N。

因此，初始化{λ1,...,λN}時，H的選擇也需要根據(jù)公式來確定。一般來說，合適的H值可以使生成的參考點數(shù)量等于種群大小N或者略小于N。當H=m時，只會在超平面的中心多出一個參考點，超平面的其余區(qū)域是沒有參考點的。然而，當m相對較大時，如m= 5，在H≥m情形下該算法會產(chǎn)生大量的參考點，這導(dǎo)致種群的數(shù)量異常龐大，從而出現(xiàn)進化緩慢、求解效率低下問題。所以，當H＞5 時就需要采用兩層權(quán)向量生成的方法，即邊界層和內(nèi)部層。內(nèi)部層產(chǎn)生的權(quán)向量不能直接應(yīng)用，需要收縮計算與邊界層的權(quán)向量在同一個平面上，最終形成參考點集W。

假設(shè)邊界層和內(nèi)部層的分割數(shù)分別是H1 和H2，那么最終的參考點個數(shù)計算如下：

通過上述公式計算了邊界層和內(nèi)部層的參考點位置以及數(shù)量之后，內(nèi)部層參考點需要進行坐標變換。假定原內(nèi)部層參考點為其在第j維的目標函數(shù)值進行如式（7）的變換：

式中，τ是收縮因子，通常取τ=0.5。最后，邊界層和內(nèi)部層的參照點一起合并成最終的參考點集Ζ。當邊界層分段數(shù)p1=2、內(nèi)部層分段數(shù)p2=1 時，三維目標空間中雙層參考點生成情況如圖1 所示。

Fig.1 Two-layer weight vector generation method圖1 兩層權(quán)向量生成法

2.2 新種群生成

對于進化算法來說，生成子代種群是很重要的環(huán)節(jié)，其主要依靠遺傳算法的選擇操作和重組操作，而重組操作又分為交叉和變異。選擇操作指從父代種群中選擇個體生成子代，而重組操作則是在選擇過程中根據(jù)交叉因子和變異因子定向改變父代個體，使得生成的子代個體向最優(yōu)解收斂。從父代種群中隨機選擇兩個個體p1和p2，將p1和p2進行編碼，對編碼基因進行交叉和變異之后生成新的子代個體c。在NSGA-II 算法中選擇固定的交叉因子Pc和變異因子Pm，而這兩個參數(shù)大小直接影響到種群迭代過程中生成的子代個體優(yōu)秀程度。在種群迭代前期，小概率的交叉操作可以保證種群的多樣性，交叉因子Pc需要小一點；當種群中優(yōu)秀個體比例較高個體差異不明顯之后，交叉因子Pc需要大一點。而變異操作能夠避免算法陷入局部最優(yōu)，種群初期提高變異概率可以加快算法的搜索速度，種群后期需要保證新種群的優(yōu)秀個體不被淘汰，所以選擇較小的變異概率。

為了在迭代過程中提高收斂速度并且豐富解的多樣性，本文提出了自適應(yīng)交叉變異策略以保證每一次的交叉和變異都是根據(jù)當前種群解的情況所得到，計算公式如式（8）和式（9）所示。

其中，Pc表示算法固定的交叉因子，Pm表示算法初始的變異因子，i表示當前的第i次迭代，gen表示算法設(shè)置的種群最大迭代次數(shù)，根據(jù)實驗情況設(shè)置為1.5 時效果最好。本文采用模擬二進制交叉（SBX）和多項式變異（PM）的方法來產(chǎn)生子代種群。通過模擬單點二進制交叉方法，兩個父代個體通過使用SBX 算子產(chǎn)生兩個后代個體

其中，β是由分布因子η按照公式（11）動態(tài)隨機決定的。η是一個自定義的參數(shù)，η值越大，產(chǎn)生的后代個體逼近父代個體的概率越大，建議η=1。

多項式變異操作使個體基因改變，提高了算法的搜索能力，計算公式如式（12）和式（13）所示。其中，i表示決策向量x的第i個分量，ai和bi分別表示第i個分量的上界和下界，pm表示變異概率，只有達到變異概率才會發(fā)生變異。

Δi的計算公式如式（13）所示。其中，隨機數(shù)u是［0，1）的隨機數(shù)，η是一個自定義的分布參數(shù)，為任意非負實數(shù)。遺傳算法通過交叉和變異這對相互配合又相互競爭的操作使其具備兼顧全局和局部的均衡搜索能力，使算法維持群體多樣性。

2.3 環(huán)境選擇

環(huán)境選擇的目的是選擇出當前種群中符合最優(yōu)條件的個體進行下一次迭代，環(huán)境選擇算法如下：

算法2：Environmental Selection（R，t）

輸入：解集Rt和迭代次數(shù)t

輸出：下一代種群Pt+1

(F1,F1,…)=Fast-non-dominated sorting（Rt）//非 支 配 排 序

Pt+1= ?,i= 1

while|Pt+1|+|Fi|≤Ndo//關(guān)鍵層之前的非支配解全部放入新種群中

Pt+1=Pt+1∪Fiandi=i+ 1

End while

Fl=Fi

if|Pt+1|≤Nthen（在關(guān)鍵層中選最后K 個）

將關(guān)鍵層中的個體根據(jù)grpipbi的值排序，Gj=

（Cji表示第i個聚集中心的第j個個體，

Gj表示所有聚集中心的第j個個體的集合）

r= 1

While|Pt+1|+|Gr|≤Ndo

Pt+1=Pt+1∪Gr（從距離參照點最近的個體開始依次放入新種群中）

r=r+1

end while （直到新種群數(shù)量為N時為止）

從Gr中隨機選擇N-|Pt+1|個體

end if

returnPt+1

初始化時，種群P0和第一代子代種群Q0混合形成新種群R，迭代選擇從種群R開始。本文根據(jù)NSGA-II 中的快速非支配排序算法將種群R按照非支配等級進行排序。首先找出當前種群R中的非支配解集，記為第一非支配層F1，該非支配解集中的解互不支配，但是能支配不在這個解集中的其他所有解。將F1的所有解賦予非支配序號irank= 1（其中irank是個體i的非支配序值），除去第一非支配層F1之后，在剩下的種群個體中找到新的非支配解集，記為第二非支配層F2，F(xiàn)2中解的非支配序號在上一支配層的基礎(chǔ)上增加為irank= 2，序號越低，解的支配優(yōu)先級越高。按照上述步驟進行下去，直到整個種群分為不同支配級別的解集，同一層內(nèi)的個體具有相同的非支配序號irank。將種群劃分成不同等級之后，先將優(yōu)先級最高的等級層中的個體放入新種群S，若放入新種群之后數(shù)量仍然小于N，則繼續(xù)加入下一個優(yōu)先級等級層的個體，直到S的數(shù)量大于或等于N。若加入Fl層時新種群數(shù)量大于N，則需要在Fl層中選擇部分合適的個體放入S直到數(shù)量等于N，此時的Fl層稱為關(guān)鍵層。

NSGA-II 算法在關(guān)鍵層中選擇合適的剩余個體是通過計算關(guān)鍵層中個體的擁擠距離來實現(xiàn)的，按照從大到小依次將個體放入新種群S中。但是擁擠距離在超過3 維的多目標進化算法中選擇效果不太理想，因此本文采用基于懲罰的邊界交叉聚合方法來選擇種群個體。對于每一個權(quán)重向量，計算該非支配層上所有個體到權(quán)重向量的gpbi值，將個體分配到具有最小gpbi值的聚簇Cj中。依次將各個聚簇中心的個體放入新種群中，直到新種群的數(shù)量為N時停止。

在生成新子代過程中，基于固定交叉因子和變異因子的多目標進化算法NSGA-II 不能根據(jù)種群的迭代情況動態(tài)調(diào)整參數(shù)，導(dǎo)致種群前期和后期在擁有不同占比優(yōu)秀解的情況下算法搜索能力下降和收斂速度減緩。同時，在關(guān)鍵層使用擁擠距離來選擇個體并不適合高維度優(yōu)化問題，這直接影響了解在Pareto 前沿上的分布和收斂效果。本文利用改進后的自適應(yīng)種群生成策略，動態(tài)地改變交叉概率和變異概率，根據(jù)種群當前的迭代情況調(diào)整進化方向，同時通過關(guān)聯(lián)個體和權(quán)重向量改變個體與權(quán)重向量聚合的方法，由此選擇出最后的剩余個體，形成新一代種群，有效提高算法的收斂性。通過在多目標問題測試集ZDT 和DTLZ上進行測試，NSGA-ACM 在解集的收斂性和分布性上效果更好。

3 仿真實驗及分析

3.1 算法性能評價指標

參數(shù)設(shè)置見表1。

分布性（Distribution）：解是否完全落在整個Pareto 前沿上，兩個解之間的分布是否與Pareto 前沿的形狀相適應(yīng)。

Table 1 Parameter settings表1 參數(shù)設(shè)置

收斂性（Convergence）：算法得到的解與真實的Pareto前沿的距離［23］顯示，真實解距離Pareto 前沿越近，越能找到近似最優(yōu)解。

逆世代距離（Inverted Generational Distance，IGD）：表示真實Pareto 前沿中每個解到近似解中所有解的歐氏距離，從而對算法的收斂性和分布性進行評估［24］。IGD 越小表示得到的解的綜合收斂效果和分布效果越好。如果IGD 值為0，則說明得到的候選解覆蓋了全部真實Pareto 前沿。

3.2 算法性能測試對比

3.2.1 測試實驗

本文主要在二維優(yōu)化問題和五維優(yōu)化問題上進行測試。在二維優(yōu)化問題上，NSGA-II 和MOEA/DD 的交叉因子Pc和變異因子Pm分別設(shè)置為0.9 和1/N，而改進后的NSGA-ACM 的交叉和變異因子是根據(jù)種群的迭代次數(shù)自適應(yīng)變化調(diào)整的，但Pc和Pm的初始值為0.9 和1/N。本實驗選擇在ZDT2 測試問題上進行對比測試。ZDT2 是非凸問題，能夠較全面地測試NSGA-ACM 在Pareto 前沿的分布性和收斂性。在五維優(yōu)化問題中，交叉因子Pc和變異因子Pm的設(shè)置與上述二維優(yōu)化問題設(shè)置相同，對比實驗選擇在DTLZ問題上進行，設(shè)置最大迭代次數(shù)maxGen=300，種群大小N=300。圖2 和圖3 分別是算法在ZDT2 問題和DTLZ1 問題上的測試結(jié)果。

Fig.2 Test result of ZDT2圖2 ZDT2 測試結(jié)果

參數(shù)初始化設(shè)置多目標問題為DTLZ1 問題，種群的最大迭代次數(shù)gen=300。

Fig.3 Test result of DTLZ1圖3 DTLZ1 測試結(jié)果

3.2.2 測試結(jié)果分析

如圖2 所示，NSGA-ACM 算法在二維優(yōu)化問題中找到的解基本上都處在真實POF 上，并且解在中心區(qū)域和靠近坐標軸區(qū)域仍然保持著均勻分布；NSGA-II 算法中雖然大部分解都能落在POF 上，但最終的分布效果不是很理想，有待于進一步優(yōu)化；MOEA/DD 算法的分布性和收斂性都不如NSGA-ACM 算法，部分解無法收斂到POF。表2為算法在測試函數(shù)上的IGD 值的平均值和標準差。從表中數(shù)據(jù)可知，NSGA-ACM 在測試函數(shù)上的IGD 值要略低于其他算法，并且在重復(fù)實驗中算法的IGD 值較為穩(wěn)定，上下浮動不大。在DTLZ 測試函數(shù)上，NSGA-ACM 收斂性比NSGA-II 更好，分布性比MOEA/DD 更廣。綜上所述，NSGA-ACM 在二維以及五維優(yōu)化問題上的實現(xiàn)效果優(yōu)于MOEA/DD 以及NSGA-II。

Table 2 IGD mean and standard deviation of each algorithm of diffevent test functions表2 在不同測試函數(shù)上各算法的IGD 的平均值和標準差

4 結(jié)語

NSGA-ACM 算法采用自適應(yīng)種群的交叉因子和變異因子定向調(diào)整種群迭代方向，在種群初期增強種群的多樣性，在迭代后期又能維護種群的多樣性，此種改進方式使得算法能夠搜索到更加符合真實Pareto 前沿的最優(yōu)解。在PBI 方法的基礎(chǔ)上通過個體與參考點關(guān)聯(lián)策略，將個體放在參考點的聚簇中，找出剩余最優(yōu)解，提高了算法的收斂性。在二維測試函數(shù)上進行測試實驗，對比分析顯示該算法不僅能夠收斂于Pareto 前沿，還能保證完全覆蓋Pareto前沿以及在Pareto 前沿上均勻分布。從各項實驗數(shù)據(jù)可知，NSGA-ACM 算法在二維和五維空間中，與NSGA-II、MOEA/DD、NSGA-II 這3 個算法對比都能展示出更優(yōu)越的性能，在均勻分布性以及收斂性方面都得到了改善。