遗传算法系列之一:遗传算法简介

最近博主在写毕业论文，没时间看资料，只能炒一些冷饭了——拿本科接触的东西写博客了。因此开始写遗传算法系列，这篇博客作为开端介绍遗传算法的基本知识。遗传算法的数学基础和变种将在后面介绍。

遗传算法 ( GA, Genetic Algorithm ) ，也称进化算法 。 遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。为了介绍遗传算法，我们先介绍一些基本概念。

1. 基因 ( Gene ) ：一个遗传因子。

2. 染色体 ( Chromosome ) ：一组的基因。

3. 个体 ( individual )：单个生物。在遗传算法中，个体一般只包含一条染色体。

4. 种群 ( Population )：由个体组成的群体。生物的进化以种群的形式进化。

5. 适者生存 ( The survival of the fittest )：对环境适应度高的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。

简单说来说，繁殖过程会发生基因交叉 ( Crossover ) 和基因突变 ( Mutation ) 。适应度 ( Fitness ) 低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的。

遗传算法将问题的解编码成个体的染色体，并用一些个体组成种群。个体包含的解越好，则个体的适应度越好。种群中适应度高的个体获得较高概率的繁殖机会，繁殖过程中会以一定概率出现基因交叉和基因突变。经过繁殖过程，新的种群（即新的一组解）产生。上述繁殖过程重复多次，直到达到收敛条件。历史上适应度最高个体所包含的解，作为遗传算法的输出。下图是遗传算法的流程图。

image.png

根据上面的流程图，遗传算法包含三个基本操作：选择、交叉和变异。

选择，也就是流程图中”根据适应度进行串赋值”。如下图所示，当一个种群三个个体进行自然选择时，适应度越大则被选择的概率就越大。

image.png

交叉，两条染色体相互交换基因片段。遗传算法交叉比人体内染色体交叉要简单许多。遗传算法的染色体是单倍体，而人体内的真正的染色体是双倍体。下图是遗传算法中两条染色体在中间进行交叉的示意图。

image.png

变异，某个基因位发生变化。下图是遗传算法中一条染色体在第二位发生基因变异的示意图。

image.png

上述的选择、交叉和变异是最简单的类型，而且并不是所有问题的解决方案都可以编码成0-1向量的形式。实际上，应用遗传算法的主要工作是设计编码方案、交叉过程、变异过程和选择过程。我们将在后续博客中介绍不同问题的遗传算法。

遗传算法是 John Henry Holland 1992年在突破性著作《Adaptation in Natural and Artificial Systems》中引入的。也就是说，遗传算法问世其实不到25年，稍微比SVM老一些。之前我一直以为遗传算法的年龄应该和神经网络差不多。John Henry Holland在去年8月9号去世。

image.png