路径算法：遗传算法 (Genetic Algorithm, GA)

港控/mmm° 2023-09-25 14:16 19阅读 0赞

![a2bcd72e0df64088ba0f63d6afdb1db0.png][]

### 遗传算法简介 ###

遗传算法是受自然进化理论启发的一系列搜索算法。通过模仿自然选择和繁殖的过程，遗传算法可以为涉及搜索，优化和学习的各种问题提供高质量的解决方案。同时，它们类似于自然进化，因此可以克服传统搜索和优化算法遇到的一些障碍，尤其是对于具有大量参数和复杂数学表示形式的问题。

### 类比达尔文进化论 ###

#### 达尔文进化理论 ####

遗传算法是类比自然界的达尔文进化实现的简化版本。

达尔文进化论的原理概括总结如下：

1.  变异：种群中单个样本的特征(性状，属性)可能会有所不同，这导致了样本彼此之间有一定程度的差异
2.  遗传：某些特征可以遗传给其后代。导致后代与双亲样本具有一定程度的相似性
3.  选择：种群通常在给定的环境中争夺资源。更适应环境的个体在生存方面更具优势，因此会产生更多的后代

换句话说，进化维持了种群中个体样本彼此不同。那些适应环境的个体更有可能生存，繁殖并将其性状传给下一代。这样，随着世代的更迭，物种变得更加适应其生存环境。而进化的重要推动因素是交叉 (crossover) 或重组 (recombination) 或杂交——结合双亲的特征产生后代。交叉有助于维持人口的多样性，并随着时间的推移将更好的特征融合在一起。此外，变异 (mutations) 或突变(特征的随机变异)可以通过引入偶然性的变化而在进化中发挥重要作用。

#### 遗传算法对应概念 ####

遗传算法试图找到给定问题的最佳解。达尔文进化论保留了种群的个体性状，而遗传算法则保留了针对给定问题的候选解集合(也称为 individuals)。这些候选解经过迭代评估 (evaluate)，用于创建下一代解。更优的解有更大的机会被选择，并将其特征传递给下一代候选解集合。这样，随着代际更新，候选解集合可以更好地解决当前的问题。

**基因型 (Genotype)**

在自然界中，通过基因型表征繁殖，繁殖和突变，基因型是组成染色体的一组基因的集合。

在遗传算法中，每个个体都由代表基因集合的染色体构成。例如，一条染色体可以表示为二进制串，其中每个位代表一个基因：

![b493637d572908aebefb05bf1db7e43d.jpeg][]

基因型

**种群 (Population)**

遗传算法保持大量的个体 (individuals) —— 针对当前问题的候选解集合。由于每个个体都由染色体表示，因此这些种族的个体 (individuals) 可以看作是染色体集合：

![00272e7d33762dbb92acd7f95f18570b.png][]

种群

**适应度函数 (Fitness function)**

在算法的每次迭代中，使用适应度函数(也称为目标函数)对个体进行评估。目标函数是用于优化的函数或试图解决的问题。

适应度得分更高的个体代表了更好的解，其更有可能被选择繁殖并且其性状会在下一代中得到表现。随着遗传算法的进行，解的质量会提高，适应度会增加，一旦找到具有令人满意的适应度值的解，终止遗传算法。

**选择 (Selection)**

在计算出种群中每个个体的适应度后，使用选择过程来确定种群中的哪个个体将用于繁殖并产生下一代，具有较高值的个体更有可能被选中，并将其遗传物质传递给下一代。

仍然有机会选择低适应度值的个体，但概率较低。这样，就不会完全摒弃其遗传物质。

**交叉 (Crossover)**

为了创建一对新个体，通常将从当前代中选择的双亲样本的部分染色体互换(交叉)，以创建代表后代的两个新染色体。此操作称为交叉或重组：

![f3e2ae0341bc8019aea8aded9e57f0ef.png][]

两点交叉

**突变 (Mutation)**

