Hybrid Ant Colony Algorithm for Solving Multi-dimensional 0-1 Knapsack Problem

摘要

在项目决策与规划，资源分配，货物装载等工作中，提出了多维0-1背包问题。多维0-1背包问题同时还是一个典型的NPC问题，对背包问题的研究无论在实际应用还是在理论研究中都有着重要意义。对这一问题的求解，国内外学者提出了许多算法。 本文推广了文献[24]中求解单维0-1背包问题的蚁群算法，并在此基础上给出了求解多维0-1背包问题的蚁群算法数学模型、算法描述和算法流程图。而且本文还对蚁群算法求解背包问题进行了信息素、蚂蚁路径选择和最优路径选择等模拟仿真。这些仿真实验的结果表明蚁群算法求解背包问题是可行的，但算法有搜索时间长和容易陷入局部最优解的缺点。 为了解决蚁群算法求解背包问题时遇到的问题，本...