?遗传算法是一种随机全局优化算法。它的灵感来自通过自然选择的生物进化理论。具体来说，是将对遗传学的理解与理论结合起来的新的综合。
与人工神经网络一样，它是最受欢迎和最广为人知的生物启发算法之一。
该算法是一种进化算法，以?遗传重组?和?遗传突变?为基础，利用?二元表示?和简单?算子?的自然选择，根据生物进化理论(适者生存)进行优化。
该算法使用类似的遗传表示(位串)、适应度(函数计算)、遗传重组(位串的交叉)和变异(翻转位)。
该算法首先创建一个固定大小的随机位串的总体。算法的主循环重复固定次数的迭代，或者直到在给定次数的迭代中，在最佳解决方案中看不到进一步的改进。
算法的一次迭代就像进化的一代。
首先，使用目标函数计算位串(候选解)的填充。将每个候选解的目标函数评价作为解的适应度，可最小化或最大化。
然后，根据适应度选择父母。一个给定的候选解决方案可能被用作零次或多次父解决方案。
一种简单有效的?选择方法?是从种群中?随机?抽取个?候选者，并从适应度最好的群体中选择成员。这称为?竞赛选择，其中是一个?超参数，并设置为一个值，例如3。这个简单的方法模拟了一个更昂贵的适合度比例选择方案。
在竞赛选择中，每个亲本都是种群中随机选择的条染色体中最适合的。
父母是产生?下一代?候选点数的基础，群体中的每个位置都需要一对父母。
然后让父母成双成对地生两个孩子。重组使用交叉操作符进行。这包括在位串上选择一个?随机的分裂点，然后创建一个子串，其中包含从第一个父节点到分裂点的位，以及从第二个父节点到字符串末尾的分裂点的位。然后，这个过程对第二个子节点进行反转。
具体流程会在下面介绍。
基本?术语：
种群(population)：它是给定问题的所有可能(编码)解决方案的子集。GA的种群与人类的种群类似。
染色体(Chromosomes)：一个染色体就是解决这个问题的一个解。
基因(Gene)：基因是染色体的一个位置元素。
等位基因(Allele)：一个基因为一个特定的染色体所取的值。
基因型(Genotype)：基因型是计算空间中的总体。在计算空间中，解以一种易于理解和使用计算系统操作的方式表示。
表现型(Phenotype)：表现型是现实世界解决方案空间中的群体，在这个空间中，解决方案以现实世界情景中的方式表示。
解码和编码(Decoding and Encoding)：对于简单的问题，表型和基因型空间是相同的。然而，在大多数情况下，表型和基因型空间是不同的。解码是从基因型到表现型空间的转化过程，编码是从表现型到基因型空间的转化过程。译码速度要快，因为遗传算法在计算适应度值时要反复进行译码。
适应度函数(Fitness Function)：简单定义的适应度函数是以解为输入，以解的适用性为输出的函数。在某些情况下，适应度函数和目标函数可能是相同的，而在另一些情况下，适应度函数和目标函数可能根据问题的不同而不同。
基因算子(Genetic Operators)：改变后代的基因组成。这包括交叉、变异、选择等。
自然选择的过程是从群体中选择最适合的个体开始的。它们产生的后代继承了父母的特征，并将遗传给下一代。如果父母有更好的健康状况，他们的后代就会比父母更好，有更好的生存机会。这个过程不断迭代，最终会找到最适合的个体。
这个概念可以应用于搜索问题。我们考虑一个问题的一组解，并从中选择一组最好的解。
遗传算法流程如下图所示：
? ? ? ? ? ? ? ? ? ? ?
?
1 种群初始化
这个过程从一组被称为种群的个体开始。每个个体是想要解决的问题的一个解决方案。个体的特征是一组称为基因的参数(变量)。基因被连接成一串，形成染色体(解决方案)。
在遗传算法中，个体的一组基因是用一串字母表示的(位串)。通常使用二进制值(1和0组成的字符串)。染色体中的编码基因：
?
2 适应度函数?
适应度函数决定了个体的适合度(个体与其他个体竞争的能力)。它给每个个体一个适合度评分。一个个体被选择繁殖的概率是基于它的适合度分数。
3 选择?
选择阶段的想法是选择最适合的个体，让他们把自己的基因传给下一代。
两对个体(父母)被选择基于他们的适合度得分。适应度高的个体被选择繁殖的机会更大。
4 交叉
交叉是遗传算法中最重要的阶段。对于每一对要交配的父母来说，交叉点是从基因中随机选择的。
例如，考虑交叉点为3，如下所示：
? ? ? ? ? ? ? 
?
这被称为单点交叉，还有许多其他的算子变体。
后代是通过父母之间的基因交换而产生的，直到达到交叉点。
? ? ? ? ? ? ? ? ? ? ? 
?新的后代被添加到种群中。
? ? ? ? ? ? ? ? ? ? ? ? ?
?
交叉被概率地应用于每一对父代，这意味着在某些情况下，父代的副本被作为子代，而不是重组操作符。交叉由设置为较大值的超参数控制，例如80%或90%。
交叉是遗传算法的显著特征。它涉及到将父母双方的部分混合和匹配来形成孩子。如何进行混合和匹配取决于个体的表现。
5 变异
在某些新形成的后代中，他们的一些基因可能会以低随机概率发生突变。突变涉及到在创建的孩子候选解决方案中翻转比特。通常情况下，变化率设置为1/L，其中L为位串的长度。
? ? ? ? ? ? ? ? ? ? ?
?
突变的发生是为了保持种群内的多样性，防止过早收敛。
6 终止
如果种群已经收敛(没有产生与上一代显著不同的后代)，则算法终止。可以说，遗传算法已经为我们的问题提供了一套解决方案。
种群数量是固定的。随着新一代的形成，最不适合的个体会死亡，为新一代提供空间。
这个阶段的顺序是重复的，以在每一代中产生比上一代更好的个体。
优点：
与传统方法相比，速度更快，效率更高。
具有很好的并行能力。
可同时优化连续和离散函数以及多目标问题。
提供一个好的解决方案列表，而不仅仅是一个单一的解决方案。
总能找到问题的答案，随着时间的推移会变得更好。
当搜索空间很大且涉及大量参数时非常有用。
缺点：
算法并不适用于所有的问题，特别是那些简单的、可以得到导数信息的问题。
适应度值是反复计算的，这对于某些问题可能是计算昂贵的。
由于是随机的，所以不能保证解的最优性或质量。
如果执行不当，遗传算法可能无法收敛到最优解
参考：
https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm
?
