Abstract: In order to more efficiently solve the multi-dimensional knapsack problem (MKP) using the ring theory optimization algorithm (RTEA), the inadequacies of the existing repair optimization operators RO1 and RO3 are first analyzed, and a new repair optimization operator, weighted repair optimization operator (RO4), is proposed based on the complementary strategy. Secondly, an inheritance strategy is introduced to improve the global evolutionary operator of RTEA, and a self-adaptive reverse mutation operator suitable for MKP of RTEA is proposed based on logistic model. Thus, a new algorithm IRTEA-RO4 for solving MKP is presented. To validate the efficiency of IRTEA-RO4, it is used to solve 114 benchmark instances of MKP and compared with six state-of-the-art algorithms for MKP. The results show that for small-scale MKP instances, IRTEA-RO4 achieves the best solution accuracy and speed; For large-scale MKP instances, the best results obtained by IRTEA-RO4 are 21% to 125% higher than six state-of-the-art algorithms, with superior average solving performance and stability, and faster computation speed.

Key words: ring theory-based evolutionary algorithm, multi-dimensional knapsack problem, weighted pseudo-utility ratio, inheritance strategy, Logistic model

摘要： 为了利用环论优化算法(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模型