遗传算法（Genetic Algorithm， GA）
- 遗传算法简介
- 类比达尔文进化论
- 达尔文进化理论
- 遗传算法对应概念
- 基因型 (Genotype)
- 种群 (Population)
- 适应度函数 (Fitness function)
- 选择 (Selection)
- 交叉 (Crossover)
- 突变 (Mutation)
- 编码补充
- 二进制编码
- 格雷码
- 浮点编码法
- 符号编码法
- 遗传算法常用术语
- 遗传算法理论
- 图式定理 (schema theorem)
- 遗传算法与传统算法的差异
- 遗传算法的优缺点
- 优点
- 局限性
- 遗传算法应用场景
- 遗传算法的基本特征
- 遗传算法的组成要素
- 算法的基本流程
- 创建初始种群
- 计算适应度
- 选择、交叉和变异
- 算法终止条件
- 其他
- 精英主义 (elitism)
- 小生境与共享
- 遗传算法实践（deap框架初体验）
- OneMax问题介绍
- 遗传算法实践
- 遗传算法解的进化
遗传算法简介
遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。
简单的说 能够生存下来的往往不是最强大的物种，也不是最聪明的物种，而是最能适应环境的物种。
类比达尔文进化论
达尔文进化理论
遗传算法是类比自然界的达尔文进化实现的简化版本。
达尔文进化论的原理概括总结如下：
**变异：**种群中单个样本的特征(性状，属性)可能会有所不同，这导致了样本彼此之间有一定程度的差异
**遗传：**某些特征可以遗传给其后代。导致后代与双亲样本具有一定程度的相似性
**选择：**种群通常在给定的环境中争夺资源。更适应环境的个体在生存方面更具优势，因此会产生更多的后代
换句话说，进化维持了种群中个体样本彼此不同。那些适应环境的个体更有可能生存，繁殖并将其性状传给下一代。这样，随着世代的更迭，物种变得更加适应其生存环境。而进化的重要推动因素是交叉 (crossover) 或重组 (recombination) 或杂交——结合双亲的特征产生后代。交叉有助于维持人口的多样性，并随着时间的推移将更好的特征融合在一起。此外，变异 (mutations) 或突变(特征的随机变异)可以通过引入偶然性的变化而在进化中发挥重要作用。
遗传算法对应概念
遗传算法试图找到给定问题的最佳解。达尔文进化论保留了种群的个体性状，而遗传算法则保留了针对给定问题的候选解集合(也称为 individuals)。这些候选解经过迭代评估 (evaluate)，用于创建下一代解。更优的解有更大的机会被选择，并将其特征传递给下一代候选解集合。这样，随着代际更新，候选解集合可以更好地解决当前的问题。
基因型 (Genotype)
在自然界中，通过基因型表征繁殖，繁殖和突变，基因型是组成染色体的一组基因的集合。
在遗传算法中，每个个体都由代表基因集合的染色体构成。例如，一条染色体可以表示为二进制串，其中每个位代表一个基因：
种群 (Population)
遗传算法保持大量的个体 (individuals) —— 针对当前问题的候选解集合。由于每个个体都由染色体表示，因此这些种族的个体 (individuals) 可以看作是染色体集合：
适应度函数 (Fitness function)
在算法的每次迭代中，使用适应度函数(也称为目标函数)对个体进行评估。目标函数是用于优化的函数或试图解决的问题。
适应度得分更高的个体代表了更好的解，其更有可能被选择繁殖并且其性状会在下一代中得到表现。随着遗传算法的进行，解的质量会提高，适应度会增加，一旦找到具有令人满意的适应度值的解，终止遗传算法。
选择 (Selection)
在计算出种群中每个个体的适应度后，使用选择过程来确定种群中的哪个个体将用于繁殖并产生下一代，具有较高值的个体更有可能被选中，并将其遗传物质传递给下一代。
仍然有机会选择低适应度值的个体，但概率较低。这样，就不会完全摒弃其遗传物质。
交叉 (Crossover)
为了创建一对新个体，通常将从当前代中选择的双亲样本的部分染色体互换(交叉)，以创建代表后代的两个新染色体。此操作称为交叉或重组：
突变 (Mutation)
突变操作的目的是定期随机更新种群，将新模式引入染色体，并鼓励在解空间的未知区域中进行搜索。
突变可能表现为基因的随机变化。变异是通过随机改变一个或多个染色体值来实现的。例如，翻转二进制串中的一位：
编码补充
二进制编码
二进制编码由二进制符号0和1所组成的二值符号集。
优点：
- 编码、解码操作简单易行
- 交叉、变异等遗传操作便于实现
- 合最小字符集编码原则
- 利用模式定理对算法进行理论分析。
二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对于一些高精度的问题，当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。
格雷码
格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。
二进制码转为格雷码：异或运算：同则为0，异则为1。公式如下：
由格雷码转二进制的转换公式为：
优点：增强遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。使用非常广泛。
浮点编码法
二进制编码虽然简单直观，但明显地。但是存在着连续函数离散化时的映射误差。个体长度较短时，可能达不到精度要求，而个体编码长度较长时，虽然能提高精度，但增加了解码的难度，使遗传算法的搜索空间急剧扩大。
所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。编码长度等于决策变量的个数。在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。
优点：
适用于在遗传算法中表示范围较大的数
适用于精度要求较高的遗传算法
便于较大空间的遗传搜索
改善了遗传算法的计算复杂性，提高了运算交率
便于遗传算法与经典优化方法的混合使用
便于设计针对问题的专门知识的知识型遗传算子
便于处理复杂的决策变量约束条件
符号编码法
符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝。
优点：
符合有意义积术块编码原则
便于在遗传算法中利用所求解问题的专门知识
便于遗传算法与相关近似算法之间的混合使用。
遗传算法常用术语
**① 染色体(Chromosome)：**染色体又可称为基因型个体(individuals)，一定数量的个体组成了群体(population)，群体中个体的数量叫做群体大小（population size）。
**② 位串(Bit String)：**个体的表示形式。对应于遗传学中的染色体。
**③ 基因(Gene)：**基因是染色体中的元素，用于表示个体的特征。例如有一个串（即染色体）S=1011，则其中的1，0，1，1这4个元素分别称为基因。
**④ 特征值( Feature)：**在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
**⑤ 适应度(Fitness)：**各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数通常会被用来计算个体在群体中被使用的概率。
**⑥ 基因型(Genotype)：**或称遗传型，是指基因组定义遗传特征和表现。对于于GA中的位串。
**⑦ 表现型(Phenotype)：**生物体的基因型在特定环境下的表现特征。对应于GA中的位串解码后的参数。
遗传算法理论
构造遗传算法的理论假设——针对当前问题的最佳解是由多个要素组成的，当更多此类要素组合在一起时，将更接近于问题的最优解。
种群中的个体包含一些最优解所需的要素，重复选择和交叉过程中的个体将这些要素传达给下一代，同时可能将它们与其他最优解的基本要素结合起来。这将产生遗传压力，从而引导种群中越来越多的个体包含构成最佳解决方案的要素。
图式定理 (schema theorem)
要素假设的一个更形式化的表达是 Holland 图式定理，也称为遗传算法的基本定理。
该定理是指图式是可以在染色体内找到的模式（或模板）。每个图式代表染色体中具有一定相似性的子集。
例如，如果一组染色体用长度为 4 的二进制串表示，则图式 1*01 表示所有这些染色体，其中最左边的位置为1，最右边的两个位置为01，从左边数的第二个位置为 1 或 0，其中 * 表示通配符。
对于每个图式，具有以下两个度量：
阶 (Order)：固定数字的数量
定义长度 (Defining length)：最远的两个固定数字之间的距离
下表提供了四位二进制图式及其度量的几个示例：
种群中的每个染色体都对应于多个图式。例如，染色体1101对应于该表中出现的每个图式，因为它与它们代表的每个模式匹配。如果该染色体具有较高的适应度，则它及其代表的所有图式都更有可能从选择操作中幸存。当这条染色体与另一条染色体交叉或发生突变时，某些图式将保留下来，而另一些则将消失。低阶图式和定义长度短的图式更有可能幸存。
因此，图式定理指出，低阶、定义长度短且适合度高于平均值的图式频率在连续的世代中呈指数增长。换句话说，随着遗传算法的发展，代表更有效解决方案的属性的更小、更简单的要素基块将越来越多地出现在群体中。
遗传算法与传统算法的差异
遗传算法与传统的搜索和优化算法(例如基于梯度的算法)之间存在一些重要区别。
- 基于种群
遗传搜索是针对一组候选解决方案 (individuals) 而不是单个候选方案进行的。在搜索过程中，算法会保留当前一代的一组个体。遗传算法的每次迭代都会创建下一代个体。相反，大多数其他搜索算法都维持单个解决方案，并迭代地修改它以寻找最佳解决方案。例如，梯度下降算法沿当前最陡下降方向迭代移动当前解，梯度方向为给定函数的梯度的负数。
- 遗传表征
遗传算法不是直接在候选解上运行，而是在它们的表示(或编码)(通常称为染色体，chromosomes)上运行。染色体能够利用交叉和突变的遗传操作。使用遗传表示的弊端是使搜索过程与原始问题域分离。遗传算法不知道染色体代表什么，也不试图解释它们。
- 适应度函数
适应度函数表示要解决的问题。遗传算法的目的是找到利用适应度函数求得的得分最高的个体。与许多传统的搜索算法不同，遗传算法仅考虑利用适应度函数获得的值，而不依赖于导数或任何其他信息。这使它们适合处理难以或不可能在数学上求导的函数。
- 概率行为
尽管许多传统算法本质上是确定性的，但是遗传算法用来从一代产生下一代的规则是概率性的。例如，选择的个体将被用来创建下一代，选择个体的概率随着个体的适应度得分增加，但仍有可能选择一个得分较低的个体。尽管此过程具有概率性，但基于遗传算法的搜索并不是随机的；取而代之的是，它利用随机将搜索引向搜索空间中有更好机会改善结果的区域。
遗传算法的优缺点
优点
- 全局最优
在许多情况下，优化问题具有局部最大值和最小值。这些值代表的解比周围的解要好，但并不是最佳的解。
大多数传统的搜索和优化算法，尤其是基于梯度的搜索和优化算法，很容易陷入局部最大值，而不是找到全局最大值。
遗传算法更有可能找到全局最大值。这是由于使用了一组候选解，而不是一个候选解，而且在许多情况下，交叉和变异操作将导致候选解与之前的解有所不同。只要设法维持种群的多样性并避免过早趋同(premature convergence)，就可能产生全局最优解。
- 处理复杂问题
由于遗传算法仅需要每个个体的适应度函数得分，而与适应度函数的其他方面(例如导数)无关，因此它们可用于解决具有复杂数学表示、难以或无法求导的函数问题。
- 处理缺乏数学表达的问题
遗传算法可用于完全缺乏数学表示的问题。这是由于适应度是人为设计的。例如，想要找到最有吸引力颜色组合，可以尝试不同的颜色组合，并要求用户评估这些组合的吸引力。使用基于意见的得分作为适应度函数应用遗传算法搜索最佳得分组合。即使适应度函数缺乏数学表示，并且无法直接从给定的颜色组合计算分数，但仍可以运行遗传算法。
只要能够比较两个个体并确定其中哪个更好，遗传算法甚至可以处理无法获得每个个体适应度的情况。例如，利用机器学习算法在模拟比赛中驾驶汽车，然后利用基于遗传算法的搜索可以通过让机器学习算法的不同版本相互竞争来确定哪个版本更好，从而优化和调整机器学习算法。
- 耐噪音
一些问题中可能存在噪声现象。这意味着，即使对于相似的输入值，每次得到的输出值也可能有所不同。例如，当从传感器产生异常数据时，或者在得分基于人的观点的情况下，就会发生这种情况。
尽管这种行为可以干扰许多传统的搜索算法，但是遗传算法通常对此具有鲁棒性，这要归功于反复交叉和重新评估个体的操作。
- 并行性
遗传算法非常适合并行化和分布式处理。适应度是针对每个个体独立计算的，这意味着可以同时评估种群中的所有个体。
另外，选择、交叉和突变的操作可以分别在种群中的个体和个体对上同时进行。
- 持续学习
进化永无止境，随着环境条件的变化，种群逐渐适应它们。遗传算法可以在不断变化的环境中连续运行，并且可以在任何时间点获取和使用当前最佳的解。但是需要环境的变化速度相对于遗传算法的搜索速度慢。
局限性
- 需要特殊定义
将遗传算法应用于给定问题时，需要为它们创建合适的表示形式——定义适应度函数和染色体结构，以及适用于该问题的选择、交叉和变异算子。
- 超参数调整
遗传算法的行为由一组超参数控制，例如种群大小和突变率等。将遗传算法应用于特定问题时，没有标准的超参数设定规则。
- 计算密集
种群规模较大时可能需要大量计算，在达到良好结果之前会非常耗时。可以通过选择超参数、并行处理以及在某些情况下缓存中间结果来缓解这些问题。
- 过早趋同
如果一个个体的适应能力比种群的其他个体的适应能力高得多，那么它的重复性可能足以覆盖整个种群。这可能导致遗传算法过早地陷入局部最大值，而不是找到全局最大值。为了防止这种情况的发生，需要保证物种的多样性。
- 无法保证的解的质量
遗传算法的使用并不能保证找到当前问题的全局最大值（但几乎所有的搜索和优化算法都存在此类问题，除非它是针对特定类型问题的解析解）。通常，遗传算法在适当使用时可以在合理的时间内提供良好的解决方案。
遗传算法应用场景
遗传算法的应用十分广泛，特别是对于以下问题遗传算法常常能表现出优异性能，但是当问题具有已知的和专业的解决方法时，使用现有的传统方法或分析方法可能是更有效的选择。
- 数学表示复杂的问题
由于遗传算法仅需要适应度函数的结果，因此它们可用于难以求导或无法求导的目标函数问题，大量参数问题以及参数混合问题类型。
- 没有数学表达式的问题
只要可以获得分数值或有一种方法可以比较两个解，遗传算法就不需要对问题进行数学表示。
- 涉及噪声数据问题
遗传算法可以应对数据可能不一致的问题，例如源自传感器输出或基于人类评分的数据。
- 随时间而变化的环境所涉及的问题
遗传算法可以通过不断创建适应变化的新一代来响应较为缓慢的环境变化。
遗传算法的基本特征
1.智能式搜索：依据适应度（目标函数）进行只能搜索
2.渐进式优化：利用复制、交换、突变等操作，使下一代结果优于上一代
3.全局最优解：采用交换和突变操作产生新个体，使得搜索得到的优化结果逼近全局最优解
4.黑箱式结构：根据问题的特性进行编码（输入）和确定适应度（输出），具有只考虑输入与输出关系的黑箱式就够，并不深究输入与输出关系的原因
5.通用性强：不要求明确的数学表达式，只需要一些简单的原则要求，可应用于解决离散问题、函数关系不明确的复杂问题
6.并行式运算：每次迭代计算都是对群体中所有个体同时进行运算，是并行式运算方式，搜索速度快
遗传算法的组成要素
遗传算法的核心是循环——依次应用选择，交叉和突变的遗传算子，然后对个体进行重新评估——一直持续到满足停止条件为止
算法的基本流程
以下流程图显示了基本遗传算法流程的主要阶段：
创建初始种群
初始种群是随机选择的一组有效候选解(个体)。由于遗传算法使用染色体代表每个个体，因此初始种群实际上是一组染色体。
计算适应度
适应度函数的值是针对每个个体计算的。对于初始种群，此操作将执行一次，然后在应用选择、交叉和突变的遗传算子后，再对每个新一代进行。由于每个个体的适应度独立于其他个体，因此可以并行计算。
由于适应度计算之后的选择阶段通常认为适应度得分较高的个体是更好的解决方案，因此遗传算法专注于寻找适应度得分的最大值。如果是需要最小值的问题，则适应度计算应将原始值取反，例如，将其乘以值 (-1)。
选择、交叉和变异
将选择，交叉和突变的遗传算子应用到种群中，就产生了新一代，该新一代基于当前代中较好的个体。
选择 (selection) 操作负责当前种群中选择有优势的个体。
交叉 (crossover，或重组，recombination) 操作从选定的个体创建后代。这通常是通过两个被选定的个体互换他们染色体的一部分以创建代表后代的两个新染色体来完成的。
变异 (mutation) 操作可以将每个新创建个体的一个或多个染色体值(基因)随机进行变化。突变通常以非常低的概率发生。
算法终止条件
在确定算法是否可以停止时，可能有多种条件可以用于检查。两种最常用的停止条件是：
已达到最大世代数。这也用于限制算法消耗的运行时间和计算资源
在过去的几代中，个体没有明显的改进。这可以通过存储每一代获得的最佳适应度值，然后将当前的最佳值与预定的几代之前获得的最佳值进行比较来实现。如果差异小于某个阈值，则算法可以停止
其他停止条件：
自算法过程开始以来已经超过预定时间
消耗了一定的成本或预算，例如CPU时间和/或内存
最好的解已接管了一部分种群，该部分大于预设的阈值
其他
精英主义 (elitism)
尽管遗传算法群体的平均适应度通常随着世代的增加而增加，但在任何时候都有可能失去当代的最佳个体。这是由于选择、交叉和变异运算符在创建下一代的过程中改变了个体。在许多情况下，丢失是暂时的，因为这些个体(或更好的个体)将在下一代中重新引入种群。
但是，如果要保证最优秀的个体总是能进入下一代，则可以选用精英主义策略。这意味着，在我们使用通过选择、交叉和突变创建的后代填充种群之前，将前 n 个个体( n 是预定义参数)复制到下一代。复制后的的精英个体仍然有资格参加选择过程，因此仍可以用作新个体的亲本。
Elitism 策略有时会对算法的性能产生重大的积极影响，因为它避免了重新发现遗传过程中丢失的良好解决方案所需的潜在时间浪费。
小生境与共享
在自然界中，任何环境都可以进一步分为多个子环境或小生境，这些小生境由各种物种组成，它们利用每个小生境中可用的独特资源，例如食物和庇护所。例如，森林环境由树梢，灌木，森林地面，树根等组成；这些可容纳不同物种，它们生活在该小生境中并利用其资源。
当几种不同的物种共存于同一个小生境中时，它们都将争夺相同的资源，从而形成了寻找新的，无人居住的生态位并将其填充的趋势。
在遗传算法领域，这种小生境现象可用于维持种群的多样性以及寻找几个最佳解决方案，每个解决方案均被视为小生境。
例如，假设遗传算法试图最大化具有几个不同峰值的适应度函数：
由于遗传算法的趋势是找到全局最大值，因此一段时间后大多数个体集中在最高峰附近。在图中通过使用 × 标记的位置表示这些点，× 代表了当前代的个体。
但是有时，除了全局最大值外，我们还希望找到其他部分(或全部)峰值。为此，可以将每个峰视为小生境，以与其高度成比例的方式提供资源。然后，找到一种在占用资源的个体之间共享(或分配)这些资源的方法，理想情况下，这将促使物种进行相应的分配，最高峰会吸引最多的人，因为它提供的奖励最多，而其他峰由于提供较少的奖励而相应减少物种数量：
实现共享机制的一种方法是将每个个体的原始适应度值除以（与之相关的）其他所有个体的距离之和。另一种选择是将每个个体的原始适应度除以周围某个半径内的其他个体的数量。
遗传算法实践（deap框架初体验）
OneMax问题介绍
OneMax 问题是一个简单的优化任务，通常作为遗传算法的 Hello World。
OneMax 任务是查找给定长度的二进制串，最大化该二进制串中数字的总和。例如，对于长度为 5 的OneMax问题，10010 的数字总和为 2，01110 的数字总和为 3。
显然，此问题的最优解为每位数字均为1的二进制串。但是对于遗传算法而言，其并不具备此知识，因此需要使用其遗传算子寻找最优解。算法的目标是在合理的时间内找到最优解，或者至少找到一个近似最优解。
遗传算法实践
在进行实践前，应首先明确遗传算法中所用到的要素定义。
选择染色体 由于 OneMax 问题涉及二进制串，因此每个个体的染色体直接利用代表候选解的二进制串表示是一个自然的选择。在 Python中，将其实现为仅包含 0/1 整数值的列表。染色体的长度与 OneMax 问题的规模匹配。例如，对于规模为 5 的 OneMax 问题，个体 10010 由列表 [1,0,0,1,0] 表示；
适应度的计算 由于要最大化该二进制串中数字的总和，同时由于每个个体都由 0/1 整数值列表表示，因此适合度可以设计为列表中元素的总和，例如：sum([1,0,0,1,0])= 2；
选择遗传算子 选择遗传算子并没有统一的标准，通常可以尝试几种选择方案，找到最适合的方案。其中选择算子通常可以处理任何染色体类型，但是交叉和突变算子通常需要匹配使用的染色体类型，否则可能会产生无效的染色体：
选择算子：此处选用锦标赛选择
交叉算子：此处选用单点交叉
突变算子：此处选用位翻转突变
设定停止条件 限制繁衍的代际数通常是一个不错的停止条件，它可以确保算法不会永远运行。另外，由于我们知道了 OneMax 问题的最佳解决方案(一个全为 1 的二进制串，也就是说其适应度等于代表个体的列表长度)，因此可以将其用作另一个停止条件。但是，需要注意的是，对于现实世界中的多数问题而言，通常不存在这种可以公式化精确定义的先验知识。
遗传算法要素配置
在开始实际的遗传算法流程之前，需要根据上述要素的设计利用代码实现：
首先导入所用包：
from deap import base
from deap import creator
from deap import tools
import random
import matplotlib.pyplot as plt
- 接下来，声明一些常量，这些常量用于设置 OneMax 问题的参数并控制遗传算法的行为：
ONE_MAX_LENGTH = 100 #length of bit string to be optimized
POPULATION_SIZE = 200 #number of individuals in population
P_CROSSOVER = 0.9 #probability for crossover
P_MUTATION = 0.1 #probability for mutating an individual
MAX_GENERATION = 50 #max number of generations for stopping condition
- 接下来，使用 Toolbox 类创建 zeroOrOne 操作，该操作用于自定义 random.randomint(a,b) 函数。通过将参数 a 和 b 固定为值 0 和 1，当在调用此运算时，zeroOrOne 运算符将随机返回 0 或 1：
toolbox = base.Toolbox()#定义toolbox变量
toolbox.register("zeroOrOne",random.randint,0,1)#注册zeroOrOne运算
- 接下来，需要创建 Fitness 类。由于这里只有一个目标——最大化数字总和，因此选择 FitnessMax 策略，使用具有单个正权重的权重元组：
creator.create("FitnessMax",base.Fitness,weights=(1.0,))
- 在 deap 中，通常使用 Individual 的类来代表种群中的每个个体。使用 creator 工具创建该类，使用列表作为基类，用于表示个体的染色体。并为该类增加 Fitness 属性，该属性初始化为步骤 4 中定义的 FitnessMax 类：
creator.create("Individual", list, fitness=creator.FitnessMax)
- 接下来，注册 individualCreator 操作，该操作创建 Individual 类的实例，并利用步骤 1 中自定义的 zeroOrOne 操作随机填充 0/1。注册 individualCreator 操作使用基类 initRepeat 操作，并使用以下参数对基类进行实例化：
将 creator.Individual 类作为放置结果对象的容器类型
zeroOrOne 操作是生成对象的函数
常量 ONE_MAX_LENGTH 作为要生成的对象数目
由于 zeroOrOne 运算符生成的对象是 0/1 的随机数，因此，所得的 individualCreator 运算符将使用 100 个随机生成的 0 或 1 填充单个实例：
toolbox.register("individualCreator",tools.initRepeat,creator.Individual,toolbox.zeroOrOne,ONE_MAX_LENGTH)
- 最后，注册用于创建个体列表的 populationCreator 操作。该定义使用带有以下参数的 initRepeat 基类操作：
将列表类作为容器类型
用于生成列表中对象的函数 —— personalCreator 运算符
这里没有传入 initRepeat 的最后一个参数——要生成的对象数量。这意味着，当使用 populationCreator 操作时，需要指定此参数用于确定创建的个体数：
toolbox.register("populationCreator",tools.initRepeat,list,toolbox.individualCreator)
- 为了简化适应度(在 deap 中称为 evaluation )的计算，首先定义一个独立的函数，该函数接受 Individual 类的实例并返回其适应度。
这里定义 oneMaxFitness 函数，用于计算个体中 1 的数量。
def oneMaxFitness(individual):
return sum(individual),#deap中的适用度表示为元组，因此，当返回单个值时，需要用逗号将其声明为元组
- 接下来，将 evaluate 运算符定义为 oneMaxfitness() 函数的别名。使用 evaluate 别名来计算适应度是 deap 的一种约定：
toolbox.register("evaluate",oneMaxFitness)
- 遗传算子通常是通过对 tools 模块中的现有函数进行别名命名，并根据需要设置参数值来创建的。根据上节设计的要素创建遗传算子:
toolbox.register("select",tools.selTournament,tournsize=3)
toolbox.register("mate",tools.cxOnePoint)
# mutFlipBit函数遍历个体的所有特征，并且对于每个特征值，
# 都将使用indpb参数值作为翻转（应用not运算符）该特征值的概率。
# 该值与突变概率无关，后者由P_MUTATION常数设置。
# 突变概率用于确定是否为种群中的给定个体调用mutFlipBit函数
toolbox.register("mutate",tools.mutFlipBit,indpb=1.0/ONE_MAX_LENGTH)
遗传算法解的进化
遗传流程如以下步骤所示：
- 通过使用之前定义的 populationCreator 操作创建初始种群，并以 POPULATION_SIZE 常量作为该操作的参数。并初始化 generationCounter 变量，用于判断代际数：
population = toolbox.populationCreator(n=POPULATION_SIZE)
generationCounter = 0
- 为了计算初始种群中每个个体的适应度，使用 map() 函数将 evaluate 操作应用于种群中的每个个体。由于 evaluate 操作是 oneMaxFitness() 函数的别名，因此，迭代的结果由每个个体的计算出的适应度元组组成。 得到结果后将其转换为元组列表：
fitnessValues = list(map(toolbox.evaluate,population)
- 由于 fitnessValues 的项分别与 population (个体列表)中的项匹配，因此可以使用 zip() 函数将它们组合并为每个个体分配相应的适应度元组：
for individual,fitnessValue in zip(population,fitnessValues):
individual.fitness.values = fitnessValue
- 接下来，由于适应度元组仅有一个值，因此从每个个体的适应度中提取第一个值以获取统计数据：
fitnessValues = [indivalual.fitness.values[0] for individual in population]
- 统计种群每一代的最大适应度和平均适应度。创建两个列表用于存储统计值：
maxFitnessValues = []
meanFitnessValues = []
- 遗传流程的主要准备工作已经完成，在循环时还需设置停止条件，通过限制代际数来设置一个停止条件，而通过检测是否达到了最佳解(所有二进制串位都为 1 )作为另一个停止条件：
while max(fitnessValues)<ONE_MAX_LENGTH and generationCounter<MAX_GENERATIONS:
- 接下来更新代际计数器：
generationCounter = generationCounter + 1
- 遗传算法的核心是遗传运算符。第一个是 selection 运算符，使用先前利用 toolbox.select 定义的锦标赛选择。由于我们已经在定义运算符时设置了锦标赛大小，因此只需要将物种及其长度作为参数传递给选择运算符：
offspring = toolbox.select(population,len(population))
- 被选择的个体被赋值给 offspring 变量，接下来将其克隆，以便我们可以应用遗传算子而不影响原始种群：
这里需要注意的是：尽管被选择的个体被命名为 offspring，但它们仍然是前一代的个体的克隆，我们仍然需要使用 crossover 运算符将它们配对以创建实际的后代。
offspring = list(map(toolbox.clone,offspring)
- 下一个遗传算子是交叉。已经在上节中定义为 toolbox.mate 运算符，并且其仅仅是单点交叉的别名。使用 Python 切片将 offspring 列表中的每个偶数索引项与奇数索引项对作为双亲。然后，以 P_CROSSOVER 常数设置的交叉概率进行交叉。这将决定这对个体是会交叉或保持不变。最后，删除后代的适应度值，因为它们现有的适应度已经不再有效：
for child1,child2 in zip(offspring[::2],offspring[1::2]):
if random.random() < P_CROSSOVER:
toolbox.mate(child1,child2)
del child1.fitness.values
del child2.fitness.values
- 最后一个遗传运算符是突变，先前已注册为 toolbox.mutate 运算符，并设置为翻转位突变操作。遍历所有后代项，将以由突变概率常数 P_MUTATION 设置的概率应用变异算子。如果个体发生突变，我们确保删除其适应性值。由于该值可能继承自上一代，并且在突变后不再正确，需要重新计算：
for mutant in offspring:
if random.random() < P_MUTATION:
toolbox.mutate(mutant)
del mutant.fitness.values
- 没有交叉或变异的个体保持不变，因此，它们的现有适应度值(已在上一代中计算出)就无需再次计算。其余个体的适应度值为空。使用 Fitness 类的 valid 属性查找这些新个体，然后以与原始适应性值计算相同的方式为其计算新适应性：
freshIndividuals = [ind for ind in offspring if not ind.fitness.valid]
freshFitnessValues = list(map(toolbox.evaluate,freshIndividuals))
for individual,fitnessValue in zip(freshIndividuals,freshFitnessValues):
individual.fitness.values = fitnessValue
- 遗传算子全部完成后，就可以使用新的种群取代旧的种群了：
population[:] = offspring
- 在继续下一轮循环之前，将使用与上述相同的方法统计当前的适应度值以更新统计信息：
fitnessValues = [ind.fitness.values[0] for ind in population]
- 获得最大和平均适应度值，将它们的值添加到统计列表中：
maxFitness = max(fitnessValues)
meanFitness = sum(fitnessValues) / len(population)
maxFitnessValues.append(maxFItness)
meanFItnessValues.append(meanFItness)
print("- Generation {}: Max Fitness = {}, Avg Fitness = {}".format(generationCounter,
maxFitness, meanFitness)
- 此外，使用得到的最大适应度值来找到最佳个体的索引，并打印出该个体：
best_index = fitnessValues.index(max(fitnessValues))
print("Best Individual = ", *population[best_index], "\n")
- 满足停止条件并且遗传算法流程结束后，可以使用获取的统计信息，使用matplotlib库可视化算法执行过程中的统计信息，展示各代个体的最佳和平均适应度值的变化：
plt.plot(maxFitnessValues,color='red')
plt.plot(meanFitnessValues,color='green')
plt.xlabel('Generation')
plt.ylabel('Max / Average Fitness')
plt.title('Max and Average fitness over Generation')
plt.show()
该部分完整代码如下：
def main():
population = toolbox.populationCreator(n=POPULATION_SIZE)
generationCounter = 0
fitnessValues = list(map(toolbox.evaluate,population))
for individual,fitnessValue in zip(population,fitnessValues):
individual.fitness.values = fitnessValue
fitnessValues = [individual.fitness.values[0] for individual in population]
maxFitnessValues = []
meanFitnessValues = []
while max(fitnessValues) < ONE_MAX_LENGTH and generationCounter < MAX_GENERATION:
generationCounter = generationCounter + 1
offspring = toolbox.select(population,len(population))
offspring = list(map(toolbox.clone,offspring))
for child1,child2 in zip(offspring[::2],offspring[1::2]):
if random.random() < P_CROSSOVER:
toolbox.mate(child1,child2)
del child1.fitness.values
del child2.fitness.values
for mutant in offspring:
if random.random() < P_MUTATION:
toolbox.mutate(mutant)
del mutant.fitness.values
freshIndividuals = [ind for ind in offspring if not ind.fitness.valid]
freshFitnessValues = list(map(toolbox.evaluate,freshIndividuals))
for individual,fitnessValue in zip(freshIndividuals,freshFitnessValues):
individual.fitness.values = fitnessValue
population[:] = offspring
fitnessValues = [ind.fitness.values[0] for ind in population]
maxFitnessValue = max(fitnessValues)
meanFitnessValue = sum(fitnessValues) / len(population)
maxFitnessValues.append(maxFitnessValue)
meanFitnessValues.append(meanFitnessValue)
print("- Generation {}: Max Fitness = {}, Avg Fitness = {}".format(generationCounter,maxFitnessValue,meanFitnessValue))
best_index = fitnessValues.index(max(fitnessValues))
print("Best Indivadual = ", *population[best_index],"\n")
plt.plot(maxFitnessValues,color="red")
plt.plot(meanFitnessValues,color="green")
plt.xlabel("Generation")
plt.ylabel("Max / Average Fitness")
plt.title("Max and Average fitness over Generation")
plt.show()
至此可以开始测试我们的遗传算法了，运行代码以验证其是否找到了 OneMax 问题的最优解。
或者还有实现二元函数最大值求解问题
import math, randomclass Population:
# 种群的设计
def __init__(self, size, chrom_size, cp, mp, gen_max):
# 种群信息合
self.individuals = [] # 个体集合
self.fitness = [] # 个体适应度集
self.selector_probability = [] # 个体选择概率集合
self.new_individuals = [] # 新一代个体集合
self.elitist = {'chromosome':[0, 0], 'fitness':0, 'age':0} # 最佳个体的信息
self.size = size # 种群所包含的个体数
self.chromosome_size = chrom_size # 个体的染色体长度
self.crossover_probability = cp # 个体之间的交叉概率
self.mutation_probability = mp # 个体之间的变异概率
self.generation_max = gen_max # 种群进化的最大世代数
self.age = 0 # 种群当前所处世代
# 随机产生初始个体集，并将新一代个体、适应度、选择概率等集合以 0 值进行初始化
v = 2 ** self.chromosome_size - 1
for i in range(self.size):
self.individuals.append([random.randint(0, v), random.randint(0, v)])
self.new_individuals.append([0, 0])
self.fitness.append(0)
self.selector_probability.append(0)
# 基于轮盘赌博机的选择
def decode(self, interval, chromosome):
'''将一个染色体 chromosome 映射为区间 interval 之内的数值'''
d = interval[1] - interval[0]
n = float (2 ** self.chromosome_size -1)
return (interval[0] + chromosome * d / n)
def fitness_func(self, chrom1, chrom2):
'''适应度函数，可以根据个体的两个染色体计算出该个体的适应度'''
interval = [-10.0, 10.0]
(x, y) = (self.decode(interval, chrom1),
self.decode(interval, chrom2))
n = lambda x, y: math.sin(math.sqrt(x*x + y*y)) ** 2 - 0.5
d = lambda x, y: (1 + 0.001 * (x*x + y*y)) ** 2
func = lambda x, y: 0.5 - n(x, y)/d(x, y)
return func(x, y)
def evaluate(self):
'''用于评估种群中的个体集合 self.individuals 中各个个体的适应度'''
sp = self.selector_probability
for i in range (self.size):
self.fitness[i] = self.fitness_func (self.individuals[i][0], # 将计算结果保存在 self.fitness 列表中
self.individuals[i][1])
ft_sum = sum (self.fitness)
for i in range (self.size):
sp[i] = self.fitness[i] / float (ft_sum) # 得到各个个体的生存概率
for i in range (1, self.size):
sp[i] = sp[i] + sp[i-1] # 需要将个体的生存概率进行叠加，从而计算出各个个体的选择概率
# 轮盘赌博机（选择）
def select(self):
(t, i) = (random.random(), 0)
for p in self.selector_probability:
if p > t:
break
i = i + 1
return i
# 交叉
def cross(self, chrom1, chrom2):
p = random.random() # 随机概率
n = 2 ** self.chromosome_size -1
if chrom1 != chrom2 and p < self.crossover_probability:
t = random.randint(1, self.chromosome_size - 1) # 随机选择一点（单点交叉）
mask = n << t # << 左移运算符
(r1, r2) = (chrom1 & mask, chrom2 & mask) # & 按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
mask = n >> (self.chromosome_size - t)
(l1, l2) = (chrom1 & mask, chrom2 & mask)
(chrom1, chrom2) = (r1 + l2, r2 + l1)
return (chrom1, chrom2)
# 变异
def mutate(self, chrom):
p = random.random ()
if p < self.mutation_probability:
t = random.randint (1, self.chromosome_size)
mask1 = 1 << (t - 1)
mask2 = chrom & mask1
if mask2 > 0:
chrom = chrom & (~mask2) # ~ 按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1
else:
chrom = chrom ^ mask1 # ^ 按位异或运算符：当两对应的二进位相异时，结果为1
return chrom
# 保留最佳个体
def reproduct_elitist (self):
# 与当前种群进行适应度比较，更新最佳个体
j = -1
for i in range (self.size):
if self.elitist['fitness'] < self.fitness[i]:
j = i
self.elitist['fitness'] = self.fitness[i]
if (j >= 0):
self.elitist['chromosome'][0] = self.individuals[j][0]
self.elitist['chromosome'][1] = self.individuals[j][1]
self.elitist['age'] = self.age
# 进化过程
def evolve(self):
indvs = self.individuals
new_indvs = self.new_individuals
# 计算适应度及选择概率
self.evaluate()
# 进化操作
i = 0
while True:
# 选择两个个体，进行交叉与变异，产生新的种群
idv1 = self.select()
idv2 = self.select()
# 交叉
(idv1_x, idv1_y) = (indvs[idv1][0], indvs[idv1][1])
(idv2_x, idv2_y) = (indvs[idv2][0], indvs[idv2][1])
(idv1_x, idv2_x) = self.cross(idv1_x, idv2_x)
(idv1_y, idv2_y) = self.cross(idv1_y, idv2_y)
# 变异
(idv1_x, idv1_y) = (self.mutate(idv1_x), self.mutate(idv1_y))
(idv2_x, idv2_y) = (self.mutate(idv2_x), self.mutate(idv2_y))
(new_indvs[i][0], new_indvs[i][1]) = (idv1_x, idv1_y) # 将计算结果保存于新的个体集合self.new_individuals中
(new_indvs[i+1][0], new_indvs[i+1][1]) = (idv2_x, idv2_y)
# 判断进化过程是否结束
i = i + 2 # 循环self.size/2次，每次从self.individuals 中选出2个
if i >= self.size:
break
# 最佳个体保留
# 如果在选择之前保留当前最佳个体，最终能收敛到全局最优解。
self.reproduct_elitist()
# 更新换代：用种群进化生成的新个体集合 self.new_individuals 替换当前个体集合
for i in range (self.size):
self.individuals[i][0] = self.new_individuals[i][0]
self.individuals[i][1] = self.new_individuals[i][1]
def run(self):
'''根据种群最大进化世代数设定了一个循环。在循环过程中，调用 evolve 函数进行种群进化计算，并输出种群的每一代的个体适应度最大值、平均值和最小值。'''
for i in range (self.generation_max):
self.evolve ()
print (i, max (self.fitness), sum (self.fitness)/self.size, min (self.fitness))if __name__ == '__main__':
# 种群的个体数量为 50，染色体长度为 25，交叉概率为 0.8，变异概率为 0.1,进化最大世代数为 150
pop = Population (50, 24, 0.8, 0.1, 150)
pop.run()
图文参考 ：
1.https://zhuanlan.zhihu.com/p/436453994
2.https://zhuanlan.zhihu.com/p/436424904
3.https://zhuanlan.zhihu.com/p/100337680
4.https://mp.weixin.qq.com/s/rV9EKbU2q1HpYchEVQXdyQ
文章出处登录后可见！