遗传算法
遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。

它从一组随机产生的初始解称为“种群”，开始搜索过程。

种群中的每个个体是问题的一个解，成为“染色体”是一串符号。

这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。

选择的原则是适应度越高,被选中的概率越大。

适应度越低，被淘汰的概率越大。

每一代都保持种群大小是常数。

经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。

这一系列过程正好体现了生物界优胜劣汰的自然规律。

比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解：
下续（表格）
下续……
即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。

如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。

当然，在实际中每代的个体和杂交的数量是比较大的。

遗传算法的具体的步骤如下：
1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。

为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。

每个解的基因数量是要通过实验确定的。

2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。

N个个体，构成了一个群体。

GA以这N个串结构数据作为初始点开始迭代。

这个参数N需要根据问题的规模而确定。

3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。

由交换概率(
P)挑选的每两个父代
c
通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。

可以得到新一代个体，新个体组合了其父辈个体的特性。

交换体现了信息交换的思想。

4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。

适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。

这个判据的选取是GA的关键所在。

5.选择（selection）：选择的目的是为了从交换后的群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。

遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献的概率大，选择实现了达尔文的适者生存原则。

本文直接选取交换后的群体中具有最大适应度的前N个个体作为下一代进行繁殖。

这一步骤的存在使得当前群体是所有搜索过的解之中是最优的前N个的集合。

6.变异（mutation）：变异首先在群体中随机选择一定数量个体，对于选中的个体以一定的概率（成为变异概率
P）
m
随机地改变串结构数据中某个基因的值。

同生物界一样，GA 中变异发生的概率很低，通常取值在0.001~0.01之间。

变异为新个体的产生提供了机会。

7.中止。

规则有三种情况：
(1)给定一个最大的遗传代数MAXGEN(人为事先确定)，
算法迭代在达MAXGEN时停止。

(2)给定问题一个下界的计算方法，当进化中达到要求的
偏差ε时，算法终止。

(3)当监控得到的算法再进化已无法改进解的性能，即解
的适应度无法再提高，此时停止计算。

遗传算法有如下特点：
1.遗传算法的处理对象不是参数本身，而是对参数集
进行了编码的个体。

此操作使得遗传算法可直接对
结构对象进行操作。

2.传统搜索算法都是单点搜索算法，容易陷入局部的
最优解。

遗传算法同时处理群体中的多个个体，即
对搜索空间中的多个解进行评估，减少了陷入局部
最优解的风险，同时算法本身易于实现并行化。

3.求解时使用特定问题的信息极少，容易形成通用算
法程序。

由于遗传算法使用适应值这一信息进行搜
索，并不需要问题导数，空间连通、凸性等与问题
直接相关的信息。

遗传算法只需适应值和串编码等
通用信息，解的定义域可任意混合，故几乎可处理
任何问题。

4.选择、交叉和变异都是随机操作，而不是确定的精
确规则。

这说明遗传算法是采用随机方法进行最优
解搜索，选择体现了向最优解迫近，交叉体现了最
优解的产生，变异体现了全局最优解的覆盖。

具有自组织、自适应自学习性。

遗传算法利用进化过程获得的信息自行组织，搜索时硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。