| 基于交换策略的蚁群算法求解多维0-1背包问题 |
| |
| 引用本文： | 潘夏福,倪子伟.基于交换策略的蚁群算法求解多维0-1背包问题[J].计算机与现代化,2008(3):83-85. |
| |
| 作者姓名： | 潘夏福 倪子伟 |
| |
| 作者单位： | 厦门大学信息科学与技术学院,福建,厦门,361005 |
| |
| 摘 要： | 在项目决策与规划、资源分配、货物装载等工作中，提出了多维0-1背包问题，对这一问题，国内外学者提出了许多算法。本文推广了文献7]中求解单维0-1背包问题的蚁群算法，并从结合2-opt等局部优化的蚁群算法求解旅行商问题中得到启示：通过交换策略可以加快算法的收敛速度和获取更高质量的解，因此提出了基于交换策略的蚁群算法。再把这种算法与AIAACA算法进行比较，实验结果显示该算法与AIAACA算法效果相当，用时更少，是求解多雏0-1背包问题的有效算法。
|
| 关 键 词： | 多维0—1背包问题 蚁群算法 交换 |
| 文章编号： | 1006-2475（2008）03-0083-03 |
| 收稿时间： | 2007-04-03 |
| 修稿时间： | 2007年4月3日 |
Ant Colony Algorithm for Solving Multi-dimensional 0-1 Knapsack Problem Based on Exchange Strategy |
| |
| PAN Xia-fu,NI Zi-wei.Ant Colony Algorithm for Solving Multi-dimensional 0-1 Knapsack Problem Based on Exchange Strategy[J].Computer and Modernization,2008(3):83-85. |
| |
| Authors: | PAN Xia-fu NI Zi-wei |
| |
| Affiliation: | ( College of Information Science and Technology, Xiamen University, Xiamen 361005, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | multi-dimensional 0-1 knapsack problem ant colony algorithm exchange |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
