蚁群算法求解多选择整数背包问题.pdfVIP

与 科研探索 知识创新 蚁群算法求解多选择整数背包问题 □ 田志波 （茂名学院 广东·茂名 525000 ） 摘 要： 本文针对一维、二维多选择整数背包问题的数学模型，采用动态规划和蚁群算法对其进行求解，并对蚁群 算法作了适当的改进。 随机数据实验表明，随着问题规模的扩大，动态规划算法的计算复杂度将急剧增大，造成求解 困难，而基本蚁群算法及改进蚁群算法能够快速有效地求得问题近优解，且改进蚁群算法解的质量比原算法平均提 高了 2.8%。 关键词： 多选择整数背包 动态规划 蚁群算法 中图分类号： 文献标识码： 文章编码： （ ） TP14 A 1007-3973 2009 06-101-03 1 引言 背包问题（Knapsack Problem ）是运筹学中一个典型的 3 动态规划算法求解多选择整数背包问题 [1] 优化难题，属于NP-hard 问题 。 对于规模较大的背包问题， 动态规划是运筹学的一个分支， 它是解决在时间过程 精确求解会产生组合爆炸，求解过程将会花费漫长的时间， 中，依次分阶段的选取一些决策，来解决整个多阶段决策的 怎样能快速有效的求解背包问题一直是人们研究的课题。 动态过程最优化的一种数学规划方法。 其主旨思想是将一 目前该问题的算法大致可分为两类：精确算法，如动态 个多级决策的问题巧妙地转化为一系列互相联系的单阶段 规划、分支定界、隐枚举法、回溯法和切割平面法等，由于该 决策问题，然后逐个加以解决。 类算法计算量是指数时间的，故当规模较大时，在实效上不 维多选择整数背包问题的动态规划算法设计如下： 实用；启发式算法，如模拟退火（ ）、噪声算法（ ）、约束 划分阶段 ：将供选择的物品按 … 排序，每个 SA NM (1) k 1,2, ,n 满意（TA ）、神经网络（NN ）、遗传算法（GA ）、贪婪算法、La- 阶段可装入一种物品； 算法、禁忌有哪些信誉好的足球投注网站（ ）[2] 等；以及上述这些方法的结合， 确定决策变量： ，装入第 种物品的件数； ，背包中 grange