当前位置：首页 > news >正文

双种群进化算法：动态约束处理与资源分配解决约束多目标优化问题

news 来源：原创 2025/7/5 11:54:51

双种群进化算法：动态约束处理与资源分配解决约束多目标优化问题

一、引言

约束多目标优化问题（CMOPs）在工程设计、资源分配等领域广泛存在，其核心是在满足多个约束条件的同时优化多个目标函数。传统方法往往难以平衡约束满足与目标优化，导致搜索效率低或陷入局部最优。本文介绍一种基于动态约束处理和资源分配的双种群进化算法（DPCPRA），通过主辅种群协作与动态机制，有效提升求解性能。

二、CMOPs数学模型与挑战

CMOPs的标准形式为：
$\begin{cases} \min \mathbf{F}(\mathbf{x}) = (f_1(\mathbf{x}), f_2(\mathbf{x}), \dots, f_m(\mathbf{x})) \\ \text{s.t.} \quad \mathbf{x} \in \Omega \\ g_j(\mathbf{x}) \leq 0, \ j = 1, 2, \dots, p \\ h_j(\mathbf{x}) = 0, \ j = p+1, \dots, q \end{cases}$
其中， $\mathbf{x}$ 为决策变量， $g_j$ 和 $h_j$ 分别为不等式和等式约束。约束违反度定义为：
$CV_j(\mathbf{x}) = \begin{cases} \max\{0, g_j(\mathbf{x})\}, & \text{不等式约束} \\ \max\{0, |h_j(\mathbf{x})| - \delta\}, & \text{等式约束} \end{cases}$
总违反度 $CV(\mathbf{x}) = \sum_{j=1}^q CV_j(\mathbf{x})$ 。
CMOPs的难点在于：

可行区域可能狭小且分散，传统算法易漏解；
不可行解的利用不足，多样性维护困难；
计算资源分配不合理，导致搜索效率低下。

在这里插入图片描述

三、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）

根据种群搜索效率动态调整资源分配比例：

子生成功率：计算主/辅助种群子代的存活比例
$Success_rate 1 = ∣ Off1中存活个体 ∣ ∣ Off1 ∣ , Success_rate 2 = ∣ Off2中存活个体 ∣ ∣ Off2 ∣ \text{Success\_rate}_1 = \frac{|\text{Off1中存活个体}|}{|\text{Off1}|}, \quad \text{Success\_rate}_2 = \frac{|\text{Off2中存活个体}|}{|\text{Off2}|}$
资源分配系数：
$Success_rate 1 Success_rate 1 + Success_rate 2 , ROS 2 = 1 − ROS 1 \text{ROS}_1 = \frac{\text{Success\_rate}_1}{\text{Success\_rate}_1 + \text{Success\_rate}_2}, \quad \text{ROS}_2 = 1 - \text{ROS}_1$
效率高的种群（存活个体多）获得更多计算资源，例如辅助种群在探索复杂不可行区域时分配更多子代生成机会。

四、算法流程

初始化：随机生成主种群POP1和辅助种群POP2，初始化存档Archive。
第一阶段（约束优先级确定）：
- POP1使用CDP处理所有约束，POP2忽略约束搜索UPF；
- 当POP2收敛到UPF时，计算各约束可行率，生成约束分组。
第二阶段（动态约束与资源分配）：
- 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 CV_j(\mathbf{x})$	衡量解的约束满足程度
可行率	$\text{Feasible Rate}(j) = \frac{\text{满足约束}j\text{的解数}}{NP}$	评估约束难度，确定优先级
子生成功率	$Success_rate = 存活子代生成子代 \text{Success\_rate} = \frac{\text{存活子代}}{\text{生成子代}}$	衡量种群搜索效率
资源分配系数	$Success_rate i Success_rate 1 + Success_rate 2 \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）。核心优势：

双种群协作：主种群保证可行性，辅助种群挖掘不可行解价值，平衡收敛与多样性；
动态机制：DCPM逐步释放约束复杂度，DRAS按需分配资源，适应不同问题结构；
泛化能力：在高维、多约束场景下表现优异，适用于工程优化等实际问题。

在这里插入图片描述

七、总结与引用

本文提出的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.