基于新修复优化算子的改进环论优化算法求解多维背包问题

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

作者：张寒崧, 贺毅朝, 孙菲, 陈国新, 陈炬

单位：1.河北地质大学 信息工程学院，石家庄 050031；2.河北省光电信息与地球探测技术重点实验室（河北地质大学），石家庄 050031

摘要：为了利用环论优化算法（RTEA）高效求解多维背包问题（MKP），在分析已有修复优化算子——基于物品整体资源消耗伪效用比的修复优化算子RO1和基于物品各维度资源消耗价值密度的修复优化算子RO3不足的基础上，结合互补策略提出一种新的修复优化算子——加权修复优化算子RO4。随后，引入继承策略改进RTEA的全局进化算子，并基于Logistic模型提出适用于MKP的自适应反向变异算子，由此提出了求解MKP的算法IRTEA-RO4。为验证IRTEA-RO4的高效性，利用它求解MKP的114个国际通用基准实例，并与已有求解MKP的6个较先进算法进行比较，结果表明：对于小规模MKP实例，IRTEA-RO4的求解精度和求解速度均为最佳；对于大规模MKP实例，IRTEA-RO4求得的最好结果比6个对比算法的最好结果提高了21%～125%，而且平均性能与稳定性更优，计算速度更快。

关键词：环论优化算法,多维背包问题,加权伪效用比,继承策略,Logistic模型

基金资助：河北省自然科学基金资助项目(F2020403013);河北省高等学校科学技术研究项目(ZD2021016);河北地质大学2023年国家自然科学基金预研项目(KY202307);2024年河北省在读研究生创新能力培养资助项目(CXZZSS2024109)