通过人工智能编写自修改/自完善的程序

作者:Kory Becker

译者: Mr派

来源:http://www.primaryobjects.com/2013/01/27/using-artificial-intelligence-to-write-self-modifying-improving-programs/(点击阅读原文前往)

简介

计算机程序可以自己编程吗?人类程序员有朝一日能被他们掌握的计算机取代吗?就像农民、装配线工人和电话接线员一样,程序员会是下一个被取代的吗?虽然这种想法似乎有些牵强,但实际上可能还没我们想象的那么遥远。这篇文章描述了一个实验来制作一个人工智能程序,它使用自修正和自完善的遗传算法开发自己的程序.

“hello”

上面的程序代码是由一个人工智能程序创建的,该程序的设计目的是编写具有自我修改和自我改进代码的程序。该程序在29分钟内创建了上述内容。编程语言是脑力劳动。为什么使用这种编程语言呢?请继续阅读。

AI程序的所有代码都在GitHub(https://github.com/primaryobjects/AI-Programmer)上。

人工智能占据编码领域

随着计算机技术、硬件、内存和CPU速度的发展,人工智能多年来一直在稳步发展。随着计算机的速度越来越快,可以进行更多的计算,这使得许多人工智能算法所需要的计算密集型处理能力越来越强。

人工智能的爱好

这对我来说是一种兴趣,涉足人工智能程序,尝试编写一个程序,它本身可以编写程序。当然,我并不是指取得程序指令或代码块子集并将它们组合在一起或以其他方式进行优化以产生最终结果的程序,而是从头开始,人工智能完全不知道如何用目标语言编程。人工智能必须自己学习如何为特定的目的创建一个功能完整的程序。

我最初是在20世纪90年代末开始尝试创建程序,用简单的if /then/ else语句来输出BASIC程序。由于种种原因,这是一项艰巨的任务。首先,使用if /then/ else条件来编写一个随机程序似乎并不十分明智。第二,BASIC计算机指令的数量太大了。更麻烦的是,一些指令是十分危险的(Shell(“format c:”))!我还尝试使用C、c++和其他一些语言生成程序。然而,这种幼稚的方法从未产生过一个可以工作的小程序。尽管这不仅仅是由于使用简单的if /then/ else语句,还因为所选的编程语言是为了供人类使用而不是计算机,因此,人工智能的自动化要复杂得多。

虽然最终的目标是制作一个计算机程序,它能够编写自己的文字处理软件、图像编辑工具、web浏览器或磁盘碎片整理程序,但我更感兴趣的是一个简单的概念验证,要证明这个想法是可行的。

猴子和打字机

我最初的想法来自于“无限猴子定理”,如果你有1000多只猴子在打字机上不停地敲打,它们最终会重现莎士比亚的剧本。这听起来很荒谬,但只要有足够的时间,猴子们肯定会按“一些”随机的字符序列,最终生成书面作品。简化这个想法,其中一只猴子至少会在敲击键盘的时候打出莎士比亚戏剧的第一个字母;这当然是可能的。

如果你能引导猴子呢?每次一只猴子按正确的顺序按下正确的键,你就奖励他一个香蕉?过了足够长的时间,也许猴子会识别一个模式?如果他真的很敏锐,也许他甚至会开始选择哪些字母组合在一起形成英语单词,这样,他就会比他的同伴获得更多的香蕉。

转向遗传算法

这是遗传算法背后的基本思想。遗传算法是一种模拟生物进化的人工智能,它除了可用的工具和有效的指令,对某个问题一无所知。人工智能选择了一系列随机指令(作为DNA片段),并检查结果的适应度。它的规模很大,有100个程序。当然,有些程序比其他程序好。那些有最好的适应度的部分会联合起来产生后代。每代人都从进化技术中获得了一点额外的多样性,如轮盘选择、组合交叉和变异。这一过程在每个孩子的下一代中重复,希望能产生更好的结果,直到找到一个目标解决方案。遗传算法是适者生存的编程实现。考虑到它们是如何为一个特定的解决方案搜索一个巨大的问题空间的,它们也可以被归类为人工智能的搜索算法。

好吧,但是为什么是Brainf-ck ?

虽然最初的实验使用BASIC、C、c++和其他语言,未能产生结果,但我通过将自产的编程语言(包括添加、减、循环等)与遗传算法和神经网络结合起来,成功地生成了AI程序。虽然这很有趣,但最终的结果只是简单的数学计算,而且编程语言本身,是未知的,并且有严重的局限性,不知道它最终会产生什么。

我开始寻找一种简单的编程语言,具有有限的指令,我可以训练人工智能程序来使用。和汇编(ASM)很接近,但仍然包含太多的排列。尽管听起来很可笑,但我最终还是尝试了brainf-ck,并最终成功地生成了上面所示的代码。

由于人类使用它很困难,brainf-ck被认为是一种笑话式的编程语言,它实际上对计算机有几个明显的优势。

Brainf-ck作为人工智能编程语言的优势

1. 它是图灵完备的

图灵完全的编程语言意味着它理论上能够解决宇宙中的任何计算问题。使用此功能的编程语言提供了大量的可能性。毕竟,如果不是所有的计算机程序都被设计成执行某种计算并以某种方式输出结果,它也将完成大多数任务。

2. 它由简化的8条指令组成

简化的指令集减少了找到目标程序代码的搜索空间。随着计算机越来越快,可以搜索更大的问题空间。然而,在个人电脑上,搜索空间需要被限制。通过将编程指令限制为8个不同的字符,人工智能可以运行得更快,并在合理的时间内(几分钟,几小时,甚至是一天)获得最佳的适应度

3. 构建解释器很容易

该指令集有良好的文档且易于理解。因此,创建一个可以执行程序的简单解释器非常简单。通过将解释器包含在AI程序和遗传算法中,代码可以优化运行,比调用外部编译器来执行每个子程序的速度要快得多。这也提供了安全约束,因为子程序运行在人工智能程序内的受控环境中。人工智能还可以访问解释器的内部组件,比如内存、指令和输出。这在计算适应分时很有用。然而,使用第三方编译器,这些组件很难访问。

4. 每个指令是1个字节

本文中使用的人工智能程序是用c#、.NET设计的, 使用一组double作为基因组。基因组中的每一个double(基因)都对应于编程语言中的一条指令。由于每个指令只有1个字节,所以很容易将每个基因映射到一个编程代码(注意,1double= 8字节;仍然等于数组中的一个槽)。

5. 易于指令扩展

大多数编程语言的解释器只是执行代码,维护内存值,并包括对控制台输入/输出的支持。但是,它可以扩展解释器来支持生成图形、网络功能、文件系统访问以及更多的内容。联想一下,你可以给予人工智能开发自己的程序的力量!)

