Artificial Neural Network 简明教程

Artificial Neural Network - Genetic Algorithm

自然一直都是全人类的伟大灵感来源。遗传算法（GA）是基于自然选择和遗传学概念的搜索算法。GA 是一个更大计算分支的子集，该分支称为 Evolutionary Computation 。

GA 是约翰·霍兰及其学生和密歇根大学的同事们（最著名的是戴维·E·戈德堡）开发的，并且此后已经在各种优化问题上取得了高度成功。

在 GA 中，我们有一个给定问题的候选解池或人群。这些解然后经过重组和变异（如同自然遗传学），生成新的孩子，并在这个过程中重复各种世代。每个个体（或候选解）都分配一个适应值（基于其目标函数值），并且适应性强的个体有较高的交配机会，并产生更多“适应性更强”的个体。这与达尔文的“适者生存”理论是一致的。

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

遗传算法在本质上是充分随机化的，但它们比随机局部搜索（我们仅尝试各种随机解决方案，同时跟踪迄今为止最好的解决方案）表现得更好，因为它们也利用历史信息。

Advantages of GAs

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

  1. 不需要任何导数信息（这在许多现实问题上可能不可用）。

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

  3. 具有极强的并行能力。

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

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

  6. 总能为问题找到答案，并且答案会随着时间而变得更好。

  7. 在搜索空间非常大且涉及大量参数时很有用。

Limitations of GAs

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

  1. 遗传算法并不适用于所有问题，尤其是简单问题和可获得导数信息的问题。

  2. 适应值被重复计算，对于某些问题而言这可能在计算上很昂贵。

  3. 由于是随机的，所以不能保证解决方案的最佳性或质量。

  4. 如果没有正确实施，遗传算法可能无法收敛到最佳解决方案。

GA – Motivation

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

Solving Difficult Problems

在计算机科学中，有很多问题是 NP-Hard 。这基本上意味着，即使是最强大的计算系统也要花很长时间（甚至数年！）才能解决该问题。在这种情况下，遗传算法被证明是一种有效工具，可以在短时间内提供 usable near-optimal solutions 。

Failure of Gradient Based Methods

基于传统微积分的方法通过从一个随机点开始并朝梯度方向移动来工作，直到我们到达山顶。这种技术有效，并且非常适合单峰目标函数，例如线性回归中的成本函数。然而，在大多数实际情况下，我们有一个非常复杂的问题，称为景观，由许多山峰和许多山谷组成，这导致此类方法失败，因为它们倾向于停滞在局部最优值，如下图所示。

failure ga

Getting a Good Solution Fast

旅行商问题 (TSP) 等一些困难问题具有实际应用，例如寻路和超大规模集成 (VLSI) 设计。现在想象一下您正在使用 GPS 导航系统，它需要几分钟（甚至几小时）来计算从源到目的地的“最佳”路径。在这样的实际应用中，延迟是不可接受的，因此需要一个“足够好”的解决方案，即“快速”交付的解决方案。

How to Use GA for Optimization Problems?

我们已经知道，优化是为了使设计、情况、资源和系统等尽可能有效。优化过程在以下图表中显示。

how to use

Stages of GA Mechanism for Optimization Process

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

  1. 随机生成初始种群。

  2. 选择具有最佳适应值的最优解。

  3. 使用变异和交叉算子重新组合选定的解决方案。

  4. 将后代插入种群中。

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