软计算中的遗传算法

遗传算法 (GA) 是更广泛的进化算法 (EA) 的一个子集，它是计算机科学和运筹学中一种受自然选择过程启发的元启发式算法。遗传算法经常采用受生物学启发的算子，包括突变、交叉和选择，来为优化和搜索问题生成高质量的解决方案。例如，用于改进决策树性能的优化、解决数独谜题、超参数优化、因果推断等都是 GA 的应用。

方法论

优化问题

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

“一代”用来描述进化过程中每一次迭代的种群，通常从随机生成的个体种群开始。每一代，种群中的每个成员都会对其适应度进行评估，适应度通常是所处理的优化问题的目标函数值。新一代是通过从当前种群中随机选择适应度最高的个体，重组它们的基因组，并引入随机突变来创建的。下一轮算法迭代将使用新一代的候选解决方案。算法通常在种群达到期望的适应度水平或生成了最大代数时终止。

标准的遗传算法必须对解决方案域进行遗传表示，并使用适应度函数进行评估。

每个潜在的解决方案通常表示为一组比特，也称为比特集或字符串。使用不同类型和结构的数组在根本上是相同的。这些遗传表示的主要优点在于其固定大小使得其部分易于对齐，并允许进行简单的交叉操作。也可以使用可变长度的表示，但在这种情况下，交叉的实现更加困难。在基因表达编程中，会考察线性染色体和树的组合。遗传编程探索树形式的表示，而进化编程则探索图形式的表示。

在定义了遗传表示和适应度函数后，GA 会初始化解决方案种群，然后通过反复使用突变、交叉、反转和选择操作来改进它。

初始化

根据问题的性质，种群的大小可以从几百到几千个潜在解决方案不等。初始种群通常是随机生成的，允许覆盖所有潜在解决方案（搜索空间）。有时，解决方案可能会在最有可能找到最佳解决方案的区域被“种子化”。

选拔

在每一代中，当前种群的一部分会被选出来繁殖新一代。选择个体解决方案时会使用基于适应度的方法，适应度更高的解决方案（由适应度函数确定）通常有更高的几率被选中。一些选择方法会评估每个解决方案的适应度并偏好最佳的解决方案。其他技术则仅仅对代表性的种群样本进行评分，因为最初的过程可能需要很长时间。

适应度函数定义在遗传表示之上，用于评估所表示解决方案的有效性。适应度函数总是取决于问题。例如，在背包问题中，目标是在特定容量的背包中装入尽可能多的物品。一个比特数组可以表示一个解决方案，其中每个比特代表一个单独的物品，其值（0 或 1）表示该物品是否在背包中。这类表示法有时并不准确，因为物品的大小有时会超出背包的存储容量。

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

遗传修饰符

通过组合遗传算子交叉（也称为重组）和突变，下一步是从最初选择的解决方案中生成第二代解决方案种群。

为了产生每个新的解决方案，会从先前选择的繁殖池中选择一对“父”解决方案。通过使用上述交叉和突变技术构建一个“子”解决方案，创建一个新的解决方案，它通常与它的“父母”共享许多特征。对于每个新的子代，都会选择新的父代，然后重复此过程，直到生成一个大小正确的新解决方案种群。一些研究表明，使用两个以上的“父代”可以产生更高质量的染色体，尽管基于使用两个父代的繁殖技术更“受生物学启发”。

这些活动最终导致下一代染色体种群与第一代不同。由于只有第一代中最优秀的个体被选中繁殖，加上一小部分适应度较低的解决方案，因此由于这种操作，种群的平均适应度应该有所提高。这些不太有效的策略保证了亲本基因库中的遗传变异，从而保证了下一代子代的遗传多样性。

交叉和突变的作用是受到争议的。Fogel (2006) 的许多参考文献都支持基于突变的搜索的重要性。

尽管交叉和突变是最常见的两个遗传算子，但遗传算法也可以利用重组、群体灭绝或迁移。

为了找到适合所考虑问题类的设置，调整突变概率、交叉概率和种群大小等变量是值得的。突变率相对较低可能导致遗传漂移的非遍历现象。如果重组率过高，遗传算法可能无法完全收敛。如果不使用精英选择，高突变率可能导致优秀解决方案的丢失。

适当的种群大小确保了足够多的遗传多样性来解决手头的问题。但是，如果设置的值大于需要，则会浪费计算资源。

启发式算法

除了上述重要算子之外，还可以使用其他启发式算法来加速或加强计算。分化启发式算法通过惩罚过于相似的候选解决方案之间的交叉来阻止种群同质化并延迟收敛到次优解。

终止

在满足终止条件之前，会重复此代际过程。典型的终止条件包括：

• 找到满足最小要求的解决方案
• 最高排名解决方案的适应度正在接近或已达到平台期，意味着后续迭代不再提供更好的结果。
• 手动检查。如前所述的这些组合。固定代数。分配的预算（计算时间/金钱）。

