基于交换策略的蚁群算法求解多维0-1背包问题  

Ant Colony Algorithm for Solving Multi-dimensional 0-1 Knapsack Problem Based on Exchange Strategy

作　　者：潘夏福[1] 倪子伟[1] 

机构地区：[1]厦门大学信息科学与技术学院,福建厦门361005

出　　处：《计算机与现代化》2008年第3期83-85,共3页Computer and Modernization

摘　　要：在项目决策与规划、资源分配、货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了许多算法。本文推广了文献[7]中求解单维0-1背包问题的蚁群算法,并从结合2-opt等局部优化的蚁群算法求解旅行商问题中得到启示:通过交换策略可以加快算法的收敛速度和获取更高质量的解,因此提出了基于交换策略的蚁群算法。再把这种算法与AIAACA算法[8]进行比较,实验结果显示该算法与AIAACA算法效果相当,用时更少,是求解多维0-1背包问题的有效算法。Multi-dimensional 0-1 knapsack problem often appears in decision making and programming, resource distribution, loading, and so on. For solving this problem, many algorithms have been proposed by scholars. This paper extends the ant colony algorithm which is used for solving 0-1 knapsack problem in reference [7], and gets enlightenment from the ant colony algorithm with 2-opt local optimization for solving traveling salesman problems：Exchange strategy can make the algorithm have faster convergence rate and get better quality solution, So this paper presents the ant colony algorithm based on exchange stragegy. Compared with AIAACA algorithm, experiment results demonstrate that the algorithm proposed in this paper has the same result but the runtime is shorter. So this algoritm is rather efficient for solving multi-dimensional 0-1 knapsack problem.

关 键 词：多维0—1背包问题 蚁群算法 交换 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]