中文摘要：

针对多维背包问题（MKP）NP-hard、约束强的特点,提出一种高效的蚁群-拉格朗日松弛（LR）混合优化算法.该算法以蚁群优化（ACO）为基本框架,并基于LR对偶信息定义了一种MKP效用指标.ACO使得整体算法具有全局搜索能力,所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起.该指标一方面可以用来定义MKP核问题,降低问题规模;另一方面,可以用作ACO的启发因子,引导算法在有希望的解区域中强化搜索.在大量标准算例上的测试结果表明,所提出算法的鲁棒性较好;与其他已有算法相比,在求解质量和求解效率方面均具有很强的竞争力.

英文摘要：

A hybrid optimization algorithm that integrates ant colony optimization（ACO） with Lagrangian relaxation（LR）is proposed for solving NP-hard and strongly constrained multidimensional knapsack problems（MKP）. This algorithm takes ACO as the basic framework and defines a novel utility index for MKP based on LR dual information. ACO endows the algorithm with global search ability, and the designed utility index organically combines the optimization object and the constraint conditions of MKP together. Benefiting from this characteristic, the utility index is used to define the core problem for MKP on the one hand, with the aim of reducing the problem scale. On the other hand, it can be used as the heuristic factor of ACO, directing the algorithm to intensively search those promising solution areas. Simulation results on a large number of benchmark instances show that the proposed algorithm is of strong robustness. Compared with existing algorithms, it is also highly competitive in terms of solution quality and efficiency.