基于遗传算法求解0-1背包问题的算法探讨 - 云南民族大学学报.pdf

第 17卷 　第 4 期 ( ) 云南民族大学学报 自然科学版 Vol. 17　No. 4 2008年 10 月 　　 ( ) Journal of Yunnan N ationalities U n iversity N atural Science s Edition O ct. 2008 基于遗传算法求解 0 - 1背包问题的算法探讨 刘 　锐 　张金波 　刘蕊洁 　李积宪 (兰州交通大学 数理与软件工程学院 , 甘肃 兰州 730070) 摘 　要 　0 - 1背包问题是一类典型的组合优化问题 ,并且是 N P完全问题 ,具有重要的研究意义. 介绍了贪婪算法和基本 遗传算法求解背包问题的设计思想 ,提出了基于贪婪算法的混合遗传算法求解 0 - 1背包问题. 实验结果表明改进的遗传算法 有更好的近似解. 关键词 　遗传算法 ;贪婪算法 ; 0 - 1背包问题 【中图分类号 】TP3016 【文献标识码 】A 【文章编号 】1672—8513 (2008) 04 - 0377 - 03 On the A lgorithm of Solving the 0 - 1 Knap sack Problem Based on the Genetic A lgorithm L iu Ru i　Zhang J inbo　L iu Ru ij ie　L i J ixian ( Schoo l of M athem atic s, Physic s and Software Engineering, L anzhou J iaotong U n iversity, L anzhou 730070 , Ch ina) A b stract: The 0 - 1 knap sack p rob lem is a typ ical k ind of com b inatorial op tim ization p rob lem s and is related to N P - comp lete, who se re search ha s great sign ificance. The greedy algorithm and the ba sic genetic algorithm for so lving the 0 - 1 knap sack p rob lem are in troduced, and an imp roved genetic algorithm ba sed on the greedy algo rithm wh ich is u sefu l for so lving the 0 - 1 knap sack p rob lem is p ropo sed. The exp erim en t show s the re su lt that the imp roved genetic algorithm can p rovide better app roxim ate so lu tion s. Key word s: genetic algorithm ; greedy algorithm ; 0 - 1 knap sack p rob lem 0　引言 1　问题描述及基本算法介绍