求解多选择多维背包问题的混合蚁群算法

摘要

本文提出了将蚁群算法和拉格朗日松弛法融合的算法来求解多选择多维背包问题.算法遵循了最大最小蚁群系统的算法方案,从拉格朗日松弛中得到的项目的拉格朗日值将被作为蚁群算法的启发式因子,它在定义的6个基于域的启发式因子中表现最好.在此基础上,提出了一种新颖的可行性指标,将可能不可行解转化为可行解.通过将该算法与现有的三种算法进行比较的实验测试,结果表明,该算法具有较强的求解能力.