多智能体改进Double-DQN与单调价值分解的多维0-1背包通用求解
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

教育部人文社会科学研究规划基金 (25YJA630038); 福建省科技特派员 (20250302)


Multi-agent Improved Double-DQN and Monotone Value Decomposition for Multi-dimensional 0-1 Knapsack General Solution
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    0-1背包问题(knapsack problem, KP)是组合优化领域中的一个经典NP难问题. 针对原始深度Q网络(deep Q-network, DQN)算法求解高维KP时易陷入局部最优和全局勘探能力不足的局限性, 本文提出一种基于多智能体的改进Double-DQN算法. 首先引入项目选择机制和变异机制, 进而整合多智能体协同框架与单调价值函数分解(QMIX)模块进行优化, 显著增强了寻优的多样性与全局勘探能力. 在包含500个不同规模0-1 KP算例的5个测试集、1个规模50个的多背包算例测试集和1个规模50个的分数背包算例测试集上进行性能评估, 实验结果显示0-1 KP算例中有86%的算例(429个)成功求得最优解, 多背包算例中有84%的算例 (42个) , 分数背包算例中有85%的算例 (43个). 与Gurobi求解器的对比实验结果表明, 所提算法具有较强的稳定性和有效性, 充分验证了改进策略的可行性.

    Abstract:

    The 0-1 knapsack problem (KP) is a classical NP-hard problem in the field of combinatorial optimization. To overcome the tendency of the deep Q-network (DQN) algorithm to become trapped in local optima and their limited global exploration capability when applied to high-dimensional KP instances, this study proposes an improved Double-DQN algorithm within a multi-agent framework. The algorithm first incorporates an item selection mechanism and a mutation strategy, and then integrates a multi-agent collaborative framework with a monotonic value function decomposition (QMIX) module, thus significantly enhancing solution diversity and global exploration capability. The proposed method is evaluated on five test sets, including 500 0-1 KP instances of varying scales, a multi-knapsack test set containing 50 instances, and a fractional knapsack test set with 50 instances. Experimental results show that 86% of the 0-1 KP instances (429) reach optimal solutions, while the corresponding rates are 84% (42) and 85% (43) for the multi- and fractional knapsack instances, respectively. Comparative experimental results with the Gurobi solver demonstrate that the proposed algorithm exhibits strong stability and effectiveness, fully confirming the feasibility of the improved approach.

    参考文献
    相似文献
    引证文献
引用本文

李斌,郑小李.多智能体改进Double-DQN与单调价值分解的多维0-1背包通用求解.计算机系统应用,2026,35(7):39-62

复制
分享
相关视频

文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-10-21
  • 最后修改日期:2025-11-21
  • 录用日期:
  • 在线发布日期: 2026-05-26
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62661041 传真: Email:csa@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号