[Paper] 高效的进化算法用于少对多优化

Source: arXiv - 2601.06387v1

概述

本文介绍了 SoM‑EMOA，一种针对 few‑for‑many（F4M）优化的新型进化算法——在这种设置下，需要用极少量的解来有效覆盖 数十甚至数百个相互冲突的目标。作者通过关注代表性解而非穷尽的帕累托前沿覆盖，解决了传统多目标优化器所面临的可扩展性瓶颈。

关键贡献

• 专用的 F4M 算法：SoM‑EMOA（基于 $(\mu!+!1)$ 进化策略）显式优化 F4M 目标，扩展了著名的 SMS‑EMOA 框架。
• 灵活的基准套件：利用 R2 指标与 F4M 形式之间的等价性，作者提供了一种系统方法，可通过加权 Tchebycheff 标量化将任何已有的多目标问题转化为 F4M 实例。
• 实验优势：在新基准上进行的大量实验（包括多达 100 个目标）表明，SoM‑EMOA 在目标数量增加时始终优于最先进的多目标算法。
• 开源实现：算法和基准生成器已在 GitHub 上发布，支持即时复现和社区扩展。

方法论

1. Problem Formulation – F4M 优化旨在寻找 少量（例如 5–10）解，使得在所有可能的权重向量下 最大后悔值 最小化，从而有效保证对任何用户指定的权衡都有良好表现。
2. Algorithm Core – SoM‑EMOA 采用经典的 $(\mu!+!1)$ 进化循环：
   • Population of $\mu$ individuals is maintained.
   • One offspring is generated each generation via mutation (Gaussian perturbation) and optional crossover.
   • Selection uses a F4M‑aware fitness: the algorithm computes the R2 indicator (a weighted sum of Tchebycheff scalarizations) and removes the individual whose removal causes the smallest degradation in the indicator, thereby preserving the most “representative” solutions.
3. Benchmark Generation – Any multi‑objective test problem (DTLZ, WFG, etc.) is transformed by sampling a large set of weight vectors, evaluating the weighted Tchebycheff scalarization for each, and then using the resulting scalar values as the basis for the R2/F4M indicator. This yields a plug‑and‑play suite that can scale to arbitrary objective counts.

结果与发现

关键要点

• 可扩展性 – 当目标数量超过约 30 时，SoM‑EMOA 的性能优势显著，传统算法要么停滞，要么产生臃肿的解集。
• 稳定性 – 该算法在 30 次独立运行中方差低，表明能够可靠地收敛到高质量的代表性解集。

实际意义

• 决策支持系统：在云资源分配、投资组合优化或汽车设计等领域，利益相关者通常需要少量能够在多种偏好权重下表现良好的“策略”选项。SoM‑EMOA 能快速生成这些选项，减轻决策者的认知负担。
• 实时或嵌入式优化：由于该算法保持小规模种群并评估轻量级指标，它适用于计算资源紧张的场景（例如，边缘设备实时调优超参数）。
• 基准测试与工具：提供的测试套件让开发者能够在 F4M 视角下对自己的多目标求解器进行基准测试，鼓励社区采用更以用户为中心的评估指标，而非单纯的帕累托覆盖率。
• 与 AutoML 流程的集成：AutoML 框架可以嵌入 SoM‑EMOA，生成一组简洁的模型超参数配置，同时平衡准确率、延迟、内存和公平性。

限制与未来工作

• 指标成本 – 尽管 R2/F4M 指标能够高效更新，但其计算仍随采样权重向量的数量而线性增长；极大的权重集合可能成为瓶颈。
• 固定种群规模 – $(\mu!+!1)$ 方案假设 $\mu$ 为固定值。自适应种群规模（例如在目标函数景观高度多模时增大 $\mu$）可能进一步提升鲁棒性。
• 理论保证 – 本文提供了实证证据，但缺乏对 F4M 目标的形式收敛证明；未来工作可以探索可证明的界限。
• 真实案例研究 – 在工业数据集（如供应链优化）上展示 SoM‑EMOA 将巩固其实际价值并揭示领域特定的挑战。

如果您想亲自尝试该算法，作者已将源代码公开在 github.com/MOL-SZU/SoM-EMOA。欢迎克隆仓库，运行基准测试套件，并尝试将 SoM‑EMOA 集成到您自己的多目标流水线中。祝优化愉快！

作者

• Ke Shang
• Hisao Ishibuchi
• Zexuan Zhu
• Qingfu Zhang

论文信息

• arXiv ID: 2601.06387v1
• 分类: cs.NE
• 出版日期: 2026年1月10日
• PDF: 下载 PDF