遗传算法

是什么

自然进化可以被模拟成一场游戏，在这场游戏中，对一个玩得好的生物体的奖励是将其遗传物质传递给它的后继者和继续生存。^[2]在自然进化中，一个个体的表现如何，取决于它与谁合作，与谁竞争，以及环境的影响。遗传算法是对一个优化问题的候选解决方案的群体（染色体、个体、生物或表型）的自然选择的模拟。

对候选者进行评估和杂交，试图做出好的解决方案。这样的解决方案可能需要大量的时间，而且对人类来说并不明显。进化阶段从一个随机生成的生命群体开始。在每一代中，人口中每个个体的适配性都被评估。一些个体被随机地从当前种群中挑选出来（基于他们的健康状况），并被修改（重新组合，可能是随机变异）以形成一个新的种群。这个循环在这个新种群中重复进行。该算法在设定的世代数过后，或在种群达到良好的适配水平后结束。如果算法因达到最大代数而结束，这并不一定意味着已经获得了良好的健身水平。

在计算机上进行编程

伪代码是。

1. 初始化。创建一些可能的解决方案；很多时候，这些解决方案会有随机值
2. 评估。健身函数对每个解决方案进行打分；分数将是一个数字，说明这个解决方案的解决程度。
3. 运行以下步骤，直到满足停止的要求。
1. 挑选。为下一次迭代挑选解决方案/个体
2. 重新组合。合并所选的解决方案
3. 变异。随机地改变新创建的解决方案
4. 评价。应用健身函数，见步骤2。
5. 如果没有达到停止的要求，就用选择步骤重新开始。

例子

上述描述是抽象的。一个具体的例子有助于。

应用

一般来说

遗传算法擅长解决包括时间表和日程安排的问题。它们也被应用于工程。它们经常被用来解决全局优化问题。

作为一般的经验法则，遗传算法在具有复杂健身景观的问题领域可能是有用的，因为混合的目的是使种群远离传统爬坡算法可能陷入的局部优化。常用的交叉运算符不能改变任何统一的群体。仅仅是变异就可以提供整个遗传算法过程的反复性（被视为马尔科夫链）。

遗传算法解决的问题的例子包括：设计用于将阳光输送到太阳能收集器的镜子、设计用于在太空中接收无线电信号的天线、计算机数字的行走方法、复杂流场中空气动力体的最佳设计

在他的《算法设计手册》中，Skiena建议不要用遗传算法来完成任何任务："用遗传算子（如比特串上的突变和交叉）来模拟应用是很不自然的。伪生物学在你和你的问题之间又增加了一层复杂性。第二，遗传算法在非微观问题上需要很长的时间。[......]与进化论的类比--重大进展需要[原文如此]数百万年--可能相当合适。[......]我从来没有遇到过任何问题，在我看来，遗传算法是攻击它的正确方式。此外，我从未见过任何使用遗传算法的计算结果给我留下良好的印象。对于你的启发式搜索需求，请坚持使用模拟退火法"。

棋盘游戏

棋盘游戏是应用于博弈论问题的遗传算法领域的一个非常相关的部分。早期关于计算智能和游戏的大部分工作都是针对经典的棋盘游戏，如井字棋、象棋和跳棋。^[3]国际象棋和跳棋。^[4]现在，在大多数情况下，棋盘游戏可以由计算机发挥出比最好的人类更高的水平，即使使用盲目的穷举搜索技术。围棋是这种趋势的一个明显的例外，到目前为止，它一直在抵制机器的攻击。现在最好的围棋电脑玩家的水平与一个优秀的新手差不多。^[5][6]据说，围棋策略在很大程度上依赖于模式识别，而不是像国际象棋和其他更多的棋子独立的游戏那样仅仅依靠逻辑分析。寻找高质量解决方案所需的巨大有效分支因素严重限制了在棋谱搜索中可以使用的前瞻。

电脑游戏

遗传算法可用于计算机游戏，以创造人工智能（计算机与你对弈）。这可以使游戏体验更加真实；如果人类玩家可以找到一连串的步骤，即使在不同的游戏中重复，也总能获得成功，那就不能再有挑战了。相反，如果一种学习技术，如战略家的遗传算法可以避免重复过去的错误，那么游戏将有更多的可玩性。

遗传算法需要以下部分。

• 用解决方案来表示挑战的方法（例如，在战略游戏中的攻击中路由士兵）。
• 一个健身或评价函数，以确定一个实例的质量（例如，在这种攻击中对对手造成的伤害的测量）。

健身函数接受一个实体的变异实例并测量其质量。这个函数是根据问题领域定制的。在许多情况下，特别是那些涉及代码优化的情况下，健身函数可能只是一个系统计时函数。一旦定义了遗传表征和健身函数，遗传算法将如前所述实例化初始候选人，然后通过重复应用突变、交叉、反转和选择操作符（根据问题领域定义）来改进。

局限性

与其他优化算法相比，遗传算法的使用有其局限性。

