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

摘要：

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

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

所属期刊栏目：31

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目61105126；中国博士后科学基金项目2014M560784

在线出版日期：2016-08-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1178-1184