解决约束多目标优化问题的新方法：MOEA/D-DAE算法深度解析
在工程优化、机器学习等众多领域，约束多目标优化问题（CMOPs）广泛存在。传统方法在处理这类问题时，常因可行区域不连通或约束违反局部极小点陷入停滞。近期，IEEE Transactions on Evolutionary Computation 上的一篇论文提出了一种新颖的解决方案——MOEA/D-DAE算法，通过结合检测-逃逸策略（DAE）和改进的ε-约束方法，有效突破了传统算法的局限。
一、CMOPs的核心挑战
1. 问题定义
CMOPs的数学模型可表示为：
{ min F ( x ) = ( f 1 ( x ) , … , f m ( x ) ) T s.t. g k ( x ) ≤ 0 , k = 1 , … , p h l ( x ) = 0 , l = 1 , … , q x ‾ i ≤ x i ≤ x ‾ i , i = 1 , … , n \begin{cases} \min F(x) = (f_1(x), \dots, f_m(x))^T \\ \text{s.t.} \quad g_k(x) \leq 0, \, k=1,\dots,p \\ h_l(x) = 0, \, l=1,\dots,q \\ \underline{x}_i \leq x_i \leq \overline{x}_i, \, i=1,\dots,n \end{cases} ⎩ ⎨ ⎧minF(x)=(f1(x),…,fm(x))Ts.t.gk(x)≤0,k=1,…,phl(x)=0,l=1,…,qxi≤xi≤xi,i=1,…,n
其中， F ( x ) F(x) F(x) 为目标向量， g k ( x ) g_k(x) gk(x) 和 h l ( x ) h_l(x) hl(x) 分别为不等式和等式约束， x x x 为决策变量。
2. 传统方法的困境
- 可行子区域不连通：约束可能将搜索空间分割为多个不连通的可行子区域，导致算法无法找到全局最优解。
- 约束违反局部极小点：约束违反度函数 C ( x ) = ∑ max { 0 , g k ( x ) } + ∑ ∣ h l ( x ) ∣ C(x) = \sum \max\{0, g_k(x)\} + \sum |h_l(x)| C(x)=∑max{0,gk(x)}+∑∣hl(x)∣ 存在多个非零极小点，使算法陷入不可行区域。
二、MOEA/D-DAE算法核心设计
1. 检测-逃逸策略（DAE）
-
停滞检测：
- 可行比率（ f r f_r fr）：当种群中可行解比例超过阈值 α \alpha α（如0.95），判断陷入局部可行区域。
- 约束违反变化率（ROC）：
ROC = ∣ C P − C P old ∣ C P \text{ROC} = \frac{|CP - CP_{\text{old}}|}{CP} ROC=CP∣CP−CPold∣
其中， C P = ∑ x ∈ P C ( x ) CP = \sum_{x \in P} C(x) CP=∑x∈PC(x) 为种群总约束违反度。若ROC低于阈值（如 1 0 − 5 10^{-5} 10−5），则判定陷入局部极小点。
-
逃逸机制：
- 权重调整：临时增大约束违反权重，引导搜索跳出当前区域。
- 临时存档：记录当前找到的可行解，为后续搜索提供初始种群。
2. 改进的ε-约束方法
-
动态调整ε：
ε ( t ) = { ( 1 − σ ) ε ( t − 1 ) , f r ≤ α ε max , otherwise \varepsilon(t) = \begin{cases} (1 - \sigma)\varepsilon(t-1), & f_r \leq \alpha \\ \varepsilon_{\text{max}}, & \text{otherwise} \end{cases} ε(t)={(1−σ)ε(t−1),εmax,fr≤αotherwise
其中， σ = max { f r , σ min } \sigma = \max\{f_r, \sigma_{\text{min}}\} σ=max{fr,σmin}，确保ε随可行解比例动态变化。 -
适应度计算：
fitness ( x ) = σ ⋅ g ( x ) + ( 1 − σ ) ⋅ C ( x ) \text{fitness}(x) = \sigma \cdot g(x) + (1 - \sigma) \cdot C(x) fitness(x)=σ⋅g(x)+(1−σ)⋅C(x)
平衡目标函数与约束违反的权重，增强种群多样性。
3. 状态转移机制
算法定义了三种状态：
- CHT0：初始状态，使用改进的ε-约束方法。
- DAE：检测到停滞时激活，执行逃逸策略。
- CHT1：DAE结束后进入，不再触发DAE。
状态转移条件基于 f r f_r fr 和 ROC，确保算法在收敛、多样性和可行性间动态平衡。
三、实验验证与性能分析
1. 实验设置
- 测试问题：涵盖LIRCMOP、CF、CTP、C-DTLZ等6类基准问题。
- 对比算法：NSGA-II-AP、CMOEA/D、MOEA/D-IEpsilon等5种先进算法。
- 性能指标：倒置世代距离（IGD）和超体积（HV）。
2. 关键结果
实验表明，MOEA/D-DAE在多数问题上显著优于对比算法，尤其在处理不连通可行区域和约束违反局部极小点时表现突出。
四、总结与展望
MOEA/D-DAE通过检测-逃逸策略和动态ε-约束方法，有效解决了CMOPs中的停滞问题。其创新点包括：
- 基于可行比率和ROC的双重停滞检测机制。
- 动态调整权重以平衡目标与约束。
- 状态转移机制确保搜索高效性。
未来，该算法可扩展至大规模CMOPs或多目标优化问题，进一步提升其普适性。
参考文献
[1] Zhu, Q., Zhang, Q., & Lin, Q. (2020). A Constrained Multiobjective Evolutionary Algorithm with Detect-and-Escape Strategy. IEEE Transactions on Evolutionary Computation, 24(5), 870-884. DOI: 10.1109/TEVC.2020.2981949.
