?遗传算法是一种随机全局优化算法。它的灵感来自通过自然选择的生物进化理论。具体来说，是将对遗传学的理解与理论结合起来的新的综合。

与人工神经网络一样，它是最受欢迎和最广为人知的生物启发算法之一。

该算法是一种进化算法，以?遗传重组?和?遗传突变?为基础，利用?二元表示?和简单?算子?的自然选择，根据生物进化理论(适者生存)进行优化。

该算法使用类似的遗传表示(位串)、适应度(函数计算)、遗传重组(位串的交叉)和变异(翻转位)。

该算法首先创建一个固定大小的随机位串的总体。算法的主循环重复固定次数的迭代，或者直到在给定次数的迭代中，在最佳解决方案中看不到进一步的改进。

算法的一次迭代就像进化的一代。

• 首先，使用目标函数计算位串(候选解)的填充。将每个候选解的目标函数评价作为解的适应度，可最小化或最大化。

• 然后，根据适应度选择父母。一个给定的候选解决方案可能被用作零次或多次父解决方案。

一种简单有效的?选择方法?是从种群中?随机?抽取个?候选者，并从适应度最好的群体中选择成员。这称为?竞赛选择，其中是一个?超参数，并设置为一个值，例如3。这个简单的方法模拟了一个更昂贵的适合度比例选择方案。

在竞赛选择中，每个亲本都是种群中随机选择的条染色体中最适合的。

父母是产生?下一代?候选点数的基础，群体中的每个位置都需要一对父母。

然后让父母成双成对地生两个孩子。重组使用交叉操作符进行。这包括在位串上选择一个?随机的分裂点，然后创建一个子串，其中包含从第一个父节点到分裂点的位，以及从第二个父节点到字符串末尾的分裂点的位。然后，这个过程对第二个子节点进行反转。

具体流程会在下面介绍。

基本?术语：

1. 种群(population)：它是给定问题的所有可能(编码)解决方案的子集。GA的种群与人类的种群类似。

2. 染色体(Chromosomes)：一个染色体就是解决这个问题的一个解。

3. 基因(Gene)：基因是染色体的一个位置元素。

4. 等位基因(Allele)：一个基因为一个特定的染色体所取的值。

5. 基因型(Genotype)：基因型是计算空间中的总体。在计算空间中，解以一种易于理解和使用计算系统操作的方式表示。

6. 表现型(Phenotype)：表现型是现实世界解决方案空间中的群体，在这个空间中，解决方案以现实世界情景中的方式表示。

7. 解码和编码(Decoding and Encoding)：对于简单的问题，表型和基因型空间是相同的。然而，在大多数情况下，表型和基因型空间是不同的。解码是从基因型到表现型空间的转化过程，编码是从表现型到基因型空间的转化过程。译码速度要快，因为遗传算法在计算适应度值时要反复进行译码。

8. 适应度函数(Fitness Function)：简单定义的适应度函数是以解为输入，以解的适用性为输出的函数。在某些情况下，适应度函数和目标函数可能是相同的，而在另一些情况下，适应度函数和目标函数可能根据问题的不同而不同。

9. 基因算子(Genetic Operators)：改变后代的基因组成。这包括交叉、变异、选择等。

自然选择的过程是从群体中选择最适合的个体开始的。它们产生的后代继承了父母的特征，并将遗传给下一代。如果父母有更好的健康状况，他们的后代就会比父母更好，有更好的生存机会。这个过程不断迭代，最终会找到最适合的个体。

这个概念可以应用于搜索问题。我们考虑一个问题的一组解，并从中选择一组最好的解。

遗传算法流程如下图所示：

? ? ? ? ? ? ? ? ? ? ?

?

1 种群初始化

这个过程从一组被称为种群的个体开始。每个个体是想要解决的问题的一个解决方案。个体的特征是一组称为基因的参数(变量)。基因被连接成一串，形成染色体(解决方案)。

在遗传算法中，个体的一组基因是用一串字母表示的(位串)。通常使用二进制值(1和0组成的字符串)。染色体中的编码基因：

?

2 适应度函数?

适应度函数决定了个体的适合度(个体与其他个体竞争的能力)。它给每个个体一个适合度评分。一个个体被选择繁殖的概率是基于它的适合度分数。

3 选择?

选择阶段的想法是选择最适合的个体，让他们把自己的基因传给下一代。

两对个体(父母)被选择基于他们的适合度得分。适应度高的个体被选择繁殖的机会更大。

4 交叉

交叉是遗传算法中最重要的阶段。对于每一对要交配的父母来说，交叉点是从基因中随机选择的。

例如，考虑交叉点为3，如下所示：

? ? ? ? ? ? ?

?

这被称为单点交叉，还有许多其他的算子变体。

后代是通过父母之间的基因交换而产生的，直到达到交叉点。

? ? ? ? ? ? ? ? ? ? ?

?新的后代被添加到种群中。

? ? ? ? ? ? ? ? ? ? ? ? ?

?

交叉被概率地应用于每一对父代，这意味着在某些情况下，父代的副本被作为子代，而不是重组操作符。交叉由设置为较大值的超参数控制，例如80%或90%。

交叉是遗传算法的显著特征。它涉及到将父母双方的部分混合和匹配来形成孩子。如何进行混合和匹配取决于个体的表现。

5 变异

在某些新形成的后代中，他们的一些基因可能会以低随机概率发生突变。突变涉及到在创建的孩子候选解决方案中翻转比特。通常情况下，变化率设置为1/L，其中L为位串的长度。

? ? ? ? ? ? ? ? ? ? ?

?

突变的发生是为了保持种群内的多样性，防止过早收敛。

6 终止

如果种群已经收敛(没有产生与上一代显著不同的后代)，则算法终止。可以说，遗传算法已经为我们的问题提供了一套解决方案。

种群数量是固定的。随着新一代的形成，最不适合的个体会死亡，为新一代提供空间。

这个阶段的顺序是重复的，以在每一代中产生比上一代更好的个体。

优点：

1. 与传统方法相比，速度更快，效率更高。

2. 具有很好的并行能力。

3. 可同时优化连续和离散函数以及多目标问题。

4. 提供一个好的解决方案列表，而不仅仅是一个单一的解决方案。

5. 总能找到问题的答案，随着时间的推移会变得更好。

6. 当搜索空间很大且涉及大量参数时非常有用。

缺点：

1. 算法并不适用于所有的问题，特别是那些简单的、可以得到导数信息的问题。

2. 适应度值是反复计算的，这对于某些问题可能是计算昂贵的。

3. 由于是随机的，所以不能保证解的最优性或质量。

4. 如果执行不当，遗传算法可能无法收敛到最优解

参考：

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm

?