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

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

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

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

“Guess lantern riddles”的图片搜索结果
谜面假儿真女配为婚真经和尚念假经天上雷公下假雨吓得道士鼓眼睛
谜底

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

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

 1 平面直线2 欧姆定律3 超越函数4 自然规律5 股票
 

 

 

谜面

(训练数据)

1, 1)

 

(2.5, 2)

I, R, V

 

2, 2, 4

3, 2, 6

2, 4 ,8

某仪器观察到一批数据,

 

共300行,波浪式前进且上升。

0.1, 0.1998

0.2 0.3986

0.3 0.5955

0.5 0.9794

…..

第谷40年观察

 

积累的天文数据

某股票连续一年

 

数据

谜底2x-3y+1=0I*R=VY=x+sin(x)开普勒行星运动定律下周行情

表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)2+…fn(a)/n!*(x-a)n+…

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

Sin( x) = x-x3/3!+x5/5!-…(-1)k-1*x2k-1/(2k-1)!+….

ex = 1+x+x2/2!+x3/3!+…+xn/n!+ ….

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

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

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

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

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

残酷的基因手术

杂交,对 1 + x4 , 5– x,施加以换头术,交换红蓝部分,可以杂交出5+ x4 1-x

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

6+x7 中的“+”变为“*”,得到 6*x7

+x7中的“+”变为“-”,得到 -x7 ,…..

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

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

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

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

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

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

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

y=2x-x3/6+x5/120

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

细心一点的观众会发现 y = x + x-x3/6+x5/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).

作者:唐常杰,四川大学,计算机学院,教授

本文采用「CC BY-SA 4.0 CN」协议转载自互联网、仅供学习交流,内容版权归原作者所有,如涉作品、版权和其他问题请给「我们」留言处理。

(0)
上一篇 2016-06-08 23:09
下一篇 2016-06-10 22:30

相关文章

关注我们
关注我们
分享本页
返回顶部