遗传算法

遗传算法(Genetic Algorithm，缩写为GA)是一种进化计算的技术，它是一种基于自然选择和遗传的搜索算法，由著名的计算机科学教授霍金(John H.Holland)1970年在他的著名的书“挑战智能系统”中所提出来的一种结合生物进化规律的方法。

遗传算法通过在给定的问题全域中进行搜索以解决复杂问题，它是将计算机编程与生物进化规律相结合的一种计算方法，主要模拟生物进化中的自然选择机制和遗传过程， 它的目的是改变搜索空间中的解的分布，不断调整和改善解的结构，以求得问题的全局最优解。

遗传算法是基于个体式分析，它充分利用了生物进化过程中的知识，是一种自适应的优化和搜索技术。它可以更有效地找到搜索空间中的潜在最优解，是戴斯特菲尔德估值函数(Fitness Function),随机变异(Random Mutation) ，声明性规则和一组锁定数据标准的基础技术，用于解决复杂的优化问题。遗传算法也可以用来解决无变量的问题，例如组合优化问题。

遗传算法的工作过程大致分为四个步骤：初始化种群、进化规则、进化遗传和适者生存。

1) 初始化种群：首先建立一个装有表示问题所需参数的初始种群，即定义个体数量、每个个体的各参数等，把该群体作为算法的初始种群。

2) 进化规则：根据自然选择的原理，用算法的进化规则生成新的后代种群。针对优胜个体，更频繁地进行变异及交叉，而对劣势个体，则更少的交叉及变异。

3) 进化的遗传：将优胜个体的表示作为模板在种群中传播，消除不优秀个体，由而种群中最优秀的个体被反复遗传。

4) 适者生存：在每一代种群中，适者生存，即各个个体依据某种指标来进行比较，从而挑选出优胜个体，最终得到拥有全局最优解的染色体（可看作问题的最优解）。

注意，遗传算法是一种概率算法，可以有不同的运行结果，所以要考虑重复运行及数据的求平均的方式求得最终解决方案，可以得到相对较准确的结果。

遗传算法的优点在于可以在探索全局最优解的同时具备良好的搜索效率。它的缺点则在于真实的解被求解的概率较低，有时候即使得到解也难以确定收敛到全局最优解了。此外，遗传算法也存在一定的运行时间消耗问题。