求解01背包问题的烟花算法研究.pdfVIP

Vo l. 23 No.3 武汉工程职业技术学院学报 第23卷第3期 loum.1 ofWuh.n Engineering Institute September 2011 2011 年9 月 求解 0/1 背包问题的烟花算法研究 张家琴 (福建江夏学院电子信息科学系 福建福州:350108) 摘 要 0/1 背包问题是一个典型的 NP 难题，具有重要的理论研究价值，也具有广泛的应用基 础。借鉴北京大学关于烟花算法的新近成果，尝试考虑二者的结合，初步设计并实现了求解 0/1 背 包问题的烟花算法，开展了较为充分的实验，并作了相关分析与探讨。 关键词 0/1 背包问题;烟花算法;选择z 变异 中固分类号:TPI8 文献标识码:A 文章编号:1671-3524(2011)03-0064-03 自然启发的元有哪些信誉好的足球投注网站方法口-3] 是计算智能的研究 种文献对该问题的描述大同小异，本节通过自然语 言和形式化两种方法简要描述该问题。 重点，它具有高效的优化性能、无需问题特殊信息等 0/1 背包问题的自然语言描述如下z 对于给定 优点，在工程优化设计、计算机科学、组合优化、优化 的 1 个背包和 n 种不同物品，背包的容量是 c ，物品 调度等领域得到了广泛的应用。自然启发的元有哪些信誉好的足球投注网站 i 的重量是吭，物品 i 的价值是叭。每个物品 i 要么 方法主要由进化算法和群体智能算法这两类构成， 装入背包，要么不装入背包。物品 i 不能多次装入 其中，进化算法主要有遗传算法、遗传策略、进化规 背包，也不能只装入一部分。问应该选定哪些物品 划、进化策略、微分进化算法等，群体智能算法主要 装入背包，使得这些装入背包中物品的总价值最大? 有粒子群算法、蚁群算法、蜂群算法等。 0/1 背包问题的形式化描述如下z 对于给定的 c 烟花算法[4] 是北京大学谭营教授等人 2010 年 O ,WjO , VjO , l~i运n ，请找出一个 n 元的 0/1 新提出的一种隶属于群体智能算法这一类别的自然 向量(Xl X2 ，…， Xn) ， Xj=O 或 1 ， 1ζiζn，使得 启发的元有哪些信誉好的足球投注网站方法。跟经典的遗传算法不同的是z 烟花算法的选择算子侧重于多样性保持而非侧重于 ~WiXi 运 C ， 且~v品的值最大。采用整数规划方 择优，烟花算法的变异算子的变异率是 100% 而非 10% 以内，烟花算法中没有交叉算子。 法来描述的话，目标函数是 max艺uρ约束条件 i=1 程春英[5] 用经典的遗传算法求解 0/1 背包问