它是如何工作的

AI程序的工作原理如下:

  1. 基因组由一组double组成。
  2. 每个基因都对应于一个brainf-ck编程语言的指令
  3. 从随机基因组的群体开始。
  4. 通过将每个基因组译码成相应的指令,将每个基因组解码成一个结果程序并执行
  5. 根据控制台输出(如果有)获得每个程序的适应度评分并对其进行排序。
  6. 用轮盘选择、组合交叉和变异来配对最好的基因组,以产生新一代。
  7. 新一代重复这个过程,直到达到目标适应度。

由于fitness方法是计算成本最高的部分(它必须为每个成员执行程序代码,可能包括无限循环和其他讨厌的东西),人工智能程序在.NET 4.5使用Parallel.ForEach 方法。通过这种方式,它可以在群体中对每一代执行多个基因组的适应度算法。这使得程序可以最大化地利用CPU资源并利用多个CPU核。这个程序也会每隔1万代保存它的状态,以防程序或PC被关闭,它可以继续从它停止的地方搜索。

适应度方法

适应度方法是通过对生成程序的输出进行评分。这个分数是通过观察程序输出的每个字符来计算的(如果有任何输出的话),并从期望的字符中减去它的值:

当然,最初生成的程序甚至无法编译,更不用说输出文本到控制台了。这些都会被丢弃,输出一些内容的程序则会被留下来;并进一步引导和进化,直到输出结果越来越接近所需的解决方案。

