这篇是MOP系列里聊遗传算法的第六篇。前几篇把 NSGA-II、MOEA/D、IBEA 这些常见框架挨个拆过这次单独把 2015 年提出的 Two_Arch2 拎出来讲。为什么值得单独写一篇因为它是多目标进化算法里少有的、把“收敛”和“多样性”这两个天然互相拖后腿的目标从结构上拆开处理的算法思路非常直白但实现细节里的坑不少。如果你正在做高维多目标优化或者准备复现经典 MOEA 写论文、做工程落地我建议认真看看这篇。就算你不打算用 Two_Arch2它这种“双档案分工”的设计思路对理解后来的很多新算法也有帮助。开头先说结论Two_Arch2 并不复杂核心就是维护两个档案——一个管 Pareto 非支配关系一个管 Iε 指标贡献。两个档案各干各的交配时把两边的好基因各取一个父本生完孩子再分别送回两个档案更新。整体框架三句话能讲完但真正复现过的人都知道Iε 怎么算、PA 的多样性替换怎么做、两个档案初始化有什么讲究这些细节直接决定算法能不能打。这篇文章我会把从零实现 Two_Arch2 的完整过程、踩过的坑和调参经验都梳理一遍。1. 为什么需要 Two_Arch2高维目标下的选择压力危机1.1 经典 Pareto 支配在高维目标下为什么失效先说一个很多刚接触多目标优化的人容易忽略的现象目标数量一多Pareto 支配关系基本就“废”了。在二目标和三目标问题上两个个体同时支配和互不支配的概率还比较正常非支配排序能比较快地把好的个体筛出来。但目标维度到了 5 个、10 个、15 个之后情况完全不一样。你可以随手做个实验在 [0,1] 之间随机生成两组 10 维向量计算它们之间谁支配谁的概率。结果会告诉你绝大多数情况下两个随机解互不支配甚至一个解同时被好几个解支配的概率都非常低。生活化一点理解你想比较两个候选人谁更优秀标准只有“技术能力”和“沟通能力”时很容易分出高下但如果加上“抗压能力”“学习速度”“团队协作”“项目推进”……一共十几个维度你会发现几乎没人能在所有维度上同时碾压另一个人。这时候单纯靠“你是不是每科都比我强”来筛选筛选效率几乎为零。NSGA-II 这类基于 Pareto 支配的经典算法在高维目标下遇到的正是这个困境。非支配层的个体数量迅速膨胀选择压力消失种群演化基本退化成随机游走。我在实际复现里测过10 目标的 DTLZ 系列测试问题上NSGA-II 跑完一代代之后非支配解集几乎覆盖了半个目标空间IGD 指标根本压不下去。1.2 指标与分解两条绕道而行的思路既然直接比“谁支配谁”在高维下不好使研究者们就绕了两条路。一条是基于指标的思路代表作是 IBEA。它的想法很简单不直接用 Pareto 支配判断而是定义一个二元指标衡量“解 A 比解 B 好多少”。比如二进制 ε 指标如果 A 在某个 ε 容忍度下能“近似支配”B就给分。这样一来即使 A 和 B 互不支配也能算出谁更接近理想前沿。指标的优点是选择压力恢复得非常快缺点是计算复杂度高而且指标很容易被某个量纲特别大的目标带偏。另一条是基于分解的思路代表作是 MOEA/D。它把多目标问题拆成一系列单目标子问题用聚合函数加权和、切比雪夫等把每个解映射到一个标量值。这样每个子问题内部的选择压力依然有效。MOEA/D 的麻烦在于对目标空间形状比较敏感PF 形状一旦不规整固定权重向量的分布就容易偏离真实前沿。这两条路其实都是在解决同一个问题Pareto 支配在高维下提供不了足够的收敛信号必须引入别的信息来源。而 Two_Arch2 的思路更“奢侈”一些——它不选边站而是同时开两条生产线。1.3 Two_Arch 到 Two_Arch2双档案思路的进化双档案算法不是 Two_Arch2 首创的。更早的 Two_Arch 算法就提出维护两个档案一个侧重收敛一个侧重多样性。但初版 Two_Arch 的收敛档案是拿一个固定的标量化目标去评估的这在很多测试问题上表现不够稳定而且两个档案之间的配合也比较机械。Two_Arch2 的改进可以概括成两点第一把收敛档案彻底替换成基于 Iε 指标的“指标档案”让收敛压力不再依赖具体的聚合函数形状第二把两个档案的职责定义得更清晰一个档案通过 Pareto 支配关系加多样性维护来保证前沿分布均匀另一个档案通过 Iε 贡献来保证种群始终有一批在“逼近前沿”方向上最领先的解。两者互补不重叠。这种“分工”思路从进化算法整体发展脉络来看正好处在 NSGA-II 这类纯支配算法和后来 NSGA-III 这类参考点引导算法之间属于指标与支配混合路线里面比较有代表性的一支。理解了它再看后续很多“双种群”“双档案”变体基本都能一眼抓住骨架。2. Two_Arch2 的核心框架与关键机制2.1 两个档案: PA 与 IA 的分工Two_Arch2 里两个档案分别是PAPareto Archive和IAIndicator Archive。PA 的职责是维护一组基于 Pareto 支配关系筛选、同时兼顾多样性的非支配解。它本质上有点像一个带容量上限的“精英非支配解池”。新个体进入 PA 时先判断它和 PA 里已有解的支配关系如果新个体被 PA 里任何解支配直接拒绝如果新个体支配了 PA 里的某些解就把被支配的删掉再加入新个体如果互不支配且 PA 没满直接加入如果 PA 满了就要用多样性规则决定是替换还是拒绝。IA 的职责则是维护一组在指标意义上收敛性最好的解。它不看 Pareto 支配关系而是用 Iε 指标的“贡献度”来判断每个解的价值。一个解对 IA 的贡献可以理解为如果把它从档案里删掉剩余档案要付出多大的 ε 代价才能重新覆盖它。贡献越大的解越不可替代越小的越冗余淘汰时就优先删冗余的。把两个档案放一起看就形成了互补PA 保证了输出的解集在目标空间里铺得开、分布均匀IA 保证了种群始终有一批收敛得特别尖的个体不至于因为过度追求多样性而拖慢逼近前沿的速度。档案判断依据主要目标潜在弱点PAPareto 支配 最近邻距离 / 夹角前沿分布均匀、覆盖完整高维下支配信号弱收敛压力不足IAIε 个体贡献收敛速度快、精英集中容易在少数区域聚集多样性丢失2.2 交配选择: 为什么要“一边取一个父本”Two_Arch2 在交配选择和绝大多数 MOEA 都不一样。传统算法是在整个种群或某个交配池里选两个父本而 Two_Arch2 是从 PA 里选一个父本再从 IA 里选一个父本然后让这两个父本去做模拟二进制交叉和多项式变异。为什么要这么设计因为 PA 和 IA 各自代表一种选择压力下的幸存者。PA 里的解是“四面开花、覆盖面广”的代表IA 里的解是“单点突破、收敛很深”的代表。让这两种不同类型的父本配对后代的基因空间会更大既可能继承 PA 的多样性也可能继承 IA 的收敛性更有机会同时兼顾两个目标。我在实现时PA 父本用基于最近邻距离或夹角的锦标赛选择优先选周围稀疏区域的解IA 父本用基于 Iε 贡献的锦标赛选择优先选贡献高、不可替代的解。要注意的是两个档案的锦标赛压力都不能拉太满。如果压力太大每次父本都是各自档案里的“第一名”后代多样性反而会下降因为遗传算子的探索能力扛不住这么强的选择压力。2.3 档案更新规则与替换逻辑先看 PA 的更新逻辑我用伪代码写一下def update_PA(c): # 1. 如果 c 被 PA 中任意解支配直接拒绝 if any(is_dominated(c, x) for x in PA): return # 2. 如果 c 支配 PA 中某些解删除被支配者加入 c dominated [x for x in PA if is_dominated(x, c)] if dominated: PA.remove(dominated) PA.add(c) return # 3. 如果 PA 未满直接加入 if len(PA) N: PA.add(c) return # 4. PA 已满且互不支配用多样性规则决定替换 # 计算每个解的最近邻距离或最小夹角淘汰最拥挤的那个 worst_idx argmin(nearest_neighbor_distance(PA)) if nearest_neighbor_distance(c) nearest_neighbor_distance(PA[worst_idx]): PA[worst_idx] c这段逻辑里最容易出问题的就是第 4 步。只比较“最近邻距离”有时候不够稳健因为两个都挤在同一区域的解距离差不多替换谁差别不大。我实际用的方式是综合考虑最近邻距离和相对夹角先看距离距离相近就比角度角度更小的说明方向更重合优先淘汰。相当于让 PA 里的点在目标空间尽量“等夹角”分布。再看 IA 的更新逻辑def update_IA(c): candidates IA [c] if len(candidates) N: IA.append(c) return # 计算每个候选解被移除时的贡献损失 # 贡献 剩余档案对它的 Iε 覆盖成本 contributions [] for i in range(len(candidates)): rest [candidates[j] for j in range(len(candidates)) if j ! i] contrib iepsilon(rest, [candidates[i]]) contributions.append(contrib) remove_idx argmin(contributions) if remove_idx len(IA): # 新解的贡献最低说明它最冗余 return IA[remove_idx] cIA 里的“贡献低”本质上说明这个解很容易被其他解替代它对档案的额外价值很小。这个思路和 IBEA 里的指标选择很像但 Two_Arch2 把它收敛到一个个体贡献层面计算量更小语义也更直接。3. 手把手复现 Two_Arch2 的工程细节3.1 测试函数与评价指标的选择复现 MOEA 算法第一步不是写代码而是把测试环境定下来。我用的是 ZDT、DTLZ、WFG 这三类问题分别覆盖不同 PF 形状和不同目标规模。ZDT 系列适合调试二维情况DTLZ 系列能方便地扩展到 5、10、15 目标WFG 系列偏工程化场景变量之间有关联能检验算法在非独立变量问题上的表现。评价指标我固定用 IGD 和 HV两个一起看。IGD 需要先知道真实 PF 的采样点把算法求得的解集和真实 PF 之间的距离算出来它综合反映收敛性和分布性HV 则是不需要真实 PF 的指标算的是解集在目标空间里覆盖参考点的体积但参考点的选择对结果影响很大。只报 IGD 或者只报 HV 都容易被带偏两个一起用相互印证才可靠。参数设置方面我复现时用的是一组比较常见的配置参数取值说明档案容量 N100PA 和 IA 各 100总个体数 200最大评估次数30000按问题难度调整交叉算子SBXη20概率 1.0模拟二进制交叉变异算子PMη20概率 1/n多项式变异n 是决策变量数交配锦标赛压力2两个档案分别做二元锦标赛这里“档案容量 100”不是随便拍的。容量太小多样性铺不开容量太大IA 的 Iε 计算成本按个体对数量级上涨。100 在两三目标到 15 目标的问题上都是比较平衡的选择。3.2 Iε 指标的计算与数值处理Iε 是 Two_Arch2 最核心的数学工具它衡量的是“解 A 要在多大 ε 容忍度下才能覆盖解 B”。对于最小化问题一对解 A、B 的 Iε 可以这样算def iepsilon_pair(a, b): # a epsilon-dominates b 所需的最小 epsilon return max(a[i] - b[i] for i in range(len(a)))这里值越负越好。如果所有目标上 a 都优于 bmax 是负的说明 a 直接支配 b 不需要任何容忍度如果有些目标 a 比 b 差最大值就是正的这个正值就是覆盖 B 需要的 ε 代价。计算一个解对档案的贡献时我用的是“移除它之后剩余档案重新覆盖它需要的 Iε 成本”def iepsilon_contribution(candidates, idx): x candidates[idx] rest [candidates[j] for j in range(len(candidates)) if j ! idx] return min(iepsilon_pair(a, x) for a in rest)这个公式解释起来很直观档案里其他解要多大“容忍度”才能顶替这个解容忍度越大说明它越不可替代贡献越高。数值处理上有个大坑目标函数的量纲不一致时Iε 会被大尺度目标主导。比如第一个目标取值范围是 [0, 10000]第二个目标只有 [0, 1]那么 max 基本只看第一个目标第二目标的选择信息全部丢失。我在实现里加了归一化步骤先把每个目标按当前种群的最小值和最大值缩放到同一量级再算 Iε。注意归一化的上下界要随代数更新否则早期一个离群点会把整个分布拉变形。3.3 主循环代码骨架下面是我复现时用的一个简化版主干结构去掉了具体测试函数适配保留核心流程import numpy as np class TwoArch2: def __init__(self, N100, max_eval30000, n_objNone, n_varNone): self.N N self.max_eval max_eval self.n_obj n_obj self.n_var n_var self.eval_count 0 self.PA [] self.IA [] def run(self): # 初始化种群 P [self.random_individual() for _ in range(self.N)] self.evaluate_all(P) self.init_archives(P) while self.eval_count self.max_eval: p_pa self.tournament_PA() p_ia self.tournament_IA() c self.variation(p_pa, p_ia) self.evaluate(c) self.update_PA(c) self.update_IA(c) return self.output() def init_archives(self, P): # PA: 用非支配层填充 # IA: 用 Iε 贡献填充贡献不足则复制高贡献解补满 raise NotImplementedError def tournament_PA(self): # 基于 PA 解在目标空间中的稀疏程度做锦标赛 return self.PA[self.tournament(np.array([self.diversity_score(x) for x in self.PA]))] def tournament_IA(self): # 基于 IA 解的 Iε 贡献做锦标赛 return self.IA[self.tournament(np.array([self.contribution_score(x) for x in self.IA]))] def variation(self, p1, p2): # SBX PM返回新个体 raise NotImplementedError骨架本身不复杂真正的复杂度都在update_PA和update_IA里。我的建议是先写一个完全可读的朴素版本把逻辑跑通、指标能出数再去做向量化和性能优化。不要一开始就追求矩阵化否则 bug 会埋得很深。3.4 从伪代码到工程级的性能优化朴素版本跑 10 目标 DTLZ2、30000 次评估速度还是有点慢的主要瓶颈在 IA 更新时反复计算 Iε 贡献。这里有几个工程优化手段比较有效第一个是增量计算。每次只有一个新个体进来完全没必要把整组候选解的贡献全部重算。可以把 IA 里每个解的贡献先缓存下来新来一个 c 的时候只计算与 c 相关的 Iε 贡献更新。如果 c 被淘汰其他解的贡献变化很小可以定期全量重算一次校准缓存。第二个是对称性复用。Iε 是反向不对称的但很多中间计算可以复用。对同一对解iepsilon_pair(a, b)和iepsilon_pair(b, a)分别只算一次存到矩阵里后续所有贡献计算直接查表。第三个是提前剪枝。IA 更新时如果新个体 c 在被加入前就已经确定被支配了可以直接跳过贡献计算。具体做法是先看 c 的 Iε 对 IA 现有解集是否有正向改进没有的话大概率淘汰。优化时注意一个原则优化不能改变算法语义。缓存贡献值的时候必须在归档发生实际替换后把影响到的依赖项失效否则指标算出来是错的后面所有分析都白搭。4. 复现过程中的坑与调参经验4.1 初始化两个档案的方式直接决定算法上限这是我刚开始复现时踩得最深的一个坑。最开始图省事把初始种群同时复制到 PA 和 IA 里结果跑了没几十代两个档案的同质化非常严重交配选择的“跨族配种”优势完全体现不出来。后来我把初始化改成PA 用初始种群的非支配层填充如果非支配解数量超过 N就用多样性规则裁剪IA 则先算每个个体的 Iε 贡献优先填贡献最高的解数量不足时用高贡献解补满。这样两个档案一开始就代表了不同的选择方向后续演化的互补性才出得来。4.2 交配选择的平衡感: 别让 IA 吞掉整个种群双档案算法最怕的事是一段时间之后其中一个档案在交配中占绝对主导另一个档案被边缘化。IA 里的解收敛性通常更好在锦标赛里容易脱颖而出如果交配时两父本都从 IA 里选种群多样性会迅速崩掉最后解集全部挤在一个目标附近。我的做法是给两个档案的父本选择加一个动态比例控制。比如前 3000 次评估里70% 的父本从 PA 选、30% 从 IA 选中期两者对半后期再让 IA 比例高一些。这样做是因为早期需要 PA 把前沿的骨架撑开后期需要 IA 把前沿边缘往里压。这个比例是我在自己测试集上调出来的换问题后最优比例会变但“早期保多样性、后期保收敛”的方向是普适的。4.3 目标缩放是隐性超参前面提过 Iε 对目标量纲敏感这里再补充一点归一化的方式本身就是超参。用当前种群的最小最大值归一化对离群点非常敏感用固定参考点和理想点归一化又需要事先对 PF 范围有合理估计。我在 DTLZ 系列测试集上用的方案是用每一代的目标最小值作为理想点用理想点加上 0.1 倍当前目标范围作为归一化参考。这样既不会让极端点主导归一化又能跟随种群演化动态调整。实测下来比固定参考点稳健不少尤其在 WFG 这种带偏差的问题上改善特别明显。4.4 算法停滞的观察与判断复现过程中除了看最终指标我还会实时观察两个指标的变化来判断算法是不是“假死”一个指标是PA 的最小夹角。如果 PA 里最近邻两个解之间的夹角越来越小、而且持续不变说明多样性维护基本失效解都堆在一起了。这时候应该检查多样性替换逻辑而不是盲目调参数。另一个指标是IA 贡献值总和。如果 IA 里所有解的贡献总和不断下降说明种群正在趋同可替代的解越来越多。单看这个很正常但如果在早期就掉得特别快说明收敛压力太大需要压低 IA 的锦标赛压力或提高变异强度。我踩过的一个典型案例是10 目标 DTLZ2 上IGD 曲线看起来一直下降但 HV 突然回弹。查了半天发现是参考点设置有问题导致 HV 在某个阶段会惩罚“过于集中”的解集。这说明只看单一指标做算法诊断是不够的必须交叉验证。5. 常见问题速查表问题可能原因处理办法PA 一直满但不更新多样性替换条件太苛刻新解永远不满足替换条件降低替换门槛加入角度二次比较检查最近邻距离计算是否用了原始目标空间IA 里的解全部集中到极端目标附近Iε 贡献被量纲大的目标主导先做目标归一化检查参考点和理想点更新逻辑两个档案同质化严重初始化时直接复制了同一个种群按 4.1 的方式分开初始化检查交配父本是否真的一个来自 PA、一个来自 IA算法前期收敛很好后期多样性崩坏后期 IA 的收敛压力过强占用了过多交配资源给 PA 父本选择更高的权重适当增大变异强度 η运行时间过长评估次数相同但耗时翻倍IA 贡献计算每次重复全量计算增量更新 查表 缓存失效机制IGD 下降但 HV 回弹参考点设置不合理或者解集分布偏向单边更换参考点取值或改用归一化 HV 后再判断除了表格这些再补充一个非常有用的调试技巧可视化中间态。跑 100 代、500 代、1000 代时分别把 PA 的解集用二维投影画出来比如用 PCA 把高维目标降到二维。你会发现 Two_Arch2 前期 PA 的投影非常散IA 的投影集中在某个角上中期两者开始靠拢后期交合。如果这个“靠拢过程”没有发生说明两个档案的协作逻辑有问题不用等跑完就能判断。我自己复现时还有一个体会不要一上来就对着论文里的数学公式抠细节。Two_Arch2 这类算法的论文写得很抽象符号体系各家不一样但核心机制非常清晰。我建议先画出两个档案的更新流程图把“什么条件下加入”“什么条件下替换”“什么条件下拒绝”三种情况写在纸上再对着流程图写伪代码最后再落到 Python。这样逻辑不容易乱调参时也知道该动哪里。最后再分享一个可以扩展的方向Two_Arch2 的双档案思路非常适合移植到带约束的多目标问题上。一个档案管约束满足一个档案管指标优化天然就是两条生产线。我之前试过一个定制版本把 PA 换成“约束支配优先”的档案IA 依旧用 Iε 收敛在几个工程约束问题上效果比单独用约束支配要好不少。如果你正在做调度、路径规划、参数寻优这类实际应用不妨沿着这个思路试试。这篇先到这里。下一部分如果有时间我会继续拆解 Two_Arch2 后面出现的那些双档案改进版本看看“双档案”这个思路是怎么一步步演化成更复杂框架的。