• 对复杂问题进行重复的适配函数评估往往是人工进化算法中最具局限性的环节。寻找复杂问题的最优解往往需要非常昂贵的健身函数评估。在现实世界的问题中，如结构优化问题，一次函数评估可能需要几个小时到几天的完整模拟。典型的优化方法不能处理这种类型的问题。通常有必要使用近似法，因为计算精确的解决方案需要太长时间。遗传算法有时结合不同的近似模型来解决复杂的实际问题。
• 遗传算法的规模不大。也就是说，当暴露在变异中的元素数量很大时，搜索空间的大小往往会呈指数级增长。这使得在设计发动机、房屋或飞机等问题上使用该技术变得非常困难。为了将遗传算法用于此类问题，必须将其分解为最简单的表示方法。由于这个原因，我们看到进化算法对风扇叶片的设计进行编码，而不是对发动机进行编码，对建筑形状进行编码，而不是对详细的施工图进行编码，对机翼进行编码，而不是对整个飞机设计进行编码。复杂性的第二个问题是如何保护那些已经进化为代表好的解决方案的部分，使其免受进一步的破坏性突变，特别是当它们的健身评估需要它们与其他部分很好地结合时。
• "更好 "的解决方案只是在与其他解决方案的比较中。因此，在每个问题中，停止标准并不明确。
• 在许多问题上，遗传算法有向局部最优甚至任意点收敛的倾向，而不是向问题的全局最优收敛。这意味着该算法不 "知道 "如何牺牲短期的适配性来获得长期的适配性。这种情况发生的可能性取决于适配函数的形状：某些问题容易找到全局最优，其他问题可能使函数更容易找到局部最优。这个问题可以通过使用不同的适配函数、增加突变率或使用保持多样化解决方案的选择技术来减少。一种维持多样性的常见技术是使用 "生态位惩罚"：任何具有足够相似性（生态位半径）的个体组都会受到惩罚，这将减少该组在下一世代的代表性，允许其他（不太相似）的个体保留在种群中。然而，这个技巧可能并不有效，这取决于问题的景观。另一种可能的技术是，当大部分群体过于相似时，简单地用随机生成的个体替换部分群体。多样性在遗传算法（和遗传编程）中很重要，因为跨越一个同质的群体不会产生新的解决方案。在进化策略和进化编程中，多样性并不重要，因为它更依赖于变异。
• 对动态数据集进行操作是很困难的，因为基因组在早期就开始向可能对后来的数据不再有效的解决方案收敛。已经提出了几种方法来解决这个问题，以某种方式增加遗传多样性，防止早期收敛，或者在解决方案质量下降时增加突变的概率（称为触发式超突变），或者偶尔在基因库中引入全新的、随机产生的元素（称为随机移民）。同样，进化策略和进化编程可以用所谓的 "逗号策略 "来实现，在这种策略中，父母不被保留，新的父母只从后代中选择。这在动态问题上可以更加有效。
• 遗传算法不能有效地解决唯一的适配度是单一的对/错度量的问题（如决策问题），因为没有办法收敛在解决方案上（没有小山可以爬）。在这些情况下，随机搜索可能会像GA一样快速找到一个解决方案。然而，如果情况允许成功/失败的试验被重复，给出（可能）不同的结果，那么成功与失败的比率就提供了一个合适的适配度。
• 对于特定的优化问题和问题实例，就收敛速度而言，其他优化算法可能比遗传算法更有效。替代和补充算法包括进化策略、进化编程、模拟退火、高斯适应、爬坡和蜂群智能（如：蚁群优化、粒子群优化）以及基于整数线性编程的方法。遗传算法的适用性取决于问题的知识量；众所周知的问题往往有更好、更专业的方法。

历史

1950年，阿兰-图灵提出了一种 "学习机"，它将与进化的原理并行。计算机模拟进化的工作早在1954年就开始了，当时尼尔斯-阿勒-巴里切利在新泽西州普林斯顿高等研究所使用计算机。他在1954年发表的文章没有受到广泛关注。从1957年开始，澳大利亚定量遗传学家亚历克斯-弗雷泽发表了一系列关于对具有控制可测量性状的多个基因座的生物体进行人工选择的模拟论文。从这些开始，生物学家对进化的计算机模拟在20世纪60年代初变得更加普遍，Fraser和Burnell（1970）和Crosby（1973）的书中描述了这些方法。弗雷泽的模拟包括现代遗传算法的所有基本要素。此外，Hans-Joachim Bremermann在20世纪60年代发表了一系列论文，也采用了优化问题的解决方案的群体，经历了重组、变异和选择。布雷默曼的研究还包括现代遗传算法的元素。其他值得注意的早期先驱包括理查德-弗里德伯格、乔治-弗里德曼和迈克尔-康拉德。许多早期论文被Fogel（1998）转载。

尽管巴里切利在他1963年报告的工作中，模拟了玩一个简单游戏的能力的进化，但由于英戈-雷恩伯格和汉斯-保罗-施韦费尔在20世纪60年代和70年代初的工作，人工进化成为一种广泛认可的优化方法--雷恩伯格的小组能够通过进化策略解决复杂的工程问题。另一种方法是Lawrence J. Fogel的进化编程技术，它被提出来用于生成人工智能。进化编程最初使用有限状态机来预测环境，并使用变异和选择来优化预测逻辑。特别是遗传算法，通过约翰-霍兰在20世纪70年代初的工作，特别是他的《自然和人工系统中的适应》（1975）一书而变得流行。他的工作起源于Holland和他在密歇根大学的学生对细胞自动机的研究。Holland提出了一个预测下一代质量的形式化框架，被称为Holland的模式定理。遗传算法的研究在很大程度上仍然是理论性的，直到20世纪80年代中期，第一届遗传算法国际会议在宾夕法尼亚州的匹兹堡举行。