进化算法求解复杂约束优化问题：技术谱系与工程实践指南

最近把软件学报2023年那篇《面向复杂约束优化问题的进化算法综述》从头到尾精读了一遍，感触很多。这篇论文的核心关键词是进化算法、约束优化、多约束优化，恰好是我这几年做算法优化时最常碰到的方向。论文的内容不浮于罗列文献，而是把约束优化问题的困难来源、进化算法中主流的约束处理技术、代表性算法以及实验验证方式都梳理得比较扎实，特别适合刚入门的研究生、需要快速了解约束优化技术栈的工程师，也适合准备在这个方向找研究点的博士低年级同学。我写下这些阅读笔记，一方面是逼自己把论文的结构和脉络消化清楚，另一方面也希望给正在读这篇综述的人提供一条更容易走通的阅读路径。

1. 论文定位与整体框架解读

1.1 为什么需要这样一篇综述

约束优化问题在现实中太常见了，工程结构设计、路径规划、生产调度、资源分配，几乎每一个有实际约束的决策场景都可以抽象成约束优化问题。传统精确算法在面对高维、非凸、非线性、约束条件耦合严重的问题时，往往会在计算时间或者内存占用上被拖垮，而进化算法因为不依赖梯度信息、天然具备全局搜索能力，在求解这类复杂问题时表现得相当灵活。软件学报选择在2023年发布这样一篇综述，说明这个方向的研究热度已经到了一个需要系统性梳理的阶段，新入行的人如果没有一张清晰的“地图”，很容易被各种算法名称搞得晕头转向。

这篇综述的价值在于，它不只是把已有的约束处理技术按时间顺序堆出来，而是把问题本身的困难来源、不同约束处理技术的适用条件、如何与不同进化算法框架集成这些关键问题放在同一个逻辑体系里讨论。我在阅读时最大的感受是，论文的叙述有明确的“技术视角”：不是每个算法都一笔带过，而是重点讲清它们是怎么处理“可行性与目标函数之间的矛盾”的。正因如此，这篇综述既适合作为课程论文阅读清单里的第一篇，也适合作为约束优化方向研究的索引。

1.2 论文的宏观组织结构

从结构上看，论文大体遵循“提出问题—分类方法—剖析集成—实验比较—展望挑战”的综述范式，但在细节上做了不少很有用的处理。开头先给出了约束优化问题的标准数学形式，然后顺着约束处理技术的发展脉络，把主流方法分成罚函数、可行性偏好、多目标转化、混合策略与协同进化等几大类，每一类都结合了近年来的代表性工作。后面又专门讨论了这些约束处理技术与遗传算法、差分进化、粒子群、进化策略等不同框架结合时会出现哪些问题，最后落在基准测试函数和评价指标上。

我的阅读建议是先看论文里的分类对比表，不要从头逐字读。把每一类方法的代表算法和优缺点弄清楚，再回到正文对应章节补充细节。这样效率会高很多，因为综述的正文往往包含大量引用，如果一边读一边查文献，很容易失去主线。于我而言，最需要细读的是“多目标转化”那一节，因为多约束优化场景下很多新算法都是从这里衍生出来的，后面我做了重点整理。

2. 约束优化问题的数学表达与难点拆解

2.1 约束优化问题的标准形式

论文里给出的标准形式并不复杂：最小化目标函数 f(x)，同时满足若干不等式约束 g_i(x) ≤ 0、等式约束 h_j(x) = 0，以及决策变量的上下界约束。决策变量的取值范围通常记作 Ω，整个搜索空间就是在 Ω 中寻找同时让目标函数尽量小、约束尽量满足的解。这里的“尽量满足”听起来很绕，但在数值优化里，等式约束因为存在浮点误差，很难真正做到严格等于零，所以绝大多数实现都会把等式约束转成不等式约束，比如 |h_j(x)| - ε ≤ 0，其中 ε 是一个很小的允许误差。

这个转换细节很关键，但很多初次接触约束优化的人往往会忽略。论文后面在讨论罚函数时也会提到这一点：如果一个算法直接对等式约束的违背量做惩罚，而违背量本身的量级很小，惩罚项就几乎没有作用。我在实际写代码时，习惯把等式约束的容差设为 1e-4 到 1e-6，具体看问题本身的物理单位。很多开源测试基准也提供了默认容差，可以直接沿用。

