求解抽象辩论框架稳定扩充的长记忆禁忌搜索算法

来源：计算机应用研究杂志2025年第11期北京时间：

作者：吴歆韵,孙俊杰,熊才权,罗茂,喻卓群,

单位：湖北工业大学计算机学院,武汉430068；

摘要：稳定扩充求解是抽象辩论框架中评估争议可接受程度的关键任务，是NP完全问题。该任务寻找满足子集无冲突和子集外的争议被子集攻击条件的争议子集。针对该任务，提出基于长记忆机制的禁忌搜索算法（long-memory tabu search for stable extension，LMTS）。采用解池结构，赋予算法对历史信息的长期记忆能力。同时，与问题相匹配的邻域评估结构能够迅速识别能带来正确性提升的邻域动作。结合自适应扰动和禁忌解禁等策略，依据当前搜索状态动态调整扰动强度以改善当前解的质量。通过对公开数据集和随机生成的数据集进行测试，结果显示该算法能够有效求解稳定扩充，在超50%的算例上求解时间和求解能力均优于对比算法。此外，消融实验验证长记忆禁忌策略与自适应扰动策略对算法的正向优化作用。

关键词：抽象辩论框架,稳定扩充,禁忌搜索,自适应扰动,长记忆,

基金资助：国家自然科学基金资助项目(62402164)；；