与一些传统的优化算法相比较，作为一种比较新的全局优化搜索算法，遗传算法凭借其简单通用、易于并行处理、鲁棒性强以及效率高等特点而受到欢迎，因而广泛应用于各个领域，并取得了良好的绩效[1]。目前，遗传算法等一些近似算法求解效率高，求解效果佳，因而越来越受到研究工作者的支持和重视，各国研究者努力寻求高速有效的近似算法。文献[13]-[15]介绍了一些算法求解0/1背包问题的实例。近年来，基于遗传算法对0/1背包问题的求解方面的研究是相当活跃的，遗传算法凭借其简单通用、全局寻优能力强等优点，在求解0/1背包问题上显示了巨大的优势[2]。

1。 0/1背包问题和遗传算法

1。1 0/1背包问题

0/1背包问题是最基本的背包问题，问题描述为：

现有件物品，一个容量为的背包。设第件物品的重量为，价值为。已知对一件物品必须选择取（用1表示）或不取(用0表示)，并且每件物品只能被取一次(这就是“0”或“1”的含义)。最后求放置哪几件物品进背包，使得背包中物品的价值最大？

此问题可形式化表示为：给定背包容量，其中每个物品的重量和价值，，求解表示物品是否放入背包的n元0/1向量(，，…，)。（0，1），，使得它们满足：

物品价值：物品重量：文献综述

由以上叙述可以看出，求解0/1背包问题的解，实质上也就是求解向量=(，，…，)中的取值（0或1），所以的取值可能是{0，0，…，0}，{0，0，…，1}，…，{1，1，…，1}，共种取值。所以可以看出，当的取值比较大时，的取值会很多，这种精确式的方法是不可取的。

1。2 遗传算法

遗传算法(Genetic Algorithm，GA)是由美国密歇根(Michigan)大学的心理学教授计算机科学和电子工程学教授John H。Holland首先提出的，它是一种随机自适应的全局搜索算法。且早在1962年，Holland就提出了关于遗传算法的基本思想。但遗传算法的数学框架和理论基础直到20世纪70年代初才形成。它是基于生物进化理论中的自然选择、适者生存以及物种遗传思想的一种搜索算法。遗传算法是将问题的每一个可能解看作是种群中的一个个体(即染色体)，并且将每个染色体用编码成串的形式，然后根据预定的目标函数对每个个体（染色体）进行分析，从而给出一个适应值。遗传算法将根据得到的适应值来进行寻优过程。遗传算法的是通过选择、杂交、变异等遗传算子来具体实现寻优过程的，它的搜索能力是由选择算子和杂交算子决定，而变异算子的功能则是能够保证算法能够搜索到问题空间的每一个点，从而使其具有搜索全局最优的能力[3]。遗传算法很好地吸收了工程学科与生命科学中的重要理论成果，用于解决一些复杂的优化问题。遗传算法是一个举足轻重的分支，其性能不断地得到改进和完善，算法的应用涉及到更加广阔的领域并展现出很好的解决问题的能力，目前，遗传算法的应用范围已经延伸到多个领域和多个学科之中。其思想源于生物科学的进化理论和遗传变异理论，是通过模仿自然界的进化活动，设计出能够有效解决优化问题的系统方法。

2。用遗传算法求解0/1背包问题

2。1简单遗传算法

遗传算法吸收了工程学科与生命科学中的重要理论成果，用于解决一些复杂优化问题。其中，达尔文(Dariwin)的进化理论和以孟德尔(Mendel)的遗传学说为基础的现代遗传学对算法的提出具有最为重要的影响。

地球上的生命自诞生以来，就一直处于漫长而深远的进化历程，经历了从单一到多样、从低级到高级、从简单到复杂、从缺陷到完善的发展过程。达尔文的进化论提出了自然界“自然选择”和“优胜劣汰”的基本进化规律；以孟德尔的遗传学说为基础的现代遗传学提出了遗传信息的重组模式。来:自[优E尔L论W文W网www.youerw.com +QQ752018766- 基于遗传算法求解0/1背包问题(2):http://www.youerw.com/shuxue/lunwen_99402.html