遗传算法简介

遗传算法是一种通过模拟自然进化过程（如“适者生存”、染色体交叉和变异）来寻找问题最佳解决方案的程序。本文将简要介绍遗传算法的编写方法，讨论编写自己的算法时需要考虑的一些重要因素，并提供一些遗传算法实际应用的示例。

关键要点

• 遗传算法模拟“适者生存”等进化过程，利用选择、交叉和变异等机制来寻找复杂问题的最优解。
• 在遗传算法中，潜在的解决方案表示为染色体，其适用性通过适应度函数进行评估，该函数决定其被选中进行繁殖的概率。
• 交叉过程将来自一对亲本解决方案的特征组合起来以创建新的后代，而变异则会在后代中引入随机变化，从而保持遗传多样性并潜在地发现新的解决方案。
• 由于遗传算法能够有效地探索大型、复杂的解决方案空间，因此对于传统搜索和优化方法难以解决的问题非常有效。
• 遗传算法的实际应用范围从设计具有增强性能特征的天线到优化网页设计，这说明了它们在解决实际问题方面的多功能性和强大功能。

破解未知信息

时间是2369年，人类已经遍布星辰大海。你是一位年轻而聪明的医生，驻扎在一个繁忙的深空星际基地，那里熙攘着星际旅行者、商人，以及偶尔出现的亡命之徒。你到达后不久，基地的一个店主对你产生了兴趣。他声称自己只是一个简单的裁缝，但谣言说他是为一个特别邪恶的政权工作的秘密特工。

你们开始每周一起共进午餐，讨论从政治到诗歌的各种话题。即使过了几个月，你仍然不确定他是在表达浪漫情愫还是在套取秘密（你当然没有任何秘密）。也许两者兼而有之。

有一天午餐时，他向你提出了一个挑战：“我有一条信息要告诉你，亲爱的医生！我当然不能告诉你是什么。但我告诉你，它有12个字符长。这些字符可以是任何字母、空格或标点符号。我会告诉你你的猜测与实际答案的差距。你很聪明；你认为你能解开它吗？”

你回到医疗舱的办公室，仍然想着他刚才说的话。突然，你之前在附近电脑上运行的一个基因测序模拟实验给了你一个主意。你不是密码破译专家，但也许你可以利用你在遗传学方面的专业知识来破译他的信息！

一些理论

正如我在开头提到的，遗传算法是一种使用模拟驱动进化的操作来搜索解决方案的程序。经过多次迭代，算法从一组可能的解决方案中选择最佳候选者（猜测），将它们重新组合，并检查哪些组合使它更接近解决方案。较差的候选者将被丢弃。

在上面的场景中，秘密信息中的任何字符都可以是A-Z、空格或基本标点符号。假设这给了我们以下32个字符的“字母表”：ABCDEFGHIJKLMNOPQRSTUVWXYZ -.,!?这意味着有32¹²（大约1.15×10¹⁸）种可能的信息，但其中只有一个是正确的。检查每种可能性需要花费太长时间。相反，遗传算法将随机选择12个字符，并要求裁缝/间谍对结果与他的信息有多接近进行评分。这比暴力搜索更有效，因为分数让我们能够微调未来的候选者。反馈使我们能够衡量每次猜测的适应度，并有望避免在死胡同浪费时间。

假设我们做了三个猜测：HOMLK?WSRZDJ、BGK KA!QTPXC和XELPOCV.XLF!。第一个候选者的分数为248.2，第二个为632.5，第三个为219.5。分数的计算方式取决于具体情况，我们稍后会讨论，但现在让我们假设它是基于候选者和目标信息之间的偏差：完美的分数是0（即没有偏差；候选者和目标相同），而较高的分数意味着偏差越大。得分248.2和219.5的猜测比得分635.5的猜测更接近秘密信息的内容。

未来的猜测是通过组合最佳尝试进行的。组合候选者的方法有很多，但现在我们考虑一种简单的交叉方法：新猜测中的每个字符都有50-50的概率从第一个或第二个父代候选者中复制。如果我们采用HOMLK?WSRZDJ和XELPOCV.XLF!这两个猜测，那么我们后代候选者的第一个字符有50%的概率是H，50%的概率是X，第二个字符将是O或E，依此类推。后代可能是HELLO?W.RLD!。

通过交叉生成新的候选者

然而，如果我们只使用父代候选者的值，则在多次迭代中可能会出现一个问题：缺乏多样性。如果我们有一个候选者由全部A组成，另一个由全部B组成，那么仅通过交叉生成的任何后代都将仅由A和B组成。如果解决方案包含C，我们就会很不幸。

为了减轻这种风险并在仍然缩小解决方案范围的同时保持多样性，我们可以引入微小的变化。与其直接进行50-50的分割，我们允许一个小的概率来代替字母表中的任意值。通过这种变异，后代可能会变成HELLO WORLD!。

