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

来源期刊：控制与决策2016年第7期

论文作者：任志刚 赵松云 黄姗姗 梁永胜

文章页码：1178 - 1184

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

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