突变操作的目的是定期随机更新种群，将新模式引入染色体，并鼓励在解空间的未知区域中进行搜索。

突变可能表现为基因的随机变化。变异是通过随机改变一个或多个染色体值来实现的。例如，翻转二进制串中的一位：

![4dc34b606a40cbd9b1fcf08b5a6ea399.png][]

突变

### 遗传算法理论 ###

构造遗传算法的理论假设——针对当前问题的最佳解是由多个要素组成的，当更多此类要素组合在一起时，将更接近于问题的最优解。

种群中的个体包含一些最优解所需的要素，重复选择和交叉过程将个体将这些要素传达给下一代，同时可能将它们与其他最优解的基本要素结合起来。这将产生遗传压力，从而引导种群中越来越多的个体包含构成最佳解决方案的要素。

#### 图式定理 (schema theorem) ####

要素假设的一个更形式化的表达是 Holland 图式定理，也称为遗传算法的基本定理。

该定理是指图式是可以在染色体内找到的模式（或模板）。每个图式代表染色体中具有一定相似性的子集。

例如，如果一组染色体用长度为 4 的二进制串表示，则图式 1\*01 表示所有这些染色体，其中最左边的位置为1，最右边的两个位置为01，从左边数的第二个位置为 1 或 0，其中 \* 表示通配符。

对于每个图式，具有以下两个度量：

1.  阶 (Order)：固定数字的数量
2.  定义长度 (Defining length)：最远的两个固定数字之间的距离

下表提供了四位二进制图式及其度量的几个示例：

<table> 
 <tbody> 
  <tr> 
   <th>图式</th> 
   <th>Order</th> 
   <th>Defining Length</th> 
  </tr> 
  <tr> 
   <td>1101</td> 
   <td>4</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>1*01</td> 
   <td>3</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>*101</td> 
   <td>3</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>**01</td> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>1***</td> 
   <td>1</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>****</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

种群中的每个染色体都对应于多个图式。例如，染色体1101对应于该表中出现的每个图式，因为它与它们代表的每个模式匹配。如果该染色体具有较高的适应度，则它及其代表的所有图式都更有可能从选择操作中幸存。当这条染色体与另一条染色体交叉或发生突变时，某些图式将保留下来，而另一些则将消失。低阶图式和定义长度短的图式更有可能幸存。

因此，图式定理指出，低阶、定义长度短且适合度高于平均值的图式频率在连续的世代中呈指数增长。换句话说，随着遗传算法的发展，代表更有效解决方案的属性的更小、更简单的要素基块将越来越多地出现在群体中。

#### 遗传算法与传统算法的差异 ####

遗传算法与传统的搜索和优化算法(例如基于梯度的算法)之间存在一些重要区别。

**1. 基于种群**

遗传搜索是针对一组候选解决方案 (individuals) 而不是单个候选方案进行的。在搜索过程中，算法会保留当前一代的一组个体。遗传算法的每次迭代都会创建下一代个体。相反，大多数其他搜索算法都维持单个解决方案，并迭代地修改它以寻找最佳解决方案。例如，梯度下降算法沿当前最陡下降方向迭代移动当前解，梯度方向为给定函数的梯度的负数。

**2. 遗传表征**

遗传算法不是直接在候选解上运行，而是在它们的表示(或编码)(通常称为染色体，chromosomes)上运行。染色体能够利用交叉和突变的遗传操作。使用遗传表示的弊端是使搜索过程与原始问题域分离。遗传算法不知道染色体代表什么，也不试图解释它们。

**3. 适应度函数**

适应度函数表示要解决的问题。遗传算法的目的是找到利用适应度函数求得的得分最高的个体。与许多传统的搜索算法不同，遗传算法仅考虑利用适应度函数获得的值，而不依赖于导数或任何其他信息。这使它们适合处理难以或不可能在数学上求导的函数。

**4. 概率行为**