当约束条件不止一个，就进入所谓多约束优化的范畴。这里的“多”不只是数量上的多，更强调约束之间的相互作用：一个解可能让第一个约束满足，却严重违反第二个和第三个约束，而改进第二个约束又会导致目标函数值变差。这种冲突会使得可行域被切得很零碎，甚至可能只占整个搜索空间的极小比例，这也是复杂度上升的本质原因。

2.2 为什么复杂约束难处理：可行域、约束违背与多约束冲突

约束优化问题的难点可以从三个维度拆开来看。第一是可行域的结构，可行域可能是不连通的多块区域，最优解往往正好落在某一条约束边界上，甚至落在多条约束边界的交点上。进化算法基于种群搜索，如果初始种群完全没有落在可行域内，很多基于可行性比较的方法会分不清方向，退化成纯随机搜索。第二是约束违背度的计算问题，不同约束之间的量纲差异很大，比如一个是长度量级毫米，一个是重量量级吨，直接加起来会导致大尺度约束主导整个违背度，因此几乎都要先做归一化处理。第三是多约束之间的冲突，这在工程场景中尤其普遍，比如成本、时间、质量三个约束经常互相矛盾，满足一个容易，但同时满足全部约束且目标最优，就很难。

可能有人会觉得，既然约束优化这么难，为什么还一定要用进化算法？其实很多真实问题的目标函数和约束都是黑盒，没有解析形式，甚至需要仿真软件或者现场试验才能得到一个函数值，这个时候连梯度都算不出来，精确算法用不上。进化算法的优势在于每次只需比较若干个解的好坏，配合合适的约束处理机制，可以在相当有限的评价次数内逼近可行区域最优解。我在实践中会把“可行域占比”作为一个预判指标，如果可行域占比极低，单纯增加种群规模不如优化约束处理策略，这个认识也是读完综述之后才更明确的。

生活里有个很形象的类比：毕业生选城市落脚，既要工资水平高，又要生活成本低，还要通勤时间短。这三个约束本身互相拉扯，工资高的城市往往生活成本也高，很少存在一个“无脑最优”的选项。约束优化问题要做的，就是在这些互相冲突的条件中找出一个真实目标的相对最优解，进化算法则是通过一代代的“试错+选择”来逼近答案。

3. 进化算法处理约束的主流技术路线

3.1 罚函数法：最简单也最需要调参

罚函数法是很多初学者的第一站，也是综述里最先介绍的经典方法。它的核心思路是给目标函数加上一个惩罚项，惩罚项反映约束违背的程度，这样原来的约束优化问题就被转化成一个无约束优化问题。实现起来非常直接，把每个约束的违背量乘上一个罚因子，加进目标函数就行。我在第一次做约束优化实验的时候，最先写的就是这一版，代码量确实很少。

但罚函数法最大的坑是罚因子不好选。罚因子太小，种群会大量停留在不可行区域，因为目标函数优化会把解往不可行方向推；罚因子太大，又会把搜索空间压得特别窄，种群很容易过早收敛到边界上的局部区域。论文里提到了动态罚函数和自适应罚函数，我看完后的理解是，自适应的关键要结合当前种群中可行解的比例，如果可行解太少，就应该适当降低惩罚权重，保留一些不可行解来探测边界；如果可行解已经很多，再慢慢提高惩罚强度，把搜索引导回可行域内部。

这里有一个值得注意的实操细节：罚函数法对等式约束尤其敏感。因为等式约束的违背量通常很小，如果不经过合适缩放，乘上罚因子后还是几乎不产生效果。我的处理方法是先把所有约束违背量做归一化，让每个约束处于同一个数量级，再乘上一个基础罚因子。另外，如果目标函数本身数值范围很大，比如是1e5级别，而约束违背量归一化后在0到1之间，罚因子就需要对应放大；否则罚函数其实就是“形同虚设”。这个细节论文里着墨不多，但实验时非常容易踩坑。

3.2 可行解优先与约束支配

在整个综述里，我最常用也是推荐新手最先掌握的约束处理方式，是可行解优先原则。这个原则通常被称为约束支配比较，也叫Deb法则，规则只有三条：第一，两个可行解比较时，目标函数值好的胜出；第二，可行解永远优于不可行解；第三，两个不可行解比较时，约束违背度小的胜出。把这个规则写进进化算法的选择环节，就相当于在求解目标的同时加入了可行性偏好。

