遗传编程入门：机器如何学会自己写代码

计算机科学的“圣杯”或许是：机器自主编写程序。遗传编程（GP）作为新兴机器学习范式，朝此目标迈出关键一步。GP在控制工程极具潜力，本文揭示其原理、表达形式与实例（系列首篇）。

遗传编程与遗传算法的异同

GP源于John Holland的遗传算法（GA），同属进化算法，依靠适应度比例选择、交叉、变异驱动种群代际进化。核心差异：GA用定长位串编码，GP用变长树结构直接表达可执行程序。GP成功运行的产出是：给定输入执行后，输出期望结果的计算机程序。

Nichael Cramer与John Koza奠基GP（Koza持GP专利，著作《遗传编程》为经典）。研究显示GP在机器人导航、博弈策略、符号回归、控制系统等领域成果斐然。

树结构程序表达：GP的核心语言

几乎任何程序均可映射为树。函数式语言（如LISP）天然契合：S表达式即树（图1）。

三种等价表达：

简单程序片段：
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END

LISP等价形式：
(progn (if (a < b)
           (setq a (+ a 1))
           (setq b (* b b))
      )
      (setq c (* (* a b) 2))
)

遗传编程入门：机器如何学会自己写代码 — **图1.** 程序树结构表示。(progn arg1 arg2...)顺序求值各参数

内部节点=函数：元数(arity)≥1，连接子树，充当“胶水”
叶节点=终结符：常量/变量，元数=0

问题建模即：选定函数集（如AND/OR/NOT）与终结符集（如X1/X2布尔输入），并定义适应度函数衡量程序优劣。XOR问题：4种输入组合各跑一次，正确响应计数为适应度，满分4分即最优解（见代码清单1）。

下一站：遗传算子

下文将详解交叉/变异/选择如何驱动进化，并演示更复杂算法实例。

遗传编程入门：机器如何学会自己写代码

遗传编程与遗传算法的异同

树结构程序表达：GP的核心语言

下一站：遗传算子

推荐阅读