遗传算法详解

进化在没有设计者的情况下造就了眼睛、翅膀和大脑,靠的只是保留有效的东西并加以变化。遗传算法借用这一思想,在计算机上解决问题。它不需要理解问题本身,只需要能分辨答案的好坏,因此当可能答案的空间太大、太古怪,无法用其他方法搜索时,它就成了一个强大的工具。

火箭从场地底部出发,绕过一堵墙飞向绿色目标,最佳飞行路线以虚线绘出
火箭从场地底部出发,绕过一堵墙飞向绿色目标,最佳飞行路线以虚线绘出

基本思想

20 世纪 60 年代和 70 年代,密歇根大学的约翰·霍兰德(John Holland)把达尔文的理论变成了一种算法,并在他 1975 年出版的《自然与人工系统中的适应》(Adaptation in Natural and Artificial Systems)一书中作了阐述。大约同一时期,德国的英戈·雷兴贝格(Ingo Rechenberg)和汉斯-保罗·施韦费尔(Hans-Paul Schwefel)为工程设计发展出了进化策略。它们的共同方法是:维持一个由候选解组成的种群,给它们打分,让较好的候选解带着变化繁殖,并重复许多代。

约翰·霍兰德,他在1975年的著作《自然与人工系统中的适应》中描述了遗传算法。
约翰·霍兰德,他在1975年的著作《自然与人工系统中的适应》中描述了遗传算法。

基因与种群

每个候选解都由一条染色体来描述,也就是一串基因。在演练场中,火箭的基因就是它的推力,飞行中的每个时刻对应一个;在其他问题中,基因可能是一个数的各个二进制位、一条路线上城市的顺序,或者一个设计中各部件的尺寸。第一代是随机的,这意味着它对答案空间的探索很广,却几乎没有好答案。

适应度函数

适应度是表示一个候选解有多好的单个数字,也是算法对问题所知的唯一信息。对火箭来说,它最奖励早到达,其次奖励最终离目标近,并惩罚坠毁。精心选择的适应度函数能顺畅地把搜索引向好答案;草率的适应度函数则会奖励错误的东西,而算法会利用它留下的任何漏洞。

选择

挑选父母时,要让适应度更高的候选解有更多后代,但较弱的候选解仍有机会,因为它们的基因中可能含有有用的片段。轮盘赌选择按适应度的比例给每个候选解分配轮盘上的一块扇区;锦标赛选择则随机挑出几个,再从中取最好的。更强的选择能加快进展,但也会让种群变得更相似,可能导致搜索过早结束。

交叉与变异

交叉把两个亲本组合起来:在这里,子代的前一部分基因来自一个亲本,其余部分来自另一个亲本,于是一枚火箭早期的机动可以与另一枚火箭后期的机动相结合。变异则随机替换少数基因。交叉重新组合种群已有的东西;变异带来种群从未有过的东西。霍兰德的模式定理描述了在选择与重组的这种组合作用下,由优良基因构成的短小积木块如何在种群中传播。

精英保留、探索与利用

把最好的几个候选解原封不动地复制到下一代,即精英保留,可以保证最佳答案永远不会丢失。每个遗传算法都必须在探索(尝试搜索空间中的新区域)与利用(改进已经不错的东西)之间取得平衡。变化太少,种群会收敛到一个平庸的答案上;变化太多,它就永远安定不下来。种群规模、变异率和选择压力就是调节这种平衡的旋钮。

局部最优

遗传算法只追随适应度,所以它可能被愚弄。当通往最佳答案的路径必须先经过较差的答案时,种群会爬上最近的山丘并停留在那里:这就是局部最优。在演练场的交错墙壁后面,撞在目标下方的火箭得分比转身离开去寻找缺口的火箭更高,于是种群堆积在墙前。补救办法包括更大的种群、更高的变异率、保持种群的多样性,而最重要的是更好的适应度函数。

动手探索

打开遗传算法演练场,让火箭进化着绕过一堵墙、穿过缺口、避开柱子、越过交错的墙壁,或绕过你自己画的墙。改变种群规模、变异率、寿命和选择方式,打开或关闭精英保留,并在图表中观察到达目标的火箭比例增长得有多快,或者为什么没有增长。

常见问题

遗传算法算是一种人工智能吗?

作为一种搜索和优化方法,它属于更广泛的人工智能和机器学习领域。它不像神经网络那样从样本中学习,而是通过尝试和选择来改进候选解。两者经常结合使用,例如用进化的方法生成神经网络的结构或权重,这种方法称为神经进化。

遗传算法总能找到最佳答案吗?

不能。它是一种启发式方法:对于困难的问题,它通常能找到好答案,但不能保证找到最佳答案,也无法证明结果离最佳答案有多近。对于精确方法足够快的问题,精确方法更好。

遗传算法和进化策略有什么区别?

两者都是进化算法。经典的遗传算法强调在类似字符串的染色体上进行交叉;进化策略则主要对实数进行变异,并且常常在运行过程中自行调整变异的幅度。现代方法融合了两者的思想。

为什么火箭一开始那么笨拙?

它们最初的基因是完全随机的推力,平均来说会相互抵消,所以火箭只是随意漂移。只有在选择保留了那些碰巧大致朝正确方向推进的少数火箭、交叉又把它们好的片段组合起来之后,协调的飞行才会出现。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开遗传算法演练场