一種雙種群協(xié)同進化的混合NSGA-II與MOPSO多目標算法

摘 要：多目標非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）是一種經(jīng)典的多目標進化算法，具有魯棒性強和搜索性能高的優(yōu)點，多目標粒子群優(yōu)化算法（Multi-objective Particle Swarm Optimization，MOPSO）是新型的進化算法，具有收斂速度快、精度高和搜索效率高的優(yōu)點。為了充分發(fā)揮這2種算法的優(yōu)勢，本文提出一種結合NSGA-II和MOPSO的雙種群協(xié)同進化多目標優(yōu)化算法。將算法應用于5個標準測試函數(shù)優(yōu)化問題進行對比試驗，試驗結果表明，本文算法得到的最優(yōu)解集更接近真實帕累托（Pareto）前沿，收斂性、均勻性和分布性更好，綜合性能更強。

關鍵詞：NSGA-II；MOPSO；協(xié)同進化；多目標算法

中圖分類號：TP 11" " " " 文獻標志碼：A

在工程實踐和科學研究中，許多問題涉及多個相互影響、相互沖突的目標。進化算法在解決多目標優(yōu)化問題方面具有獨特優(yōu)勢，因此受到廣泛關注。非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）是經(jīng)典的多目標進化算法之一[1]，其魯棒性和搜索性能較強。多目標粒子群優(yōu)化算法（Multi-objective Particle Swarm Optimization，MOPSO）是一種新興的進化算法范例[2]，其收斂速度快，精度和搜索效率高。這2種算法在開發(fā)和探索過程中各具特色，為了充分利用其各自的優(yōu)勢，本文提出一種雙種群協(xié)同進化的混合改進NSGA-II和MOPSO的多目標算法。針對多個標準測試函數(shù)優(yōu)化問題進行試驗，試驗結果表明，與對比方法相比，本文提出的算法在大多數(shù)試驗中效果更好。

1 多目標粒子群（MOPSO）算法原理

1995年提出的粒子群算法（Particle Swarm Optimization，PSO）是一種模擬鳥類覓食行為的算法，具有操作簡單、速度快等特點。但是在實際應用中，許多決策問題都是多目標優(yōu)化問題，采用粒子群算法來處理多目標優(yōu)化問題是一種有效方法，COELLO等[3]將粒子群優(yōu)化算法擴展至多個目標，提出了基于外部存檔思想和帕累托（Pareto）支配基本原理的MOSPO。假設D維的搜索域中包括N個粒子，那么第i個粒子的位置和速度如公式（1）、公式（2）所示。

xid=（xi1，xi2，…，xid） （1）

vid=（vi1，vi2，…，vid） （2）

式中：xid為第i個粒子在第d維的位置；vid為第i個粒子在第d維的速度。

在粒子群優(yōu)化算法中，單個粒子的速度更新過程如公式（3）所示。

vid（t+1）=wvid（t）+c1r1（Pbestid（t）-xid（t））+c2r2（Gbestd（t）-xid（t）） （3）

式中：vid（t+1）為粒子i在維度C中的速度更新后的值；t為當前迭代次數(shù)；w為慣性權重，控制上一個時刻速度對當前速度的影響，協(xié)調(diào)全局/局部搜索能力；vid（t）為粒子i在維度d中的當前速度；c1、c2分別為局部和加速因子，表示個體經(jīng)驗和群體經(jīng)驗的權重；r1、r2為隨機數(shù)，其作用是增加算法隨機性；Pbestid（t）為粒子i在維度d中的個體最優(yōu)位置；xid（t）為粒子i在維度d中的當前位置；Gbestd（t）為整個粒子群體在維度d中的全局最優(yōu)位置。

粒子i在維度d中的位置更新過程如公式（4）所示。

xid（t+1）=xid（t）+vid（t+1） （4）

式中：xid（t+1）為在第t+1時刻粒子i在維度d中的位置。

多目標粒子群算法的流程如下。1）初始化多目標粒子群算法參數(shù)，包括設置種群規(guī)模和最大迭代次數(shù)等。2）計算粒子群的適應度，根據(jù)Pareto支配原則確定非劣解和局部最優(yōu)個體Pbest。3）計算非劣解集的密度信息，并在其中選擇全局最優(yōu)解Gbest。4）判斷是否滿足粒子群的收斂條件。如果滿足，那么輸出全局最優(yōu)解Gbest；如果不滿足，那么更新粒子的速度和位置，重新計算適應度并更新非劣解集。

這個流程使粒子群不斷進行優(yōu)化，向適應度更高的區(qū)域移動，最終獲得全局最優(yōu)解。

2 多目標非支配排序遺傳算法（NSGA-II）原理

多目標遺傳算法是一種分析和解決多目標優(yōu)化問題的進化算法，其核心是協(xié)調(diào)各個目標函數(shù)之間的關系，尋找使各個目標函數(shù)盡可能達到最優(yōu)化值的解集。最優(yōu)解集通常包括多個Pareto最優(yōu)解，這些最優(yōu)解的集合稱為Pareto前沿。多目標優(yōu)化問題數(shù)學模型的計算過程如公式（5）所示 [4]。

