第九课 遗传算法（ Genetic Algorithm, GA）

遗传算法概述

• 遗传算法（ Genetic Algorithm， GA） 是一种进化算法， 其基本原理是仿效生物界中的“物竞天择、 适者生存” 的演化法则， 它最初由美国Michigan大学的J. Holland教授于1967年提出。
• 遗传算法是从代表问题可能潜在的解集的一个种群（ population） 开始的， 而一个种群则由经过基因（ gene） 编码的一定数目的个体(individual)组成。 因此， 第一步需要实现从表现型到基因型的映射即编码工作。 初代种群产生之后， 按照适者生存和优胜劣汰的原理， 逐代（ generation） 演化产生出越来越好的近似解， 在每一代， 根据问题域中个体的适应度(fitness)大小选择个体，借助于自然遗传学的遗传算子(genetic operators) 进行组合交叉和变异， 产生出代表新的解集的种群。 这个过程将导致种群像自然进化一样， 后生代种群比前代更加适应于环境， 末代种群中的最优个体经过解码（ decoding） ， 可以作为问题近似最优解。

GA三个基本操作：

选择（ Selection） 、 交叉（ Crossover） 和变异（ Mutation）

• （1） 选择。 选择的目的是为了从当前群体中选出优良的个体， 使它们有机会作为父代为下一代繁衍子孙。 根据各个个体的适应度值， 按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。 选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大。（圆盘赌，将优良个体设置大区域）
• （2）交叉。 通过交叉操作可以得到新一代个体， 新个体组合了父辈个体的特性。 将群体中的各个个体随机搭配成对， 对每一个个体， 以交叉概率交换它们之间的部分染色体。
• （3）变异。 对种群中的每一个个体， 以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。 同生物界中一样，变异发生的概率很低， 变异为新个体的产生提供了机会。（与交叉相比，变异发生的概率比较低）

遗传算法的基本步骤：

• 编码： GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。
• 初始群体的生成：随机产生N个初始串结构数据， 每个串结构数据称为一个个体， N个个体构成了一个群体。 GA以这N个串结构数据作为初始点开始进化。
• 适应度评估：适应度表明个体或解的优劣性。不同的问题， 适应性函数的定义方式也不同。
• 选择：选择的目的是为了从当前群体中选出优良的个体， 使它们有机会作为父代为下一
  代繁殖子孙。 遗传算法通过选择过程体现这一思想， 进行选择的原则是适应性强的个体为
  下一代贡献一个或多个后代的概率大。 选择体现了达尔文的适者生存原则。

5)交叉：交叉操作是遗传算法中最主要的遗传操作。 通过交叉操作可以得到新一代个体，
新个体组合了其父辈个体的特性。 交叉体现了信息交换的思想。
6)变异：变异首先在群体中随机选择一个个体， 对于选中的个体以一定的概率随机地改变
串结构数据中某个串的值。 同生物界一样， GA中变异发生的概率很低， 通常取值很小。