蚁群算法求解多维0_1背包问题

CN43 -1258/T P ISSN 1007 -130X 计算机工程与科学 COMPUTER ENGINEERING NP -完全问题; 整数规划; 背包问题 Key words: ant colony algorithm; NP -complete; integer programming; knapsack problem 中图分类号: T P311文献标识码: A 1 引言 背包问题( Knapsack Problem) 是典型的组合优化问 题, 它极大地吸引了理论研究人员和实际工作者的注意力。 理论方面研究兴趣来自于该问题简单的结构, 这种特点既 可以深入探索许多组合特性, 又可以通过解决一系列背包 子问题来最终求解更为复杂的优化问题。从实践的角度来 看, 这些问题可以表述许多工业场合的应用, 最典型的应用 如资金预算、 货物装载、 存储分配和密码加密等 1。 蚁群优化算法是 20 世纪 90 年代才提出的一种新型的 模拟进化算法 2, 3, 它是由意大利学者 M. Dorigo 等人首 先提出的, 称为蚁群系统 ( Ant Colony System) , 并应用该 算法求解 TSP 问题、 分配问题、 Job -shop 调度问题, 取得了 较好的结果。受其影响, 蚁群系统模型逐渐引起研究者的 注意, 并用该方法求解一些实际问题。近几年, 在欧、 美召 开的有关会议上, 蚁群优化算法已成为研究的热点之一。 对此, 我们在文中针对多维 0/1 背包问题的特点设计了基 于二进制编码的有向图遍历的蚂蚁算法。 2 多维背包问题的数学模型 多维背包问题是带有一组约束的背包问题, 其描述如 下: 存在重量分别为 W 1 , W 2 , , W n 和价值相应为 V1, V2, , V n的 n 个物品以及负重为 C1 , C2 , , C m 的 m 个背包。要将尽量多的物品放入背包, 在确 保每个背包中物品不超出承重的前提下满足最大化背包中 物品的总价值。这里设 X i j 为二进制变量。如果物品 i 被放入背包 j 则X i j = 1, 否则 X i j = 0。则多维 背包问题的数学描述如下: max = E m j = 1 E n i= 1 Vi Xi j E m j = 1Xi j 1, E m i= 1W iX i j Cj , X i j I 0, 1, i = 1, 2, , n, j = 1, 2, , m。因此, 背包问题是一个特殊的 整数规划问题, 也是一个 NP 难题。对于多维的背包问题, 在确定一个物品最多只能放入一个背包条件满足下, 它的 时间复杂度为 O(2m n) 。在现实生活中, 使用背包理论解决 78 *收稿日期: 2005 -01 -20; 修订日期: 2006 -06 - 02 基金项目: 国家自然科学基金资助项目( 60472099) 作者简介: 熊伟清( 1966 ) , 男, 浙江丽水人, 副教授, 研究方向为进化计算和软件工程。 通讯地址: 315211 浙江省宁波市宁波大学计算机科学与技术研究所; T el: ( 0574) 87605806; E -mail: xwqdds tom. com Address:Institute of Computer Science and T echnology, Ningbo University, Ningbo, Zhejiang 315211, P. R. China 的一些实际问题都具有相当大的规模, 需要寻找一些可行 的方法尽可能快地寻找较优的解4。 3 蚁群系统模型 现以求解 n 个城市的对称 T SP 问题为例, 说明蚁群系 统模型。 初始时刻, 各条路径上信息量相等, 设 Si j(0) =C( C 为常数 )。蚂蚁 k( k= 1, 2, , m) 在运动过程中根据各条 路径上的信息量决定转移方向。移动概率 Pki j是在 t 时刻 蚂蚁 k 由位置 i 转移到位置 j 的概率: Pki j= SAij(t) # GBij( t) E S I allowedk SAis( t) # GBis( t), j, s I allowedk 0, otherwise ( 1) 其中, m 是蚁群中蚂蚁的数量, A是轨迹的相对重要性(A 0 ) ,B是能见度的相对重要性 (B0 ), Gi j是边弧 ( i, j ) 的 能见度, Si j是 t 时刻在 ij 连线上残留的信息量, allowedk = 0 , 1 , , , n- 1 - tabuk表示蚂蚁k 下一步允许选择 的城市。 与实际蚁群不同, 人工蚁群系统具有记忆功能, tabuk ( k= 1, 2, , m) 用以记录蚂蚁 k 当前所走过的城市, 集合 tabuk随着进化过程作动态调整。Q是轨迹的持久性 ( 0 Q 1 ) , 随着时间的推移, 以前留下的信息逐渐消逝, 用参数 1- Q (表示信息消逝程度。经过 n 个时刻, 蚂蚁完成一次循 环。各路径上信息量要根据下式作调整: Si j(t+ n) = Q# Si j( t) + ( 1- Q ) # $ Si j( 2) $ Si j= E m k= 1 $ Skij( 3) 其中, $ Skij表示第 k 只蚂蚁在本次循环中留在路径 ij 上的 信息量, $Sij表示本次循环中路径ij 上的信息量的增量: $Skij= Q / Lk, 若第 k 只蚂蚁在本次循环中经过 ij 0, 否则 ( 4) 其中, Q 是体现蚂蚁所留轨迹数量的一个常数, Lk表示第 k 只蚂蚁在本次循环中所走路径的长度。在初始时刻, Sij( 0) = c, $Sij= 0, i, j = 0, 1, , n- 1。Gij表示城市i 转移到城市 j 的期望程度, 可根据某种启发式算法具体确定。根据具 体算法的不同, Sij(t) 、 $Sij( t) 及 P k ij的表达形式可以不同, 需要根据具体问题而定。 4 多维 0/ 1 背包问题蚁群算法的设计 4 11 编码设计 首先要对多维背包问题的解进行编码。上面已经提到 的多维背包问题的数学模型为一个 0/ 1 整数规划。对于 m 个背包n 个物品, 其解空间为 m n 的矩阵。在这个矩阵 中, 当 X i j = 1时, 表示物品 i 放入背包j ; 当 X i j = 0 时, 表示物品 i 不放入 j 。对于 X i j 这个基因就只存 在这两种情况, 因此使用二进制字符串编码。使用长度为 m n位的二进制字符串构成的矩阵来表示一个个体。 另外, 由于考虑到编码长度过长对算法效率的影响, 我 们对于多维 0/ 1 背包问题采用了分工的蚂蚁算法5, 即蚂 蚁根据维数的不同分成相应功能的蚂蚁, 在各自维中遍历。 4 12 做出有向图 G 定义有向图 G =(C, L)。其中, 顶点集 C 为 c0( vs) , c1( v0N) , c2( v1N), c3( v0N- 1), c4( v 1 N- 1), , c2N - 3( v 0 2), c2N- 2 (v 1 2) , c2N- 2( v 1 2), c2N- 1( v 0 1) , c2N( v 1 1) , vs为起始顶点, 顶点 v0j和 v 1 j分别用于表示二进制码串中位 bj取值为 0 和 1 的 状态。有向弧集合 L 为( vs, v 0 N), ( vs, v1N) , ( v0N, v0N- 1) , (v 0 N, v1N- 1) , ( v1N, v 0 N- 1) , ( v1N, v1N - 1) , , ( v02, v01), ( v 0 2, v11) , (v 1 2, v 0 1) , ( v 1 2, v 1 1) , 即对于 j = 2, 3, , N, 在所有顶点 v 0 1和 v11处分别有且只有指向 v 0 j- 1和 v1j- 1的两条有向弧, 如图 1 所示。多维 0/ 1 背包问题求解对应多个如图 1 所示的有向 图。由于是二进制编码, 蚂蚁无需具有记忆功能, 只需根据 面对的两条边留下的信息素大小选择。 图 1 二进制编码对应的有向图 4 13 初始化 随机产生 m 个初始解, 计算这 m 个初始解的适应度, 由这 m 个初始解得到各个分量值的候选组, 并根据候选组 中的值按它们所在解的适应度计算其信息量。 4 14 蚂蚁状态转移规则 第 k 只蚂蚁按以下概率从状态 i 转换到状态j : j = maxSAis# GBis, s Iallowedk, if r p0 依概率 pkij选择 j , else (6) 其中, p0I ( 0, 1) , r 是( 0, 1) 中均匀分布的随机数, 由此增 加了所得解的多样性, 在一定程度上削弱了蚁群陷入局部 最优的趋势。Sij( t)表示第 i 个分量候选组中第 j 个值的信 息量。 4 15 信息量全局更新规则 文献6提出信息量的全局修正规则如下: Sij(t+ n) = Q# Sij(t) + (1- Q) # $Sij(7) $Sij= $Skij, 第 k 只蚂蚁是发现本次循环中最短路径的 蚂蚁。$Skij按 (4)式求得。全局修正规则只是让实现最好 环游的蚂蚁释放信息素。它和改进的状态转移规则结合的 搜索保证了蚂蚁在优秀父辈完成的环游的领域内进行更多 搜索, 使得求解速度大大提高。 4 16 引入变异 引入遗传算法的变异算子, 以变异率随机选择一位由 / 10变为/ 00, 或由/ 00变为/ 10。经过变异后的解如果好于 当前最优解, 则保留, 否则淘汰。 4 17 适应度函数和终止条件 背包问题中个体的适应度函数是由个体解确定的所有 背包中物品的总价值来决定的, 即: f = E m j= 1 E n i= 1 V i X i j 终止条件: 进化一定的代数后。 (下转第 86 页) 79 2 Jean -Francois Boulicaut, Baptiste Jeudy. Mining Free Itemsets Under Constraints A . Proc of the Int. l Database Engineering & Applications Symp C. 2001. 322 -329. 3 R Srikant, R Agrawal. Mining Quantitative Association Rules in Iarge Relational Tables A . Proc of the 1996 ACM SIGMOD Int. l Conf on Management of Data C. 1996. 1 -12. 4 Mohammed J Zaki. Sequence Mining in Categorical Domains: In - corporating Constraints C . Proc of the 9th Int. l Conf on Infor - mation and Knowledge Management C . 2000.422 -429. 5 Salvatore Orlando, Raffaele Perego, Claudio Silvestri. A New Algorithm for Gap Constrained Sequence Mining A . Proc of the 2004 ACM Symp on Applied Computing C. 2004. 540 -547. 6 Mohammed J Zaki. SPADE: An Efficient Algorithm for Mining Frequent Sequence J . Machine Learning, 2001, 42( 1 - 2) : 31 -60. 7 Jian Pei, J Han, B Mortazav- i Asl, et al. PrefixSpan: Mining Se - quential Patterns Efficiently by Prefix-Projected Pattern Growth J. IEEE Trans on Knowledge and Data Engineering, 2004, 16 (11) : 1424 -1440. ( 上接第79页) 4 18 非法个体修正算子 在种群初始化产生新个体过程中不可避免地会产生一 些非法的个体。为了保持种群中个体的合法性, 就需要对非 法的个体进行修正, 以获取合理的、 优良的个体。 在初始化种群阶段, 在个体基因位变换过程中对解进行 实时判断修正, 即当将一个基因位置 1 时, 判断是否打破约 束, 如果约束被破坏则重新置 0。 在变异阶段防止非法个体产生的方法和初始化种群阶 段相类似, 只需在个体的基因产生变异时判断约束是否被打 破: 如果约束被破坏, 则取消变异。 5 仿真实例 在本实例中, 假设一个由 100个物品以及三个背包组成 的背包问题。为了对测试结果的分析更加直观方便。在这 里, 假设所有物品的价值密度相同, 即将这里的整数 0/1 背 包问题简化为在不超出各个背包容量的情况下最大化所有 背包内物品的总质量, 即要求的价值最大, 简化为质量最大 ( 这里的质量都是整数的)。在这里给出的 100 个物品的质 量如表 1 7 所示, 而三个背包的容量分别为 c1 = 3 398、 c 2= 1 327、 c3 = 1 873。 表 1 物品质量表 253245243239239239238238237232 231231230229228227224217213207 203201195194191187187177175171 169168166164161160158150149147 141140139136135132128126122120 119115116114111110105105104103 93929079787776767573 62626160605957565353 51504444424238363428 2724221812107441 在这个实例中具有 100 个物品以及三个背包。取 A = 1, B = 2, Q = 0 135, Q= 1 10, p0= 0 1 35, Pm= 0 1 1。具体测试情况 如下: (1) 单背包问题测试: 使用仿真实例的数据, 仿真处理 100 个物品的单背包问题, 背包的容量为 c1= 3 398。 每次运行可以得到总承重为 3 398, 参数选取为 m(蚂蚁 数目) = 20, 进化代数 200 时并且运行时间也相当短。可以 说, 此算法在解决单背包问题时具有相当好的效果。 (2) 二维背包问题测试: 选取 c1 = 3 398、 c2= 1 327 两个背包, c1+ c 2= 4 725。在这里测试的 m( 蚂蚁数目) = 40, 蚂蚁分工为两种, 每一维 20个蚂蚁遍历。进化代数为 300。每次运行可以得到 4 725, 并且测试中进行运算的平均 时间也比较短。 (3) 三维背包问题测试: 使用了仿真实例中所有的三个 背包 c1 = 3 398、 c2= 1 327、 c3= 1 873, c1+ c 2 + c 3 = 6 598。在这里测试的 m( 蚂蚁数目) = 60, 蚂蚁分工为 三种, 每一维 20个蚂蚁遍历。进化代数为 600, 每次运行都 可以得到 6 598。 通过以上这三种背包问题的测试, 说明本文设计的蚂蚁 算法对于单维以及多维背包问题都是有效的, 虽然当维数增 加时寻找最优解的效率会以比较快的速度降低。但是, 对于 高维的背包问题使用一定规模的种群大小及最高进化代数 总能寻找到背包问题的最优解, 而且出现最优解的概率是比 较稳定的。 6 结束语 本文针对多维 0/ 1背包问题的特点设计了基于二进制 编码的有向图遍历的蚂蚁算法。通过仿真实例表明, 此算法 对于多维的 0/ 1背包问题结果具有比较高的性能, 表明应用 蚂蚁算法时合理的编码及恰当的变化算子设计对解决问题 是非常重要的。 0/ 1背包问题是一个 NP 难题, 而所有的 NP 难题都具 有一定的共性。本文使用蚂蚁算法比较高效地解决了多维 0/1 背包问题, 这说明只要对蚂蚁算法