求解多维背包问题的蚁群-拉格朗日松弛混合优化算法  

Hybrid optimization algorithm of ant colony optimization and Lagrangian relaxation for solving multidimensional knapsack problem

作　　者：任志刚[1] 赵松云[1] 黄姗姗[1] 梁永胜[1] 

机构地区：[1]西安交通大学电子与信息工程学院,西安710049

出　　处：《控制与决策》2016年第7期1178-1184,共7页Control and Decision

基　　金：国家自然科学基金项目(61105126);中国博士后科学基金项目(2014M560784)

摘　　要：针对多维背包问题(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.

关 键 词：多维背包问题 蚁群优化 拉格朗日松弛 核问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]