[Paper] 基准测试元启发式算法用于具有多策略的可维修系统的双目标冗余分配问题

Source: arXiv - 2512.18343v1

概述

本文解决了一个经典的工程难题——如何在可维修系统中分配冗余组件，以在花费最少资金的同时，使系统的可用性尽可能高。通过将问题构建为双目标优化，并严格基准测试 65 种现代元启发式算法，作者为需要设计容错硬件、云服务或物联网部署的人员提供了实用的衡量标准。

关键贡献

• 全面基准：对 65 种多目标元启发式算法在六个日益复杂的冗余分配实例上进行评估。
• 引入 Scaled Binomial Initialization (SBI)，一种简单而强大的搜索初始化方法，能够持续提升超体积指标。
• 系统分析 四种冗余策略（冷备、热备、温备、混合）及其在不同权重（预算）限制下对成本与可用性权衡的影响。
• 开源发布所有代码、数据和参考帕累托前沿（Zenodo DOI: 10.5281/zenodo.17981720），以实现可重复性。
• 实证表明 预算规模（目标函数评估次数）会显著改变算法排名，警示“千篇一律”性能声明的风险。

方法论

1. Problem formulation – 冗余分配问题（RAP）被建模为二进制决策向量：每个子系统决定安装多少备件 and 使用哪种待机策略（冷备、温备、热备或混合）。
2. Availability evaluation – 系统可用性通过解析方法使用连续时间马尔可夫链计算，捕捉每种冗余模式的失效/维修动态。
3. Benchmark design – 生成六个案例研究（从小型到大型系统），并控制结构复杂度。对每个案例施加四种权重限制（从严格到宽松），得到 24 种测试配置。
4. Algorithm pool – 运行 65 种最先进的多目标元启发式算法（NSGA‑II 变体、MOEA/D、CMOPSO、NNIA 等），在两种初始化方式下进行：随机和 SBI。
5. Evaluation budget – 每个算法获得固定的 2 × 10⁶ 次目标函数评估预算，分为多次独立运行，以便进行统计检验。
6. Performance metrics – 主要质量指标是 hypervolume（由获得的 Pareto 前沿支配的目标空间体积）。基于预算的性能曲线用于跟踪每个算法逼近其最佳超体积的速度。

结果与发现

• 主导策略： 热备份和混合冗余在帕累托最优前沿占主导。冷备份和温备份很少出现，尤其在重量限制严格时。
• 重量限制影响： 当允许的总重量较低时，倾向于使用热备份（所需备件更少）。在重量限制宽松时，混合冗余——结合热备份和冷备份——能够实现更好的成本‑可用性平衡。
• SBI 的影响： 在初始种群中加入 SBI 平均可将超体积提升至 30 %，在一些情况下，SBI 种子已经接近最终参考前沿。这可能改变算法排名（例如，NNIA‑SBI 超越未使用 SBI 的 NSGA‑II）。
• 预算敏感性： 算法在不同预算下表现不同。
  • 紧张预算（评估次数少）：NNIA‑SBI 和 CMOPSO‑SBI 在早期获得最高的超体积。
  • 中等/大预算： NSGAIIARSBX‑SBI 上升至榜首，提供最佳的最终前沿。
• 可扩展性： 更大的 RAP 实例（子系统更多，二进制变量更多）需要显著更多的评估次数才能达到可比的超体积水平，这表明搜索工作量必须提前规划。

实际意义

• 设计自动化工具 可以将 SBI 嵌入为一种低成本的预处理步骤，为工程师提供强有力的起点，从而减少昂贵的仿真调用次数（Markov‑chain 评估）。
• 云原生服务 依赖冗余微服务时，可利用热备份与混合备份的洞察，决定是保持热容器（成本更高）还是仅在需要时启动冷实例。
• 硬件制造商 可以利用基准结果选择符合其计算预算的优化器，例如用于快速原型的 NNIA‑SBI，或用于最终设计验证的 NSGAIIARSBX‑SBI。
• 开放数据集 使开发者能够在无需重新实现 Markov‑chain 可用性计算的情况下，测试自定义启发式算法或基于机器学习的代理模型。
• 预算感知的优化：研究指出，仅报告单一“最佳算法”具有误导性；实践者应根据可用的评估预算和问题规模匹配合适的优化器。

局限性与未来工作

• 基准测试聚焦于 binary decision variables；将其扩展到连续尺寸（例如组件容量）将扩大适用范围。
• 可用性采用 exponential failure/repair times 进行建模；实际数据常表现出非指数行为，这可能影响 Pareto 前沿。
• 仅使用 hypervolume 作为质量度量；加入面向多样性的指标可以更全面地展示解的分布情况。
• 未来研究可探讨 adaptive budget allocation，即算法根据中间 hypervolume 增益动态决定在探索与利用上分配多少评估次数。
• 将 surrogate modeling（例如 Gaussian processes）集成以近似马尔可夫链评估，可显著降低大规模系统的计算成本。

作者

• Mateusz Oszczypała
• David Ibehej
• Jakub Kudela

论文信息

• arXiv ID: 2512.18343v1
• 分类: cs.NE
• 发布日期: 2025年12月20日
• PDF: 下载 PDF