多维背包问题一个蚁群优化算法.pdf

第 3 1 卷 　第 5 期 计 　　算 　　机 　　学 　　报 Vol . 3 1 No . 5 2008 年 5 月 C H IN ESE J OU RN AL O F COM PU T ER S May 2008 　 多维背包问题的一个蚁群优化算法 喻学才 　　张田文 ( 哈尔滨工业大学计算机科学与技术学院　哈尔滨 　15000 1) ( ) 摘 　要 　蚁群优化 A CO 是一种通用的启发式方法 , 已被用来求解很多离散优化问题. 近年来 , 已提出几个 A CO ( ) 算法求解多维背包问题 M KP . 这些算法虽然能获得较好的解但也耗用太多的 CPU 时间. 为了降低用 A CO 求解 M KP 的复杂性 ,文章基于一种已提出但未实现过的 M KP 的信息素表示定义了新的选择概率的规则和相应的基于 背包项的一种序的启发式信息 ,从而提出了一种计算复杂性较低 、求解性能较好的改进型蚁群算法. 实验结果表 明 ,无论串行执行还是虚拟并行执行 ,在计算相同任务时 ,新算法耗用时间少且解的价值更高. 不仅如此 ,在实验 中 ,文中的新算法获得了 ORL IB 中测试算例 525022 的两个“新”解. 关键词 　蚁群优化 ;信息素模型 ;启发式信息 ;组合优化 ;多维背包问题 中图法分类号 TP3 16 An Improved Ant Algorithm f or Multidimensional Knapsack Problem YU XueCai 　ZHAN G TianWen ( ) S chool of Comp uter S cience an d Technology , H arbi n I ns t it ute of Technology , H arbi n 　15000 1 Abstract 　A nt Colony Op timization (A CO) i s a met aheuri stic . A nd it ha s been app lied to many har d di scret e op timization p roblem s. Recent ly , so me re searcher s have p rop o sed several diff erent A CO algorit hm s to solve t he multidimen sional knap sack p roblem ( M KP) , w hich i s an N Phar d co mbinatorial op timizatio n p roblem . Alt hou gh t he se algorit hm s could obt ain goo d solution s of M KP , t hey con sum