人工神经网络 - 遗传算法

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

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

在 GA 中，我们有一个针对给定问题的可能解决方案池或群体。然后，这些解决方案会进行重组和突变（就像在自然遗传学中一样），产生新的子代，并且该过程会在各个世代中重复。每个个体（或候选解决方案）都被分配一个适应度值（基于其目标函数值），适应度更高的个体有更高的机会交配并产生更多"适应度"的个体。这符合达尔文的"适者生存"理论。

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

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

GA 的优势

GA 具有多种优势，这些优势使它们非常受欢迎。这些包括 −

• 不需要任何衍生信息（对于许多实际问题来说，这些信息可能不可用）。

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

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

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

• 提供"良好"解决方案列表，而不仅仅是单一解决方案。

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

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

GA 的局限性

与任何技术一样，GA 也存在一些局限性。这些包括 −

• GA 并不适合所有问题，尤其是那些简单且有衍生信息的问题。

• 适应度值被重复计算，对于某些问题来说，这可能在计算上很昂贵。

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

• 如果实施不当，GA 可能无法收敛到最优解。

GA – 动机

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

解决难题

在计算机科学中，存在大量NP-Hard问题。这本质上意味着，即使是最强大的计算系统也需要很长时间（甚至数年！）才能解决该问题。在这种情况下，GA 被证明是一种有效的工具，可以在短时间内提供可用的近乎最优的解决方案。

基于梯度的方法失败

传统的基于微积分的方法从随机点开始，沿着梯度方向移动，直到到达山顶。这种技术非常有效，并且对于单峰目标函数（如线性回归中的成本函数）非常有效。然而，在大多数现实世界中，我们有一个非常复杂的问题，称为地形，由许多山峰和山谷组成，这导致此类方法失败，因为它们存在陷入局部最优的固有倾向，如下图所示。

快速获得良好的解决方案

一些困难的问题，如旅行商问题 (TSP)，有现实世界的应用，如路径查找和 VLSI 设计。现在想象一下，您正在使用 GPS 导航系统，需要几分钟（甚至几个小时）来计算从源到目的地的"最佳"路径。在这种实际应用中，延迟是不可接受的，因此需要"快速"交付的"足够好"的解决方案。

如何使用 GA 解决优化问题？

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

GA 机制用于优化过程的阶段

以下是 GA 机制用于优化问题的阶段。

• 随机生成初始种群。

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

• 使用突变和交叉运算符重新组合选定的解决方案。

• 将后代插入种群。

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