王登科:生命游戏与遗传编程_最新动态_新闻资讯_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 新闻资讯 > 最新动态 > 王登科:生命游戏与遗传编程

王登科:生命游戏与遗传编程

 2014/11/24 14:24:16    程序员俱乐部  我要评论(0)
  • 摘要:文/王登科今天在一本书中读到一个很神奇的故事,在九十年代,生物学家ThomasS.Ray写过一个80条指令的病毒,并把这条病毒放在计算机里面『培养』,这些病毒不断复制和变异,变化出了各种不可思议的变种,比如在几十亿次运行之后,出现了仅仅有22条指令却有完善功能的病毒,当时麻省理工的科学家尝试用最短的指令来写一只病毒,却还是用了31条指令。指令的多少关系到对计算机资源的索取,所以45条指令的病毒比80条指令的病毒更具优势,这位生物学家调整了计算机规则,给不同指令的病毒分配不同的资源
  • 标签:游戏 编程

生命游戏与遗传编程

  文/王登科

  今天在一本书中读到一个很神奇的故事,在九十年代,生物学家 Thomas S. Ray 写过一个 80 条指令的病毒,并把这条病毒放在计算机里面『培养』,这些病毒不断复制和变异,变化出了各种不可思议的变种,比如在几十亿次运行之后,出现了仅仅有 22 条指令却有完善功能的病毒,当时麻省理工的科学家尝试用最短的指令来写一只病毒,却还是用了 31 条指令。

  指令的多少关系到对计算机资源的索取,所以 45 条指令的病毒比 80 条指令的病毒更具优势,这位生物学家调整了计算机规则,给不同指令的病毒分配不同的资源,以达到某种『平等』,但是在一百五十亿次『繁衍』之后,出现了一种 36 条指令的病毒,这个病毒很『狡猾』,他在末尾多占用了一个字节,以『骗取』了多一倍的运行资源,结果横扫了整个系统。

  作者还提出一种设想,让计算机程序也在运行中做到生物那样的自我进化,非人为的变得越来越人性化,比如 Word,在你每次用完它之后就会默默的自我更新以达到更漂亮的外观和更人性化的体验,当然,前提是你应该为这些『程序生物』的繁衍设定一些规则。

  看到这些神奇的东西,我感到我多年的计算机知识白学了。我立马开始搜索这方面的资料,我的感受是,这个世界太奇妙了。

  『让计算机模拟生物进化』一直以来都是计算机科学和生物学的课题,事实上,早在 1970 年,美国数学家 John Horton Conway 就发明了一种『细胞自动机』,这也被称之为『生命游戏』。

生命游戏与遗传编程

  生命游戏是一个零玩家游戏。它包括一个二维矩形世界,这个世界中的每个方格居住着一个活着的或死了的细胞。一个细胞在下一个时刻生死取决于相邻八个方格中活着的或死了的细胞的数量。如果相邻方格活着的细胞数量过多,这个细胞会因为资源匮乏而在下一个时刻死去;相反,如果周围活细胞过少,这个细胞会因太孤单而死去。实际中,玩家可以设定周围活细胞的数目怎样时才适宜该细胞的生存。如果这个数目设定过高,世界中的大部分细胞会因为找不到太多的活的邻居而死去,直到整个世界都没有生命;如果这个数目设定过低,世界中又会被生命充满而没有什么变化。

  实际中,这个数目一般选取 2 或者3;这样整个生命世界才不至于太过荒凉或拥挤,而是一种动态的平衡。这样的话,游戏的规则就是:当一个方格周围有 2 或 3 个活细胞时,方格中的活细胞在下一个时刻继续存活;即使这个时刻方格中没有活细胞,在下一个时刻也会“诞生”活细胞。

  在这个游戏中,还可以设定一些更加复杂的规则,例如当前方格的状况不仅由父一代决定,而且还考虑祖父一代的情况。玩家还可以作为这个世界的“上帝”,随意设定某个方格细胞的死活,以观察对世界的影响。

  在游戏的进行中,杂乱无序的细胞会逐渐演化出各种精致、有形的结构;这些结构往往有很好的对称性,而且每一代都在变化形状。一些形状已经锁定,不会逐代变化。有时,一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。

  显然 Thomas S. Ray 的『病毒生物』比生命游戏中的这些『细胞』更加强大,它们运行在计算机系统中而非软件中,换言之,它们更加『高级一层』,所以这些病毒造成的变异更加神奇,而不仅仅是生命游戏中的形状体现。很遗憾我没有找到 Thomas S. Ray 的病毒样本 Thomas S. Ray 的项目主页是:http://life.ou.edu/tierra/,有下载,有论文,自取。不过我找到了好几款现在还可以运行的生命游戏,有兴趣的不妨看看:http://simplesource.blog.163.com/blog/static/103414062010089838173/,还有个程序员在 Conway 的生命游戏的基础上进行了更多的设置,使得其更加复杂有趣,这个『高级版』可以在这找到:http://www.cnblogs.com/conmajia/archive/2012/05/31/life-game-note.html

  后来我知道,Thomas S. Ray 的程序其实属于遗传编程(GP)的范畴,按照百科的解释,遗传编程是一种特殊的利用进化算法的机器学习技术, 它开始于一群由随机生成的千百万个计算机程序组成的"人群",然后根据一个程序完成给定的任务的能力来确定某个程序的适合度,应用达尔文的自然选择(适者生存)确定胜出的程序,计算机程序间也模拟两性组合,变异,基因复制,基因删除等代代进化,直到达到预先确定的某个中止条件为止。

  复杂的生命形式可以通过最简单的规则来进行演化,生命之奇妙莫过于此。更直观的感受可以通过以下一个五分钟的小视频来感受:

  算法是人写的,可是演化却是人所不能控制的,这种由简单规律和大量个体智慧共同作用的结合让我想到了分布式计算和大数据,我们炒的很火的新概念,其实早就根植于我们进化的基因当中,而拥有强大运算能力的现代计算机,则是潘多拉的魔盒,我们通过它来研究生命,但是里面也充满着未知。

  我们所有计算机老师都告诉我们计算机是最老实的,你让它做什么它就做什么,可是计算机也有不老实的时候,某些时候,计算机的『失控』比『受控』更加令人兴奋。

  失控的计算机,带来的是崭新的世界,诸如人工智能,进化模拟等等领域,我们需要的正是出乎我们预料的结果。

  其实我也一直好奇,是什么让这些变异发生?让这些进化开启?让人所写的程序变得不被人理解?想来,这个原因应该和我们之所以从细胞进化到人,而又从石器时代走到信息时代的原因一样,这个原因就是生命之与世界的奥秘。

能够知道这些奇妙的东西真是太爽了。

发表评论
用户名: 匿名