遗传算法

课前小测验

遗传算法（GA）是一种基于进化的AI方法，它使用群体进化的方法来获取给定问题的最优解。它们由John Henry Holland于1975年提出。

遗传算法基于以下思想：

• 问题的有效解决方案可以表示为基因
• 交叉允许我们将两个解决方案组合在一起以获得新的有效解决方案
• 选择用于使用某些适应度函数选择更优的解决方案
• 突变被引入以破坏优化过程，使我们摆脱局部最小值

如果您想实现一个遗传算法，您需要以下内容：

• 找到一种将问题解决方案编码为基因 g∈Γ的方法
• 在基因集Γ上定义适应度函数 fit: Γ→R。较小的函数值对应于更好的解决方案。
• 定义交叉机制，以便将两个基因组合在一起得到一个新的有效解决方案 crossover: Γ²→Γ。
• 定义突变机制 mutate: Γ→Γ。

在许多情况下，交叉和突变是相当简单的算法，用于操作基因作为数值序列或位向量。

遗传算法的具体实现可以从一个案例到另一个案例有所不同，但总体结构如下：

1. 选择初始种群 G⊂Γ
2. 随机选择将在该步骤中执行的操作之一：交叉或突变
3. 交叉：

• 随机选择两个基因 g₁, g₂ ∈ G
• 计算交叉 g=crossover(g₁,g₂)
• 如果 fit(g)<fit(g₁) 或 fit(g)<fit(g₂)，则用 g 替换种群中的相应基因。

4. 突变 - 随机选择一个基因 g∈G 并将其替换为 mutate(g)
5. 从第2步重复，直到我们得到足够小的 fit 值，或者达到步骤限制。

典型任务

遗传算法通常解决的任务包括：

1. 调度优化
2. 最优打包
3. 最优切割
4. 加速穷举搜索

✍️ 练习：遗传算法

继续学习以下笔记本：

前往 这个笔记本 查看遗传算法的两个示例：

1. 公平分配财宝
2. 八皇后问题

结论

遗传算法用于解决许多问题，包括物流和搜索问题。该领域受到心理学和计算机科学结合的研究启发。

挑战

“遗传算法易于实现，但其行为难以理解。”来源 做一些研究，找到一个遗传算法的实现，例如解决数独谜题，并解释它是如何工作的，比如通过草图或流程图。

课后小测验

复习与自学

观看，讨论计算机如何通过遗传算法训练的神经网络学会玩超级马里奥游戏。我们将在下一节深度强化学习中了解更多关于计算机学习玩游戏的内容。

作业：丢潘图方程

您的目标是解决所谓的丢潘图方程——一个整数根的方程。例如，考虑方程 a+2b+3c+4d=30。您需要找到满足此方程的整数根。

此作业灵感来自这篇文章。

提示：

1. 您可以认为根在区间 [0;30] 内
2. 将根的列表视为基因

请使用 Diophantine.ipynb 作为起点。

声明:
本文件灏天文库团队进行了翻译。尽管我们力求准确，但请注意，翻译可能包含错误或不准确之处。原文档以其原始语言为准。我们不对因使用此翻译而产生的任何误解或误译负责。