改進聚類算子的自適應多目標進化算法研究

謝倩文，何利力

（浙江理工大學 信息學院，浙江 杭州 310018）

0 引言

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

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

1 研究現狀

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

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

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

2 改進的多目標進化算法

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

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

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

輸入：種群迭代大小，優化問題MOP

輸出：Pareto 非支配解

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

whilet＜max Gendo（迭代次數未達到）

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

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

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

t=t+ 1

end while

returnPt

2.1 初始化

根據Indraneel 等［22］提出的Systematic Approach 產生一組均勻的權重向量{λ1,…,λN（}N是權重向量的個數，也即種群大?。唇Y構化的參考點。權重向量的個數與優化目標個數m和分割數H有關，H表示在每個目標方向上的分割數，計算如下：

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

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

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

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

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

Fig.1 Two-layer weight vector generation method圖1 兩層權向量生成法

2.2 新種群生成

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

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

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

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

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

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

2.3 環境選擇

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

算法2：Environmental Selection（R，t）

輸入：解集Rt和迭代次數t

輸出：下一代種群Pt+1

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

Pt+1= ?,i= 1

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

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

End while

Fl=Fi

if|Pt+1|≤Nthen（在關鍵層中選最后K 個）

將關鍵層中的個體根據grpipbi的值排序，Gj=

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

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

r= 1

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

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

r=r+1

end while （直到新種群數量為N時為止）

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

end if

returnPt+1

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

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

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

3 仿真實驗及分析

3.1 算法性能評價指標

參數設置見表1。

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

Table 1 Parameter settings表1 參數設置

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

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

3.2 算法性能測試對比

3.2.1 測試實驗

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

Fig.2 Test result of ZDT2圖2 ZDT2 測試結果

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

Fig.3 Test result of DTLZ1圖3 DTLZ1 測試結果

3.2.2 測試結果分析

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

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

4 結語

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