遗传算法

Genetic Algorithm

术语

基因型(genotype)：性状染色体的内部表现；
表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；
进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
适应度(fitness)：度量某个物种对于生存环境的适应程度。
选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
解码(decoding)：基因型到表现型的映射。
个体（individual）：指染色体带有特征的实体；
种群（population）：个体的集合，该集合内个体数称为种群

遗传算法包含了名为染色体（chromosome）的个体组成的种群。所有染色体都要竞争解决一些问题，每条染色体都由定义其特性的基因组成。染色体解决问题的能力由适应度函数（fitnessfunction）定义。遗传算法要经历很多代（generation）。在每一代中，适应力较强的染色体更有可能被选中进行繁殖。每一代中还有可能发生两条染色体的基因合并，这被称为交换（crossover）。此外，每一代都有一种重要的可能性，即染色体中的基因可能会随机发生变异（mutate）。当种群中某些个体的适应度函数超过某个指定阈值后，或者算法运行了指定数量的代之后，将会返回表现最佳的个体（适应度函数中得分最高的个体）。
遗传算法并不是解决所有问题的好办法。它们依赖3种部分或完全随机的操作：选择、交换和变异。因此，它们可能无法在合理的时间内找到最优解。对大多数问题而言，更具确定性的算法会更有保证，但是有些问题不存在快速的确定性算法，在这些情况下，遗传算法就是一个不错的选择。

遗传算法通常是高度专用的，需要针对特定应用进行调优。在本章中，我们将定义一种通用的遗传算法，该算法适用于多种问题，且未针对其中任意一类问题进行专门的调优。虽然它会包含一些可配置的选项，但目标仍是为了演示算法的基本原理而不是可调优的程度。首先我们将定义一个接口，以便定义该通用算法能够操作的个体。抽象类Chromosome定义了4种基本特征。染色体必须能够实现以下几个功能。

• 确定自己的适应度。
• 创建一个携带了随机选中基因的实例（用于填充第一代个体的数据）。
• 实现交换，即让自己与另一个同类结合并创建后代，换句话说，就是使自己与另一条染色体混合。
• 变异——让自己的体内数据发生相当随机的小变化。