尽管许多传统算法本质上是确定性的，但是遗传算法用来从一代产生下一代的规则是概率性的。例如，选择的个体将被用来创建下一代，选择个体的概率随着个体的适应度得分增加，但仍有可能选择一个得分较低的个体。尽管此过程具有概率性，但基于遗传算法的搜索并不是随机的；取而代之的是，它利用随机将搜索引向搜索空间中有更好机会改善结果的区域。

### 遗传算法的优缺点 ###

#### 优点 ####

**1. 全局最优**

在许多情况下，优化问题具有局部最大值和最小值。这些值代表的解比周围的解要好，但并不是最佳的解。

大多数传统的搜索和优化算法，尤其是基于梯度的搜索和优化算法，很容易陷入局部最大值，而不是找到全局最大值。

遗传算法更有可能找到全局最大值。这是由于使用了一组候选解，而不是一个候选解，而且在许多情况下，交叉和变异操作将导致候选解与之前的解有所不同。只要设法维持种群的多样性并避免过早趋同(premature convergence)，就可能产生全局最优解。

**2. 处理复杂问题**

由于遗传算法仅需要每个个体的适应度函数得分，而与适应度函数的其他方面(例如导数)无关，因此它们可用于解决具有复杂数学表示、难以或无法求导的函数问题。

**3. 处理缺乏数学表达的问题**

遗传算法可用于完全缺乏数学表示的问题。这是由于适应度是人为设计的。例如，想要找到最有吸引力颜色组合，可以尝试不同的颜色组合，并要求用户评估这些组合的吸引力。使用基于意见的得分作为适应度函数应用遗传算法搜索最佳得分组合。即使适应度函数缺乏数学表示，并且无法直接从给定的颜色组合计算分数，但仍可以运行遗传算法。

只要能够比较两个个体并确定其中哪个更好，遗传算法甚至可以处理无法获得每个个体适应度的情况。例如，利用机器学习算法在模拟比赛中驾驶汽车，然后利用基于遗传算法的搜索可以通过让机器学习算法的不同版本相互竞争来确定哪个版本更好，从而优化和调整机器学习算法。

**4. 耐噪音**

一些问题中可能存在噪声现象。这意味着，即使对于相似的输入值，每次得到的输出值也可能有所不同。例如，当从传感器产生异常数据时，或者在得分基于人的观点的情况下，就会发生这种情况。

尽管这种行为可以干扰许多传统的搜索算法，但是遗传算法通常对此具有鲁棒性，这要归功于反复交叉和重新评估个体的操作。

**5. 并行性**

遗传算法非常适合并行化和分布式处理。适应度是针对每个个体独立计算的，这意味着可以同时评估种群中的所有个体。

另外，选择、交叉和突变的操作可以分别在种群中的个体和个体对上同时进行。

**6. 持续学习**

进化永无止境，随着环境条件的变化，种群逐渐适应它们。遗传算法可以在不断变化的环境中连续运行，并且可以在任何时间点获取和使用当前最佳的解。但是需要环境的变化速度相对于遗传算法的搜索速度慢。

#### 局限性 ####

**1. 需要特殊定义**

将遗传算法应用于给定问题时，需要为它们创建合适的表示形式——定义适应度函数和染色体结构，以及适用于该问题的选择、交叉和变异算子。

**2. 超参数调整**

遗传算法的行为由一组超参数控制，例如种群大小和突变率等。将遗传算法应用于特定问题时，没有标准的超参数设定规则。

**3. 计算密集**

种群规模较大时可能需要大量计算，在达到良好结果之前会非常耗时。可以通过选择超参数、并行处理以及在某些情况下缓存中间结果来缓解这些问题。

**3. 过早趋同**

如果一个个体的适应能力比种群的其他个体的适应能力高得多，那么它的重复性可能足以覆盖整个种群。这可能导致遗传算法过早地陷入局部最大值，而不是找到全局最大值。为了防止这种情况的发生，需要保证物种的多样性。

**4. 无法保证的解的质量**