变异使事情保持新鲜！

不出所料，遗传算法借鉴了大量遗传科学的词汇。因此，在我们进一步讨论之前，让我们完善一些术语：

• 等位基因：遗传字母表中的一个成员。等位基因的定义取决于算法。例如，0和1可能是用于处理二进制数据的遗传算法的等位基因，用于处理代码的算法可以使用函数指针等。在我们的秘密信息场景中，等位基因是字母表中的字母、空格和各种标点符号。
• 染色体：给定的等位基因序列；候选解决方案；“猜测”。在我们的场景中，HOMLK?WSRZDJ、XELPOCV.XLF!和HELLO WORLD!都是染色体。
• 基因：染色体中特定位置的等位基因。对于染色体HOMLK?WSRZDJ，第一个基因是H，第二个基因是O，第三个基因是M，依此类推。
• 种群：作为问题解决方案提出的一个或多个候选染色体的集合。
• 世代：算法特定迭代期间的种群。一代中的候选者提供基因来产生下一代的种群。
• 适应度：评估候选者与所需解决方案接近程度的度量。适应性强的染色体更有可能将其基因传递给未来的候选者，而适应性较弱的染色体更有可能被丢弃。
• 选择：选择一些候选者进行繁殖（用于创建新的候选染色体）并丢弃其他候选者的过程。存在多种选择策略，它们对选择较弱候选者的容忍度各不相同。
• 繁殖：将一个或多个候选者的基因组合起来以产生新的候选者的过程。供体染色体称为父代，产生的染色体称为后代。
• 变异：在后代中随机引入异常基因，以防止在许多世代中失去遗传多样性。

给我看一些代码！

我怀疑，鉴于高级概述和术语列表，您可能现在很想看到一些代码。因此，让我们来看一些解决我们的秘密信息问题的JavaScript代码。在阅读过程中，我邀请您思考哪些方法可能被认为是“样板代码”，以及哪些方法的实现更紧密地与我们试图解决的问题相关联：

// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...

我们首先定义一个Candidate数据对象，只是为了将染色体与其适应度分数配对。为了方便起见，还附加了一个静态排序方法；当我们需要查找或输出最合适的染色体时，它会派上用场。

接下来，我们有一个GeneticAlgorithm类，它实现了遗传算法本身。

构造函数采用解决模拟所需各种参数的对象。它提供了一种指定遗传字母表、目标消息以及其他参数的方法，这些参数用于定义模拟将在其下运行的约束。在上面的示例中，我们期望每一代都有100个候选者的种群。从中，只有40个染色体将被选中进行繁殖。我们有3%的概率引入变异，并且在发生变异时，我们将最多改变两个基因。maxGenerations值用作保护措施；如果我们在100万代后没有收敛到一个解决方案，我们将无论如何终止脚本。

值得一提的是，运行算法时提供的种群、选择大小和最大世代数相当小。更复杂的问题可能需要更大的搜索空间，这反过来会增加算法的内存使用量以及运行所需的时间。但是，强烈建议使用较小的变异参数。如果它们变得太大，我们将失去基于适应度繁殖候选者的任何好处，并且模拟开始变成随机搜索。

像randomInt()、init()和run()这样的方法可能被认为是样板。但仅仅因为有样板并不意味着它不会对模拟产生实际影响。例如，遗传算法大量使用随机性。虽然内置的Math.random()函数适合我们的目的，但对于其他问题，您需要更精确的随机生成器。Crypto.getRandomValues()提供更强的密码学随机值。

性能也是一个考虑因素。我在本文中力求清晰易懂，但请记住，操作将反复进行。您可能会发现自己需要微优化循环中的代码，使用更高效的内存数据结构，以及内联代码而不是将其分离到函数/方法中，所有这些都与您的实现语言无关。

calcFitness()、select()、reproduce()甚至stop()方法的实现是特定于我们试图解决的问题的。

calcFitness()返回一个值，该值根据某些期望标准衡量染色体的适应度——在我们的例子中，它是它与秘密消息匹配的程度。计算适应度几乎总是依赖于具体情况；我们的实现使用每个基因的ASCII值计算均方误差，但其他指标可能更合适。例如，我可以计算两个值之间的汉明距离或莱文斯坦距离，甚至可以结合多个测量值。最终，重要的是适应度函数要根据手头的问题返回有用的测量值，而不仅仅是布尔“适合”/“不适合”。

select()方法演示了一种精英选择策略——仅选择整个种群中最合适的候选者进行繁殖。正如我前面提到的，还存在其他策略，例如锦标赛选择，它从种群中各个候选者的集合中选择最合适的候选者，以及玻尔兹曼选择，它对选择候选者施加越来越大的压力。这些不同方法的目的是确保染色体有机会传递可能在以后被证明有益的基因，即使它可能并不立即显而易见。这些和其他选择策略的深入描述以及示例实现很容易在网上找到。

