人工神经网络 - 遗传算法

自然一直是全人类极大的灵感来源。遗传算法 (GA) 是基于自然选择和遗传学概念的基于搜索的算法。遗传算法是更大计算分支（称为进化计算）的一个子集。

遗传算法由John Holland及其在密歇根大学的学生和同事（最著名的是David E. Goldberg）开发，此后已在各种优化问题上进行了尝试，并取得了高度成功。

在遗传算法中，我们有一组或一个给定问题的可能解决方案池。然后，这些解决方案会进行重组和变异（就像自然遗传一样），产生新的后代，并且该过程会重复几代。每个个体（或候选解决方案）都会被赋予一个适应度值（基于其目标函数值），并且适应性更强的个体具有更高的交配机会，并产生更多“适应性更强”的个体。这符合达尔文的“适者生存”理论。

通过这种方式，我们不断“进化”出更好一代的个体或解决方案，直到达到停止标准。

遗传算法本质上是随机的，但它们比随机局部搜索（我们只是尝试各种随机解决方案，并跟踪迄今为止最好的解决方案）要好得多，因为它们也利用历史信息。

遗传算法的优点

遗传算法具有多种优势，使其广受欢迎。这些包括：

• 不需要任何导数信息（许多现实世界的问题可能无法提供）。

• 与传统方法相比，速度更快，效率更高。

• 具有非常好的并行能力。

• 优化连续和离散函数以及多目标问题。

• 提供一系列“良好”的解决方案，而不仅仅是一个解决方案。

• 始终获得问题的答案，并且随着时间的推移会变得更好。

• 当搜索空间非常大并且涉及大量参数时非常有用。

遗传算法的局限性

与任何技术一样，遗传算法也有一些局限性。这些包括：

• 遗传算法不适用于所有问题，特别是那些简单且可以获得导数信息的问题。

• 适应度值被重复计算，这对于某些问题来说可能计算成本很高。

• 由于具有随机性，因此无法保证解决方案的最优性或质量。

• 如果实现不当，遗传算法可能无法收敛到最优解。

遗传算法——动机

遗传算法能够“足够快”地提供“足够好”的解决方案。这使得遗传算法在解决优化问题方面具有吸引力。需要遗传算法的原因如下：

解决难题

在计算机科学中，有一大类问题是NP难的。这实际上意味着，即使是最强大的计算系统也需要很长时间（甚至数年！）才能解决该问题。在这种情况下，遗传算法被证明是提供可用的近似最优解的有效工具，并且所需时间很短。

基于梯度的方法的失败

传统的基于微积分的方法的工作原理是从一个随机点开始，沿着梯度的方向移动，直到到达山顶。对于单峰目标函数（例如线性回归中的成本函数），这种技术是有效的并且运行良好。但是，在大多数现实世界的情况中，我们有一个非常复杂的问题，称为景观，由许多峰和许多谷组成，这会导致此类方法失败，因为它们具有固有的倾向停留在局部最优解，如下图所示。

快速获得良好的解决方案

旅行商问题 (TSP) 等一些难题具有路径查找和 VLSI 设计等现实世界的应用。现在假设您正在使用 GPS 导航系统，并且计算从起点到目的地的“最佳”路径需要几分钟（甚至几小时）。在这些现实世界的应用中，延迟是不可接受的，因此需要“足够好”的解决方案，并且交付“快速”。

如何将遗传算法用于优化问题？

我们已经知道，优化是使设计、情况、资源和系统尽可能有效的一种行为。优化过程如下图所示。

用于优化过程的遗传算法机制阶段

以下是将遗传算法用于问题优化时的阶段。

• 随机生成初始种群。

• 选择具有最佳适应度值的初始解。

• 使用突变和交叉算子重组选定的解。

• 将后代插入种群。

• 现在，如果满足停止条件，则返回具有最佳适应度值的解。否则，转到步骤 2。