离散灰狼优化算法求解有界背包问题

作者：贺毅朝; 李泽文; 李焕哲; 郭晓虎; 李亚

来源：计算机工程与设计, 2019, 40(04): 1008-1015.

DOI：10.16208/j.issn1000-7024.2019.04.018

• 有界背包问题
• 灰狼优化算法
• 遗传算法
• 编码转换法
• 修复与优化法

为利用灰狼优化算法求解有界背包问题,基于编码转换法提出一种离散灰狼优化算法(discrete grey wolf optimizer,DGWO)。引入遗传算法的交叉策略增强局部搜索能力,使用基于贪心策略的修复与优化法处理不可行解,保证算法的求解效果,加快算法的收敛速度。对于3类大规模有界背包问题实例,通过与已有算法的计算结果比较与分析,验证了DGWO的有效性和稳定性。实验结果表明,DGWO的收敛速度比其它算法快,对于所有的有界背包问题实例均能获得一个近似比接近1的近似解。

• 单位
  河北地质大学