构建块理论

尽管遗传算法很容易创建，但理解它们的行为却很困难。特别是，很难理解为什么这些算法在解决现实世界问题时通常会产生高度适应的解决方案。构建块假设 (BBH) 的组成部分是：

1. 一种通过定位和重组“构建块”（即低阶、短定义长度且适应度高于平均值的模式）来适应的启发式解释。
2. 该思想是遗传算法通过有效和隐式地实现这种启发式来适应。

根据 Goldberg 的说法，通过采样、重组（交叉）和重新采样短、低阶、高适应度的模式来生成可能具有更高适应度的字符串。在某种意义上，通过使用这些特定的模式（构建块），我们降低了问题的复杂性；我们不是通过测试所有可能的组合来生成高性能字符串，而是利用早期采样中最佳的部分解决方案来生成越来越好的字符串。

我们已经给它们取了一个特殊的名字：构建块。这是因为具有短定义长度和低阶的高适应度模式在遗传算法的运行中起着至关重要的作用。遗传算法通过并列短、低阶、高性能的模式或构建块来寻求接近最优的性能，就像一个蹒跚学步的孩子用基础的木块搭建奇妙的堡垒一样。

尽管需要就构建块假设的有效性达成更多共识，但它已被反复评估并用作参考。例如，已经提出了许多分布估计过程来创建一个假设成立的环境。虽然已经公布了一些问题类别的好结果，但关于构建块假设作为 GA 有效性理由的普遍性和可行性的怀疑依然存在。从分布算法估计的角度来看，已经做了大量研究来理解其局限性。

局限性

与其他优化算法相比，使用遗传算法存在一些缺点：

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

变体

染色体表示

最基本的方法是将每个染色体表示为位串。尽管可以使用浮点表示，但整数通常可以用来表示数值参数。进化编程和进化技术都适合浮点表示。已经提出了实值遗传算法，但这是一种误称，因为它需要准确反映 20 世纪 70 年代 John Henry Holland 的构建块理论。然而，根据理论和实验结果（见下文），有一些证据支持这一概念。

在比特级别，基本算法执行交叉和突变。其他变体将染色体视为一组整数，表示哈希、对象、链表中的节点、指令表的索引或任何其他类型的数据结构。在执行交叉和突变时，会尊重数据元素的边界。对于大多数数据类型，都可以创建特定的变异算子。对于许多专门的问题类别，不同的染色体数据类型似乎表现更好或更差。

当使用数字的位串表示时，通常会使用格雷码。这使得通过突变或交叉轻松修改整数成为可能。研究表明，这样做可以防止过早收敛到所谓的汉明障碍，即需要过多的同时突变（或交叉事件）才能改变染色体到一个更有利的状态。

其他方法将染色体表示为实值整数数组，而不是位串。模式的概念表明，一般来说，字母表越小，性能越好；然而，实值染色体起初就产生了良好的结果，这让研究人员感到惊讶。有人提出，当选择和重组占主导地位时，有限种群染色体中的基本值集会形成一个虚拟字母表，其基数远小于浮点表示所预测的。

通过将多种类型的异构编码基因连接到一个染色体中，可以扩展遗传算法可访问的区域。这种特定方法使得在问题参数的定义域多样化时能够解决优化问题。例如，在级联控制器调优问题中，外部循环可以实现具有根本不同描述的语言控制器（如模糊系统）。相反，内部循环控制器结构可以对应于标准的三参数调节器。这种特定类型的编码，它需要一种专门的交叉机制来按段重组染色体，对于复杂自适应系统的研究和建模，特别是进化过程，非常有用。

精英主义

作为创建新种群的基本过程的一个实际变体，可以将当前一代中最优秀的个体（们）不受改变地传递到下一代。这种被称为精英选择的策略确保了 GA 获取的解决方案的质量不会从一代到下一代下降。

并行应用

并行遗传算法实现有两种类型。粗粒度并行进化算法假设每个计算节点上都有一个种群，个体在节点之间移动。细粒度并行遗传算法的假设是每个处理器节点都有一个个体，该个体与其邻居进行交互以进行选择和繁殖。其他变体包括将时间依赖性或噪声引入适应度函数，例如用于在线优化问题的遗传算法。

可调 GAs

遗传算法的另一个值得注意且令人兴奋的变体是参数可调（自适应遗传算法，或 AGA）。根据交叉概率 (pc) 和突变概率 (pm)，遗传算法可以实现不同程度的解决方案准确性和收敛速度。研究人员已经对 GA 收敛进行了分析。

