发布时间 : 星期三 文章论文-遗传算法的基本步骤【精品毕业设计】(完整版)更新完毕开始阅读ffc8d573df80d4d8d15abe23482fb4daa48d1d58
遗传算法
遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。
比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解：
下续（表格）
下续??
初始群体 判别值 8 7 4 10 第一次迭代 判别值 8 10 12 9 第二次迭代 判特征组合 别值 1,3,5,7,9 1,2,3,7,8 1,3,5,7,8 1,2,3,7,9 13 10 10 12 特征组合 特征组合 1,2,3,4,9 2,3,6,8,9 6,7,8,9,10 1,3,5,7,8 1,2,3,4,9 1,3,5,7,8 1,2,3,7,9 1,3,4,5,8 即设有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)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率(Pc)挑选的每两个父代通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。
4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。
5.选择（selection）：选择的目的是为了从交换后的群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献的概率大，选择实现了达尔文的适者生存原则。本文直接选取交换后的群体中具有最大适应度的前N个个体作为下一代进行繁殖。这一步骤的存在使得当前群体是所有搜索过的解之中是最优的前N个的集合。
6.变异（mutation）：变异首先在群体中随机选择一定数量个体，对于选中的个体以一定的概率（成为变异概率Pm）随机地改变串结构数据中某个基因的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。
7.中止。规则有三种情况：
(1) 给定一个最大的遗传代数MAXGEN(人为事先确定)，
算法迭代在达MAXGEN时停止。
(2) 给定问题一个下界的计算方法，当进化中达到要求的
偏差ε时，算法终止。
(3) 当监控得到的算法再进化已无法改进解的性能，即解
的适应度无法再提高，此时停止计算。