差异演化算法求解多维0_1背包问题_第1页
差异演化算法求解多维0_1背包问题_第2页
差异演化算法求解多维0_1背包问题_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第 12 卷第 6 期2012 年 2 月 16711815( 2012) 06-1278-03 科学技术与工程 Science Technology and Engineering Vol. 12No. 6Feb 2012 2012Sci. Tech. Engrg. 差异演化算法求解多维 01 背包问题 张欣王志刚夏慧明 ( 南京师范大学泰州学院数学科学与应用学院, 泰州 225300) 摘要多维 01 背包问题是典型的 NP 难题。设计了一种求解它的差异演化算法, 阐述了算法求解多维 01 背包问题的 具体操作过程。用提出的算法对 55 个测试算例进行了仿真实验, 得到了全部算例的最优解。测试结果表明了算法是求解多 维 01 背包问题的一种有效方法。 关键词背包问题差异演化算法组合优化 中图法分类号TP301 6;文献标志码A 2011 年 12 月 1 日收到 第一作者简介: 张欣, 女。徐州人。E- mail: 252941329 qq com。 多维 01 背包问题是运筹学中一个典型的具 有 NP 难度的组合优化问题, 有着广泛的实际应用 背景, 例如投资决策、 资源分配、 项目选择、 货物装 载、 材料切割等问题。研究它有很重要的实际意 义。求解这一问题的算法很多, 如遗传算法 1, 2 、 免 疫算法 3 、 禁忌搜索算法4 、 蚁群算法5 、 DNA 计 算 6 等, 但到目前为止还没有很好的算法解决该 问题。 多维 01 背包问题的形式化描述如下: max n j =1 xjwj, s t n j =1 xjaij ci, i = 1, 2, , m, xj 0, 1 ,j = 1, 2, , n ( 1) 式( 1) 中 n 为物品的个数; m 为背包个数; wj为第 j 个物品的价值; ci为第 i 个背包的容积; aij为第 j 个 物品占用第 i 个背包的容积大小; xj= 1 表示第 j 个 物品装入背包, xj=0 表示不装入背包。 差异演化算法( Differential Evolution,DE) 是 Rainer Storn 和 Kenneth Prince 提出一种基于群体差 异的演化算法 7 , 属于直接搜索算法。差异演化算 法具有收敛速度快、 操作简单, 易编程实现, 极强的 稳健性等优点, 在连续问题的优化中得到了广泛的 应用, 并取得了大量的研究成果, 但在离散优化领 域的研究和应用却相对较少。本文尝试利用差异 演化算法的优点, 用其来求解多维 01 背包问题。 通过与粒子群优化算法以及文献 3 中的实验结果 进行对比, 表明本文提出的算法在求解多维 01 背 包问题上是可行的和有效的。 1差异演化算法 差异演化算法是基于实数编码的进化演化算 法, 它与进化算法的结构很类似, 与进化算法的不 同在于产生新的后代方面, 差异演化算法采用一种 “贪婪” 的选择模式。在本文中, 我们选择文献 8 中提出的差异演化算法作为最好的版本, 这时的差 异信息对文章的算法最有效。差异演化算法也有 选择, 变异, 交叉等一些操作。它主要是由三个参 数来控制: N- 种群大小、 F- 变异比例因子和 CR- 交叉 常数。在每一代, 差异演化算法都保持 N 个个体的 种群, 通过不断的进化和迭代, 算法得到优化。算 法的操作步骤如下: 步骤 1: gen =0, 初始化参数 N, F, CR, 变量的维 数 D, 最大进化代数 maxgen 的值。 步骤 2: 初始化随机产生每个个体的位置 xij , 计 算并评估 f( xij) 。 步骤 3: 循环更新 步骤 3 1: 对每个种群个体 i, 产生随机整数 r1, r2, r3( 1, N) , 使 f( r1) f( ri) 且 r1 r 2 r 3i, 产 生另一个随机整数 jrand( 1, D) 。 步骤 3 2: xij candidate = ( xij+ xr1j) /2 + F( xr1jxij+ xr2jxr3j) , if ( rand( 0, 1) CR)or j = jrand xij, otherwise ( 2) 步骤 3 3: 对每个个体进行评估并更新。 步骤 4: 如果满足中止条件, 退出, 否则转向步 骤 3。 2求解多维 01 背包问题的差异演化算法 多维 01 背包问题是非连续的离散优化问题, 而上述的差异演化算法适用于连续优化问题。针 对多维 01 背包问题的具体特点, 本文采用次序表 达法 9 的方式进行求解: 将第 i 个个体的 D 维分量 ( i =1, 2, , N, D 为物品的个数) 按大小进行排序, 然后按照大小顺序依次向背包中装入物品, 直至超 出背包的容积限制。例如对于一个有 5 件物品的背 包问题, 假设种群中第 i 个个体为 xi= (1 2, 0 6, 3 2, 1 7, 0 3) , 按其分量的大小进行排序后, 装入 背包的顺序为 34251, 即先从第 3 个物品 开始装入, 再装入第 4 个物品, 依次下去, 直到超过 背包的容积限制为止。这样做不需要对差异演化 算法的公式进行构造, 也不需对运算规则进行重新 规定。与函数优化问题不同的是, 向量每一维分量 的上下界没有给出, 需要自己设定, 经过实验发现, 求得问题解的好坏和收敛性对上下界的变化不敏 感。本文中选取上界为 10, 下界为 10。 求解多维 01 背包问题的差异演化算法的步 骤如下: ( 1)gen =0, 初始化参数 F, CR, 种群大小 N, 物 品的个数 D, 最大进化代数 maxgen 的值; ( 2)初始化随机产生每个个体 xij, 采用次序表 达法计算并评估 f( xij) ; ( 3)循环更新 ( 3 1)对每个种群个体 i, 产生随机整数 r1, r2, r3( 1, N) , 使 f( r1) f( ri) 且 r1 r 2 r 3i, 产生另 一个随机整数 jrand( 1, D) ; ( 3 2)对种群个体按下式进行更新 xij candidate = ( xij+ xr1j) /2 + F( xr1j xij+ xr2j xr3j) , if( rand( 0, 1) CR) or j = jrand, xij,otherwise 。 ( 3 3)对每个个体用次序表达法进行评估并 更新; ( 4)如果满足中止条件, 退出, 否则转向( 3) 。 3仿真试验 对提出的算法用 55 个测试算例进行了仿真试 验, 与 Kennedy 等人 10 提出的二进制粒子群优化算 法( BPSO) 及文献 3提出的免疫优势克隆算法 ( IDCA) 进行了对比, 其中这 55 个测试多维背包算 例的数据可以在( http: / /people brunel ac uk/ mastjjb/jeb/orlib/files/mknap1 txt ( mknap2 txt)下 载。试验中种群规模取为 100, 最大进化代数均为 2 000, 重复试验 20 次, CR = 0 1, F = 0 5; BPSO 中 w =1、 c1= c2=2; 。表 1 为 3 种算法的对比结果, 表 1 中没有列出的问题本文算法每次都可以找到最优 解, BPSO 和 IDCA 也几乎次次都能找到问题的最优 解, 因此在这里就不做对比了。 表 1 中, T 表示在 20 次试验中获得已知最优解 的次数, AVE 表示获得最优解的平均值。从表 1 中 可以看出, 除了 WEING7 这个算例本文算法找到最 优解的次数不如 BPSO 和 IDCA 外, 其余算例本文算 法 20 次试验都找到了最优解。即使是对于 WE- ING7, 虽然本文算法找到最优解的次数较少, 但获 得最优解的平均值却优于 IDCA。从实验结果可以 看出本文算法是求解多维 01 背包问题的一种有 效方法。 表 1BPSO、 IDCA 和本文算法对测试算例的求解结果 测试算例BPSOIDCA本文算法 名称nm最优值TAVETAVETAVE HP23543 186143 182 123 150 5203 186 Knap3939510 618910 610 41410 6132010 618 PB23443 186163 183 433 154 9203 186 PB520102 13962 125 452 123 3202 139 PB737301 035201 03521 029 8201 035 WEING7 10521 095 44551 095 39861 095 382 141 095 394 6 WEISH06 4055 557185 555 45135 552205 557 WEISH23 8058 34488 342 268 341 9208 344 WEISH25 8059 939189 936 4129 937 4209 939 4结论 从促进差异演化算法在离散优化问题中应用 的角度出发, 本文设计了基于差异演化算法的方案 求解多维 01 背包问题。通过仿真实例的计算, 表 明了该算法求解多维 01 背包问题的可行性和有 效性。 差异演化算法的研究仍处于初期, 但从当前的 应用效果来看, 差异演化算法无疑具有十分光明的 前景, 进一步拓展差异演化算法新的应用领域仍是 一项非常有意义的工作, 今后将继续探讨差异演化 算法在求解离散优化问题中的进一步应用。 97216 期张欣, 等: 差异演化算法求解多维 01 背包问题 参考文献 1Sakawa M , Kato K Genetic algorithms with double strings for 0 1 programming problems European Journal of Operational Research, 2003; 144: 581597 2曾智,杨小帆,陈静, 等 求解多维 01 背包问题的一种改 进的遗传算法 计算机科学, 2006; 33( 7): 2225 3杜海峰, 焦李成, 刘若辰 免疫优势克隆算法 电子与信息学报, 2004; 26( 12): 19181924 4贺一, 邱玉辉, 刘光远, 等 多维背包问题的禁忌搜索求解 计 算机科学, 2006; 33( 9): 169172 5熊伟清, 魏平 二进制蚁群进化算法 自动化学报, 2007; 33 ( 3) : 259264 6刘毅, 宋玉阶 多维背包问题的 DNA 计算 生物数学学报, 2008; 23( 1): 180186 7Storn R,Price K Differential evolution a Simple and efficient heu- ristic for global optimization over continuous spaces Journal of Global Optimization, 1997; 11: 341359 8Price K Differential evolution vs the functions of the 2nd ICEO Proceeding of 1997 IEEE International Conference on Evolutionary Computation, 1997 9玄光男, 程润伟, 于歆杰, 等 遗传算法与工程优化 北京: 清华大 学出版社, 2004: 5557 10Kennedy J,Eberhart R C A discrete binary version of the particle swarm algorithm Proceedings of the World Multi- conference on Sys- temics, Cybernetics and Informatics,Piscataway,Nagoya Japan, 1997: 41014109 Solving Multidimensional 01 Knapsack Problem by Differential Evolution ZHANG Xin, WANG Zhi- gang, XIA Hui- ming ( School of Mathematics,Nanjing Normal University Taizhou College, Taizhou 225300, P R China) AbstractMultidimensional 01 knapsack problem is a typical NP problem A kind of special differential evolution for multidimensional 01 knapsack problem is designed,and the detailed realization of the algorithm is illustrated 55 multidimensional 01 knapsack test instances are tested by the produced algorithm,all instances achieve optimum solutions Experimental results demonstrate the proposed algorithm is rather efficient for solving multidimensional 01 knapsack problem Key wordsKnapsack problemdifferential evolution 檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸 combinational optimization ( 上接第 1271 页) An Novel Unambiguous Synchronization Scheme for BOC( n,n)Signals CHEN Xiang,QI Jia- min,CHEN Jia- pin ( Key laboratory for Thin Film and Microfabrication of Ministry of Education, Research Institute of Micro/Nano Science and Technology,SJTU,Shanghai 200240,P R China) AbstractThe Binary Offset Carrier ( BOC)has been used in many Global Navigation Satellite Systems But it makes acquisition more challenging and tracking potentiall

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论