遗传算法 - 简介

遗传算法 (GA) 是一种基于遗传学和自然选择原理的搜索优化技术。它经常用于寻找解决难题的最佳或接近最佳的解决方案,否则这些问题将需要一生的时间才能解决。它经常用于解决优化问题、研究和机器学习。

优化简介

优化是使某事变得更好的过程。在任何过程中,我们都有一组输入和一组输出,如下图所示。

优化

优化是指以某种方式找到输入值,以便我们获得"最佳"输出值。 "最佳"的定义因问题而异,但在数学术语中,它是指通过改变输入参数来最大化或最小化一个或多个目标函数。

输入可以采用的所有可能解决方案或值的集合构成了搜索空间。在这个搜索空间中,有一个点或一组点可以给出最佳解决方案。优化的目的是在搜索空间中找到该点或点集。

什么是遗传算法?

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

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

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

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

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

GA 的优势

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

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

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

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

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

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

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

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

GA 的局限性

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

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

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

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

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

GA – 动机

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

解决难题

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

基于梯度的方法的失败

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

GA Motivation

快速获得良好的解决方案

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