雙種群進化算法：動態約束處理與資源分配解決約束多目標優化問題

一、引言

約束多目標優化問題（CMOPs）在工程設計、資源分配等領域廣泛存在，其核心是在滿足多個約束條件的同時優化多個目標函數。傳統方法往往難以平衡約束滿足與目標優化，導致搜索效率低或陷入局部最優。本文介紹一種基于動態約束處理和資源分配的雙種群進化算法（DPCPRA），通過主輔種群協作與動態機制，有效提升求解性能。

二、CMOPs數學模型與挑戰

CMOPs的標準形式為：
$$?\begin{array}{l}\min \mathbf{F}(\mathbf{x})=(f_1(\mathbf{x}),f_2(\mathbf{x}),\dots ,f_m(\mathbf{x}))\\ \text{s.t.}\mathbf{x}\in \Omega \\ g_j(\mathbf{x})\le 0,j=1,2,\dots ,p\\ h_j(\mathbf{x})=0,j=p+1,\dots ,q\end{array}$$
其中，$\mathbf{x}$為決策變量，$g_j$和$h_j$分別為不等式和等式約束。約束違反度定義為：
C V j ( x ) = { max ? { 0 , g j ( x ) } , 不等式約束 max ? { 0 , ∣ h j ( x ) ∣ ? δ } , 等式約束 CV_j(\mathbf{x}) = \begin{cases} \max\{0, g_j(\mathbf{x})\}, & \text{不等式約束} \\ \max\{0, |h_j(\mathbf{x})| - \delta\}, & \text{等式約束} \end{cases} CVj?(x)={max{0,gj?(x)},max{0,∣hj?(x)∣?δ},?不等式約束等式約束?
總違反度$CV(\mathbf{x})={\sum }_{j=1}^{q}C{V}_j(\mathbf{x})$。
CMOPs的難點在于：

1. 可行區域可能狹小且分散，傳統算法易漏解；
2. 不可行解的利用不足，多樣性維護困難；
3. 計算資源分配不合理，導致搜索效率低下。

三、DPCPRA算法原理

1. 雙種群架構：主種群與輔助種群

• 主種群（POP1）：專注可行解搜索，采用約束主導原則（CDP），優先選擇可行解或約束違反度低的不可行解，確保收斂到可行帕累托前沿（CPF）。
• 輔助種群（POP2）：探索不可行區域，通過動態約束處理機制（DCPM）逐步增加處理的約束數量，利用部分約束信息擴大搜索空間，為POP1提供多樣性引導。

2. 動態約束處理機制（DCPM）

（1）約束優先級排序

計算每個約束的可行率（Feasible Rate）：
$$\text{Feasible?Rate}(j)=\frac{\text{種群中滿足約束}j\text{的解數量}}{\text{種群規模}}$$
按可行率升序排序，低可行率的約束優先級更高（更難滿足），形成約束分組${\text{Group}}_k$，每組包含前$k$個約束。

（2）逐步約束優化

輔助種群從無約束（優化目標函數）開始，逐步加入高優先級約束：

• 初始階段：忽略所有約束，搜索無約束帕累托前沿（UPF），擴大搜索范圍；
• 迭代階段：按分組依次加入約束，如${\text{Group}}_1$處理第1個約束，${\text{Group}}_2$處理前2個約束，直至包含所有約束。
  通過這種方式，輔助種群在不可行區域中逐步逼近可行區域，避免直接處理所有約束導致的搜索空間爆炸。

3. 動態資源分配方案（DRAS）

根據種群搜索效率動態調整資源分配比例：

• 子生成功率：計算主/輔助種群子代的存活比例
  $${\text{Success\_rate}}_1=\frac{|\text{Off1中存活個體}|}{|\text{Off1}|},{\text{Success\_rate}}_2=\frac{|\text{Off2中存活個體}|}{|\text{Off2}|}$$
• 資源分配系數：
  $${\text{ROS}}_1=\frac{{\text{Success\_rate}}_1}{{\text{Success\_rate}}_1+{\text{Success\_rate}}_2},{\text{ROS}}_2=1?{\text{ROS}}_1$$
  效率高的種群（存活個體多）獲得更多計算資源，例如輔助種群在探索復雜不可行區域時分配更多子代生成機會。

四、算法流程

1. 初始化：隨機生成主種群POP1和輔助種群POP2，初始化存檔Archive。
2. 第一階段（約束優先級確定）：
   • POP1使用CDP處理所有約束，POP2忽略約束搜索UPF；
   • 當POP2收斂到UPF時，計算各約束可行率，生成約束分組。
3. 第二階段（動態約束與資源分配）：
   • POP2按分組逐步加入約束，每次處理${\text{Group}}_k$時，若收斂則切換到${\text{Group}}_{k+1}$；
   • 基于DRAS動態調整POP1和POP2的子代數量，例如$\text{Off1}={\text{ROS}}_1\times NP/2$，$\text{Off2}={\text{ROS}}_2\times NP/2$；
   • 存檔Archive保存優秀不可行解，用于輔助種群重新初始化。

五、關鍵公式總結

模塊	公式	作用
約束違反度	$CV(\mathbf{x})={\sum }_{j=1}^{q}C{V}_j(\mathbf{x})$	衡量解的約束滿足程度
可行率	$\text{Feasible?Rate}(j)=\frac{\text{滿足約束}j\text{的解數}}{NP}$	評估約束難度，確定優先級
子生成功率	$\text{Success\_rate}=\frac{\text{存活子代}}{\text{生成子代}}$	衡量種群搜索效率
資源分配系數	${\text{ROS}}_i=\frac{{\text{Success\_rate}}_i}{{\text{Success\_rate}}_1+{\text{Success\_rate}}_2}$	動態調整計算資源分配

六、實驗驗證與優勢

通過MW、LIRCMOP、DASCMOP三大測試集驗證，DPCPRA在可行率（RFS）、逆世代距離（IGD）、超體積（HV）等指標上優于主流算法（如CTAEA、CCMO）。核心優勢：

1. 雙種群協作：主種群保證可行性，輔助種群挖掘不可行解價值，平衡收斂與多樣性；
2. 動態機制：DCPM逐步釋放約束復雜度，DRAS按需分配資源，適應不同問題結構；
3. 泛化能力：在高維、多約束場景下表現優異，適用于工程優化等實際問題。

七、總結與引用

本文提出的DPCPRA通過雙種群架構、動態約束處理和資源分配，有效解決了CMOPs中約束與目標的平衡問題。實驗表明，該算法在基準測試和實際問題中均表現出優越性能，為復雜約束優化提供了新思路。

引用文獻

Qiao K, Chen Z, Qu B, et al. A dual-population evolutionary algorithm based on dynamic constraint processing and resources allocation for constrained multi-objective optimization problems[J]. Expert Systems with Applications, 2024, 238: 121707.