什么是遗传算法

遗传算法 (GA) 是更大类别的进化算法 (EA) 的子集，是计算机科学和运筹学中使用的一种元启发式算法，其灵感来自于自然选择的过程。遗传算法经常采用受生物学启发的算子，包括变异、交叉和选择，以产生优化和搜索问题的高质量解决方案。优化决策树以提高性能、解决数独难题、超参数优化、因果推理等都是 GA 应用的一些例子。

历史
艾伦·图灵在 1950 年提出了一种模仿进化过程的“学习机器”。尼尔斯·阿尔·巴里切利 (Nils Aall Barricelli) 在新泽西州普林斯顿高级研究所使用计算机，于 1954 年率先使用计算机来模拟进化。他 1954 年出版的作品并没有引起多少关注。澳大利亚数量遗传学家 Alex Fraser 于 1957 年开始发表一系列出版物，内容涉及模拟对具有影响可量化性状的许多基因座的动物进行人工选择。从这些开始，生物学家对进化的计算机建模在 20 世纪 60 年代初有所增加。Fraser 和 Burnell (1970) 以及 Crosby (1973) 出版了概述这些技术的书籍。弗雷泽的模拟包含了当代遗传算法的所有基本组成部分。Hans-Joachim Bremermann 还在 20 世纪 60 年代撰写的几篇出版物中使用了优化问题的一组解决方案，这些出版物经历了重组、突变和选择。现代遗传算法也是布雷默曼研究的一部分。理查德·弗里德伯格、乔治·弗里德曼和迈克尔·康拉德是著名的早期先驱。Fogel (1998) 转载了许多早期出版物。

尽管 Barricelli 在 1963 年发表的作品中模拟了简单游戏中技能的进化，但由于 Ingo Rechenberg 和 Hans-Paul Schwefel 的工作，人工进化成为 20 世纪 60 年代和 1970 年代初期常用的优化技术。雷兴伯格的团队使用进化技术来寻找具有挑战性的技术问题的解决方案。另一种策略是劳伦斯·J·福格尔的进化编程方法，该方法被建议用于创建人工智能。最初，有限状态机在进化编程中用于预测环境，并使用变异和选择来改进预测逻辑。通过 John Holland 在 20 世纪 70 年代初的工作，尤其是他的著作《自然和人工系统的适应》(Adaptation in Natural and Artificial Systems, 1975)，遗传算法尤其受到欢迎。

他的研究始于霍兰德和他在密歇根大学的学生的元胞自动机实验。他建立的霍兰德图式定理是预测下一代素质的正式框架。直到 20 世纪 80 年代中期在宾夕法尼亚州匹兹堡召开第一届国际遗传算法会议之前，遗传算法的研究仍主要停留在理论层面。

工业品
通用电气于 20 世纪 80 年代末开始销售世界上第一个遗传算法产品——一种为工业流程而设计的基于大型机的工具集。Evolver 是世界上第一个用于台式计算机的商业 GA 解决方案，由 Axcelis, Inc. 于 1989 年推出。正如《纽约时报》的 John Markoff 在 1990 年报道的那样，Evolver 是 1995 年之前唯一的交互式商业遗传算法。 Evolver 于 1997 年出售给 Palisade，并被翻译成多种语言，现已上市。自 20 世纪 90 年代以来，MATLAB 已包含两种直接搜索算法（简单搜索和模式搜索）以及三种无导数优化启发式技术（模拟退火、粒子群优化和遗传算法）。

适合的问题领域
时间表和调度问题是遗传算法特别适合解决的问题之一，许多调度软件解决方案都是基于遗传算法的。工程师也在他们的工作中使用了 GA。全局优化挑战经常使用遗传算法来解决。

具有复杂适应性景观的问题域可能会受益于遗传算法，因为混合或变异与交叉相结合的目的是使群体远离标准爬山算法可能陷入的局部最优。请记住，交叉算子，经常使用，不能改变任何统一的人口。整个遗传算法过程（视为马尔可夫链）的遍历性可以仅通过变异来实现。
进化算法已经解决的问题的例子包括复杂流场中空气动力体的最佳设计、计算机图形的行走程序以及用于在太空中进行无线电传输的天线。
Skiena 在他的《算法设计手册》中警告不要将进化算法用于任何目的：

使用位串上的突变和交叉等遗传算子对应用程序进行建模是非常奇怪的。伪生物学又增加了一层复杂性，将你和你的问题分开。其次，将遗传算法应用于复杂问题需要很长时间。进化的类比是一个很好的类比，因为有意义的发展需要数百万年的时间才能发生。

当我遇到问题时，遗传算法从来都不是解决问题的最佳方法。此外，我从未遇到过任何令我满意的遗传算法的计算结果。对于您所有的启发式搜索魔法要求，请坚持使用模拟退火。

