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

關(guān)鍵詞：NSGA-II；MOPSO；協(xié)同進(jìn)化；多目標(biāo)算法

中圖分類號：TP 11" " " " 文獻(xiàn)標(biāo)志碼：A

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

1 多目標(biāo)粒子群（MOPSO）算法原理

1995年提出的粒子群算法（Particle Swarm Optimization，PSO）是一種模擬鳥類覓食行為的算法，具有操作簡單、速度快等特點(diǎn)。但是在實(shí)際應(yīng)用中，許多決策問題都是多目標(biāo)優(yōu)化問題，采用粒子群算法來處理多目標(biāo)優(yōu)化問題是一種有效方法，COELLO等[3]將粒子群優(yōu)化算法擴(kuò)展至多個目標(biāo)，提出了基于外部存檔思想和帕累托（Pareto）支配基本原理的MOSPO。假設(shè)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為當(dāng)前迭代次數(shù)；w為慣性權(quán)重，控制上一個時刻速度對當(dāng)前速度的影響，協(xié)調(diào)全局/局部搜索能力；vid（t）為粒子i在維度d中的當(dāng)前速度；c1、c2分別為局部和加速因子，表示個體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)的權(quán)重；r1、r2為隨機(jī)數(shù)，其作用是增加算法隨機(jī)性；Pbestid（t）為粒子i在維度d中的個體最優(yōu)位置；xid（t）為粒子i在維度d中的當(dāng)前位置；Gbestd（t）為整個粒子群體在維度d中的全局最優(yōu)位置。

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

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

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

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

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

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

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

（5）

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

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

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

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

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

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

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

（6）

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

（7）

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

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

3.3 改進(jìn)MOPSO——非線性學(xué)習(xí)因子

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

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

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

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

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

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

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

3.4 基于世代距離GD的自適應(yīng)變異策略

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

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

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

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

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

（13）

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

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

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

式中：ΔGD*（t）為第t代種群與第t-1代種群的世代距離之差，可表征算法的收斂速度；當(dāng)ΔGD*（t）gt;0時，算法收斂速度快，應(yīng)縮小變異規(guī)模，提升算法效率；當(dāng)Δ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ī)模，當(dāng)t=1，2，3時，Q（t）等于當(dāng)前非支配排序?yàn)?的粒子數(shù)量。

4 算法性能分析

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

[2]邢毓華，任甜甜.改進(jìn)MOPSO在微電網(wǎng)優(yōu)化調(diào)度中的應(yīng)用研究[J].太陽能學(xué)報，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]李汶娟，李廣，聶志剛.多項(xiàng)式變異和自適應(yīng)權(quán)重優(yōu)化的阿奎拉鷹算法[J].計算機(jī)技術(shù)與發(fā)展，2024，34（2）：163-170.

通信作者：馮芝麗（1986-），女，湖南永州人，碩士研究生，湖南環(huán)境生物職業(yè)技術(shù)學(xué)院副教授，研究方向?yàn)槿斯ぶ悄堋?/p>

電子郵箱：570561252@qq.com。

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