遗传算法
遗传算法（GeneticAlgorithm,GA）是近几年发展起来的一种崭新的全局优化算法。它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。
1、基本思想
遗传算法（GeneticAlgorithm,GA）是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。
这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也即是假设解。然后，把这些假设解置于问题的“环境”中，也即一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制,淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，至到最适合环境的值。
遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。
2、术语说明
由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：
1、染色体(Chronmosome)
染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。
2、基因(Gene)
基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
3、基因地点(Locus)
基因地点在算法中表示一个基因在串中的位置称为基因位置(GenePosition)，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。
4、基因特征值(GeneFeature)
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
5、适应度(Fitness)
各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数.这个函数是计算个体在群体中被使用的概率。
3、操作算法
霍兰德(Holland)教授最初提出的算法也叫简单遗传算法，简单遗传算法的遗传操作主要有三种：选择(selection)、交叉(crossover)、变异(mutation)这也是遗传算法中最常用的三种算法：
1、选择(selection)
选择操作也叫复制操作，从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。最通常的实现方法是轮盘赌(roulettewheel)模型。令Σfi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它被选择的概率正好为其适应度值所占份额fi／Σfi。
2、交叉(Crossover)
交叉算子将被选中的两个个体的基因链按一定概率pc进行交叉，从而生成两个新的个体，交叉位置pc是随机的。其中Pc是一个系统参数。根据问题的不同，交叉又为了单点交叉算子（SinglePointCrossover）、双点交叉算子（TwoPointCrossover）、均匀交叉算子(UniformCrossover)，在此我们只讨论单点交叉的情况。单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体，将两者的部分基因码值进行交换。
3、变异(Mutation)
这是在选中的个体中，将新个体的基因链的各位按概率pm进行异向转化，最简单方式是改变串上某个位置数值。对二进制编码来说将0与1互换：0变异为1，1变异为0。
4、精英主义（Elitism）
仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。也就是说当利用交叉和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。在此我们使用精英主义（Elitism）方法，在每一次产生新的一代时，我们首先把当前最优解原封不动的复制到新的一代中，其他步骤不变。这样任何时刻产生的一个最优解都可以存活到遗传算法结束。
上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA某些性能。比如选择算法还有分级均衡选择等等。
4、算法参数
说简单点遗传算法就是遍历搜索空间或连接池，从中找出最优的解。搜索空间中全部都是个体，而群体为搜索空间的一个子集。并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的概率进行，一般在程序设计中交叉发生的概率要比变异发生的概率选取得大若干个数量级。大部分遗传算法的步骤都很类似，常使用如下参数：
Fitness函数：见上面介绍。
Fitnessthreshold（适应度阀值）：适合度中的设定的阀值，当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时(变化率为零)，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到选择操作处继续循环执行。
P：种群的染色体总数叫种群规模，它对算法的效率有明显的影响，其长度等于它包含的个体数量。太小时难以求出最优解，太大则增长收敛时间导致程序运行时间长。对不同的问题可能有各自适合的种群规模，通常种群规模为30至160。
pc：在循环中进行交叉操作所用到的概率。交叉概率（Pc）一般取0.6至0.95之间的值，Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。
Pm：变异概率，从个体群中产生变异的概率，变异概率一般取0.01至0.03之间的值变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。
另一个系统参数是个体的长度，有定长和变长两种。它对算法的性能也有影响。由于GA是一个概率过程，所以每次迭代的情况是不一样的,系统参数不同，迭代情况也不同。
5、算法步骤
遗传算法流程图
2、随机初始化群体P(0)：=(p1,p2,…pn)；
3、计算群体上每个个体的适应度值(Fitness)
4、评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi)，适应度表示了该个体的性能好坏
5、按由个体适应度值所决定的某个规则应用选择算子产生中间代Pr(t)
6、依照Pc选择个体进行交叉操作
7、仿照Pm对繁殖个体进行变异操作
8、没有满足某种停止条件，则转第3步，否则进入9
9、输出种群中适应度值最优的个体
程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。
推荐阅读