遗传算法是非常健壮的进化算法。而如果我们将操作对象由 bits 改变为程序的解析树的话， 那么就能通过遗传编程生成程序了。

程序的树状描述

我们用程序的解析树来表示我们的程序。 假设我们要表示 $xy + x^2y$：

$$ \newcommand{\node}[1]{ \enclose{circle}[mathcolor="black", padding="7px", thickness="1px"]{\color{black}{#1}} } \newcommand{\boldnode}[1]{ \enclose{circle}[mathcolor="black", padding="7px", thickness="2px"]{\color{black}{#1}} } $$
$$ \begin{xy} \xymatrix { &&&& \node{+} \ar[lld] \ar[rrd]\\ && \node{*} \ar[ld] \ar[rd] &&&& \node{*} \ar[ld] \ar[rd] \\ & \node{x} && \node{y} && \node{pow} \ar[rd] \ar[ld] && \node{y} \\ &&&& \node{x} && \node{2} } \end{xy} $$

选择树是因为树可以表示绝大多数语言的语法。而且有了树之后我们可以非常低成本地通过节点为单位实现交叉互换与突变。

变异：程序的交叉互换与突变

假设现在我们的种群中有两个函数，一个是 $xy + x^2y$ 另一个是 $x + \sqrt{x + y}$ 我们对他们进行交叉互换。 当然除了上述个体间的互换，还可以做个体内的互换，这里我就不赘述了。 高亮的节点是我们随机选中要进行交换的节点。我们将节点及其子节点交换，如下图所示。

Before Crossover

$$ \begin{xy} \xymatrix { &&&& \node{+} \ar[lld] \ar[rrd]\\ && \node{*} \ar[ld] \ar[rd] &&&& \node{*} \ar[ld] \ar[rd] \\ & \node{x} && \node{y} && \node{pow} \ar[rd] \ar[ld] && \boldnode{y} \\ &&&& \node{x} && \node{2} } \end{xy} $$
$$xy + x^2y$$
$$ \begin{xy} \xymatrix { & \node{+} \ar[ld] \ar[rd] \\ \node{x} && \boldnode{sqrt} \ar[d] \\ && \node{+} \ar[ld] \ar[rd] \\ & \node{x} && \node{y} } \end{xy} $$
$$x + \sqrt{x + y}$$

After Crossover

$$ \begin{xy} \xymatrix { &&&& \node{+} \ar[lld] \ar[rrd]\\ && \node{*} \ar[ld] \ar[rd] &&&& \node{*} \ar[ld] \ar[rd] \\ & \node{x} && \node{y} && \node{pow} \ar[rd] \ar[ld] && \boldnode{sqrt} \ar[d] \\ &&&& \node{x} && \node{2} & \node{+} \ar[ld] \ar[rd] \\ &&&&&& \node{x} && \node{y} } \end{xy} $$
$$ xy + x^2\sqrt{x+y} $$
$$ \begin{xy} \xymatrix { & \node{+} \ar[ld] \ar[rd] \\ \node{x} && \boldnode{y} } \end{xy} $$
$$ x + y $$

突变

突变的话就非常简单了，我们把所有可用的符号丢到一个数组里， 每一个节点使其能够有一定概率随机突变为该数组内任意一个符号，其子树不变。 不过这样的话会产生非法运算符的情况，我们就将其作为致命突变直接 kill 好了。

或者按照维基百科上说的，我们保证所有的操作都是 fail-safe 的。 比如可以自动补充 missing 参数，然后 handle 非法参数。

定向选择：Fitness 函数

不同的问题有不同的 fitness 函数。 有的问题，我们可以准备一些测试数据，以数据 pass 的 rate 作为我们的 fitness。 有的问题我们则可以以函数输出的偏差来为 fitness。

实例

现在我们有一张图，假设我们需要抠出里面的花。

source

当然用 HSL 通道很容易。 现在假设我们想要基于 RGB 来做这个事情。 我们先用 Photoshop 或者 Gimp 手工做出一个二值化结果，然后用遗传编程去自动生成算法。

target

我们定义一些符号：

  • R - 图像的红通道
  • G - 图像的绿通道
  • B - 图像的蓝通道
  • sub - 二元操作符，返回两个图像通道的差值
  • mul - 二元操作符，返回两个图像通道的乘积
  • add - 二元操作符，返回两个图像通道的和
  • max - 二元操作符
  • min - 二元操作符
  • avg - 二元操作符

然后我们定义 fitness 函数为：对于任意程序，取其运算结果，与我们之前手工做出的结果进行相似度比较。

我用 JavaScript 写了一个小小的 Demo，请用 Chrome 开启:

https://zenozeng.github.io/select-flower/

g1

g2

g3

观察这个流程我们可以发现，我们的突变不断的被积累。 从一开始完全不match，到G4的时候已经有些像模像样了。 然后到 G15 的时候，相似度已经达到了 0.88。

注意哦，二值化不是我给定的原子函数之一， 这个二值化效果是因为 mul, min 和 max 这些操作符混合出来的。 但是效果却意外得好。

不过不要问我为什么这段程序能标记出花来，这是程序写出来的程序，不是我写的:)。

Notes

  • 使用遗传编程的时候要小心选择原子函数，好的原子函数选取可以在保证对问题的原子描述的前提下，大大缩减搜索空间。
  • 像 Lisp 这样天生为树语言非常适合遗传编程，但是理论上来说任何可以得到 AST 的语言都是可以做一做遗传编程的。

参考文献