一种用于集合覆盖问题（Set Covering Problem, SCP）的、带有数据驱动修复（Data-Driven Repair）机制的新型二进制饥饿游戏搜索（Binary Hunger Games Search, BHGS）算法

《Biomimetics》：A Novel Binary Hunger Games Search Algorithm with Data-Driven Repair for the Set Covering Problem

　　

资源高效分配与组织相关问题日益受到科学界关注。评估这类方法时常采用集合覆盖问题（Set Covering Problem, SCP）这一NP难组合优化问题。研究中常用的近似技术可在可接受计算时间和成本内求解复杂覆盖问题。元启发式（Metaheuristics, MH）多面向连续搜索空间，应用于覆盖问题须改为离散域，核心挑战是设计将连续解转为二进制解的变换方法。现有路径包括两步式二值化，以及研究人员提出的由基于多臂老虎机（Multi-Armed Bandit, MAB）框架的自适应修复选择机制（Adaptive Repair Selection Mechanism, ARSM）调度修复算子。研究人员选取二进制饥饿游戏搜索（Binary Hunger Games Search, BHGS）作为元启发式，因为个体相对质量决定其饥饿水平，进而调节种群移动与最优解影响。不可行解由基于禁忌搜索（Tabu Search）的修复算子处理；不同于全程使用单一修复规则，所提方法根据搜索中观测贡献动态选择算子，各算子还引入禁忌记忆以避免修复时重复决策。实验采用经典Beasley基准实例。

研究背景方面，物流、通信、道路基础设施与医疗等资源管理中，组合复杂度随问题规模指数增长，精确方法在大规模场景下时间与内存开销过大，元启发式（Metaheuristics, MH）成为获取近似解的重要替代。但连续型MH用于SCP须解决二进制化与覆盖约束满足问题：连续位置经传递函数与离散规则转出的二进制向量常不可行，修复算子选择又会显著影响解的质量与稳定性。因此，研究人员以饥饿游戏搜索（Hunger Games Search, HGS）这一受动物饥饿驱动行为启发的种群式连续MH为底座，研究其在约束二进制问题中的迁移效果。

主要关键技术方法上，研究人员采用V3传递函数加ELIT离散规则的二步二值化（V3-ELIT Binarization Scheme）；构建三类带短期禁忌记忆的修复算子，即Tabu Complex Stochastic（TCS）、Tabu Complex Penalized（TCP）、Tabu Complex Stochastic Drop（TCS-D），以成本—覆盖比与冗余列剔除为依据；用基于MAB的ε-greedy自适应修复选择机制（Adaptive Repair Selection Mechanism, ARSM）按全局最优改进量更新算子效用；以OR-Library中Beasley基准实例为样本来源，做31次独立运行，并用相对百分比偏差（Relative Percentage Deviation, RPD）、变异系数（Coefficient of Variation, CV）、收敛迭代（Convergence Iteration, CI）等指标评价。

研究结果部分，第二章集合覆盖问题（Set Covering Problem, SCP）给出数学建模与医院选址示例，说明二值化后仍需修复才能满足覆盖约束，并解释选用Beasley实例的参照价值。第三章饥饿游戏搜索（Hunger Games Search, HGS）阐述饥饿机制、自适应权重W₁与W₂、探索阶段位置更新X_i^t+1=X_i^t+N(0,1)·X_i^t类扰动、利用阶段围绕最优个体移动，以及l参数随时间衰减的结构。第四章二进制适配经V3-ELIT将连续值映到[0,1]再依最优解比特定二进制决策；可行性修复将不可行向量转可行解；三类Tabu修复算子分别用成本—覆盖比c_j/u_j、频率惩罚c_j/u_j+λ·f_j、先修复后按高成本冗余列可去条件移除；ARSM以奖励R=G_best^before-G_best^after更新效用Q_a=(Q_a·(n_a-1)+R)/n_a。第五章二进制HGS（Binary HGS, BHGS）把连续更新、二值化、可行性检测、ARSM选算子、奖励更新串成算法闭环。第六章实验结果中，6.1方法论说明31次运行与指标定义；6.2参数设置里ε=0.2因中位RPD 0.215%、CV 0.264%与15/18中位最优而选定；6.3.1 Tabu自适应修复显示65个实例最佳解达已知最优60个、中位最优45个，平均RPD约0.086%、中位RPD约0.48%、平均CV约0.42%，NRG与NRH更难，XPT高于93%说明利用主导、CI较早；6.3.2复杂修复算子最佳最优58/65但中位仅9/65，平均RPD约2.03%、CV约2.90%，CSD贡献最大却选择不一定最多；6.4统计分析与Wilcoxon检验表明Tabu在64/65实例占优、59个显著，NRG/NRH全显著；6.5与SCA、PSA、GWO、BGO、BDOA、BAOA比对，45个公共实例上BHGS平均RPD 0.009%、最优率97.8%，Friedman检验显著，Wilcoxon事后检验中BHGS与BDOA无差异，对其余五种显著更优。

讨论与结论部分，研究人员指出BHGS结合V3-ELIT二值化与Tabu式ARSM，在SCP上不只提升最佳解，还改善中位行为与稳定性；复杂修复依赖单一CSD，Tabu修复让TCS、TCP、TCS-D贡献更均衡。未来可改进入口探索不足、扩大实例规模做扩展性评估。结论翻译为：所提带有数据驱动修复的二进制饥饿游戏搜索（Binary Hunger Games Search, BHGS）为SCP提供高精度且稳定的近似求解框架；基于多臂老虎机（Multi-Armed Bandit, MAB）的修复选择优于固定规则，Tabu记忆降低重复列选择；在Beasley基准上BHGS与基于数据驱动算子的BDOA同属顶尖水平，并显著优于SCA、PSA、GWO、BGO、BAOA等连续型MH的二进制变体。该文发表于《Biomimetics》。