解释指令集

brainf - ck由以下指令集组成:

结果呢?

hi

在大约1分钟的时间里,经过5700代,人工智能成功地编写了一个程序,输出了“hi”。它产生了以下代码:

虽然上面的代码包含解析错误,如非匹配的方括号,但是我们的模拟解释器在程序失败之前计算结果,因此在上面的例子中,语法错误(在找到解决方案后,代码中稍后会出现)不会影响到适应度。

您可以尝试将上面的代码粘贴到一个brainf - ck解释器中。单击“开始调试”,忽略警告,然后单击“运行到断点”。注意输出。

如果我们对多余的代码进行修剪,我们会看到以下的语法正确的代码:

你可以查看下面在程序运行时的截图:

AI learning how to program

AI learning how to program, almost there

AI learning how to program, a solution is found

AI program fitness over time

这是历史图表,随着时间的推移,绘制出适应分。您可以看到AI怎样学习如何用目标语言编程并实现所需的解决方案。

hello

在大约29分钟的时间里,在252,0000代后,人工智能成功地编写了一个程序,输出了“hello”。它产生了以下代码

在生成过程中,人工智能非常接近于一个解决方案,但是一对字母在一个循环中彼此绑定。人工智能在问题1中创建一个内部循环,成功地输出正确的字符,并继续进行处理。

AI learning how to program

AI learning how to program, a solution is found

AI program fitness over time

Executing the program, developed by the AI

Hi!

人工智能在大约2小时7分钟后,经过219,400代,成功地编写了一个程序输出“你好!“。它产生了以下代码:

这实际上是我的最爱之一。运行它,您可以看到原因(单击启动调试器并运行到断点)。就好像电脑知道自己在做什么。有趣的是,这个程序的生成时间比前两个要长。这可能是由于使用的字符包括大写字母和符号。另外两个例子使用的字符在ASCII系统中值更接近,这对人工智能来说比较容易找到。

AI learning how to program, a solution is found

Executing the program, developed by the AI

AI program fitness over time

reddit

在大约22分钟的时间里,人工智能成功地编写了一个程序输出“reddit”。它产生了以下代码:

这是一个挑战。这可能是由于它的长度,或者可能是由于d的位置。人工智能会不断地停留在局部最大值内。局部最大值是当一个遗传算法找到了它在当前参数中所能看到的最好的适应度,即使还有一个更好的适应度可能存在。人工智能无法走出它的洞穴,达到更好的适应度,因为这样做会要求适应度再次增加之前先下降,这通常是违反遗传算法的规则的。

我可以通过增加变异函数的多样性来解决这个问题。在此之前,基因变异只会改变基因组中的一条指令。变异被增强,不仅包括变异单个位(替换变异),还包括改变位(插入变异)和转移(删除变异)。这种额外的多样性使人工智能得以继续前进。

AI learning how to program

AI learning how to program, a solution is found

AI program fitness over time

hello world

这是在大约2小时内580900代之后产生的。它产生了以下代码:

如果你修剪掉多余的部分,打印文本的实际代码要短得多:

AI learning how to program, a solution is found

AI program fitness over time

I love all humans

这是在大约10小时6057,200代之后产生的。它产生了以下代码:

如果你修剪掉多余的部分,打印文本的实际代码更短:

在上面的运行中,AI提供了一个启动程序,指令数组大小为300 (ie,300字节,或者更确切的说是2400字节,因为1倍= 8字节) 人工智能不需要完整的程序代码长度。它可以用209条指令编写程序。

