摘要：

针对传统多维背包问题的求解算法存在的修复方式单一、种群动态适应性差等问题，提出一种双决策交互差异算法（DDEA）。融合自主学习思想，设计多维加权价值密度和相对价值概率指标，双重决策确定物品选择顺序，制定相应解的修复优化策略。采用双种群交互差异进化算法，设置主群和辅助群2个种群，种群间进行信息交互，提高种群多样性，避免陷入局部最优，提高算法寻优能力。主群实施差异进化机制，依照个体优劣依次划分为3个子群，分别按照特定方式进化，并在进化过程中完成与辅助群的交互，增强算法群智能性。引入刺激-响应机制，平衡算法的全局和局部搜索能力，并加入精英库协同寻优，加快算法收敛速度。仿真结果表明，DDEA算法可求出全部最优解，平均相对误差率为3.04×10^-5，相比于同类算法降低2个数量级，有效提升了多维背包问题的求解精度、效率和稳定性。

关键词: 多维背包问题, 双种群交互进化, 多维加权价值密度, 相对价值概率, 刺激-响应机制

Abstract:

A double-decision interactive diversity algorithm called the DDEA is proposed to solve the problems of the single-repair method and poor adaptability of population dynamics in traditional solving algorithms for the Multidimensional Knapsack Problem(MKP).The principle of autonomous learning is integrated.Two indicators(multidimensional weighted value density and relative value probability) are designed to determine the order of goods selection through double decision-making, and the repair and optimization strategies of the corresponding solutions are formulated. The double-population interactive evolution algorithm is adopted, and the main and auxiliary groups are established. The information exchange between the groups can improve the diversity of the population to prevent falling into the local optimum and improve the optimization ability of the algorithm.The main group implements the diversity evolution mechanism, which is divided into three subgroups based on the advantages and disadvantages of the individual.It evolves in a specific manner and completes the interaction with the auxiliary group in the process to enhance the group intelligence of the algorithm.The stimulus-response mechanism is introduced to improve the balance during the global and local searches of the algorithm. The elite pool is joined for collaborative optimization to accelerate convergence.The simulation results show that the solution result of the DDEA can achieve full optimization.The average relative error rate is 3.04×10^-5, which is two orders of magnitude lower than other algorithms, demonstrating an effective improvement in the accuracy, efficiency, and stability of solving MKPs.

Key words: Multidimensional Knapsack Problem(MKP), double-population interactive evolution, multidimensional weighted value density, relative value probability, stimulus-response mechanism