REF · 经典模型

遗传算法GENETIC ALGORITHMS

John Holland,1975 — 把"变异 + 选择 + 重组"从生物学里拆出来,当成一台通用的搜索机器(genetic algorithm,学界常缩写成 GA,下文也这么用)

被引用于:Topic 26 复杂适应系统

01它问的是什么问题(The Question It Poses)

有一类问题,你说得出什么叫"好",却写不出通往好的路。天线该弯成什么形状才能在指定频段收得最好?三百个班次怎么排,才能既满足所有约束又少用两架飞机?这类问题没有公式可解,也没有可以顺着往下走的坡度——你只能一个个试,而可试的组合多到宇宙年龄都试不完。

自然界解决过同类问题,而且用的办法笨得出奇:生一堆略有不同的后代,让环境筛掉大部分,把活下来的重新组合,再来一轮。Holland 要问的是:这套办法离开生物学还成不成立?把它写成几十行代码,它还能不能在一个从没被人理解过的问题上找出好解?

02规则本身(The Rules)

  1. 把一个候选答案编码成一串符号(最经典的是一串 0 和 1),这一串叫一个个体
  2. 随机生成一群个体,比如 100 个,这群叫一个种群(population)。
  3. 给每个个体打一个分。打分的那个函数叫适应度函数(fitness function)——它是你唯一必须提供的东西,也是你把"什么叫好"告诉算法的唯一渠道。
  4. 选择:分高的个体更可能被挑中当父代。注意不是只留最高的那个,中等的也要留一些,否则多样性一轮就没了。
  5. 交叉(crossover):取两个父代,在随机位置剪开,互换后半段,得到两个子代。
  6. 变异(mutation):以很小的概率(常见是千分之几)翻转某些位。
  7. 用子代换掉旧种群,回到第 3 步。重复几百到几万代。

值得停一下的是第 3 步和第 5 步。适应度函数只说"多好",从不说"为什么好"——算法对问题的结构一无所知,这正是它能用在你看不懂的问题上的原因。而交叉是这套方法区别于"随机乱试"的地方:它假设好解的一些片段可以被分别找到、再拼起来。这个假设成立与否,决定了它在你的问题上是快得惊人还是慢得可笑。

一次交叉 + 一次变异 父代 A 1 0 1 1 0 0 1 父代 B 0 1 0 0 1 1 0 随机切点 子代 1 1 0 1 1 1 1 0 子代 2 0 1 0 0 0 1 1 变异翻了这一位 交叉负责"把已经找到的好片段拼起来",变异负责"别让某个位置全场都一样" 两者缺一:只有变异 = 慢得像纯随机搜索;只有交叉 = 种群很快同质化,此后再拼也拼不出新东西 算法自始至终不知道这些位代表什么 — 它只见过分数
一次交叉产生两个子代,随后小概率的变异翻掉某一位。这两步就是全部的"创新"来源。

03跑起来会看到什么(What You See When It Runs)

最典型的曲线是一条先陡后平的上升线:前几十代分数猛涨(随便捡捡就有的改进),然后越来越慢。这条曲线的形状本身是有信息的——它告诉你剩下的改进空间大致还有多少。

第二件常见的事叫早熟收敛(premature convergence):种群里所有个体变得几乎一模一样,卡在一个不算好的解上。此后交叉不再产生任何新东西(两串一样的东西怎么剪都还是它自己),只剩变异在做微小的随机扰动,曲线彻底走平。多样性一旦耗尽就很难恢复,这是这类算法最常见的失败方式。

同一个问题,两次运行 代数 → 最好个体的分数 保住了多样性 早熟收敛 此后全场基因几乎一样 曲线走平不一定说明"已经最优",也可能说明"没得可试了" — 这两件事必须分开诊断
走平的曲线有两种完全不同的病因。分辨方法很土:直接测种群里个体之间的差异度,看它是不是也塌了。

第三件事最有意思:跑出来的解常常很怪。2006 年 NASA 的 ST5 卫星上飞过一副由演化算法设计的天线,形状像一段被随手掰弯的回形针,没有任何人类天线工程师会画成那样,但它满足了那组指标。这是这类方法最诚实的广告——它不理解问题,所以也不受"看起来该是什么样"的约束。

04它解释了现实中的什么(What It Explains)

严格说,遗传算法首先是个工具,不是个解释。但它顺带证明了一件在别处很难演示的事:"没有设计者的设计"是可行的,而且需要的零件极少。一堆候选、一个只说好坏的分数、一套复制与重组的手续——三样凑齐,复杂而有效的结构就会出现,不需要任何人理解它为什么有效。

这也正是它在本站的位置:它是"适应"这件事的最小可运行版本。当你怀疑某个组织、市场、生态是不是在适应,把这三样零件对着找一遍,比任何比喻都管用。

它不能解释什么(What It Cannot Explain)

延伸阅读(Further Reading)