（5）

式中：F（x）min為目標函數(shù)向量； fi（x）為第i個目標函數(shù)，共有m 個目標函數(shù)需要同時優(yōu)化；g（x）、h（x）分別為不等式約束和等式約束。

3 雙種群協(xié)同進化的混合改進NSGA-II和MOPSO多目標算法

NSGA-II與MOPSO的信息共享機制不同，NSGA-II利用遺傳算子來傳遞信息，MOPSO利用全局最優(yōu)粒子來引導其他粒子。2種算法各有優(yōu)勢，NSGA-II搜索能力較強，MOPSO收斂速度較快。因此，本文結合這2種算法，以充分利用其各自的優(yōu)點，并對其分別進行改進，進一步提升性能。具體的改進策略如下。

3.1 雙種群協(xié)同進化策略

種群協(xié)同進化策略基于NSGA-II的非支配排序。將初始化和非支配排序后的種群分為2個部分。Pareto等級較高的上半部分為精英種群，利用NSGA-II的強大搜索能力在該區(qū)域中探索更多Pareto解集，確定非支配解。Pareto等級較低的下半部分使用MOPSO算法，學習精英種群來提升自身質(zhì)量。為避免MOPSO算法導致早熟收斂，本文采用輪盤賭方法，從精英種群中選擇個體作為MOPSO的“社會部分”學習樣本。

3.2 改進NSGA-II——基于擁擠度的動態(tài)交叉與變異概率

在NSGA-II中，交叉與變異操作是個體探索空間的關鍵手段，但是傳統(tǒng)方法有一定的盲目性。為了合理控制種群的交叉與變異范圍，本文提出一種基于種群擁擠度和進化迭代數(shù)的動態(tài)交叉與變異概率，以增強種群的收斂性。交叉率和變異率的計算過程如公式（6）、公式（7）所示。

（6）

式中：pc為交叉率；pcagv、 pcmax、 pcmin為pc的平均值、最大值和最小值；t為當前迭代次數(shù)；maxIt為最大迭代次數(shù)；maxt為當前最大迭代次數(shù)；d（i）為第i個個體的擁擠度；dagv（i）為第i個個體所在前沿的平均擁擠度。

（7）

式中：pm為變異率；pmagv、pmmax和 pmmin分別為pm的平均值、最大值和最小值。

公式根據(jù)個體擁擠度與種群平均擁擠度之間的關系確定交叉和變異概率的進化方向，同時引入迭代因子，完成種群的自適應進化，加快收斂速度。

3.3 改進MOPSO——非線性學習因子

基本的粒子群算法采用固定的學習因子，不利于全局搜索最優(yōu)解。因此，本文對其進行調(diào)整。在算法前期，迭代次數(shù)少，那么c1較大，c2較小，利于局部尋優(yōu)，增加種群多樣性；在算法后期，迭代次數(shù)多，那么c1較小，c2較大，利于全局搜尋，加快收斂。改進后的迭代過程如公式（8）～公式（11）所示。

vid（t+1）=wvid（t）+c1r1（Pbestid（t）-xid（t））+c2r2（xNSGA-IIrd（t）-xid（t）） （8）

式中：xNSGA-IIrd（t）為NSGA-II種群中隨機選擇的粒子在維度d中的位置。

c1=c1min+（c1max-c1min）×t/maxt " （9）

c2=c2max+（c2max-c2min）×t/maxt （10）

式中：c1max、c1min、c2max和c2min分別為學習因子c1和c2的最大值和最小值。

xi（t+1）=xi（t）+vi（t+1） （11）

3.4 基于世代距離GD的自適應變異策略

對經(jīng)過NSGA-II遺傳操作以及MOPSO引導尋優(yōu)后得到的粒子進行非支配排序，其中非支配排序為1的個體包括當前最優(yōu)的進化信息，無論是NSGA-II還是MOPSO都存在容易陷入局部最優(yōu)的問題，若干代后可能出現(xiàn)大量相似的個體，算法無法找到最優(yōu)Pareto前沿。因此，本文對這部分解進行變異操作，提高種群跳出局部最優(yōu)的能力。同時，本文采用世代距離衡量非支配排序為1的群體變化的動態(tài)過程，并根據(jù)該變化對變異規(guī)模進行動態(tài)調(diào)整。

在變異方面，本文采用多項式變異[5]，隨機選擇個體中的一維進行變異，如公式（12）所示。

xd new=xd+（xUd-xLd）δ×k " " " " " " " " " " " " " " " " " " " " " " " "（12）

式中：xd new為變異后的粒子；xd為選擇的粒子；xUd和xLd為粒子第d維的上界和下界；δ為擾動項；k為擾動比例系數(shù)。

