论文部分内容阅读
针对多维背包问题(MKP)NP-hard、约束强的特点,提出一种高效的蚁群-拉格朗日松弛(LR)混合优化算法.该算法以蚁群优化(ACO)为基本框架,并基于LR对偶信息定义了一种MKP效用指标.ACO使得整体算法具有全局搜索能力,所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起.该指标一方面可以用来定义MKP核问题,降低问题规模;另一方面,可以用作ACO的启发因子,引导算法在有希望的解区域中强化搜索.在大量标准算例上的测试结果表明,所提出算法的鲁棒性较好;与其他已有算法相比,在求解质量和求解效率方面均具有很强的竞争力.
Aiming at the NP-hard multi-dimensional knapsack problem (MKP) and its strong constraint, this paper proposes a highly efficient ant colony-Lagrange relaxation (LR) hybrid optimization algorithm based on ant colony optimization (ACO) An MKP utility index is defined based on the LR dual information.ACO makes the global search ability of the whole algorithm.The designed utility index organically integrates the optimization goal of MKP with the constraints.This index can be used to define the MKP kernel And reduce the scale of the problem.On the other hand, it can be used as the heuristic factor of ACO to guide the algorithm to enhance the search in the promising solution area.The test results on a large number of standard examples show that the proposed algorithm is robust ; Compared with other existing algorithms, it has strong competitiveness in solving quality and solving efficiency.