趣味数据挖掘系列9：灯谜、外星殖民、愚公移山和进化计算

本文从《基因表达式编程》的课程PPT中取了一些素材，加以简化和趣味化，从猜谜出发，借用外星殖民的科幻，讨论了公式发现的进化算法，分析了其中的愚公移山思想，描述了进化计算的七个特征，为下篇博文做些概念的准备。

1 春节将至，先猜灯谜在童年的一个春节，笔者在走马灯上见过一首字谜诗，韵律规范，对仗工整，令人捧腹，久久回味而不易忘却(为增加思考的趣味，把窍门放在文末）：

猜后感：(1)窍门就像窗户纸，一旦捅破，就那么显然，但是，窍门不易找到；(2) 从谜面到谜底比较难，反之，从谜底造谜面较易（可能造出的谜面不唯一，文字没有这样美）。

2 猜大自然之谜与公式发现， 表1中给出了几个与自然和社会规律相关的谜语，谜面是训练数据。问题1告诉了迷底类型是直线，可以用待定系数法 ax+by+c=0 求出 a/c, b/c ，当数据点多于两个，用线性回归，找出一条使均方差最小的直线。问题2，易观察规律，问题3将在下面讨论；对于问题4，开普勒用了十年时间，作手工数据挖掘得出了结果；问题5 事关财产大事，猜对了，可能一夜致富，猜错了，可能倾家荡产。

表1几个与自然规律和社会相关的问题

3外星殖民 — 学当一回上帝 地球资源的短缺敦促人类寻找新的宜居星球。假定地球人在太阳系外找到了一个宜居，但还没有较高级生物的星球，不妨取名新大陆，但发现那里的大气、土壤与地球略有不同。怎样把它改造为适宜地球人居住的家园呢？

假如那一天真的来临，笔者建议学习大自然的进化算法，要点如下：

Begin。

Step1：

初始化：带上一些地球上的微生物和低等生物（低等的变异比较大），随机或按一定规则布署；

Repeat

让他们在新大陆上生存、变异、发展；

until 低等生态环境建立（如大气成分与地球相近，等等）；

Step2: 移植一些高等动物植物到新大陆；

Repeat

让它们竞争，进化，优胜劣汰；

人类随机地，或按一定规则给干预，引导他们的进化，

例如制造一点困难（如水旱洪荒），作为适应度函数，淘汰一些适应度数低的物种；

如果发生大灾难，送去诺亚方舟，….；

Until 农牧业环境建立；

能够存活下来的物种不是最智慧的；存活下来的物种不是最强壮的；但是存活下来的物种是那些最能够适应其生存的环境变化的物种。）

Step3：人类进驻新大陆星球；

End

这个过程也许需若干世纪；不着急，人类只需抓大放小、做些宏观干预；相信人类的科学家，在地球资源枯竭或被大行星撞击之前，一定能办成这件事。

信上帝的人或许会说，此算法知识产权属于上帝。其实，大自然的进化算法与上帝算法有所区别，上帝算法是目的论典范，例如。偶尔听到这种说法：“为了能吃到高树叶，长颈鹿的长了长脖子”，而大自然的进化算法是非目的论的，有几个要点：

（1）在多灾多难多变的地球环境中，不善变异的物种容易灭绝，如今不善变异物种不多，如熊猫等活化石物种。大多数物种都善于变异，善于改革开放（改革自身，向环境开放），在变中求存。

达尔文的粉丝们，读了《物种起源》后，替他起草了一段“名言”，虽属是枪手之作，但的确符合其本人的核心思想：“能够存活下来的物种不是最智慧的；存活下来的物种不是最强壮的；但是存活下来的物种是那些最能够适应其生存的环境变化的物种。（it is not the most intellectual of the species that survives; it is not the strongest that survives; but the species that survives is the one that is able best to adapt and adjust to the changing environment in which it finds itself。）
（2）一将功成万骨枯，当环境变化时，海量的个体中，一部分发生了变异，不变异的被淘汰了，虽变异但仍不适应新环境的也被淘汰了，有那么一只或几只，变异对了路，新性状能适应变化了的环境、生存并繁衍了。

（3）没有“为了”，没有目的，从而也没有上帝。这可能是达尔文学说最犯教会之忌的地方。

在下面猜测自然之谜的过程中，要学当一回上帝，要借用大自然进化的方法。

4 明码的进化计算法，挖掘表1第4列的谜底 表1第4列谜面数据是某仪器观察到一批数据，波浪式前进上升。怎样从谜面发现其谜底y=x+sin(x)呢？

千言难尽，科普博文只能简单说明思路，这里跳过基因编码和基因表达，用不编码的公式进化。这种“明码进化”，效率低，需要人的智能，不适合计算机，但适合初学者理解。

准备用多项式去逼近目标：函数f(x)可展开成泰勒级数(只需满足不太苛刻的条件)：

f(x) = f(a)+f'(a)*(x-a)+f”(a)/2!*(x-a)²+…fⁿ(a)/n!*(x-a)ⁿ+…

收敛速度与|x-a|ⁿ相关, 用上式计算f(x)在x=a 附近的近似值,收敛较快，在下面两个公式中，a=0 :

Sin( x) = x-x³/3!+x⁵/5!-…(-1)^k-1_*x^2k-1/(2k-1)!+….

e^x = 1+x+x²/2!+x³/3!+…+xⁿ/n!+ ….

染色体和基因为简单，用10个公式作群体进化（进化计算程序中，群体规模常为100-1000）,下面随意写出了4个公式:

y1=1+x4 , y2=5-x ,y3=10-x3, y4=x2-X5, y5=5+x7 ,……

每个公式个体是一个候选的近似答案，公式可杂交、变异、繁殖，有一定生命力，本博文中暂称为染色体。染色体中的变量、符号（串），如+，-，*, /，2，x ,x³, x² , sin(x), e^-x等，既易变异，又可能表达出可遗传的性状，不妨称为基因。例如：

含有sin(x)的公式，可能有周期性，不妨把sin(x)称为周期性基因；

含有 e^-x的公式，可能有衰减性；不妨把e^-x称为衰减性基因。

残酷的基因手术

杂交，对 1 + x⁴ , 5– x，施加以换头术，交换红蓝部分，可以杂交出5+ x^{4 _，}1-x

变异：在染色体中插入、删除、或修改符号或符号片段。

6+x⁷ 中的“+”变为“*”，得到 6*x⁷

+x⁷中的“+”变为“-”，得到 -x⁷ ，…..

变异手术中常用换头术、挖心术、加瘤术和移植器官术，比较残酷；早期的进化算法在做变异手术时候，大量的公式都死亡了或伤残了，尽管公式们不会呻吟，也不会抗议，但极大地制约了进化的速度和质量。

Candida Ferreira 于2000年提出了基因表达式编程^[2]，由于编码巧妙，可以保证染色体在残酷的变异手术下全部存活。

选择标准是进化指挥棒，兼议若干金鱼实为遗传病携带者培养金鱼品种时，通过杂交，变异（如辐射、或化学方法），人工选留下一代。如果培育者喜欢头上长肉瘤的，则美其名曰凤头，如果喜欢浑身长疱块的，则美其名曰珍珠；而高度近视容易受伤的鼓眼，则称为龙睛，并大加培育。其实，这些品种在某种程度上都是遗传病携带者，但是养鱼人喜欢这种病态美（就像宝哥哥喜欢林黛玉），又有观赏和市场价值，从而得到繁衍，设若把这些病态美的金鱼放归大自然，很快就被淘汰了。

进化计算中的选留机制是适应度函数，旨在使进化目标在训练数据集上的综合误差最小，当然，为了防止局部收敛和早熟，适当照顾多样性，选留少数适应度不高的个体。

适应度函数是指挥棒，它引导着进化的方向，就像高考对中学教育的作用,如今，有识之士已经认识到各种考试的利与弊，拒绝金鱼模式，拒绝病态美。

不难想象，经过若干代的进化。种群中的公式中会有迎合训练数据的基因出现，如用n个x连乘得到 xⁿ；用x/x得到1，用1累加得到n, 也不难进化出n! ，如果训练数据有衰减性，可能会从多项式基因进化出e^-x的泰勒级数前面若干项。

5难能可贵的基因组合。在上面的进化挖掘过程中，经过若干代杂交、变异、和筛选，一个明星突然横空出世：

y=2x-x³/6+x⁵/120

它对表1第4列的训练数据的适应性比较好，在0<x<0.5(弧度）时，误差不超过1%,(1弧度=57.3^o）,其实，只要有0到45^o 的正弦数近似值，利用中学三角函数知识，任意三角函数也能近似计算了。

细心一点的观众会发现 y = x + x-x³/6+x⁵/120≈x+sin(x)，它是欲猜之谜底的泰勒展式的前三项。

上述过程在基因表达式编程中，在普通PC机器上，进化几百代，大约需时几秒。实验表明，单次成功率高于70%，即连续做两次，就至少一次成功。

6 愚公移山，回到第4节的明码的进化计算。 对照寓言中的愚公移山，做两个比喻：

训练数据（谜面） — 王屋山，

谜底（y=x+sin(x)） — 挖掉大山后得到的路。

注意，在挖掘过程中，有

两个不变：山还是那座山（训练数据不变），梁还是那道梁（谜底y=x+sin (x)）不变；

一个进步：公式群体可不是原来那个公式群体，通过遗传，继承优良基因优势；通过变异，创生新的基因，通过杂交，集中优良基因，群体协同、在适应度函数的选择压力之下，并行地进步，精度一代比一代高。

愚公精神：儿子辈公式达不到精度，还有孙子辈公式，子子孙孙没有穷尽，直到达到收敛标准或达到规定的辈数。

7进化算法的特色：适、指、全、黑、并、渐、通

今天，人们把进化计算作为数据挖掘或机器学习的一个分支，实际上进化计算概念是单独提出、独立发展的[1]，由于其复杂性，在硕博士生课程中，常作为单独一门课程开设；数据挖掘的教科书偶尔会蜻蜓点水地提一下。

进化计算有多种模型，如遗传算法（Genetic Algorithm）、遗传编程(Genetic Programming)，基因表达式编程(Gene Expression Programming)，等等，这三者大概都是一个学期的课程，2-3学分。他们的共性可以用七个字描述，即：适、指、全、黑、并、渐、通，解释如下：

适–有适应度函数与适应度阈值，它是指挥棒，控制和引导了进化方向；指–有指导的进化；全–全局优化；黑–黑箱特性；并–并行性，是一个种群集体进化，具备先天的并行特性，易在并行计算机上进行；渐–渐进性；通–通用性。

有了这些概念的铺垫，下篇准备简介进化计算家族中比较新的成员“基因表达式编程”。

关于谜语的窍门：

假儿真女配为婚，假儿–而，而+女=耍；

真经和尚念假经： 真经和尚，尚，假经：巾；尚+巾=常

天上雷公下假雨：假雨：羽；公+羽=翁

吓得道士鼓眼睛：道士=倒立的士，干；鼓眼睛后 为 平

参考文献

[1] Russell C. Eberhart and Yuhui Shi,”Computational Intelligence: Concepts to Implementations “,Publisher: Morgan Kaufmann; 1 edition (August 24, 2007),ISBN-13: 978-1558607590;

[2] Candida Ferreira , Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence (Studies in Computational Intelligence),Publisher: Springer; 2nd edition (July 11, 2006).

作者：唐常杰，四川大学，计算机学院，教授