遗传算法 - 简介
遗传算法(GA)是一种基于遗传学和自然选择原理的基于搜索的优化技术。它经常被用来寻找解决难题的最佳或接近最佳的解决方案,否则这些问题将需要一生的时间才能解决。它经常用于解决研究和机器学习中的优化问题。
优化简介
优化是使事物变得更好的过程。在任何流程中,我们都有一组输入和一组输出,如下图所示。
优化是指以某种方式找到输入值,从而获得“最佳”输出值。“最佳”的定义因问题而异,但用数学术语来说,它是指通过改变输入参数来最大化或最小化一个或多个目标函数。
输入可以采用的所有可能的解决方案或值的集合构成了搜索空间。在这个搜索空间中,有一个点或一组点可以给出最优解。优化的目的是在搜索空间中找到该点或点集。
什么是遗传算法?
大自然一直是全人类灵感的重要源泉。遗传算法 (GA) 是基于自然选择和遗传学概念的基于搜索的算法。遗传算法是一个更大的计算分支(称为进化计算)的子集。
遗传算法由密歇根大学的约翰·霍兰德 (John Holland) 及其学生和同事(其中最著名的是大卫·E·戈德堡 (David E. Goldberg))开发,此后在各种优化问题上进行了尝试,并取得了高度成功。
在 GA 中,我们有一个针对给定问题的可能解决方案池或群体。然后这些解决方案经历重组和突变(就像自然遗传学一样),产生新的孩子,并且这个过程在不同的世代中重复。每个个体(或候选解决方案)都被分配一个适合度值(基于其目标函数值),并且更适合的个体有更高的机会交配并产生更多“更适合”的个体。这符合达尔文“适者生存”的理论。
通过这种方式,我们一代又一代地不断“进化”出更好的个体或解决方案,直到达到停止标准。
遗传算法本质上是足够随机的,但它们的性能比随机局部搜索(我们只是尝试各种随机解决方案,跟踪迄今为止最好的解决方案)要好得多,因为它们也利用了历史信息。
GA 的优点
GA 具有多种优点,使其非常受欢迎。这些包括 -
不需要任何衍生信息(这可能不适用于许多现实世界的问题)。
与传统方法相比,速度更快、效率更高。
具有非常好的并行能力。
优化连续和离散函数以及多目标问题。
提供一系列“好的”解决方案,而不仅仅是一个解决方案。
问题总能得到答案,并且随着时间的推移会变得更好。
当搜索空间非常大并且涉及大量参数时很有用。
GA 的局限性
与任何技术一样,遗传算法也有一些限制。这些包括 -
遗传算法并不适合所有问题,尤其是简单且可以获得衍生信息的问题。
适应度值是重复计算的,这对于某些问题来说可能是计算昂贵的。
由于是随机的,无法保证解决方案的最优性或质量。
如果实施不当,遗传算法可能无法收敛到最优解。
GA——动机
遗传算法有能力“足够快”地提供“足够好”的解决方案。这使得遗传算法在解决优化问题中具有吸引力。需要 GA 的原因如下:
解决难题
在计算机科学中,存在大量的问题,这些问题都是NP-Hard的。这本质上意味着,即使是最强大的计算系统也需要很长时间(甚至几年!)来解决这个问题。在这种情况下,遗传算法被证明是一种有效的工具,可以在短时间内提供可用的近乎最优的解决方案。
基于梯度的方法的失败
传统的基于微积分的方法的工作原理是从随机点开始,沿着梯度方向移动,直到到达山顶。该技术非常高效,并且对于单峰目标函数(例如线性回归中的成本函数)非常有效。但是,在大多数现实世界的情况下,我们有一个非常复杂的问题,称为景观,它由许多山峰和许多山谷组成,这导致这些方法失败,因为它们具有陷入局部最优的固有倾向。如下图所示。
快速获得良好的解决方案
一些难题,如旅行推销员问题 (TSP),在现实世界中有应用,如路径查找和 VLSI 设计。现在想象一下,您正在使用 GPS 导航系统,需要几分钟(甚至几个小时)来计算从源点到目的地的“最佳”路径。这种现实世界应用程序中的延迟是不可接受的,因此需要“快速”交付的“足够好”的解决方案。