多目标优化MOP这个方向如果只让我挑一个“真正经典”的遗传算法我会选SPEA2。全称Strength Pareto Evolutionary Algorithm 22001年提出至今仍然被当作多目标进化算法的标杆之一。很多人在做对比实验、工程选型、甚至复习面试题时都会碰到它但教材里动不动就是强度值、原始适应度、k近邻密度、档案截断第一次读确实劝退。这篇文章不绕弯子把SPEA2从设计动机到公式、主循环、参数推荐、再到实战里容易踩的坑一层层拆开讲。适合刚开始学多目标优化的人也适合已经跑过几个算法、但一直没搞明白“SPEA2和NSGA-II为什么长得像但行为不同”的人。1. 为什么SPEA2能在多目标优化里不可绕过1.1 早期进化多目标算法踩过的坑多目标进化算法早期最头疼的问题只有一个在多目标互相冲突的前提下怎么同时保证收敛性和多样性。1999年第一代SPEA提出用“强度”strength来衡量一个个体在目标空间里压制了多少个其他个体压制越多说明越强。这个想法自然但实际操作中很快暴露出两个问题。第一个问题如果一个个体不被任何其他个体支配按照原始SPEA的强度逻辑它的原始适应度R就是0。问题在于一个种群里的非支配个体通常是一大片它们之间谁都不支配谁算出来的R全是0。这一下选择压力就没了非支配个体之间没有高低之分进化方向失去引导。被支配的个体虽然R很大、会被淘汰但真正决定前沿质量的反而是这批R0的个体它们却全靠随机性在选择。第二个问题第一代SPEA用层次聚类维护档案聚类合并邻居个体时会丢掉细节边界解尤其容易在合并过程中被抹掉。这两个坑不是小问题它们直接限制了一个多目标算法能不能在真实工程里用。2001年SPEA2针对性地做了修正所以我一直觉得学习SPEA2的核心不是背公式而是理解它是怎么一项一项“填坑”的。1.2 SPEA2给出的三项核心改进SPEA2的改进可以归纳成三条每一条都针对上面说的具体问题。第一适应度赋值从单一强度改成“强度值 原始适应度 密度项”的组合。每个个体的最终适应度F由两部分组成原始适应度R代表被谁压制、压得有多狠密度项D代表它周围挤不挤。R把所有个体的支配关系都考虑进来D让那些互不支配的非支配解也有数值上的区别选择压力重新回到正轨。第二密度估计从聚类改成k近邻距离。具体做法是对每个个体找出它在目标空间里第k近的那个邻居用这个距离衡量个体是不是处在拥挤区域。这个方案比聚类细得多聚类是一批一批合并k近邻是一个一个算距离保留的多样性信息更完整。这里有个细节值得注意密度公式分母上那个“2”。很多人不解为什么要加一个2其实就两个目的一是防止距离为0时除零报错二是让密度项存在一个上界。按公式D(i) 1 / (σ_i^k 2)密度最大也只有0.5永远不会大到把支配关系带来的差异完全淹没。这个细节在实际实现时非常关键不加这个上界密度项可能反客为主。第三环境选择中的档案截断法从聚类改成“逐个删除最近邻距离最小的个体”。当非支配个体数量超过档案容量时不停去找当前集合里邻域最拥挤的个体删掉直到容量达标。这个方法可控性好每次删除都是可解释的并且能尽量保留分布稀疏的个体。可以说这三条改动后来成为许多多目标进化算法的共同遗产这也是SPEA2到现在还值得精读的原因。2. 主循环怎么跑适应度计算、环境选择与遗传算子2.1 适应度赋值强度、原始值、密度SPEA2的每一代主循环前半段都在做适应度赋值后半段做环境选择、配对选择和遗传运算。先看适应度赋值它是在“当前种群P_t 当前档案A_t”这个整体上进行的这一点很重要千万别只算种群不算档案。第一步算强度值S。对每个个体iS(i)等于当前P_t ∪ A_t当中被i支配的个体数量。强度值衡量的是这个个体“压制”了多少其他人。第二步算原始适应度R。R(i)等于所有支配i的个体的强度值S(j)之和。注意这里和第一代SPEA不同第一代SPEA把强度值除以了(N1)做归一化SPEA2直接求和不再做归一化因为后面加了密度项归一化反而会干扰两项之间的平衡。第三步算密度D。先取k √(N N̄)的整数部分其中N是种群大小、N̄是档案容量。对每个个体i找出它第k近的邻居距离σ_i^k然后密度就是D(i) 1 / (σ_i^k 2)。最终适应度是F(i) R(i) D(i)F越小越好。R为0意味着个体不被任何人支配也就是非支配个体它们完全靠密度项分高下被大量个体压制的个体R会非常大加上密度也翻不了身。这样选择压力既集中在非支配个体上又保留了少数被支配个体作为种群多样性储备不会让种群过早锁死在局部前沿。2.2 环境选择档案里的非支配解怎么留下适应度算完之后进入环境选择这一步决定下一代的档案A_{t1}是什么。逻辑分三种情况处理。第一种从P_t ∪ A_t里取出所有非支配个体放进档案。如果数量正好等于预设的档案规模N̄那一切好说。第二种如果非支配个体数量超过N̄就需要截断。截断采用我前面说的“逐个删除最近邻距离最小者”在档案中找第k近邻距离最小的个体删掉如果两个个体第k近邻距离一样就比较第k1近邻依此类推删完再检查是否还超直到档案大小等于N̄。第三种如果非支配个体数量不够N̄就从被支配个体里按F从小到大挑补足档案。这里我补充一个新手实现时非常容易搞错的地方所谓“最近邻距离最小”不是随便找两个点之间欧氏距离最小那么简单而是严格按k近邻序列逐位比较。论文里写得很明确先比第k近邻距离平局再比第k1近再平局继续往后比。如果把比较规则简化了截断结果会出现大量随机平局档案分布会不稳定。我自己早期实现时就吃过这个亏后来老老实实按这个规则重写分布质量立刻改善。2.3 配对选择与遗传算子档案确定之后配对选择在A_{t1}上进行。SPEA2用二元锦标赛选择每次随机挑两个档案个体比F值F小者胜出进入交配池。锦标赛规模取2是标准做法比较稳妥取3、4会增加选择压力但选择压力过大会让非支配个体中的少数极端点被反复选中多样性反而下降。我做实验时基本固定规模为2除非组里做高维目标研究需要在收敛上施加更强压力才会偶尔用3。交配池凑齐后遗传算子的用法和普通遗传算法完全一样。连续决策变量用模拟二进制交叉SBX和多项式变异离散或组合问题则换成均匀交叉、位翻转变异等。核心认知是多目标遗传算法的“多目标”部分全在适应度赋值和环境选择遗传算子本身并不感知目标数量。理解这一点你就能把任何单目标遗传算法快速改造成多目标版本只要替换掉选择机制和适应度函数就行。3. 手工演算4个个体如何被SPEA2淘汰3.1 手工演算的设定与支配关系公式堆多了容易飘我做一个能手工验算的小例子。考虑一个两目标最小化问题当前集合里只有4个个体先忽略档案假设就对这4个个体计算适应度。四个个体的目标值分别是a (1, 3)b (2, 2)c (3, 1)d (4, 4)先在目标空间里想一下位置a的f1最小但f2最大c的f1最大但f2最小b夹在中间d则整体偏向右上方。按最小化目标看a、b、c三者互不支配因为每个点都在某个目标上优于其他人、又在另一个目标上劣于其他人。而d (4, 4)f1和f2同时大于或等于a、b、c的对应值所以a、b、c都能支配d。这个关系很干净适合手动验算。3.2 强度值与原始适应度计算先算强度值SS(i)等于被i支配的个体数S(a) 1因为a支配dS(b) 1因为b支配dS(c) 1因为c支配dS(d) 0d没有支配任何人再算原始适应度R(i)R(i)等于所有支配i的个体强度之和R(a) 0没有个体支配aR(b) 0没有个体支配bR(c) 0没有个体支配cR(d) S(a) S(b) S(c) 3因为a、b、c都支配d到这里已经能看出来d因为R3在环境选择里肯定被优先淘汰。但a、b、c三者R都是0无法区分。如果SPEA2没有密度项这三者之间就没有选择压力只能靠随机性选择这就是第一代SPEA的核心缺陷在真实数据上的体现。3.3 密度项计算与最终适应度接着算密度项。取k2也就是看每个个体第二近邻的距离。两两欧氏距离如下d(a,b) √2 ≈ 1.414d(b,c) √2 ≈ 1.414d(a,c) √8 ≈ 2.828d(d,b) √8 ≈ 2.828d(d,a) √10 ≈ 3.162d(d,c) √10 ≈ 3.162找每个个体的第二近邻距离σ²对a最近是b距离1.414第二近是c距离2.828所以σ_a² 2.828对b最近是a或c距离都是1.414第二近也是1.414所以σ_b² 1.414对c最近是b距离1.414第二近是a距离2.828所以σ_c² 2.828对d最近是b距离2.828第二近是a或c距离3.162所以σ_d² 3.162密度D 1 / (σ² 2)最终适应度F R DF(a) 0 1/(2.8282) ≈ 0.207F(b) 0 1/(1.4142) ≈ 0.293F(c) 0 1/(2.8282) ≈ 0.207F(d) 3 1/(3.1622) ≈ 3.194结果非常直观d的适应度最高先被淘汰。如果这个例子还需要从a、b、c中再淘汰一个那么b因为处在a和c中间、邻居最密集σ_b²最小、密度项最大会被优先淘汰。这个手工演算说明了两件事支配关系提供主要筛选压力密度项负责在同等支配等级的个体之间做二次排序。这也解释了SPEA2为什么能在非支配解很多时依然保持选择压力。4. 参数怎么调ZDT/DTLZ测试下的实测推荐4.1 六个关键参数与推荐范围SPEA2需要设置的参数不复杂但每个参数影响都不小。我把自己做标准测试时的起始配置整理成一张表新问题可以直接拿这个当起点。参数推荐范围说明种群规模N100 ~ 200目标数增加时往大取档案规模N̄一般等于N太小会丢多样性锦标赛规模2不轻易加大SBX交叉概率0.8 ~ 0.9连续变量常用0.9SBX分布指数η_c15 ~ 20越大子代越接近父代多项式变异概率1/nn为决策变量数量变异分布指数η_m20 ~ 100越大扰动幅度越小密度近邻参数k√(NN̄)取整论文建议不必手调重点说一下SBX的η_c和多项式变异的η_m怎么理解。η_c大时模拟二进制交叉产生的子代更贴近父代局部开发能力强η_c小时子代扩散范围大探索能力强但过小会让算法像随机搜索。η_m同理η_m越大改动的幅度越小适合后期精细打磨η_m越小变异越猛适合前期跳出局部。连续问题我通常从η_c20、η_m20起步收敛速度不够再降η_m多样性不够再降η_c。这个顺序能帮你快速定位是哪个环节出了问题。4.2 测试函数和指标怎么看验证SPEA2效果最常用的是ZDT系列和DTLZ系列。ZDT1是凸前沿适合看基本收敛能力ZDT2是非凸前沿用来测试算法会不会卡在局部前沿ZDT3的前沿是不连续分段专门考察多样性保持能力。DTLZ1和DTLZ2可以把目标数推到5到10个用来观察算法在高维目标空间里的退化程度。我建议新手上手先跑ZDT1和ZDT3这两个一个测收敛一个测多样性基本就能看出算法实现有没有大问题。评价指标方面GD世代距离测收敛性IGD反世代距离同时测收敛性和多样性HV超体积测综合覆盖范围。这里有个经验教训IGD比GD敏感得多。GD只衡量你找到的那组解离真实前沿有多近哪怕你只找到前沿上很小的一段只要这段离前沿足够近GD就能很好看。IGD不一样它从真实前沿上均匀采样点再算这些点到你所求集合的距离如果覆盖缺失IGD立刻变差。所以SPEA2这种注重分布均匀性的算法看IGD才看得到真实水平。跑实验时每种参数至少独立跑10到20次结果取中位数不要只看均值避免个别极端运行污染结论。4.3 和NSGA-II怎么选SPEA2和NSGA-II是同一年代诞生的两个经典算法经常被拿来对比。下面这张表总结了两者的本质差别。对比维度SPEA2NSGA-II核心机制强度原始适应度密度非支配排序拥挤距离密度度量k近邻距离相邻个体长方体平均边长边界解处理靠k近邻距离自然形成边界解距离直接设为无穷大强制保留效率截断时要反复刷新距离较慢拥挤距离一次排序即可较快典型优势前沿分布更精细均匀收敛速度快、适用范围广从实际项目视角说如果目标数不多、且你特别在意前沿覆盖的细粒度SPEA2值得优先选。如果问题是大规模决策变量、又要求快速迭代NSGA-II通常更稳。还有一个不太被注意的点SPEA2的档案截断机制在每次删除个体后都要重新检查近邻关系计算开销明显高于NSGA-II的拥挤距离排序。我在一个决策变量50、种群200的多目标参数优化实验里SPEA2单代耗时差不多是同规模NSGA-II的两到三倍这个倍数会随档案规模上升继续放大。所以“选哪个”不是看谁更先进而是看你的评估代价和精度要求SPEA2拿时间换分布质量NSGA-II拿速度换一点精细度。5. 实战中容易踩的坑和排查过程5.1 常见现象对应表跑SPEA2时最容易遇到的现象、可能原因和排查手段我整理成速查表。现象可能原因排查手段档案每代都满大量截断档案规模N̄太小或者目标数太高打印每代非支配解数量按需调大N̄收敛很快但前沿覆盖窄探索能力不足SBX过强或变异过弱调低η_c、增大变异概率、降低η_m中间点频繁被删两端点偏多k近邻密度惩罚拥挤区域检查密度项权重或改用NSGA-II的拥挤距离每次运行结果波动极大种群规模太小或随机因素主导增大N多跑几次取中位数和四分位距目标数5以上效果急剧变差支配关系稀疏几乎所有解都非支配降低目标维度或换用指标基/分解类算法离散问题结果不合理连续算子不匹配离散编码换成均匀交叉和位翻转变异这些坑里中间点被删这件事比较微妙。SPEA2的密度项用k近邻距离判断拥挤度中间点往往周围都是邻居容易被当作冗余点删掉。这在某些均匀分布需求很强的问题上不是好事。如果你发现档案集中在两端、中间稀疏我会建议直接看看密度分布把每一代档案里每个个体的σ_i^k打出来你很快能定位是不是截断规则删过头了。这时候与其硬调参数不如换成NSGA-II的拥挤距离策略边界点有强制保留保护分布形态会更均衡。5.2 复杂度和大规模问题怎么办SPEA2的计算瓶颈始终是距离计算。适应度赋值阶段要对种群档案全体算两两距离档案截断阶段每次删除一个个体后剩余个体之间的近邻关系已经变了严格实现需要重新计算。这个复杂度在高维决策空间里会雪上加霜因为距离计算本身就变贵。我自己的处理思路有三层。第一层找问题本身是否允许降规模。决策变量太多时先做变量筛选把大量无关决策变量去掉比优化算法本身更管用。第二层限制档案规模。档案不是越大越好N̄保持在100左右通常能覆盖前沿的主要结构再往上加只是让后续距离计算更慢。第三层如果确实需要跑大档案规模就换用快速近似近邻方法比如用KD树做最近邻搜索虽然实现麻烦一点但能把每代距离计算从全量遍历降到近对数量级。这个优化在种群上千时效果非常明显。还有一个排查经验把截断过程可视化。每一代开始前画一下当前档案里所有个体的两两距离分布很快就能看出档案是不是重叠区域太多、种群是不是早熟。如果距离分布整体偏小说明种群已经高度聚集这时不是调密度项能解决的要回到遗传算子参数上增强探索。6. SPEA2的适用边界、扩展思路6.1 现在还在哪些场景用SPEA2SPEA2虽然是2001年的老算法但它到现在仍然是许多场景下的“默认选项”。学术实验里它是被拿来当baseline最频繁的算法之一和NSGA-II一样属于对比基准配置。工程领域里小规模组合优化、路径规划里的多目标权衡、连续参数自动调优都能看到SPEA2的身影。尤其是配合代理模型使用的场景SPEA2对每次评估都比较谨慎档案截断策略能保证有限的评估次数尽量花在多样的候选解上。我之前在某个资源调度项目里就是用SPEA2做候选方案生成外层接一个仿真打分效果比当时新潮的某些算法更稳定。不过要清醒一点目标数量一旦超过5个SPEA2会明显退化。这是因为高维目标空间里支配关系变得极其稀疏几乎两两都互不支配强度值和原始适应度的区分能力大幅下降最后起作用的只剩密度项算法容易退化成“均匀撒点”式搜索。这种场景下基于分解的MOEA/D类或基于指标的选择策略通常更合适。6.2 可以往哪些方向改进针对SPEA2的弱点业界做过不少有效扩展挑几个实用的方向说一说。一是结合代理模型。对昂贵仿真问题用Kriging或神经网络预测适应度SPEA2只对少数有潜力的候选解做真实评估能大幅降低总计算成本。二是自适应档案容量。SPEA2的N̄是固定参数但不同进化阶段非支配解数量差异很大动态调整N̄可以避免前期频繁截断、后期容量不足。三是局部搜索。在档案个体上做小步长局部扰动能加快收敛尤其适合连续光滑问题。四是改良密度度量。标准SPEA2只用目标空间距离如果决策变量之间存在强相关性可以改用决策空间和目标空间的加权组合距离。五是高维目标修正。把欧氏距离换成夹角距离或余弦相似度能缓解高维空间中“距离趋同”的问题。这些扩展不需要全部做选一个和你实际问题最匹配的切入即可。我自己这两年做实验时最常用的是代理模型和自适应档案这两个方向因为它们对工程算例的收益最明显改造成本又相对可控。最后说点个人体会。这几年做多目标优化实验我的习惯是SPEA2先跑一遍新算法再跑一遍最后用IGD和HV对答案。SPEA2不是最快、也不是各项指标都最亮眼的算法但它的每一步设计都极其“教科书”非常适合当教学载体。你把强度、密度、档案截断这些概念吃透了再回头看任何现代多目标进化算法基本都能快速理解它改动了哪个环节、解决了什么问题。如果你第一次上手别急着调参数先跑一个标准ZDT1看看档案里个体在目标空间的分布再改其中一个选项直观感受“这个改动影响了哪里”这比读十篇博客都管用。