让计算机自动为我们写程序吧

当你夜深加班，头昏脑胀，用发酸的手腕在键盘上敲if else for 的时候，有没有想过，要是能让计算机自动为我们编程，彻底解放我们的双手，让我们有充分的时间，可以睡觉睡到自然醒，泡妞泡到手抽筋，该有多好。
这并非天方夜谈。有一批异想天开的家伙搞这个事情已经很有些年头了，他们搞的这个领域被称为Genetic Programming（简称GP，javaeye刚发了个相关新闻http://www.iteye.com/news/6797-apache-mahout-0-1-release-machine-learning-algorithm），中文叫“遗传编程”或“基因编程”，顾名思义，就是模拟生物学上进化论来自动产生程序。理论上的东西先不讲，按照规矩，先来个GP的“Hello World”。
比如，我们想要一个程序，功能是对两个数求和，得到类似下面这个c函数代码：

//compute the sum of a and b
int Sum(const int a, const int b)
{
    return a+b;
}

解决问题的思路是从大师的教导出发。大师教导我们：
     程序 = 数据结构 + 算法
很明显，这里我们的数据有两个，a和b，记为：
     data = { a,b }
为简化起见，算法假设只有三个，加、减、乘，记为：
     op = { +,-,* }
那么，所有可能的代码组合为：

                      s = a ;
                      s = aa;   
                      s = aa+;  
                      s = a;    
                      s = a+;   
                      s = a;    
                      s = ab;   
                      s = ab+;
                      s = a ;   
                      s = aa;   
                      s = aa-;  
                      s = a;    
                      s = a-;   
                      s = a;    
                      s = ab;   
                      s = ab-;  
                      s = a ;   
                      s = aa;   
                      s = aa*;  
                      s = a;    
                      s = a*;   
                      s = a;    
                      s = ab;   
                      s = ab*;  

现代的电脑，可以在0.00001秒内找到正确的程序代码：
                      s = ab+;
顺便说下，GP中采用后置表达式更方便，所以搞GP、AI的人都喜欢用Lisp一类的语言。

至此，我们终于让计算机我们编写了第一个程序，虽然这个程序只有一行代码。

当然，对于简单的程序还可以采用这种穷举的办法，但对于一个复杂程序，采用这种方法已经不是当前的计算机所能承受的了。牛人们给出的道路是采用遗传算法，其思想就是模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。科学松鼠会的fwjmath就成功的模拟了如何从一堆杂乱的图形，进化出一个 firefox 图标的过程：

你可能会认为GP只能搞点这些华而不实的小玩意儿。但GP实际上已经做到的事情可能会让你大吃一惊，下面直接引用wiki上的一段话：

引用

“近年来，随着遗传编程技术自身的发展和中央处理器计算能力的指数级提升，GP开始产生了一大批显著的结果。例如在2004年左右，GP在多个领域取得近 40项成果：量子计算，电子设计，游戏比赛，排序，搜索等等。这些计算机自动生成的程序（算法）中有些与2000年后人工产生的发明十分类似，甚至有两项结果产生了可以申请专利的新发明”。

如果你还对GP的能力有怀疑，那么你要先问下自己：自己写过的那么多代码中，产生过一项专利吗？所以，夺取我们饭碗的敌人，不是ruby on rail，不是90后，而是GP啊。当然，我们目前暂时还不用太担心：产生那些成果用的都是一些昂贵的大型机，至少目前，这些大型机的价格还是比程序员贵很多。

评论

5 楼 kj021320 2011-10-16  

门外汉谈AI

4 楼 xuby 2009-04-15  

night_stalker 写道

变异 + 遗传 + 选择

这个例子体现了哪一部分？？

这个条件不简单。科学不是魔法，你得老老实实给一组测试，譬如：
assert(3, Sum(1, 2));
assert(78, Sum(34, 44));

一般来说越复杂的算法，筛选测试就得越复杂。

不过像投资什么的筛选基准就很简单：赚钱越多越优。所以也只有评价标准简单的事情适合用遗传算法解决。

大型机什么的就更扯了……

这个例子主要体现的是自动编程的可能性，就是通过数据和算法的排列组合来达到目的。这个是自动编程基本出发点。当然，一个稍微复杂的算法，以目前的计算机做穷举都是很困难的，这样才需要遗传算法，不求得到最优解，只求得到可接受的解。可以说遗传算法只是自动编程的一个手段。
选择条件是GP里面很关键的一点，很多需求没法自动编程就是因为没法找到一个能快速收敛的筛选条件，但我们这个例子太简单了，傻瓜看一眼都知道选择条件是什么。
大型机那个只是开个玩笑。

3 楼 night_stalker 2009-04-13  

变异 + 遗传 + 选择

这个例子体现了哪一部分？？

这个条件不简单。科学不是魔法，你得老老实实给一组测试，譬如：
assert(3, Sum(1, 2));
assert(78, Sum(34, 44));

一般来说越复杂的算法，筛选测试就得越复杂。

不过像投资什么的筛选基准就很简单：赚钱越多越优。所以也只有评价标准简单的事情适合用遗传算法解决。

大型机什么的就更扯了……

2 楼 xuby 2009-04-12  

night_stalker 写道

不是什么新东西…… 满世界都在用遗传算法。譬如某些炒股软件。

而且这个例子有问题：你忽略了设置筛选条件这一步。

筛选条件已经隐含了。因为这个例子的筛选条件相当明确、简单，不像其他一般的算法，筛选条件处于关键地位。

1 楼 night_stalker 2009-04-11  

不是什么新东西…… 满世界都在用遗传算法。譬如某些炒股软件。

而且这个例子有问题：你忽略了设置筛选条件这一步。