这个原则的优点是不需要设置罚因子，逻辑非常简单。在遗传算法里，只需要把比较函数改成约束支配判断，整条算法的主流程都不用动。不过它也有一个隐患：如果初始种群几乎没有可行解，那么所有个体都会被当作不可行解处理，比较压力完全集中在约束违背度上，这可能会丢失目标函数方向的引导。简单来说，算法变成了“先求可行，再求最优”，这个方向本身没问题，但纯靠约束违背度来选个体，容易让种群集中在某一个约束已经满足、其他约束还差一点的状态中。

我在实际项目中想要补救这个问题，通常会在约束支配比较的基础上引入一个小比例的不可行解保留机制，比如在每一代允许极少量的不可行解进入下一代，以保持群体探索边界的能力。论文里讨论的各种可行性保留策略，其实都是在与“多样性”做权衡，没有绝对最优，关键看当前搜索阶段。

3.3 多目标优化转化为约束处理

多约束优化问题在进化算法里还有一个非常巧妙的处理思路，那就是把约束本身变成优化目标。原本我们只有一个目标 f(x)，如果把所有约束的违背程度加起来作为一个新目标，那这个问题就变成了一个两目标优化问题：一个是原目标，一个是约束违背度。甚至可以把每个约束分别作为一个目标，变成多目标优化问题，然后用NSGA-II、MOEA/D这些经典多目标进化算法来求解。这种方式的好处很明显，既不用设置罚因子，也不会因为过于追求可行性而丧失对边界的探索。

论文在这部分花了不少篇幅，因为近年的先进方法很多都走这条路。两目标化之后，算法会保留一系列处于不同“目标—约束违背”权衡状态下的解，其中包括一些约束违背度很小但目标值也不错的不完全可行解。对于最优解位于可行域边界上的问题，这种保留特别有价值。但它的代价也很直接：目标数量增加后，非支配解的数量会显著增长，尤其在约束数量多的时候，每个约束都单独做目标容易导致选择压力分散。更实用的变体是把多个约束通过加权聚合为少数几个目标，或者利用偏好信息来引导非支配排序。

我读综述时特别注意到了一个点：多约束优化问题里，“约束全是硬约束”还是“一部分是软约束”会影响转化方式。如果有些约束可以放宽，那把约束目标化就能给决策者提供一组权衡解；如果所有约束都是硬性的，则还是需要在多目标解集里再附加可行性筛选。这一节的阅读价值在于，它打通了约束优化和多目标优化两个方向的连接，很多后续研究都在这里延伸。

3.4 混合策略与协同进化

单一约束处理方式各有短板，于是很多算法开始走混合路线。混合策略的含义比较宽泛：可以在同一个算法内同时使用罚函数和维护不可行解集，也可以在不同阶段切换不同约束处理方式。比如早期先用罚函数法让种群快速靠近可行区域，后期改用可行解优先原则精细搜索边界。也可以把约束违反度作为一种启发式信息，只在选择压力不足时加入。

更复杂一点的协同进化则从问题分解入手：把多个约束分成若干组，用多个子种群分别负责处理不同的约束子集，再通过一个协调机制交换信息。这样做的动机很直接——多约束优化问题中约束之间可能存在交互，如果一次性把所有约束都压在一个个体上，搜索难度太高；拆开之后，每个子种群只需要面对局部信息，更容易找到方向。不过协同进化的实现复杂度也明显上升，子种群的通讯频率、分组方式都需要额外设计，论文里一般会用专门的实验来说明在什么条件下协同进化优于整体处理。

我在自己的实验中体会是，混合策略往往比纯用某一种方法更稳，但是也更难调试。一个缺席了很久的教训是：并不是方法越多就越好，每多一个模块，就多一组参数，而参数之间的交互效应很难肉眼判断。因此，真正值得做的是把基础方法跑通，再逐步加入新的增强模块，每一步都对比一次效果，而不是一次性把所有新技术都堆上去。

4. 典型算法与代表性工作梳理

4.1 遗传算法与差分进化

遗传算法（GA）是进化计算里最经典的框架，在约束优化场景下，它一般承担的是“搜索骨架”的角色。选的约束处理方式不同，GA表现差异很大。早期工作多用罚函数，后来基于可行性比较的GA成为更常见的基线。GA的交叉变异算子对约束处理的成败也有很大影响，如果交叉后产生的子代完全违背变量范围，进化过程就会很浪费评价次数。我读论文时注意到，许多效果好的GA类算法都会在子代生成后加一个修复操作，把越界的变量拉回边界，再重新计算约束违背度，这是一个便宜但有效的小技巧。

