基于贪心遗传算法求解0-1背包问题-论文.pdf

《基于贪心遗传算法求解0-1背包问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、-’I_TJ二u斗平常二否常斗ElectronicSci．＆Tech．／Apr．15．2014基于贪心遗传算法求解0．1背包问题姚文鹃，吴菲，夏倩，邵彪，张龙忠，刘剑(兰州交通大学交通运输学院，甘肃兰州730070)摘要在解决0—1背包问题中，将贪心算法和遗传算法相结合，提出了贪心遗传算法。通过算法构造出更优的新算子，与原有算子相比，既加快了算法的收敛速度，又克服了传统方法容易陷入局部最优的特点，提高了搜索效率。通过计算机仿真试验结果表明，贪心遗传算法相比普通的遗传算法具有更好的近似解，充分证明了贪心遗传算法来求解背包问题的有效性和实用性。关键词背包问题；遗传算法；贪心算法；贪·遗

2、传算法中图分类号TP301．6文献标识码A文章编号1007—7820(2014)04—051—03Solutionto0-IKnapsackProblemBasedontheGreedy-geneticAlgorithmYA0Wenjuan，WUFei，XIAQian，SHAOBiao，ZHANGLongzhong，LIUJian(SchoolofTrafficandTransportation，LanzhouJiaotongUniversity，Lanzhou730070，China)AbstractAgreedy—geneticalgorithmisproposedcombin

3、inggreedyalgorithmsandgeneticalgorithms．Thea1一gorithmconstructsanewandbetteroperatorthantheoriginalone．Itnotonlyacceleratestheconvergencespeedbutalsoavoidsthelocaloptimumtrapofthetraditionalmethod，thusimprovingsearcheficiency．Thecomputersimula-tionresultsshowthatthegreedygeneticalgorithmhasbet

4、terapproximatesolutionsthantheaveragegeneticalgo—rithms，demonstratingtheeffectivenessandpracticalityofgreedy—geneticalgorithmsinsolvingtheknapsackprob—lem．Keywordsknapsackproblem；greedyalgorithm；geneticalgorithm；Greedy—Genetiealgorith近年来，背包问题⋯吸引了许多理论科学家和实品，使得在有限的容量内装人物品的价值最大。际工作者对其进行深入的研究。在结构方

5、面，背包问问题的一般可表示为0—1整数规划问题题形式看似简单，但其却有组合爆炸的性质。如今，在maxf(x2，⋯)=∑P实际工作中，越来越多的领域运用到了背包问题。求解背包问题的方法可分为启发式算法，如贪心目标函数算法、模拟退火算法、蚁群算法；最优化算法，如动态规划算法、回溯法、分支定界法等J。这些算法均能找到s．tflWiXi≤Ci相应的最优解，但也均有各自的局限性及缺陷。∈{0，1}，i=0，1，2，⋯本文介绍了贪心算法和遗传算法求解0—1背包其中，为0—1决策变量；=1表示将物品装入背问题，并在其基础上提出基于贪心算法的遗传算法来包；=0表示不将物品装入背包中。解决背包问题。

6、2问题求解方法最后，运用计算机仿真技术来验证混合遗传算法的设计。这样，即克服了传统算法的缺陷，又加快了算2．1贪心算法法的收敛性，可得到更好的最优解。贪心算法属于启发算法，即通过问题的初始状态，1背包问题经若干次的贪心选择而得出最优的一种解题方法]。贪心算法每一步只需考虑一个数据，因此所背包问题的一般提法为：已知n个物品的重量得出的解只是某种意义上的局部最优解。w和价值P分别为W>0和P>0，背包的容量C。背2．2遗传算法包的容量C>0，其中，1，2，3，4，⋯，则如何选择物遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自适应全局概率搜索算收稿日期：2013—1

7、0—08法]。其将问题的每一个可能解看作是群体中的一个作者简介：姚文鹃(1988一)，女，硕士研究生。研究方向：管理科学与工程。E—mail：Winnie—xwj@126．com个体，并将每个染色体编码成串的形式，通过选择个WWW．dianzik~ji．0rq——51姚文鹃，等：基于贪心遗传算法求解0—1背包问题体，并预定目标对个体进行评价，给出一个适应值2J。新的染色体Y。通过选择，杂交和变异，从而获得全局最优解J。Step4在y中以P()的概率选择出适应度差虽然遗