说明各种选择策略

组合基因的方法也有很多。我们的代码使用均匀交叉创建后代，其中每个基因都有相同的概率从一个父代中选择。其他策略可能偏向于一个父代的基因而不是另一个父代。另一种流行的策略是k点交叉，其中染色体在k个点处分割，产生k 1个片段，这些片段组合起来产生后代。交叉点可以是固定的，也可以是随机选择的。

说明k点交叉策略

我们也不限于两个父代染色体；我们可以组合来自三个或更多候选者的基因，甚至可以基于单个候选者构建。考虑一个通过绘制随机多边形来进化图像的算法。在这种情况下，我们的染色体实现为图像数据。在每一代中，从种群中选择最合适的图像作为父代，并且所有子代候选者都是通过将其自身的多边形绘制到父代副本上来生成的。父代染色体/图像作为基础，子代染色体/图像是父代的独特变异/图纸。

遗传算法的实际应用

遗传算法既可以用于娱乐，也可以用于盈利。也许遗传算法实际应用的两个最流行的例子是BoxCar 2D和NASA进化出的X波段天线。

BoxCar 2D是一个使用遗传算法来进化能够穿越模拟地形的最佳“汽车”的模拟。汽车由八个随机向量构成一个多边形，并将车轮连接到随机点。该项目的网站可以在boxcar2d.com上找到，该网站在其关于页面上简要介绍了该算法，并提供了一个排行榜，展示了一些最佳设计。不幸的是，该网站使用Flash，现在可能对许多人来说无法访问——在这种情况下，如果您好奇，可以在YouTube上找到各种屏幕录制。您可能还想查看Rafael Matsunaga使用HTML5技术编写的类似（优秀）模拟，可在rednuht.org/genetic_cars_2上找到。

BoxCar 2D中进化出的汽车，图片来自BoxCar 2D排行榜

2006年，NASA的太空技术5号任务在太空中测试了各种新技术。其中一项技术是使用遗传算法设计的新型天线。设计新型天线可能是一个非常昂贵且耗时的过程。它需要特殊的专业知识，并且当需求发生变化或原型无法按预期执行时，经常会发生挫折。进化出的天线创建时间更短，增益更高，功耗更低。讨论设计过程的论文全文可在网上免费获得（使用进化算法的自动化天线设计）。遗传算法也已被用于优化现有天线设计以获得更高的性能。

它们类别中最好的进化天线，图片来自自动化天线设计论文

遗传算法甚至已被用于网页设计！Elijah Mensch的一个高级项目（通过应用交互式遗传算法优化网站设计）使用它们通过操作CSS规则并使用A/B测试对适应度进行评分来优化新闻文章轮播。

第1代和第9代的最佳布局，图片来自优化网站设计论文

结论

到目前为止，您应该对遗传算法是什么有了基本的了解，并且对它们的词汇足够熟悉，可以解读您在自己的研究中可能遇到的任何资源。但是，理解理论和术语只是工作的一半。如果您计划编写自己的遗传算法，您还必须了解您的特定问题。在开始之前，以下是一些需要自问的重要问题：

• 我如何将我的问题表示为染色体？我的有效等位基因是什么？
• 我知道目标是什么吗？也就是说，我在寻找什么？是特定值还是任何适应度超过某个阈值的解决方案？
• 我如何量化候选者的适应度？
• 我如何组合和变异候选者以产生新的候选解决方案？

我希望我还帮助您了解程序如何从自然中汲取灵感——不仅在形式上，而且在过程和功能上。请随时在论坛中分享您自己的想法。

关于遗传算法的常见问题

• 什么是遗传算法（GA）？遗传算法是一种启发式搜索和优化技术，其灵感来自自然选择过程。它用于通过模拟进化的原理来寻找优化和搜索问题的近似解。
• 遗传算法是如何工作的？遗传算法通过在连续几代中进化候选解决方案的种群来工作。该过程包括选择、交叉（重组）、变异和评估种群中的个体，旨在迭代地提高解决方案的质量。
• 遗传算法适用于哪些类型的问题？遗传算法用途广泛，可以应用于各种优化和搜索问题，包括但不限于调度、路由、机器学习和函数优化。
• 如何为遗传算法选择参数？种群大小、变异率和交叉率等参数取决于特定问题和解决方案空间的特征。实验和调整是为给定问题找到最佳参数值的常用做法。
• 适应度函数在遗传算法中的作用是什么？适应度函数量化了个体解决方案在给定问题中的执行情况。它指导选择过程，有利于对优化目标有积极贡献的解决方案。

以上是遗传算法简介的详细内容。更多信息请关注PHP中文网其他相关文章！