差分进化（DE）则更适合连续实数优化问题。它的变异方式是基于种群中个体之间的差分向量，天然适应实数编码，因此在很多连续型约束优化基准上，DE比传统GA跑得更准。综述里会反复提到一个经典组合：ε约束法+差分进化。ε约束法本质上给“不可行解”设定一个动态阈值ε，在比较个体时，如果约束违背度小于ε，就视作可行解参与比较；随着代数增加，ε逐步减小，最终把搜索收紧到严格可行域。这种机制能显著保持种群多样性，同时避免罚函数法的调参问题。

我个人的实操建议是：如果问题变量是连续实数，直接选用差分进化+ε约束法作为第一个尝试方案，通常比直接上GA的结果更稳定。原因在于DE的差分变异对连续空间的探索效率更高，而ε约束法又不会过早丢弃不可行解，两者放在一起相当互补。当然，如果问题带有大量组合离散特征，GA依然有它自己的优势。

4.2 粒子群与进化策略

粒子群算法（PSO）在无约束连续优化里以快著称，但处理约束时有一个天生的毛病：粒子容易越过约束边界，并且在边界附近出现振荡。不少改进算法会在每次更新后检查粒子位置，如果越过边界就按某种规则反弹或拉回，同时保留其历史最佳位置中的边界信息。这种“边界修复+可行性比较”的组合在小规模问题上很好使，但在高维多约束问题上，单纯靠边界修复解决不了约束耦合的问题。

进化策略（ES）尤其是CMA-ES，在目标函数光滑且无约束时表现极其强劲，但基础ES并不知道约束的存在，因此需要外部挂一个约束处理层。最简单的做法是只允许可行解参与均值更新，但这在可行域占比极低时会导致算法几乎停止。综述里提到的思路是把约束处理作为适应度修正的一部分，但修正方式不能破坏CMA-ES的协方差估计。这个方向上手难度较高，我建议有数值优化基础再去尝试。

通观论文里这些典型算法会发现，没有一个算法是“约束处理万能药”。不同框架在变量结构、搜索偏好、种群多样性保持机制上的差异，会导致同一个约束处理技术移植后变化很大。所以在看综述时，我更愿意把精力放在理解“为什么某个算法框架适合某类约束结构”，而不是追求记住最多算法名。

4.3 多约束优化场景下的自适应机制

多约束优化之所以值得单独强调，是因为约束数量上来之后，静态的策略往往不够用。一个很直观的问题是：当约束有十个二十个，每个约束的重要程度不同，搜索阶段也各不相同，用同一个罚因子或者同一个可行性阈值去处理所有约束，显然是粗糙的。论文里专门梳理了自适应机制，核心思想是根据当前进化状态自动调整约束处理的强度。

常见的自适应机制包括三类：一是基于种群可行比例调整选择压力，比如可行解比例过低时降低可行性权重；二是动态调整ε阈值，让不可行解逐步退出择优范围；三是自适应调整罚因子，让惩罚强度随搜索进展变化。这些机制的实现不复杂，难点在于设计反馈信号。例如，如果当前种群的最优目标函数值变化很小，但可行比例还在增加，说明算法正在“补可行性”，这时候可以适当加快收敛压力。

我读完这一节的最大启发是，多约束优化的研究点不完全在于提出新的进化算子，而在于现有约束处理方法能否做到“随约束分布而变化”。很多最新的工作会把深度强化学习引入约束处理参数控制，让算法在运行过程中自己学习应该选择严格可行还是宽松探索。虽然这个方向还偏重工程验证，但确实值得跟踪。

5. 实验设计、基准函数与评价指标

5.1 常用基准测试函数（CEC系列等）

读综述时另一个需要留心的地方是实验设计。约束优化不比普通无约束优化，“能跑通”不代表“有效”，必须在统一的基准和统计口径下比较。目前最常用的约束优化基准多来自CEC系列测试集，比如CEC 2017、CEC 2020的约束优化问题，以及更早的CEC 2006。这些测试问题的设计刻意覆盖了多种困难特性：可行域占比极低、最优解位于边界、约束函数类型混合、决策变量维度不同等。

下面是我对照论文和相关资料整理出来的常见测试问题类型简表：

