遗传算法

在计算机科学和运筹学中，遗传算法（GA）是一种元启发式的自然选择过程，属于较大的进化算法（EA）。遗传算法通常被用来生成高质量的优化和搜索问题的解决方案，依靠的是受生物启发的运算符，如变异、交叉和选择。遗传算法的一些应用实例包括优化决策树以提高性能，解决数独谜题，超参数优化等。

在遗传算法中，一个优化问题的候选解决方案的群体（称为个体、生物、生物体或表型）向更好的解决方案进化。每个候选解决方案都有一组属性（它的染色体或基因型），这些属性可以被变异和改变；传统上，解决方案以二进制表示为0和1的字符串，但其他编码也是可能的。进化通常从一个随机生成的个体群体开始，是一个迭代过程，每次迭代的群体称为一代。在每一代中，对种群中每个个体的适应性进行评估；适应性通常是正在解决的优化问题中的目标函数值。更适合的个体被随机地从当前种群中选出，每个个体的基因组被修改（重新组合并可能随机变异）以形成新的一代。新一代的候选解决方案然后被用于算法的下一次迭代。通常情况下，当产生了xxx的代数，或者群体达到了令人满意的健身水平时，算法就会终止。一个典型的遗传算法需要。解域的遗传表示，评估解域的健身函数。每个候选解的标准表示是一个比特数组（也叫比特集或比特串）。其他类型和结构的数组可以以基本相同的方式使用。使这些遗传表示法变得方便的主要属性是，由于其固定的大小，其部分很容易对齐，这有利于简单的交叉操作。可变长度的表示法也可以使用，但在这种情况下，交叉操作的实现更为复杂。在遗传编程中探索了树状表示法，在进化编程中探索了图状表示法；在基因表达编程中探索了线性染色体和树的混合。一旦定义了遗传表示法和健身函数，GA就开始初始化解决方案的群体，然后通过重复应用变异、交叉、反转和选择操作符来改进它。

群体大小取决于问题的性质，但通常包含几百或几千个可能的解决方案。通常，初始群体是随机产生的，允许整个可能的解决方案（搜索空间）的范围。偶尔，解决方案可以在可能找到最优解决方案的区域被播种。

在每一个连续的世代中，现有种群的一部分被选择来繁殖新的世代。个别解决方案是通过一个基于健身的过程来选择的，其中更适合的解决方案（由健身函数衡量）通常更可能被选中。某些选择方法对每个解决方案的适用性进行评级，并优先选择最佳解决方案。其他方法只对群体的随机样本进行评级，因为前一个过程可能非常耗时。健身函数是在遗传表示上定义的，并衡量表示的解决方案的质量。健身函数总是取决于问题。例如，在背包问题中，人们希望xxx限度地提高可以放在某个固定容量的背包中的物体的总价值。一个解决方案的代表可能是一个比特数组，其中每个比特代表一个不同的物体，而比特的值（0或1）代表该物体是否在背包中。

不是每一个这样的表示都是有效的，因为物体的大小可能超过背包的容量。如果表示是有效的，解决方案的适用性是背包中所有对象的值之和，否则就是0。在一些问题中，很难甚至不可能定义适配性表达式；在这些情况下，可以用模拟来确定表征的适配性函数值（例如，用计算流体力学来确定车辆的空气阻力，其形状被编码为表征），甚至可以使用交互式遗传算法。

下一步是从那些被选中的解决方案中产生第二代种群，通过一个com