遗传算法（Genetic Algorithm, GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。

遗传算法基本思想

核心是达尔文优胜劣汰适者生存的进化理论的思想。假设一个种群，通过长时间的繁衍，种群的基因会向着更适应环境的趋势进化，适应性强的个体基因被保留，后代越来越多，适应能力低个体的基因被淘汰，后代越来越少。经过几代的繁衍进化，留下来的少数个体，就是相对能力最强的个体了。

遗传算法借鉴了达尔文的进化论，是一种解决最佳化的搜索算法，具体步骤：

1、初始化

先初始化一堆染色体，也就是一组编码，常见的编码方式有二进制、浮点数编码。

2、适应度函数

根据要达成的目标进行一个适应度排序（比如求要求一个函数的最小值，那么染色体所代表的数据越小，适应度越高），适应度决定了下一个阶段--选择中它们被使用的概率。

3、选择

一种比较常见的选择方法是使用轮盘选择法，根据适应度算出每条染色体在轮盘上所占的面积（百分比），根据这个比例随机选取要操作的两个亲本染色体。

4、交叉

两个染色体各选取长度相等的一部分进行交换，得到两个新的染色体，当然交叉的发生是有一定概率的，这个概率是可以设置的。

5、变异

一条染色体的某一位发生变异，如0->1或1->0，变异的概率也是可以设置的。

6、对新生成的染色体和原有的染色体进行适应度评估，剔除适应度较小的染色体，如果不符合终止条件，则跳转至步骤3，这里的终止条件是达到了预定的遗传次数， 也就是适应度达到了要求。

遗传算法的特点

1、GA是对问题参数的编码组进行计算，而不是针对参数本身。

2、GA的搜索是从问题解的编码组开始搜素、而不是从单个解开始。

3、GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息。

4、GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。

遗传算法的优点

1、与问题领域无关且快速随机的全局搜索能力。

2、搜索从群体出发，具有潜在的并行性，鲁棒性高。

3、搜索使用评价函数启发，过程简单。

4、使用概率机制进行迭代，具有随机性。

5、具有可扩展性，容易与其他算法结合。

6、具有极强的容错能力。

遗传算法的缺点

遗传算法的编程实现比较复杂，对初始种群的选择有一定的依赖性，且局部搜索能力较差，导致单纯的遗传算法比较费时。在进化后期搜索效率较低。在实际应用中，遗传算法容易产生过早收敛的问题，采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。

遗传算法的应用

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。