基于蚁群优化算法的0-1背包问题求解

• 来源期刊: 系统工程学报
• 学科: 工学
• 关键词: 0-1背包问题 蚁群优化算法 组合优化
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 优化理论
• 页码范围: 520-523,529
• 页数: 5页
• 分类号: TH116
• 字数: 3430字
• 语种: 中文

摘要

蚁群优化算法在求解旅行商问题、指派问题、Job-shop调度问题和网络路由问题等获得了极大的成功.将蚁群优化算法应用于0-1背包问题,首先将0-1背包问题表示成相应的构造图,并针对该图设计了两个状态转移公式,蚂蚁根据这两个状态转移公式在带权图中移动直到死亡.此时,蚂蚁所走过的路径即构成背包问题的一个可行解.仿真实验对该算法的参数进行了讨论,再与遗传算法进行比较,结果显示该算法具有较高的性能.