优化问题
在遗传算法中，优化问题（人、生物、有机体或表型）的潜在解决方案群体朝着更优的解决方案发展。传统上，解决方案以二进制形式表示为 0 和 1 的字符串，但其他编码也是可行的。每个候选解决方案都有一组可以更改和修改的属性（其染色体或基因型）。

一代是一个术语，用于描述进化的每次迭代中的群体，通常从随机生成的个体群体开始。每一代人都会对每个成员的健康状况进行一次评估；适应度通常是正在解决的优化问题中的目标函数的值。新一代是通过从当前人群中随机选择最适合的人、重组他们的基因组并引入随机突变来创建的。以下算法迭代使用新生成的候选解。该算法通常在种群达到理想的适应水平或已产生最大代数时结束。

传统的遗传算法必须以遗传方式表示解域并使用适应度函数进行评估。

每个潜在的答案通常表示为位的集合，也称为位集或字符串。各种类型和结构的数组的使用基本相同。这些遗传表示的根本好处是它们的固定大小使得它们的片段易于对齐并允许简单的交叉程序。也可以采用可变长度表示，但在这种情况下交叉实现更加困难。在基因表达编程中，检查线性染色体和树的组合。遗传编程探索树形式的表示，而进化编程探索图形的表示。

遗传算法在定义遗传表示和适应度函数后启动解决方案群体，然后通过重复使用变异、交叉、反转和选择操作来改进它。

1、初始化
根据问题的性质，潜在的解决方案可能有数百到数千种。初始群体通常是随机产生的，允许完整的潜在答案集（搜索空间）。有时，答案可能会“播种”在最有可能找到最佳答案的区域。

2、选择
在接下来的每一代中，选择当前人口的一定比例来繁殖新一代。基于适应度的方法用于选择单独的解决方案，更适合的解决方案（由适应度函数确定）通常有更高的机会被选择。一些选择方法评估每个解决方案的适应性并选择最好的解决方案。其他技术仅对代表性人口样本进行评级，因为初始程序可能需要较长时间。

在遗传表示上定义的适应度函数评估所表示解决方案的有效性。适应度函数始终取决于问题。例如，在背包问题中，目标是最大化可装入具有特定容量的背包中的物品的总体价值。位数组可以表示一个解决方案，每个位代表一个单独的对象及其值（0 或 1），指示该对象是否在背包中。这种表示有时是准确的，因为物品的大小有时会超过背包的存储容量。

当很难甚至不可能定义问题的适应度表达式时，可以使用模拟甚至交互式遗传算法来估计表型的适应度函数值（例如，使用计算流体动力学来估计表型的空气阻力）其形状被编码为表型的车辆）。

3、基因修饰剂
通过结合遗传算子的交叉（也称为重组）和变异，下一步是从最初选择的解决方案中产生第二代解决方案群体。

从先前选择的池中选择一对“父”解决方案来培育以产生每个新解决方案。通过采用上述交叉和变异技术来构建“子”解决方案，创建了一个新的解决方案，该解决方案通常与其“父母”共享许多特征。对于每个新孩子，都会选择新的父母，并重复此过程，直到产生大小正确的新解决方案群体。一些研究表明，尽管基于两个亲本的繁殖技术更具“生物学启发”，但两个以上的“亲本”会产生优质染色体。

这些活动最终导致下一代的染色体群体与第一代不同。由于只选择第一代中最好的生物以及一小部分不太适合的解决方案进行繁殖，因此种群的平均适应性应该会因这一操作而增长。这些不太有效的方法保证了亲代遗传库内的遗传变异，从而保证了下一代儿童的遗传多样性。

交叉和突变的相对作用是有争议的。Fogel (2006) 中的大量参考文献支持基于突变的搜索的重要性。

虽然两个最常见的遗传算子是交叉和变异，但遗传算法也可以利用重组、殖民灭绝或迁移。

为了找到适合所考虑问题类别的适当设置，调整突变概率、交叉概率和总体规模等变量是值得的。遗传漂变的非遍历现象可能是由于相对较低的突变率造成的。如果重组率太高，遗传算法可能无法完全收敛。如果不使用精英选择，高突变率可能会导致好的解决方案的丢失。

适当的种群规模可以确保有足够的遗传多样性来解决当前的问题。不过，如果设置的值大于必要的值，则可能会浪费计算资源。

启发式
除了上述重要运算符之外，还可以使用其他启发式方法来加速或加强计算。物种形成启发式通过惩罚过于相似的候选解决方案之间的交叉来阻碍种群同质性并延迟收敛到不太理想的解决方案。

终止
重复这一生成过程，直到满足终止条件为止。典型的终止情况包括：

• 发现了满足最低要求的解决方案
• 排名最高的解决方案的适应度接近或已达到稳定水平，这意味着后续迭代不再提供更好的结果。
• 人工检查。如前所述，这些的组合。固定的世代数。分配的预算（计算时间/金钱）。