遗传算法的使用并不能保证找到当前问题的全局最大值（但几乎所有的搜索和优化算法都存在此类问题，除非它是针对特定类型问题的解析解）。通常，遗传算法在适当使用时可以在合理的时间内提供良好的解决方案。

### 遗传算法应用场景 ###

遗传算法的应用十分广泛，特别是对于以下问题遗传算法常常能表现出优异性能，但是当问题具有已知的和专业的解决方法时，使用现有的传统方法或分析方法可能是更有效的选择。

**1. 数学表示复杂的问题**

由于遗传算法仅需要适应度函数的结果，因此它们可用于难以求导或无法求导的目标函数问题，大量参数问题以及参数混合问题类型。

**2. 没有数学表达式的问题**

只要可以获得分数值或有一种方法可以比较两个解，遗传算法就不需要对问题进行数学表示。

**3. 涉及噪声数据问题**

遗传算法可以应对数据可能不一致的问题，例如源自传感器输出或基于人类评分的数据。

**4. 随时间而变化的环境所涉及的问题**

遗传算法可以通过不断创建适应变化的新一代来响应较为缓慢的环境变化。

### 遗传算法的组成要素 ###

遗传算法的核心是循环——依次应用选择，交叉和突变的遗传算子，然后对个体进行重新评估——一直持续到满足停止条件为止

#### 算法的基本流程 ####

以下流程图显示了基本遗传算法流程的主要阶段：

![d7438064211d3baf70a1816ef6fa8e91.png][]

基本遗传算法流程

#### 创建初始种群 ####

初始种群是随机选择的一组有效候选解(个体)。由于遗传算法使用染色体代表每个个体，因此初始种群实际上是一组染色体。

#### 计算适应度 ####

适应度函数的值是针对每个个体计算的。对于初始种群，此操作将执行一次，然后在应用选择、交叉和突变的遗传算子后，再对每个新一代进行。由于每个个体的适应度独立于其他个体，因此可以并行计算。

由于适应度计算之后的选择阶段通常认为适应度得分较高的个体是更好的解决方案，因此遗传算法专注于寻找适应度得分的最大值。如果是需要最小值的问题，则适应度计算应将原始值取反，例如，将其乘以值 (-1)。

#### 选择、交叉和变异 ####

将选择，交叉和突变的遗传算子应用到种群中，就产生了新一代，该新一代基于当前代中较好的个体。

**选择** (selection) 操作负责当前种群中选择有优势的个体。

**交叉** (crossover，或重组，recombination) 操作从选定的个体创建后代。这通常是通过两个被选定的个体互换他们染色体的一部分以创建代表后代的两个新染色体来完成的。

**变异** (mutation) 操作可以将每个新创建个体的一个或多个染色体值(基因)随机进行变化。突变通常以非常低的概率发生。

#### 算法终止条件 ####

在确定算法是否可以停止时，可能有多种条件可以用于检查。两种最常用的停止条件是：

*  已达到最大世代数。这也用于限制算法消耗的运行时间和计算资源
 *  在过去的几代中，个体没有明显的改进。这可以通过存储每一代获得的最佳适应度值，然后将当前的最佳值与预定的几代之前获得的最佳值进行比较来实现。如果差异小于某个阈值，则算法可以停止

其他停止条件：

*  自算法过程开始以来已经超过预定时间
 *  消耗了一定的成本或预算，例如CPU时间和/或内存
 *  最好的解已接管了一部分种群，该部分大于预设的阈值

### 其他 ###

#### 精英主义 (elitism) ####

尽管遗传算法群体的平均适应度通常随着世代的增加而增加，但在任何时候都有可能失去当代的最佳个体。这是由于选择、交叉和变异运算符在创建下一代的过程中改变了个体。在许多情况下，丢失是暂时的，因为这些个体(或更好的个体)将在下一代中重新引入种群。

