自适应邻域约简模因算法破解集合并集背包难题，实现大规模实例高效优化

《Swarm and Evolutionary Computation》：Adaptive neighborhood reduction-based memetic algorithm for the set-union knapsack problem

针对集合并集背包问题（SUKP）在大规模场景下求解效率低、精度不足的瓶颈，北京邮电大学团队提出自适应邻域约简模因算法（ANRMA），以动态利润-重量评分、多样性驱动交叉和自适应种群更新为核心，在132例基准测试中刷新15项历史最优，显著超越现有算法，为组合优化与资源配置提供新工具。

　　

在金融投资组合、柔性制造、数据管理等场景中，决策者常需在容量限制下挑选若干“项目”以最大化总收益，但不同项目可能共享相同“元素”，导致传统背包模型重复计算权重，难以精准刻画现实。集合并集背包问题（Set-Union Knapsack Problem, SUKP）正是为刻画“元素仅计一次”这一特性而提出的NP-困难变体。尽管过去三十年相继出现贪心、人工蜂群（ABC）、粒子群（PSO）、禁忌搜索（TS）及进化算法，但面对物品与元素规模动辄上千的实例，现有方法要么陷入局部最优，要么因邻域爆炸而耗时剧增，始终缺乏兼顾精度与效率的通用求解器。
为突破这一瓶颈，Zequn Wei、Jianing Yu、Jin-Kao Hao与Jintong Ren组成的研究团队设计了一种全新的种群模因框架——自适应邻域约简模因算法（ANRMA），并在《Swarm and Evolutionary Computation》发表成果。该研究以“强化开采、兼顾探索”为核心思路，通过三项创新机制显著提升了SUKP在大规模场景下的求解效率与鲁棒性。

关键技术方法概括为：

1. 多样性驱动贪心交叉（DGC）：基于父母解的汉明距离自适应设定物品入选概率，优先挑选动态利润-重量比高的物品生成子代。
2. 自适应邻域约简禁忌搜索（SBTS-ANR）：以动态利润-重量比为准则，将候选移除/添加物品规模分别压缩至n_{与n，实现常数级邻域扫描；并用三重哈希向量实现O(1)时间判重。}
3. 自适应种群更新：提出兼顾目标值与种群多样性的自适应优良度评分φ_{，动态调整质量权重β，淘汰评分最低个体，维持种群活力。}
4. 参数自适应：种群规模PopSize=n/1000+5，最大连续未改进迭代λ_{=n/8，均随实例规模线性增长，无需人工调参。}

研究结果按原文小节展开如下：
3.1 主框架
ANRMA先以随机贪心+一次SBTS快速生成初始种群，再循环执行“DGC交叉→SBTS-ANR改进→全局最优更新→自适应种群替换”，直至时限终止。

3.2 种群初始化
PopSize与n线性相关，每个个体经随机可行构造和一次“轻量”SBTS（λ_{=1）即可入群，兼顾多样性与初步质量。}

3.3 自适应邻域约简禁忌搜索
SBTS-ANR将传统O(n^{)的swap邻域压缩为O(n_{·n)，其中n=min(round(e)+1,|A|)，n=min(n+1,|ā|)。利用动态利润-重量比R、R遴选最可能改进的移除与添加候选，使单步迭代降至O(nm)且随n增大趋近常数。}}

3.4 多样性驱动贪心交叉
DGC将物品按父母选择频次分为V_{与V，对“均未选”物品赋予与种群平均汉明距离D?呈指数增长的入选概率，以强制探索；随后按R^{贪心填充，直到容量饱和。}}

3.5 自适应种群更新
新解进入后，计算其与种群的最小汉明距离D(S)与归一化目标值，以β=(f(S_{)-f)/(f-f)动态加权，淘汰φ最低者，实现“高质量阶段重质量，低质量阶段重多样”的自适应平衡。}

3.6 复杂度分析
初始化O(n^{m)，单次SBTS-ANR O(nm)，交叉与更新均为O(nm)或O(n)，整体复杂度O(n+G·n)，其中m=O(n)时简化为O(n)。}

4 实验与比较
在132例公开基准（含85-5000物品/元素）上，ANRMA与MSBTS、PSO-B、AES-BM、I2PLS、ATS-DLA及CPLEX 22.1.1对比：

• Set I（小-中规模）：60例中命中全部6例CPLEX最优解与全部历史最优值BKV，平均解质量显著优于对比算法。
• Set II（中规模）：54例中刷新12例BKV，9个分组里4组最佳f_{与7组最佳f均被ANRMA夺得。}
• Set III（大规模）：18例中改进2例BKV，其余全部追平；CPLEX在大多数大例上2小时内无解，而ANRMA平均17-106秒即给出高质量可行解，标准差稳定低于7.5。

结论与讨论
ANRMA通过“邻域约简+动态评分+多样性维护”三位一体策略，首次在无需人工调参的前提下实现SUKP从小规模到5000级大规模实例的稳健求解，刷新15项历史最优，验证了其在组合优化、资源配置及预算最大覆盖等衍生问题上的广泛适用性。研究同时揭示，动态利润-重量比可显著减少无效评估，而自适应种群机制能在搜索早期保持探索、后期强化开采，为其他NP-困难问题提供了可复制的算法设计范式。未来工作将探讨在多目标SUKP及实时决策场景中的拓展，并开放源码以促进社区进一步研究。