构建块理论
尽管创建遗传算法很容易，但理解它们的行为却具有挑战性。理解为什么这些算法在用于解决现实问题时经常产生高度拟合的答案尤其具有挑战性。构建块假设 (BBH) 的组成部分是：

• 对通过定位和重新组合“构建块”或具有高于平均适应性的低阶、短定义长度模式进行适应的启发式解释。
• 这个想法是，遗传算法通过有效且隐式地将这种启发式付诸实践来实现自适应。

我们已经给它们起了一个特定的名字：构建块。这是由于具有短定义长度和低阶的高度拟合模式在遗传算法的操作中发挥着重要作用。遗传算法通过并置短的、低阶的、高性能的图式或积木来寻求近乎最佳的性能，就像幼儿用基本的木块建造奇妙的堡垒一样。

尽管需要就其有效性达成更多共识，但多年来，构件假说已被反复评估并用作参考。例如，已经对分配程序进行了大量的估计，以创建假设成立的环境。尽管某些类别问题的有希望的结果已经发表，但对作为 GA 有效性理由的构建块假设的普遍性和可行性的怀疑仍然存在。为了从分布算法估计的角度理解其局限性，已经进行了大量研究。

局限性
与其他优化算法相比，使用遗传算法有一些缺点：

• 对于复杂的情况，重复的适应度函数评估通常是人工进化算法中最具挑战性和约束的部分。复杂的高维、多模态问题经常需要昂贵的适应度函数分析才能找到最佳解决方案。在结构优化等实际问题中，评估单个函数可能需要数小时到数天的详尽模拟。标准优化技术无法解决此类问题。在这种情况下，可能需要放弃精确的评估，转而采用计算上有效的近似适应度测量。组合近似模型可能是将遗传算法成功应用于复杂现实问题的最有前途的方法之一。
• 遗传算法努力增加复杂性。也就是说，在遭受突变的元素数量较多的区域中，搜索空间大小经常呈指数增长。因此，将该方法应用于诸如制造发动机、房屋或飞机等问题是非常具有挑战性的。这些问题必须简化为最基本的形式，以便通过进化搜索来处理。因此，我们经常发现进化算法编码的是风扇叶片而不是发动机的想法，编码的是建筑形式而不是精确的施工蓝图，编码的是机翼而不是完整的飞机设计。第二个复杂性问题是防止已经进化为代表合理解决方案的部件进一步发生破坏性突变，特别是当它们的适应性评估要求它们与其他部件良好结合时。
• “更好”的解决方案只是与其他解决方案相比。因此，停止条件并不总是明显的。
• 遗传算法有时会倾向于局部最优或任意位置，而不是获得问题的整体最优。这表明它缺乏放弃即时健身而追求长期健身的“诀窍”。这种可能性取决于适应度景观的形式；特定的困难可以使达到全局最优变得容易，而其他困难则可以使函数更容易找到局部最优点。尽管没有免费午餐定理表明这个问题没有通用的解决方案，但可以通过采用不同的适应度函数、加速突变或利用维持多样化解决方案群体的选择方法来解决。“利基惩罚”是保护多样性的常见策略。它涉及对任何彼此足够相似的人群（利基半径）增加惩罚，这会减少他们在后代中的代表性，并允许其他（不太相似）的人留在人群中。然而，根据问题的性质，这种策略可能行不通。当大多数群体彼此过于相似时，另一种策略是用随机产生的个体替换一部分群体。遗传算法（和遗传编程）需要多样性，因为同质群体在交叉时不会产生新的解决方案。在进化编程或方法中，多样性是不必要的，因为突变被更频繁地使用。
• 对动态数据集进行操作具有挑战性，因为早期基因组收敛导致的结论可能不适用于后续数据。有人建议，可以通过增加遗传多样性和延迟早期收敛来解决这个问题，或者通过在解决方案质量下降时增加突变的可能性（称为触发超突变的过程），或者通过偶尔引入全新的、随机生成的元素进入基因库（称为随机移民的过程）。再一次，进化编程和策略可以使用所谓的“逗号策略”来实现，其中新的父母仅从后代中选择，并且现有的父母不被保留。对于运动困难的情况，这可能效果更好。
• 由于没有机制可以收敛到答案（没有什么山可以爬），当唯一的适应度度量是单个正确/错误的度量时（例如选择问题），遗传算法无法成功解决问题。在某些情况下，随机搜索也可以同样快速地找到解决方案。然而，如果情况允许以（可能）不同的结果重复成功/失败实验，则成功与失败的比率是一个足够的适应性指标。
• 对于特定的优化问题和问题案例，就收敛速度而言，其他优化方法可能比遗传算法更有效。替代和补充算法包括基于整数线性规划、蚁群优化、进化规划、模拟退火、高斯适应、爬山和群体智能（例如，蚁群优化、粒子群优化）的方法。对问题的理解程度影响遗传算法是否合适；众所周知的问题通常具有高级的专业技术。