但是，如果要保证最优秀的个体总是能进入下一代，则可以选用精英主义策略。这意味着，在我们使用通过选择、交叉和突变创建的后代填充种群之前，将前 n 个个体( n 是预定义参数)复制到下一代。复制后的的精英个体仍然有资格参加选择过程，因此仍可以用作新个体的亲本。

Elitism 策略有时会对算法的性能产生重大的积极影响，因为它避免了重新发现遗传过程中丢失的良好解决方案所需的潜在时间浪费。

#### 小生境与共享 ####

在自然界中，任何环境都可以进一步分为多个子环境或小生境，这些小生境由各种物种组成，它们利用每个小生境中可用的独特资源，例如食物和庇护所。例如，森林环境由树梢，灌木，森林地面，树根等组成；这些可容纳不同物种，它们生活在该小生境中并利用其资源。

当几种不同的物种共存于同一个小生境中时，它们都将争夺相同的资源，从而形成了寻找新的，无人居住的生态位并将其填充的趋势。

在遗传算法领域，这种小生境现象可用于维持种群的多样性以及寻找几个最佳解决方案，每个解决方案均被视为小生境。

例如，假设遗传算法试图最大化具有几个不同峰值的适应度函数：

![566083a30a6f3747f724173557e40c39.png][]

全局最大值

由于遗传算法的趋势是找到全局最大值，因此一段时间后大多数个体集中在最高峰附近。在图中通过使用 × 标记的位置表示这些点，× 代表了当前代的个体。

但是有时，除了全局最大值外，我们还希望找到其他部分(或全部)峰值。为此，可以将每个峰视为小生境，以与其高度成比例的方式提供资源。然后，找到一种在占用资源的个体之间共享(或分配)这些资源的方法，理想情况下，这将促使物种进行相应的分配，最高峰会吸引最多的人，因为它提供的奖励最多，而其他峰由于提供较少的奖励而相应减少物种数量：

![5eb89c37a8716b9b147fce7982b4f342.jpeg][]

小生境

实现共享机制的一种方法是将每个个体的原始适应度值除以（与之相关的）其他所有个体的距离之和。另一种选择是将每个个体的原始适应度除以周围某个半径内的其他个体的数量。

[遗传算法 (Genetic Algorithm, GA) 详解与实现 - 知乎][_Genetic Algorithm_ GA_ _ -]

[遗传算法实践详解(deap框架初体验) - 知乎][deap_ -]

[a2bcd72e0df64088ba0f63d6afdb1db0.png]: https://img-blog.csdnimg.cn/a2bcd72e0df64088ba0f63d6afdb1db0.png
[b493637d572908aebefb05bf1db7e43d.jpeg]: https://img-blog.csdnimg.cn/img_convert/b493637d572908aebefb05bf1db7e43d.jpeg
[00272e7d33762dbb92acd7f95f18570b.png]: https://img-blog.csdnimg.cn/img_convert/00272e7d33762dbb92acd7f95f18570b.png
[f3e2ae0341bc8019aea8aded9e57f0ef.png]: https://img-blog.csdnimg.cn/img_convert/f3e2ae0341bc8019aea8aded9e57f0ef.png
[4dc34b606a40cbd9b1fcf08b5a6ea399.png]: https://img-blog.csdnimg.cn/img_convert/4dc34b606a40cbd9b1fcf08b5a6ea399.png
[d7438064211d3baf70a1816ef6fa8e91.png]: https://img-blog.csdnimg.cn/img_convert/d7438064211d3baf70a1816ef6fa8e91.png
[566083a30a6f3747f724173557e40c39.png]: https://img-blog.csdnimg.cn/img_convert/566083a30a6f3747f724173557e40c39.png
[5eb89c37a8716b9b147fce7982b4f342.jpeg]: https://img-blog.csdnimg.cn/img_convert/5eb89c37a8716b9b147fce7982b4f342.jpeg
[_Genetic Algorithm_ GA_ _ -]: https://zhuanlan.zhihu.com/p/436453994
[deap_ -]: https://zhuanlan.zhihu.com/p/436424904