δ的計算過程如公式（13）所示。

（13）

式中：r為（0，1）的隨機數(shù)；μ為變異分布指數(shù)。

世代距離GD可以表示待評價解集中的解與真實Pareto解之間的歐氏距離，但是在本應用中，需要衡量非支配排序為1的群體的動態(tài)變化過程，因此取當前代的種群與前一代之間的世代距離，記作GD*，相鄰2代解集的GD*差值記作ΔGD*，如公式（14）所示。

ΔGD*（t）=GD*（t）-GD*（t-1），t≥3 （14）

式中：ΔGD*（t）為第t代種群與第t-1代種群的世代距離之差，可表征算法的收斂速度；當ΔGD*（t）gt;0時，算法收斂速度快，應縮小變異規(guī)模，提升算法效率；當ΔGD*（t）lt;0時，須增大變異規(guī)模，提升算法收斂性與多樣性。GD*（t）為第t代的種群的世代距離；GD*（t-1）為第t-1代的種群的世代距離。異規(guī)模的調(diào)整過程如公式（15）所示。

（15）

式中：Q（t+1）為第t+1代的變異規(guī)模；integer（）為取整函數(shù)；Q（t）為第t代的變異規(guī)模，當t=1，2，3時，Q（t）等于當前非支配排序為1的粒子數(shù)量。

4 算法性能分析

為了驗證算法的有效性，選擇ZDT函數(shù)集問題中的函數(shù)進行性能測試，雙種群協(xié)同進化的NSGA-II與MOPSO混合算法（NSGAMOPSO）、NSGA-II和MOPSO 3種算法進行對比。運行程序，對比結果如圖1所示，越靠近真實的Pareto前沿線，效果越好。

由圖1可知，在ZDT3-6中的測試曲線，NSGAMOPSO算法的最優(yōu)值基本都靠近ZDT3-6的Pareto真實前沿曲線，在 ZDT4 和 ZDT6 中，MOPSO 算法和 NSGA_II 算法的大部分最優(yōu)值都偏離了Pareto真實前沿曲線。3種算法的測試性能對比見表1～表5。

由表1～表5可知3個算法在ZDT1-6中的測試結果，使用NSGAMOPSO算法，4項評價指標都比MOPSO算法和NSGA-II算法更好，本文算法得到的最優(yōu)解集更接近Pareto真實前沿，收斂性、均勻性和分布性更好，綜合性能更強。

5 結論

本文提出一種雙種群協(xié)同進化的混合NSGA-II與MOPSO多目標算法。雙種群協(xié)同進化策略在NSGA-II的非支配排序基礎上進行。首先，利用2種經(jīng)典算法的優(yōu)點提出一種基于種群擁擠度和進化迭代數(shù)的動態(tài)交叉與變異概率方法進行交叉與變異操作，合理控制了種群的交叉與變異范圍。其次，在MOPSO算法的基礎上使用非線性學習因子，提升算法搜索全局最優(yōu)解的能力。最后，在非支配排序過程中采用世代距離衡量GD方法和多項式變異方法，使算法更容易跳出局部最優(yōu)，更靠近Pareto真實前沿。針對多個標準測試函數(shù)優(yōu)化問題進行對比試驗，試驗結果表明，與 NSGA-II 和 MOPSO算法相比，本文算法效果更好，給多目標優(yōu)化問題提供新的參考方法。

參考文獻

[1]王偉，曲輔凡，楊鈁，等.基于NSGA-II算法的分布式驅(qū)動電動汽車制動轉矩分配控制策略研究[J].汽車技術，2024（5）：22-30.

[2]邢毓華，任甜甜.改進MOPSO在微電網(wǎng)優(yōu)化調(diào)度中的應用研究[J].太陽能學報，2024，45（6）：191-200.

[3]COELLO CA C，PULIDO G T，LECHUGA M S.Handling

multiple objectives with particle swarm optimization[J].IEEE Transactions

on evolutionary computation，2004，8（3）：256-279.

[4]DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II[J].IEEE Transactions on evolutionary computation，2002，6（2）：182-197.

[5]李汶娟，李廣，聶志剛.多項式變異和自適應權重優(yōu)化的阿奎拉鷹算法[J].計算機技術與發(fā)展，2024，34（2）：163-170.

通信作者：馮芝麗（1986-），女，湖南永州人，碩士研究生，湖南環(huán)境生物職業(yè)技術學院副教授，研究方向為人工智能。

電子郵箱：570561252@qq.com。

基金項目：湖南省教育科學研究工作者協(xié)會2024年度高校課題“基于深度學習模型的高職智慧課堂的構建策略與應用研究”（項目編號：XJKX24B241）；2024—2025年度湖南省職業(yè)教育與成人教育學會科研規(guī)劃課題“新質(zhì)生產(chǎn)力背景下職業(yè)教育數(shù)字化轉型的價值定義與實踐路徑研究”（項目編號：XH2024198）。