混合差异演化算法求解多维背包问题.pdfVIP

总第 255 期 2011 计算机与数字工穗 Computer . Digital Engineering 混合差异演化算法求解多维背包问题. 划署E骏1) 划大瑾2) VoL 39 No.l 10 〈南京工业大学电子与信息工程学院υ 南京 210089)(南京理工大学泰州科技学院2) 泰州 225300) 摘 要 提出了…种求解多维 0-1 背包问题的混合差异演化算法，算法使用了两个主要的思想策略，即依据物品单位 容积价值的高低选择物品的贪赞算法和基于工进制编码的差异演化算法。对 10 个测试算例进行了仿真试验，结巢表明文 章提出的算法可以快速找到这些测试算例的最优解，是求解多维背包问题的…种有效方法。 关键词 背包问跑 p 差异演化算法;贪婪算法 中图分类号 TP301. 6 Solution of Multidimensional 0-1 Knapsack Problem by Hybrid Differential Evolution Liu Jiajun l ) Liu Dajin 2 ) (Nanjing University of Technologyl), Nanjing 210089) (Nanjing University of Science and Technology2) , Taizhou 225300) Abstract Proposed a hybrid differential evolution to solve multidimensíonal 0-1 knapsack problem in this paper. The algorithm utilizes two important strategies, i.巳 how to select the item based on its average value and the binary dífferential evolution. The hybrid differentíal evolution is applied to 10 multidimensional 0-1 knapsack test instances and the experimental results show the proposed algorithm is rather efficient for solving multidimensional 0-1 knapsack problern. KeyWo民也 knapsack problem, differential evolution, greedy algorithm CI幽s Nt.n曲创丁P30 1. 6 1 号|窗 羔异演化算睐(Dífferential Evolution , DE) 是 …种藤于群体接异的演化算法[1] ，和其它进化算法 相比，接异演化算法具有以下优点:1)搓鼻演化算 法在求解非凸、多峰、非线性嗣敬优化问题表现极 强的稳健性。 2) 在同样的精度要要求下，握排演化算 法收她的班股快。的整异演化算挫尤其擅伏求解 多变蟹的幽费生优化问翩。 4) 操作简单.易编程实 现。它在首届 IEEE 演化计算大赛中表现皑群，随 质在各领域得到了广泛的应用LMJ ，并取得了大量 的研究成果。但这些研究成果主要是对各类连续 空间优化问题研究所取得的，但对南散问题的研究 却少之又少。 多维。-1 背钮是…充很典型的组合优化问酶， 研究它有很意要的实际意义，这不仅f是由于它结构 简洁，可以作为子问题为研究更复杂的问题藤定理 论革础，有很高的理论研究价假$而且由于它是许 多实际工程应用问题的一种通用化描述，在很多实 际问蹭鸣中有着非常广眨的应用带策，例如项目决 策与规划、资掘分配、货物装载、资金预算等工作。 对这一问腿许多学者利用不阔的思想提出了各种 各样的算法。 2002 年 .Plateau A 等将内点法 (in- terior point methods)和超启发式(metaheuristics) 结合阳得到了一种求解。1 线性规划的混合有哪些信誉好的足球投注网站 算法[5] 0 2005 年. Vasquez M 等将线性规划和禁 ·收稿日期 :2010 年 7 月 30 日.修四日期 :2010 年 8 月 31 日 作者简介:刘家骏.男.研究方向 2计算机软件.刘大瑾，男.副教授，研究方向 2应用数学. 2011 年第 1 期 计算机与数字工穰 11 忌有哪些信誉好的足球投注网站算怯结合越来，而得到了 LP十TS 算法，在 此基础上，阴定某些变元的值而得到一种比 LP十 TS 性能更好的启发式算法 fix+LP+TS[6). 2005 年，杜梅l峰等提出了基于细胞克陆选拇学说的人工