由 chrisname 发布

2013年6月21日 (最后更新: 2013年6月23日)

评分: 3.6/5 (210票)

什么是遗传算法？

遗传算法是进化算法的一个子集；它们是受生物学启发的搜索启发式算法，用于寻找已知预期结果的问题的解决方案。遗传算法试图为问题找到最佳的候选解决方案。该解决方案通常是正确解决方案的近似值，尤其是在无法获得精确解、难以处理（需要无限时间或资源）或根本不需要精确解的问题中。这些算法通过“进化”解决方案来工作。

遗传算法如何工作？

遗传算法通过构建一组初始的随机潜在解决方案来工作。从中选择一部分用于“繁殖”，以产生新的潜在解决方案，这些新解决方案随后成为新种群。此过程一直持续，直到满足某些终止条件。这些条件可能包括找到一个“足够好”（即使不是精确）的解决方案、种群没有改进（收敛）、达到设定的最大代数（即新种群）或达到设定的计算时间和资源限制。

由此，我们可以提取三个步骤

1. 初始化 - 创建 N 个随机候选解决方案的初始种群（其他更生物学的术语是“个体”、“生物体”或“染色体”）
2. 再生 - 从上一个种群中创建一个新种群
3. 退出（满足终止条件后）- 返回迄今为止找到的最佳解决方案，算法停止运行

再生有三个子步骤

1. 选择 - 从种群中通过算法选择一部分种群
2. 重组（也称为“交叉”）- 将选定的个体组合起来以产生新的个体
3. 变异 - 对新的个体（“后代”）进行变异以增加遗传多样性

初始化

随机创建 N 个解决方案的初始种群。通常，解决方案被编码为一系列比特（二进制数字）。这些可以被认为是类似于构成真实 DNA 基因的基本配对，尽管真实基因由基本配对的三联体组成，每个三联体有四种可能的“值”（核苷酸 - 腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶（在 RNA 中，胸腺嘧啶被尿嘧啶取代））而我们的比特只有两种——0 或 1。此外，在生物学中，染色体是 DNA 的缠绕链，包含许多基因；然而，在我们的术语中，染色体将仅指一系列比特。解决方案的“DNA”稍后可以解码。通常 N 的值在几百到几千之间。初始值 1,000 是可以接受的，之后可以进行调整。

再生

选择

在选择过程中，使用选择算法从种群中选择一部分种群——通常是两个解决方案，当然也可以使用更多（一些研究表明使用两个以上的父代可以产生更高质量的后代）。一个例子称为适应度比例选择，或轮盘赌选择。在此算法中，个体以基于其适应度的概率随机选择，适应度是一个值，表示该个体距离成为有效解决方案有多近（通常，该值介于 0 和 1 之间）。适应度函数将在稍后详细讨论。每次 FPS 迭代返回一个单独的个体，因此该算法可以应用多次以获得所需的父代数量。更简单的选择算法包括截断选择，即选择种群的最佳一半、三分之一或其他分数，以及锦标赛选择，即从种群的随机子集中选择最佳个体。另一种更复杂但更公平的算法称为随机通用采样，它是 RWS 的修改版本，其中解决方案均匀分布，因此较弱的解决方案（即适应度函数值较低的解决方案）有公平的机会被选中（尽管算法仍然普遍选择更高的适应度）。允许选择较弱解决方案的好处是，较弱的解决方案可能只是对更强的解决方案进行微小修改，而只允许选择最适合的解决方案可能会导致解决方案遗传多样性不足。

重组

在重组中，选择的解决方案进行交叉以创建新的解决方案，尽管通常存在发生的概率；例如，70%。这种交叉的概念也取自生物学：在减数分裂（导致四个基因不同的细胞的细胞分裂）过程中，相应的父（来自父亲）和母（来自母亲）染色体会聚集在一起，并可能交换基因（交叉）。在遗传算法中，这个过程通过多种方式进行模拟。最简单的方法是单点交叉，即选择染色体中的一个随机位置，然后将该点之后的所有内容与另一条染色体交换。其他方法更复杂，但可能产生更高质量的后代和更多的遗传多样性。

变异

交叉发生后，变异可能以非常小的概率（每个比特约 0.1%）发生。在变异中，遍历染色体，每个比特都可能根据小概率被翻转。这类似于细胞分裂过程中偶尔发生的替换突变。除了简单地翻转比特，还可以前置、插入、追加和/或删除它们，这相当于生物学中的插入和删除突变。通过这种方式，进一步增加了遗传多样性。

关于编码和解码

如前所述，遗传算法中的染色体通常被编码为一系列比特。一组比特——一个基因——可以代表字符串中的一个字符，例如，如果要生成字符串“hello world”，字母 h 可能由二进制数 000 表示，e 由 001 表示，l 由 010 表示，o 由 011 表示，空格由 100 表示，w 由 101 表示，r 由 110 表示，d 由 111 表示。最终，人们会希望偶然发现序列 000,001,010,010,011,100,101,011,110,010,111，这对应于字符串“hello world”。像这样编码数据的绝妙之处在于，遗传算法可以非常通用地编写——任何具有适应度函数、交叉函数和变异函数的对象都可以使用，并且算法永远不需要知道实现细节。通常解码会在两个阶段进行：一次在需要计算适应度函数时，一次在想要显示遗传算法输出时。

到底什么是适应度函数？

我多次提到了适应度函数，但没有真正解释它们是什么。简单来说，它们衡量个体的适应度，即它接近解决所需问题的程度。产生此结果的计算是高度领域特定的，尽管通常需要一个介于 0 和 1 之间的值。在我们“hello world”的例子中，适应度函数可能会将二进制序列解码为 ASCII 字符串，然后将其与作为所需输出提供的 ASCII 字符串进行比较。两者之间的差异然后转换为 0 到 1 之间的数字，如下所示：1/(y - x) – 其中 y 是期望的解决方案，x 是解码结果。

待办事项

• 选择算法的伪代码实现
• 交叉算法的伪代码实现
• 变异算法的伪代码实现
• 通用遗传算法类的骨架结构