需要注意的是，基准函数只是一部分，最终还是要回到真实场景验证。不少论文只在基准函数上做实验，但实际工程里约束形式往往不可导、不可解析，甚至一次评估要消耗较长时间，这种差别会直接影响算法适用性。做对比实验时，除了列数值，还要观察算法在相同评价次数内的收敛曲线。

5.2 评价指标与统计比较

约束优化算法的评价通常不会只看“找到的最好解”这一个数，因为随机算法的单次运行有很强的不确定性。常见的指标包括多次运行的最优值、平均最优值、标准差、找到可行解的成功率，以及达到目标精度的评价次数。成功率这个指标特别关键，一个算法如果每次都能快速收敛到可行解的边界，但从不真正进入可行域，那它再快也没有意义。

统计比较方面，论文里通常会用Wilcoxon秩和检验或Friedman检验来证明不同算法之间的差异不是随机波动。做这类检验时，至少需要独立运行25到30次，统一最大评价次数和初始种群生成方式。我在复现论文实验时踩过一个坑：为了节省时间，只跑5次就做统计，结果方差太大，什么显著性都测不出来。后来学乖了，先用10次粗調参数，确认方向后再正式跑30次。

另有一个容易忽略的细节是，不同算法应享有相同的“公平条件”。种群大小、交叉变异概率、评价次数上限这些参数如果随意设置，会给人“田忌赛马”式的误导。综述本身不一定展开这些，但做研究时一定要在论文里交代清楚，否则实验结果的可信度会大打折扣。

6. 阅读心得、研究启发与实操建议

6.1 综述带给我的几个关键认识

系统读完整篇综述，我最强烈的感受是约束优化没有银弹。罚函数法简单但调参痛苦，可行解优先稳定但容易丢失边界探索，多目标转化理论优雅但计算代价高，混合策略能力强大但实现复杂。不同问题结构、不同评价预算、不同约束类型，都值得相应调整。以前我拿到一个约束优化问题就想直接套某个现成算法，现在我会先列一张问题特性表，比如可行域占比、约束类型、函数是否可导、维数大小，再去选匹配的技术路线。

第二个认识是不可行解不是垃圾，反而是宝贵的信息源。很多基于罚函数或可行解优先的算法之所以效果有限，是因为它们太早放弃了不可行解。实际上，不可行解的空间分布能够告诉我们约束边界在哪里，尤其是当可行域占比极低时，利用不可行解去“逼近边界”比盲目随机重启要聪明得多。这个理念在多目标转化和ε约束法中体现得淋漓尽致。

第三个认识是约束优化与多目标优化之间的界限越来越模糊。尝试把约束违背度当成目标，或者用非支配排序处理可行不可行解，本质上都是在利用多目标搜索的思路解决约束问题。这篇综述把这条演化脉络讲得很清楚，我甚至觉得它不只是约束优化的综述，也是进化计算整体研究趋势的一个缩影。

6.2 如果想做相关研究，该从哪里切入

如果读者是刚进入这个方向的研究生，我建议不要急着提出新算法，先把论文里提到的几类基础方法复现一遍。最简单的是在一个标准基准函数上实现遗传算法+约束支配比较，再实现差分进化+ε约束法，把两者的收敛曲线和成功率跑出来，边跑边理解参数的影响。这个过程通常只需要一两个星期，但能帮你建立起对约束处理机制的直觉。

如果已经有一些基础，可以聚焦在多约束优化场景下的自适应机制，例如约束数量较多且重要性不同的问题。尝试设计一种根据种群反馈动态调整约束处理策略的方法，并和固定策略的基线做对比。这类研究的可解释性强，也容易被审稿人理解。另一个值得探索的方向是把深度强化学习、图神经网络等工具用于约束关系建模，但要注意不能为了“蹭热点”而忽视问题本身。

最后分享一个我做文献笔记的小技巧：读这类综述时，我会做一个三列表格，第一列写方法名称，第二列写核心机制和关键参数，第三列写适用问题和局限性。等把综述全部读完，这个表格就是一份非常实用的速查手册，后续写论文或者做工程选型时，直接查表定位，比重新翻原文高效得多。

如果你和我一样，经常要处理带各种约束的实际优化问题，我强烈建议先把这篇综述的“分类框架”装进脑子里，再针对手里的具体问题去找对应类别的算法。毕竟比起记住某一个算法的代码，理解为什么这个方法适合这类型约束，才是真正能迁移的经验。