论文摘要
在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题。多维0-1背包问题同时还是一个典型的NPC问题,对背包问题的研究无论在实际应用还是在理论研究中都有着重要意义。对这一问题的求解,国内外学者提出了许多算法。本文推广了文献[24]中求解单维0-1背包问题的蚁群算法,并在此基础上给出了求解多维0-1背包问题的蚁群算法数学模型、算法描述和算法流程图。而且本文还对蚁群算法求解背包问题进行了信息素、蚂蚁路径选择和最优路径选择等模拟仿真。这些仿真实验的结果表明蚁群算法求解背包问题是可行的,但算法有搜索时间长和容易陷入局部最优解的缺点。为了解决蚁群算法求解背包问题时遇到的问题,本文提出了基于交换策略的蚁群算法。这是从结合了2-opt、3-opt等局部优化的蚁群算法求解旅行商问题中得到启示:通过交换策略可以加快算法的收敛速度和获取更高质量的解。为了能够在求解背包问题时使用交换策略,本文研究了求解背包问题的蚁群算法与求解TSP的蚁群算法的不同之处,针对背包问题的特点,提出了求解背包问题2-opt、3-opt等局部搜索算法,并将这些局部搜索算法引入蚁群算法中。基于交换策略的蚁群算法大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。最后本文从搜索代数、解的质量和搜索时间等方面对基于交换策略的蚁群算法与其它智能算法进行比较,实验结果也显示本文算法比其它智能算法用时更少,解的质量更高,是求解多维0-1背包问题的有效算法。