一种改进的混合遗传算法求解0_1背包问题.pdfVIP

第 21卷 第 l4期 电子设计工程 2013年 7月 Vo1．21 No．14 ElectronicDesignEngineering Ju1．2013 一 种改进的混合遗传算法求解0_1背包问题 ’ 白东玲 ，郭绍永 (1．新乡It学院 计算机 中心，河南 新乡 453003；2．新乡医学院 现代教育技术 中心，河南 新乡 453003) 摘要 ：背包1-3题是组合优化 中的NP(Non—DeterministicPolynomia1)难题之一，论文将贪婪算法与遗传算法相结合提 出一种改进 的混合遗传算法来求解 0_1背包问题。改进 的混合遗传算法通过遗传算法的择优 ，重复执行选择、交叉和 变异以及贪婪算法的修正这样一个过程，使得所求解在可以接受的时间内越来越接近最优解。同时采用精英保留机 制来加快算法的收敛速度。最后通过实证明该改进的算法可 以有效地克服遗传算法中早熟的现象，该方法 同样也适 用其他优化 问题 。 关键词 ：遗传算法；贪婪算法 ；背包问题 ；精英选择 中图分类号 ：TP18 文献标识码 ：A 文章编号 ：1674—6236(2013)14—0o09一o3 An improvedhybridgeneticalgorithm for0 1knapsackproblem _ BAIDong-ling，GUO Shaoy·ong2 (1．Compu~rCen~r，XinxiangMedcidUnivers ，Xinxiang453003，China； 2．CenterofModemEducationTechnology，XinxiangMedicalUniversity，Xinxiang453003，China) Abstract：knapsackproblem isacombinatorialoptimizationofoneoftheNP．Thispaperproposesanimprovedhybridgenetic algorithm，whichiscomposedbygeneticalgorithm andgreedyalgorithm，forsolvingthe0-Iknapsackproblem．Th ehybrid geneticalgorithm repeatshteprocess，whichisdonebyselection，crossover，mutionandgreedyalgorihtm，untiltheoptimal solutionisfoundoutinareasonableamountoftime，usingtheelitism mechanism toacceleratehteconvergenceprocess．The experimentlresultsshowthattheimprovedGA effectivelyove~ometheprematurephenomenonandisalsosuitableforother combinatorialoptimizationproblems． Keywords：GeneticAlgorihtm(GA)；greedyalgorithm；knapsackproblem；elitismmechnaism 背包 问题 。【!(KnapsackProblem)属于典型的组合优化 问 不可撤 回的决策 。用贪婪算法求解背包 问题 的特点是每次迭 题 。研究组合优化 问题 的求解方法 已成为当前众多科学