原文出处：Genetic Algorithms 原作者：Microsoft · 许可证：MIT License 中文译本由诸葛AI学院整理，仅供学习参考，版权归原作者与微软所有。
遗传算法
课前小测
遗传算法（Genetic Algorithm，GA）基于一种进化式的思路：这类 AI 方法借用种群的进化过程，为给定问题寻找最优解。1975 年，约翰·亨利·霍兰德（John Henry Holland）提出了这种方法。
遗传算法建立在以下几个想法之上：
- 问题的可行解可以表示成基因（gene）
- 通过交叉（crossover），我们可以把两个解结合，得到一个可行的新解
- 通过选择（selection），用某个适应度函数（fitness function）挑出更优的解
- 引入变异（mutation），是为了扰动优化过程，帮我们跳出局部极小值（local minimum）
想实现一个遗传算法，你需要准备好下面几件事：
- 找到一种方法，把问题的解编码成基因 g ∈ Γ
- 在基因集合 Γ 上定义适应度函数 fit: Γ → R。函数值越小，解越好。
- 定义交叉机制，把两个基因结合成一个可行的新解：crossover: Γ² → Γ
- 定义变异机制 mutate: Γ → Γ
在很多情况下，交叉和变异都只是相当简单的算法：把基因当成数字序列或者位向量（bit vector）来操作。
遗传算法的具体实现因问题而异，但整体结构如下：
- 选择一个初始种群 G ⊂ Γ
- 随机决定这一步执行哪种操作：交叉还是变异
- 交叉： * 随机选取两个基因 g₁, g₂ ∈ G * 计算交叉结果 g = crossover(g₁, g₂) * 若 fit(g) < fit(g₁) 或 fit(g) < fit(g₂)，就用 g 替换种群中对应的那个基因
- 变异：随机选一个基因 g ∈ G，用 mutate(g) 替换它
- 回到第 2 步重复，直到 fit 的值足够小，或者达到步数上限。
典型任务
遗传算法通常解决的问题包括：
- 排程优化
- 最优装箱
- 最优下料
- 加快穷举搜索
✍️ 动手实践：遗传算法
在下面的笔记本里继续学习：
打开这个笔记本，看遗传算法的两个应用例子：
- 公平分赃（宝物如何均分）
- 八皇后问题
小结
遗传算法被用来解决很多问题，包括物流和搜索类问题。这个领域的兴起，源于把心理学和计算机科学合并起来的研究。
🚀 挑战
"遗传算法实现起来简单，但它的行为很难理解。"（来源）请做一些调研，找到一个遗传算法的实现例子，比如用遗传算法解数独，再用草图或流程图讲清楚它是怎么工作的。
课后小测
复习与自学
看这个很棒的视频，讲的是如何用遗传算法训练神经网络，让电脑学会玩超级马里奥。关于电脑如何学习玩这类游戏，我们会在下一节继续展开。
作业：丢番图方程
你的目标是求解所谓的丢番图方程（Diophantine equation），也就是根为整数的方程。举个例子，看方程 a + 2b + 3c + 4d = 30，你需要找出满足它的整数根。
这份作业的灵感来自这篇帖子。
提示：
- 可以把根的取值范围限定在 [0, 30] 区间内
- 基因可以考虑编码成一组根值的列表
从 Diophantine.ipynb 开始动手。