《Rapidly Handling Constrained Multi-objective Optimization Problems with Hypervolume Gradient Subspace Approximation》Kenneth M. Zhang, Angel E. Rodriguez-Fernandez, Ke Shang,Senior Member, IEEE, Hisao Ishibuchi,Fellow, IEEE, and Oliver Sch¨utze提出了一种处理带约束的连续多目标优化问题CMOPs的新方法。核心思想是结合基于集合的超体积梯度子空间近似HVGSA与多目标进化算法MOEA形成一个混合框架HVGSA-MOEA。摘要本文提出了一种新颖的混合方法用于数值求解带约束的连续多目标优化问题CMOPs。第一步我们提出了基于集合的局部搜索引擎 HVGSA旨在改进超体积HV指标。该算子的独特之处在于其搜索方向可以在不显式使用梯度信息、也不需要额外目标函数或 HV 评估的情况下计算得出尽管需要求解一个特定的线性方程组。相反它利用现有的邻域信息在由此产生的一组方向所张成的空间中近似出最贪婪的搜索方向。作为副产品沿该方向的方向导数也可以被近似从而支持自适应步长控制的使用。HVGSA 能够处理等式和不等式约束并且原则上可应用于具有任意数量目标的 MOPs。第二步我们提出了HVGSA-MOEA这是一个将 (μμ) 多目标进化算法MOEAs与新的搜索引擎相结合的框架。HVGSA 既可以应用于整个种群也可以应用于特定的子集精英个体以降低计算负担。最后我们在真实世界基准问题上验证了 HVGSA 作为独立算法以及 HVGSA-MOEA 的优势。结果表明这种新颖的混合方法与当前最先进的方法相比极具竞争力。1. 快速浏览一遍文章的时候摘要结构清晰但是不清楚看懂字但是没理解也不知道没理解什么就是“再说什么”2. 什么是超体积HV指标3. ”搜索方向可以在不显式使用梯度信息、也不需要额外目标函数或 HV 评估的情况下计算得出“ 这句话是什么意思原有的搜索方向是怎么样确定的又有什么缺点不足之处呢4. (μμ) 多目标进化算法MOEAs是什么意思5. 新的搜索引擎是什么意思还有旧的搜索引擎吗搜索引擎在CMOPS中是一个必备的组件或者模块吗一、看不懂现实工程问题 → 抽象成数学问题 → 梳理前人已经做到哪、还有哪些坑没填 → 找到自己的切入缺口 → 设计算法 / 理论 → 实验验证 → 写论文发表。一开始我看不懂这篇文章因为缺少 “领域地图”不知道这个领域要解决什么现实痛点前人分别走了哪几条技术路线每条路线分别解决了什么、留下什么弊病。 论文作者是站在这张地图上写文章但我手里没有地图直接看他的 “新造的小工具HVGSA”就不知道这个工具放在地图的哪个位置不知道他为什么要造这个工具。于是乎可以借助 AI 梳理并提问了解背景相关知识帮你把这个地图构建出来。大领域进化计算Evolutionary Computation, EC→ 多目标优化Multi-objective Optimization, MOP→ 约束多目标优化Constrained Multi-objective Optimization, CMOP基于超体积Hypervolume, HV指标的进化算法与局部搜索Local Search相结合的模因算法Memetic Algorithm分支细分方向约束多目标优化CMOP中的基于指标Indicator-based的进化算法特别是以超体积HV作为选择或搜索准则的方法。该方向面临的核心难题HV 梯度计算成本极高超体积是评价解集质量最优秀的指标之一但它的梯度即如何调整整个种群以最大化 HV计算或近似非常昂贵。直接计算 HV 梯度需要大量的函数评估FEs和 HV 评估这在现实世界优化问题如 RCM 基准测试中往往是不可接受的。约束处理与可行域狭窄约束多目标问题中可行域可能非常狭窄、不连通甚至在早期种群中完全不可行。传统的约束处理技术如约束支配原则 CDP容易导致种群陷入局部可行域丢失对全局 Pareto 前沿的探索。局部搜索与全局进化的平衡将数学规划中的局部搜索如梯度下降与进化算法EA结合即模因算法可以加速收敛但局部搜索通常需要梯度信息且很难处理约束容易在不可行区域“卡住”。关于 HV 相关 的问题研究 可以看下面这篇综述会更有总体观更加清晰K. Shang, H. Ishibuchi, L. He and L. M. Pang, A Survey on the Hypervolume Indicator in Evolutionary Multiobjective Optimization, inIEEE Transactions on Evolutionary Computation, vol. 25, no. 1, pp. 1-20, Feb. 2021, doi: 10.1109/TEVC.2020.3013290.这篇文章对超体积Hypervolume, HV指标的相关研究进行了系统性的梳理文章围绕HV指标的以下五个核心主题展开超体积计算Hypervolume Calculation探讨如何精确且高效地计算该指标。这在多维目标空间下是公认的难题因为计算成本会随维度增长而急剧增加。最优μ-分布Optimal μ-Distribution研究在真实帕累托前沿上为使HV最大化一组固定数量μ个的解在理论上的最优分布形态。超体积子集选择Hypervolume Subset Selection, HSSP即“从大量候选中挑出最优子集”的问题。这是基于HV的算法在每一代进行环境选择时必需面对的挑战。基于超体积的EMOAs调查那些将HV指标直接嵌入搜索过程用其引导种群进化的算法设计与应用。超体积指标的扩展Extensions讨论HV的各种变体这些变体旨在克服原始HV在某些场景下的局限如计算开销大、参考点敏感等。本篇笔记所提出的算法处于综述中“超体积计算”与“基于超体积的算法设计”的交汇点并特别针对“约束多目标优化”这一应用场景进行了“指标扩展”。它试图通过梯度子空间近似的方法解决传统超体积方法在约束多目标优化中计算慢、效率低的问题。研究目标设计算法用尽量少的计算代价输出高质量解集。论文第二章 Related Work 写的内容所有约束多目标进化算法基本归为 4 条路。1. 路线 A给普通 MOEA 套约束处理规则代表NSGA‑II‑CDPC‑MOEA/D 思路不改动进化算法主体加一套规则比较两个解的时候优先选可行解不可行解之间看谁约束违反更小。✅优点简单实现方便。❌痛点 如果可行域被巨大不可行区域包围种群很难穿越等式约束尤其难处理只靠交叉变异这种随机搜索在复杂地形收敛慢。2. 路线 B多阶段策略Push‑Pull、ToP‑NSGA‑II思路分阶段。第一阶段“推”暂时无视约束先找到无约束的帕累托前沿第二阶段“拉”再把解拽回可行域。✅优点可以找到一些别的算法找不到的可行解。❌痛点什么时候切换阶段没有普适标准调参困难。3. 路线 C多档案 / 多种群协同C‑TAEA、CMOEA‑CD思路维护好几个档案一部分专门探索不可行区域一部分专注可行域收敛互相交换个体。✅优点可以同时兼顾探索和可行性。❌痛点维护多个档案计算开销上涨逻辑复杂。4. 路线 DMemetic文化基因算法进化算法 局部搜索这就是本文作者站的赛道进化算法交叉变异 全局探索擅长大范围找区域但局部精细收敛弱局部搜索 精细打磨在小邻域内快速提升解质量。Memetic 两者混合。这里路线 D 内部又分裂出两个子方向这就是作者真正的切入点最关键D‑1对【单个解】做局部搜索绝大多数旧 memetic‑MOEA拿种群里面某一个个体 x对 x 做局部搜索把 x 打磨得更好放回种群。✅简单直观。❌痛点 局部搜索只优化一个点多目标要的是一整套解集。你单独把某一个解变好不代表整套解集的 HV 会提升。选哪个个体做局部搜索也是麻烦事。D‑2对【整套解集】做局部搜索新一代集合式局部搜索不再打磨单个解。把整个解集当成一个整体直接优化整套解集的指标( 比如 HV 超体积 )目标让这一堆解合起来的 HV 变大。已有的工作HVGAHV 梯度上升、HIGAMO、HV‑Newton。✅优点直接瞄准解集整体质量天然同时兼顾收敛 多样性。❌巨大痛点这就是本文作者看到的缺口 想要做集合局部搜索需要 HV 的梯度信息求梯度要大量额外的目标函数评估计算代价爆炸高。HVGA需要差分求梯度每一步要调用非常多次目标函数现实工程问题用不起。之前有个会议版本工作PPSN2024初代 HVGSA实现无约束场景下不用显式梯度做集合局部搜索但是不能处理约束只能绑定 SMS‑EMOA参数多。总结集合层面局部搜索效果好但求 HV 梯度代价太大现存无梯度版本 HVGSA会议版只能处理无约束优化现实工程几乎都是约束多目标问题有等式、不等式约束进化过程种群经常出现大量不可行个体没有一套通用的集合局部搜索可以不用显式 HV 梯度省函数评估支持等式 不等式约束允许输入不可行解集适配进化算法前期可以很方便嫁接给各种各样型 MOEA而不是绑定某一个特定算法。这就是作者想解决的 “研究缺口”整篇文章全部围绕这个缺口展开。下次读一篇论文先问自己 4 个问题现实场景这个研究对应工程上什么问题数学形式被抽象成了一个什么优化问题前人工作现在主流有几大类方法每一类优缺点是什么还有哪些没解决作者的切入点作者抓住哪一个痛点他想造出一个具备什么特性的新算法此外另一个思考方式就是作者是怎么样去切入一个领域的问题的如何去理解作者的思路是否可以扩展到其他问题上对未来工作研究可以有什么启发如果你是审稿人 你会如何去看待这一篇文章写文章其实也是在售卖自己的科研产品如何说服审稿人为什么会被说服也是值得思考的原因。二、 一些我自己不懂的概念1. 求解MOP的方法1 传统数学规划方法Classical Methods这是最早的方法通常将多目标问题转化为单目标问题来求解。权重法Weighted Sum Method给每个目标赋予一个权重加起来变成一个目标。缺点是无法找到凹的帕累托前沿部分。ε-约束法ε-Constraint Method保留一个主要目标把其他目标变成约束例如要求目标2必须小于某个值ε。标量化方法Scalarization如切比雪夫分解Tchebycheff。这类方法是很多现代算法如MOEA/D的基础。特点数学理论严谨但对于非凸、不连续、高维的问题往往无能为力且一次运行通常只能得到一个解。2进化算法Evolutionary Algorithms, EAs这是目前最主流的方法因为进化算法天生就是基于“种群”的一次运行可以找到一组解帕累托前沿的近似。代表算法NSGA-II基于非支配排序和拥挤度距离—— 最经典。SPEA2基于强度帕累托进化算法。MOEA/D基于分解的多目标进化算法—— 将多目标问题分解成多个单目标子问题同时求解。特点全局搜索能力强能处理非凸、不连续、甚至黑盒问题。缺点是计算量大收敛到精确前沿的速度较慢尤其在问题维度高时。3局部搜索方法Local Search Methods在多目标领域通常被称为基于数学规划的局部搜索或多目标局部搜索。原理从一个初始解出发利用梯度信息或近似梯度、单纯形法等沿着某个方向逐步移动寻找更优的解。代表方法多目标最速下降法、多目标牛顿法、以及文章里提到的HVGSA基于超体积梯度的子空间近似。特点收敛速度极快能精确找到局部帕累托前沿。缺点是极易陷入局部最优且严重依赖初始点的选择对目标函数的连续性/可导性有要求。4混合方法Hybrid Methods既然进化算法全局好但收敛慢局部搜索收敛快但全局差那把两者结合起来就成了自然的选择。策略用进化算法进行全局探索找到有潜力的区域然后在这些区域启动局部搜索进行精细开发加速收敛。代表Memetic Algorithms文化基因算法、以及论文提出的HVGSA-MOEA。特点兼顾全局和局部是目前解决复杂昂贵优化问题的主流方向。5其他前沿/特定方法群体智能算法Swarm Intelligence如多目标粒子群优化MOPSO、多目标蚁群算法。本质上是受自然界启发的随机搜索和进化算法类似。代理模型辅助优化Surrogate-Assisted Optimization当目标函数评估极其昂贵如一次仿真要几小时时用机器学习模型如高斯过程、神经网络来近似真实函数减少真实评估次数。偏好驱动优化Preference-based Optimization不找整个帕累托前沿而是只找决策者感兴趣的那一部分如参考点法、角度惩罚距离。所以作者聚焦在“进化算法局部搜索”混合方法而这两种方法存在着痛点痛点1随机算子的局限多目标进化算法MOEAs依赖“随机算子”比如变异、交叉当问题地形复杂时性能会下降。特别是等式约束equality constraint非常难搞因为它会把搜索空间维度降低导致很难找到可行解。痛点2局部搜索的局限与混合的困难传统的局部搜索Local Search擅长沿着解集移动但容易陷入局部最优。为了弥补研究者尝试把MOEAs和局部搜索结合起来混合算法。但问题是如何选择合适的“起始点”和“局部搜索策略”非常棘手这直接决定了最终解集的质量。2. 什么是“算子”Operator在进化算法中“算子”指的是模拟自然进化过程的操作规则。最典型的两个算子是交叉Crossover模拟生物交配把两个父代解的部分基因变量交换生成新的子代。变异Mutation模拟基因突变随机改变解中的某些变量以增加种群的多样性。为什么叫“随机”Stochastic因为这些算子的操作不是确定性的而是基于概率的。例如变异算子并不是说“把第3个变量增加0.5”而是说“以某个很小的概率 pmpm将第3个变量随机替换为搜索空间内的另一个值”。这意味着即使你给同样的父代运行两次算法生成的子代也可能完全不同。这就是“随机”的含义。“依赖随机算子”带来的问题虽然随机算子赋予了算法全局探索的能力不容易一开始就卡死但在处理复杂问题如带约束的多目标优化问题时它的缺点就暴露了盲目性/低效性随机算子像是一个“盲人摸象”。它不知道梯度方向也不知道约束边界在哪里。它只能通过大量随机尝试偶尔碰巧生成一个更好的解。等式约束的致命打击正如文中提到的等式约束如 x1x21会极大地缩小可行搜索空间降低维度。随机算子生成的点极大概率落在不可行区域。比如随机生成 x10.3,x20.4 加起来是0.7不满足等于1的约束这个解就废了。算法需要浪费大量的计算资源去“碰运气”找到一个可行解。收敛慢在复杂景观Landscape下随机算子无法像梯度下降那样沿着最陡峭的方向快速逼近最优解导致收敛速度变慢甚至找不到好的解。3. 超体积HV - Hypervolume指标在多目标优化中我们最终得到的不是单一的最优解而是一组互不支配的解比如车A便宜但马力小车B贵但马力大两辆车各有千秋无法说谁绝对比谁好。这就产生了一个问题怎么评价这一组解的好坏超体积HV就是目前学术界公认最好的评价指标之一。它的计算方法是先在目标空间里找一个“最差参考点”比如价格最贵且马力最小的那个点作为底线。把你找到的这一组解比如5款车画在图上。计算这组解与“最差参考点”之间围成的体积面积/空间。比喻理解假设价格和马力构成了一个二维平面。你选出的几款车在这个平面上形成了一条前沿曲线。HV 就是这条曲线向“最差参考点”方向扩展所覆盖的总面积。HV 越大说明你的解集既逼近了真实的最优前沿收敛性好又分布得很均匀多样性好。在本文中作者的目标就是通过算法让种群最终占据的 HV 体积最大化。4. 标量优化问题SOP - Scalar Optimization Problem一句话解释把“同时优化多个目标”的难题通过某种数学手段转化为“只优化一个数字”的简单问题。详细解释多目标问题MOP很难直接用数学公式求导或找梯度因为目标之间是冲突的。为了能用经典的数学工具求解我们通常需要把它“降维”成一个单目标问题SOP。常见的转化方法比如给价格和马力分别打分然后加权求和总分 0.5 * 价格得分 0.5 * 马力得分。这样只需要让“总分”最高就行了。在本文中的转化本文没有用简单的加权求和而是用“超体积HV”作为那个唯一的标量目标。也就是说作者把问题变成了“寻找一组解使得这组解所占的超体积HV数值最大。”这样原本复杂的 MOP 就变成了一个可以用数学方法求解的 SOP。5. 梯度子空间近似GSA - Gradient Subspace Approximation一句话解释一种不用算微积分求导仅靠观察周围邻居就能找出“往哪个方向走能让分数HV涨得最快”的数学捷径。详细解释梯度Gradient在数学上梯度代表了函数值增长最快的方向。如果我们知道 HV 的梯度我们就能顺着梯度方向调整种群让 HV 迅速变大。痛点计算 HV 的梯度极其困难且计算量巨大因为 HV 是一个基于集合的复杂几何指标不是简单的连续函数。GSA 的解法子空间Subspace既然算不出全局的梯度我就在当前解的附近局部空间找几个邻居点。近似Approximation观察这几个邻居点的 HV 值变化用线性代数的方法求解一个线性方程组估算出一个“最贪婪的搜索方向”。这就好比在浓雾中爬山看不见山顶全局梯度但可以用脚试探周围几步邻域信息判断出哪个方向是上坡近似梯度然后往那个方向走一步。三、文章思路总结到这这篇文章就懂的七七八八了但是深入的数学证明、数学公式什么的是没有去深究的如果真的觉得这篇文章很好有被说服的话很有意思可以继续深入探究本文的创新应用以前 GSA 多用于单目标问题。这篇论文首次将 GSA 应用到了基于 HV 指标的标量优化问题中。因为 GSA 不需要真实梯度只需要邻域信息所以作者可以高效地计算出一个搜索方向用来指导整个种群解集向 HV 更大的区域移动而且计算成本大大降低。总结它们之间的逻辑关系我们面对一个多目标问题MOP使用超体积HV作为评价这组解好坏的唯一标准。于是问题转化成了“最大化 HV 值”的标量优化问题SOP。为了高效求解这个 SOP我们放弃了传统的求导方法采用了梯度子空间近似GSA技术通过邻域信息估算搜索方向。最终这套组合拳构成了论文的核心算法HVGSA。1. 理论突破口What is the key insight?引入 GSA为了解决计算导数太贵的问题学术界提出了梯度子空间近似GSA。它不需要计算真实的梯度而是利用“邻域信息”来估算最贪婪的搜索方向。本文的灵感作者思考——能不能把 GSA 的思想应用到基于“超体积HV”指标的优化中核心策略将 GSA 应用于由 HV 指标和原 MOP 隐含定义的 SOP。从“单点”到“集合”以前的局部搜索是对单个解操作本文的方法是对整个解集种群进行操作。降本增效利用邻域信息避免了直接计算或近似 HV 梯度的巨大计算量。2. 具体解决方案How to implement?作者基于上述灵感提出了具体的算法和框架逻辑上分为三层底层引擎HVGSA 算法独立搜索引擎功能能处理等式和不等式约束。实现不依赖梯度信息而是通过求解一个特定的线性方程组来计算搜索方向。优化引入了自适应步长控制。上层框架HVGSA-MOEA混合框架功能将 HVGSA 作为一个“插件”原则上可以集成到任何 (μμ) MOEA 中。优化为了减少计算负担不把 HVGSA 用在所有个体上而是只用在“精英个体”上。版本迭代对比前作本文是对之前初步研究 [22] 的扩展。旧版基于 SMS-EMOA只能解决无约束问题参数多。新版通用框架能处理约束有自适应步长更强大。3. 验证与总结Does it work?实验验证在实际基准问题上测试。结论证明了 HVGSA 作为独立算法是有效的且 HVGSA-MOEA 混合框架的性能超越了当前最先进的技术State-of-the-art。文章结构最后交代了论文的后续章节安排回顾基础 - 详解 HVGSA - 详解 HVGSA-MOEA - 实验 - 结论。四、如何复现文章代码Phase 3Cell 3a-5b帮我们算出最贪婪的方向。 这个过程是如何计算的 数学上怎么理解已知当前种群 X0∈Rμn拼接成一个大向量r 个邻居种群 X1,…,Xr它们的 HV 值 Λ(X0),Λ(X1),…,Λ(Xr)要求找到一个方向 νS∗使得沿着它走HV 上升最快。理想情况这个方向就是 HV 的梯度 ∇Λ(X0)但直接算梯度太贵所以我们不直接算。核心思路我们不搜整个 Rμn 空间只在一个低维子空间S 里找。这个子空间由邻居方向张成Sspan{ν1,…,νr}在这个子空间里找最接近真实梯度的方向。用邻居方向张成一个低维子空间在这个子空间里解一个 KKT 系统近似出 HV 梯度方向同时用牛顿步修正约束。整个过程不需要显式计算梯度只需要邻居的 HV 值和约束值。第一步构造子空间直观理解我们不知道真实梯度在哪但猜测它大概率落在这 r 个方向张成的子空间里。这就像不知道山顶在哪但知道几个脚印的方向山顶大概率在这些方向之间。第二步在子空间里找最接近梯度的方向第三步消除对真实梯度的依赖第四步处理约束牛顿修正步层面作者的做法可迁移的思想问题识别找到“HV 梯度计算昂贵”这个根本瓶颈识别昂贵计算寻找替代方案核心方法用邻居信息近似梯度GSA信息复用替代直接计算约束处理牛顿修正步主动降低约束违反度当主目标失效时用约束违反度作为替代准则计算优化精英子集搜索U μ只对精英做昂贵操作框架设计HVGSA-MOEA 混合框架局部搜索 全局进化鲁棒性双准则接受前沿扩展设计替代准则避免算法“死掉”当精确计算太贵时用已有信息在低维子空间里近似当主目标失效时用约束违反度作为替代准则当计算资源有限时只对精英子集做昂贵操作。作者其实并没有提出什么新的定义和概念而是把现有的一些方法组合起来形成了一个能处理约束、计算高效、自适应强的局部搜索引擎并成功嵌入到主流 MOEA 中。1.把 GSA 从无约束推广到有约束通过牛顿修正步原始 GSA 只能处理无约束问题。作者引入牛顿修正步把约束违反度作为“额外目标”让 GSA 在不可行区域也能产生有效方向。这是组合不是新概念但解决了 GSA 的一个关键局限。2. 把 GSA 从“单点”推广到“集合”种群级别原始 GSA 作用于单个决策向量。作者把它作用于整个种群拼接成高维向量用 HV 作为标量目标。这是组合但需要处理高维线性系统、匹配问题等工程细节。3. 提出“精英子集 前沿扩展”的实用策略对整个种群做 GSA 太贵作者只对精英子集做。但只用 CDP 选精英会丢失有潜力的不可行解作者提出“前沿扩展”来保留它们。这是工程创新不是理论创新但很实用。4. 设计双准则步长接受机制HV 提升 约束违反度下降两个准则取“或”。保证算法在可行和不可行情况下都能有进展。这是工程创新但逻辑清晰、效果好。5. 把 HVGSA 做成“即插即用”的框架不绑定特定 MOEA可以嵌入 NSGA-II、ICMA、CMOEA-CD 等。这是框架创新降低了使用门槛。