基于核问题的果蝇优化算法求解多维背包问题

作者：张清勇; 钱浩; 雷德明^*

来源：华中科技大学学报(自然科学版)科技大学, 2019, 47(02): 92-97.

DOI：10.13245/j.hust.190217

• 多维背包问题
• 果蝇优化算法
• 核问题
• 突跳机制
• 二级结构

针对多维背包问题(MKP)维度高、约束强的特点,提出了一种基于核问题的果蝇优化算法(CBFOA).该算法通过求解MKP的线性规划松弛问题(LPR-MKP)的对偶问题得到MKP效用比,并运用核问题降低问题规模;果蝇的生成采用的二级结构和时变的搜索步距有利于前期快速寻优和后期精确搜索,采用的修复补偿策略、一级果蝇交流以及视觉搜索中的突跳机制以提高求解质量.通过标准测试集的测试和算法性能的对比,结果表明CBFOA对于MKP有较强的搜索能力.

• 单位
  武汉理工大学; 自动化学院