注意,这个解决方案花了10个小时完成。然而,要记住,这是使用人工智能程序进行编程,而不是人类,他们完成一个程序所需的时间就会少一些。人工智能可以简单地在后台运行,而人类还要在其他任务上工作。我还预计,随着计算机在未来几年变得更快,计算时间将会显著减少。

未来

这个实验是一个概念验证,人工智能程序可以开发自己的计算机程序来执行特定的任务。在这方面,它是成功的。人工智能一开始可以对目标编程语言一无所知,而成功地学习如何生成一个有效的计算机程序,该程序在执行时,解决一个特定的任务。

与所有的遗传算法一样,这也涉及到设计适应度函数的工作。适应度函数相当于向人工智能描述你要找的东西。通过这种方式,创建适应度函数本身,有点像编程(代表人类)。如果人工智能有可能发展自己的适应度函数,这将是一个进步。与此同时,我们仍然可以开发这个项目来创建更复杂的子程序,比如那些接受用户输入,计算结果的程序。

十年前,这个项目在任何合理的时间内都不会成功。五年前,这个项目可能需要几天甚至更长的时间。今天,执行只花了几分钟时间。明天,程序可能以毫秒级运行。随着计算机的发展越来越快,越来越大的搜索空间可以计算出来。我等不及了。

如果你已经发现其中的趣味的并且想要了解更多,下载GitHub的完整源代码或者联系Kory Becker。阅读我关于使用c# . net中的遗传算法和神经网络的教程。本文中的可执行程序是Brainfuck.NET编译器编译的。

原文发布于微信公众号 - java达人(drjava)

原文发表时间:2017-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钱曙光的专栏

一周极客热文:你工作了几年以及待遇大概多少?

本周被盖到400+楼的最最最热门文章是《大家聊聊待遇:工作几年,待遇大概多少??》。由于回复的内容“炒鸡”多,小编也无法很好的整理并得出高大上的结论,我想大家还...

21610
来自专栏CDA数据分析师

分享 | 8条数据清洗经验,收藏备用!

文 | Philip Guo 来自Chaoslog 平时习惯了在某些特定的数据集合上做实验,简单的tokenization、预处理等步骤就足够了。但是在数据...

2525
来自专栏python全栈布道师

python2018.06聚会笔记

这个小哥哥身穿白色T恤, 下身穿粉红色短裤, 讲起话来很幽默,而且喜欢自嘲式的谦虚.

1002
来自专栏java达人

如何编写复杂sql

经常有人问我那非常复杂的sql是怎么写出来的,我一直不知道该怎么回答。 因为虽然我写这样的sql很顺手,可是我却不知道怎么告诉别人怎么写。很多人将这个问题...

7169
来自专栏Java学习网

编程能力七段论

编程能力七段论 前言   程序员的编程技能随着经验的积累,会逐步提高。我认为编程能力可以分为一些层次。   下面通过两个维度展开编程能力层次模型的讨论。   一...

3375
来自专栏逍遥剑客的游戏开发

面向对象vs面向数据

3024
来自专栏牛客网

金蝶java岗 技术面+hr面 面经(略水)

看了那么多大佬的面经,感觉都是可望而不可及,问的题目都挺难。今天我就发份简单点的面经,让大家参考一下这种公司的水平大概都是会问些什么,有所了解。  一面 : ...

5446
来自专栏DevOps时代的专栏

图解:云原生应用架构The 12-Factor App准则

云原生应用凭借”快速运行环境整备、故障隔离、容错、自动故障恢复、易于随用户数量增多而进行容量伸缩、便于移动和多种客户端应用访问“等优势[1]在现代软件开发领域迅...

4375
来自专栏IT派

我用 Python 爬取微信好友,最后发现一个大秘密

你身处的环境是什么样,你就会成为什么样的人。现在人们日常生活基本上离不开微信,但微信不单单是一个即时通讯软件,微信更像是虚拟的现实世界。你所处的朋友圈是怎么样,...

1864
来自专栏GopherCoder

『Go 语言学习专栏』-- 第十三期

2122

扫码关注云+社区

领取腾讯云代金券