01它问的是什么问题(The Question It Poses)
有一类问题,你说得出什么叫"好",却写不出通往好的路。天线该弯成什么形状才能在指定频段收得最好?三百个班次怎么排,才能既满足所有约束又少用两架飞机?这类问题没有公式可解,也没有可以顺着往下走的坡度——你只能一个个试,而可试的组合多到宇宙年龄都试不完。
自然界解决过同类问题,而且用的办法笨得出奇:生一堆略有不同的后代,让环境筛掉大部分,把活下来的重新组合,再来一轮。Holland 要问的是:这套办法离开生物学还成不成立?把它写成几十行代码,它还能不能在一个从没被人理解过的问题上找出好解?
02规则本身(The Rules)
- 把一个候选答案编码成一串符号(最经典的是一串 0 和 1),这一串叫一个个体。
- 随机生成一群个体,比如 100 个,这群叫一个种群(population)。
- 给每个个体打一个分。打分的那个函数叫适应度函数(fitness function)——它是你唯一必须提供的东西,也是你把"什么叫好"告诉算法的唯一渠道。
- 选择:分高的个体更可能被挑中当父代。注意不是只留最高的那个,中等的也要留一些,否则多样性一轮就没了。
- 交叉(crossover):取两个父代,在随机位置剪开,互换后半段,得到两个子代。
- 变异(mutation):以很小的概率(常见是千分之几)翻转某些位。
- 用子代换掉旧种群,回到第 3 步。重复几百到几万代。
值得停一下的是第 3 步和第 5 步。适应度函数只说"多好",从不说"为什么好"——算法对问题的结构一无所知,这正是它能用在你看不懂的问题上的原因。而交叉是这套方法区别于"随机乱试"的地方:它假设好解的一些片段可以被分别找到、再拼起来。这个假设成立与否,决定了它在你的问题上是快得惊人还是慢得可笑。
一次交叉产生两个子代,随后小概率的变异翻掉某一位。这两步就是全部的"创新"来源。
03跑起来会看到什么(What You See When It Runs)
最典型的曲线是一条先陡后平的上升线:前几十代分数猛涨(随便捡捡就有的改进),然后越来越慢。这条曲线的形状本身是有信息的——它告诉你剩下的改进空间大致还有多少。
第二件常见的事叫早熟收敛(premature convergence):种群里所有个体变得几乎一模一样,卡在一个不算好的解上。此后交叉不再产生任何新东西(两串一样的东西怎么剪都还是它自己),只剩变异在做微小的随机扰动,曲线彻底走平。多样性一旦耗尽就很难恢复,这是这类算法最常见的失败方式。
走平的曲线有两种完全不同的病因。分辨方法很土:直接测种群里个体之间的差异度,看它是不是也塌了。
第三件事最有意思:跑出来的解常常很怪。2006 年 NASA 的 ST5 卫星上飞过一副由演化算法设计的天线,形状像一段被随手掰弯的回形针,没有任何人类天线工程师会画成那样,但它满足了那组指标。这是这类方法最诚实的广告——它不理解问题,所以也不受"看起来该是什么样"的约束。
04它解释了现实中的什么(What It Explains)
严格说,遗传算法首先是个工具,不是个解释。但它顺带证明了一件在别处很难演示的事:"没有设计者的设计"是可行的,而且需要的零件极少。一堆候选、一个只说好坏的分数、一套复制与重组的手续——三样凑齐,复杂而有效的结构就会出现,不需要任何人理解它为什么有效。
这也正是它在本站的位置:它是"适应"这件事的最小可运行版本。当你怀疑某个组织、市场、生态是不是在适应,把这三样零件对着找一遍,比任何比喻都管用。
它不能解释什么(What It Cannot Explain)
- 它不是自然选择的模型。这里的适应度函数是人给的、固定的、算得出来的;真实演化里"什么算好"由环境和其他所有生物共同决定,而且随时在变(第 31 期的红皇后讲的就是这件事)。拿 GA 的行为去论证生物学结论,要非常小心。
- 没有免费午餐。Wolpert 与 Macready 1997 年证明:在所有可能的问题上平均,任何一个优化算法都不比别的更好,包括纯随机搜索。所以 GA 的优势从来不是"它更聪明",而是它的假设(好片段可以分别找到再拼起来)恰好匹配了某一类问题的结构。问题不匹配时,它就是个很贵的随机搜索。
- 它不保证最优,也不告诉你离最优多远。跑完之后你手上有一个解和一条曲线,没有任何关于"还差多少"的界。需要这种保证的场合(有严格最优性要求的调度、有可证明界的组合优化),该用别的方法。
- 评估太贵就用不起。它动辄需要几万到几百万次打分。如果一次打分意味着跑一次流体仿真、做一次真实实验、等一个季度的业绩,这个方法在预算上直接出局。
- 编码决定成败,而编码没有理论。同一个问题,换一种编码方式,结果可以天差地别;哪种编码让"好片段"真的成片,目前只能靠试和手艺。这一条是使用者最容易低估的成本。
- 别把图式定理当成"它为什么有效"的完整解释。Holland 的图式定理(schema theorem)与建筑块假说(building block hypothesis)给了一个直觉框架,但学界几十年来对它能否解释 GA 的实际表现一直有争议。用它讲故事可以,当证明不行。