为了保持种群的变异性以及收敛能力，AGA 使用每一代的种群信息，而不是使用预设的 pc 和 pm 值。AGA（自适应遗传算法）中 pc 和 pm 的调整取决于解决方案的适应度值。AGA 版本的其他示例包括：一种增强收敛的简单早期示例是连续缩放方法。CAGA（基于聚类的自适应遗传算法）中 pc 和 pm 的调整取决于种群的优化阶段，这些阶段通过聚类分析进行评估。在更近期的方法中，使用抽象变量来确定 pc 和 pm。示例包括优势和共优势原理，以及 LIGA（分级插值遗传算法），它通过结合柔性 GA 和修改的 A* 搜索来解决搜索空间各向异性问题。

将 GA 与其他优化技术相结合有潜力非常成功。GA 在找到普遍合理的全局解决方案方面非常有效，但在找到找到精确最优解所需的最后几次变异方面效率不高。其他方法（如简单的爬山法）在找到约束区域内的绝对最优值方面非常有效。将爬山法与 GA 相结合可以提高爬山法的鲁棒性，同时增强 GA 的有效性。

这表明在自然情景中，遗传变异的原理可能意味着不同的东西。例如，交叉可能将几个母体 DNA 步骤相加，再加上几个父体 DNA 步骤，依此类推，假设这些步骤按顺序保留。这类似于向表型景观添加向量，这些向量更有可能沿着山脊。因此，过程效率可能会提高许多数量级。反转算子还可以选择将步骤以任何其他合理的顺序排列，这可能会增加它们生存的机会或提高它们的效率。

基因池重组是一种变体，其中种群进化而不是其个体。

已经创建了多种修改来提高 GA 在具有高度适应度上位性（即，解决方案的适应度取决于其变量的交互子集）的问题上的性能。这些算法试图（在使用之前）理解这些有利的表型连接。因此，它们通过自适应地减少破坏性重组来支持构建块假设。该策略的一些著名例子包括 mGA、GEMGA 和 LLGA。

问题领域

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

具有复杂适应度景观的问题领域可以从遗传算法中受益，因为混合（突变与交叉结合）旨在将种群从标准爬山算法可能陷入的局部最优中移出。请记住，经常使用的交叉算子不能改变任何统一的种群。整个遗传算法过程（视为马尔可夫链）的遍历性仅可以通过突变来实现。

进化算法已解决的问题示例包括复杂流场中的最佳空气动力学体设计、计算机图形的行走程序以及用于在太空中接收无线电传输的天线。

Skiena 在其《算法设计手册》中警告不要使用进化算法做任何事情。

使用像位串上的突变和交叉这样的遗传算子来建模应用程序非常奇怪。伪生物学增加了额外的复杂性，使您和您的问题分离。其次，将遗传算法应用于复杂问题需要很长时间。进化类比是一个很好的类比，因为有意义的进化需要数百万年。

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

• Stephen Skiena

历史

1950 年，艾伦·图灵（Alan Turing）提出了一个“学习机器”，该机器将模仿进化过程。1954 年，尼尔斯·阿勒·巴里切利（Nils Aall Barricelli）在普林斯顿高等研究院使用计算机模拟进化。他的 1954 年出版物几乎没有引起关注。从 1957 年开始，澳大利亚数量遗传学家亚历克斯·弗雷泽（Alex Fraser）发表了一系列关于模拟具有影响可量化性状的多个基因座的人工选择的论文。从这些开端开始，生物学家对进化的计算机建模在 20 世纪 60 年代初有所增加。Fraser 和 Burnell (1970) 以及 Crosby (1973) 出版了概述这些技术的书籍。Fraser 的模拟包含了当代遗传算法的所有基本组成部分。Hans-Joachim Bremermann 在他 20 世纪 60 年代撰写的几篇论文中也使用了优化问题的解决方案种群，这些解决方案经过重组、突变和选择。现代遗传算法也是 Bremermann 研究的一部分。Richard Friedberg、George Friedman 和 Michael Conrad 是值得注意的早期先驱。Fogel (1998) 重新打印了许多早期出版物。

尽管 Barricelli 在 1963 年出版的工作中模拟了一个简单游戏的技能进化，但由于 Ingo Rechenberg 和 Hans-Paul Schwefel 的工作，人工进化在 20 世纪 60 年代和 70 年代初成为一种常用的优化技术。Rechenberg 的团队使用进化技术来解决棘手的技术问题。另一种策略是 Lawrence J. Fogel 的进化编程方法，该方法被提议用于创建人工智能。最初，进化编程中使用有限状态机来预测环境，并通过变异和选择来改进预测逻辑。通过 John Holland 在 20 世纪 70 年代初的工作，特别是他的著作《自然和人工系统中的适应》（Adaptation in Natural and Artificial Systems, 1975），遗传算法尤其流行起来。

他的研究始于 Holland 和密歇根大学学生的细胞自动机实验。他建立的 Holland 的模式定理（Schema Theorem）是一个用于预测下一代质量的正式框架。直到 20 世纪 80 年代中期在匹兹堡举行的第一届遗传算法国际会议，GA 的研究主要仍停留在理论层面。

工业产品

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