进化规划

Question

我只是看着丹尼·希利斯过时的1994年

在视频中的一个点一个很酷ted talk，他谈到了“进化规划”，即他要求通过生成随机生成几百个节目的电脑然后测试每个程序如何排序数字。他保留10％的数字排序最好的程序，然后根据10％的程序生成下一轮程序，这些程序运行良好并重复多次，最终生成最终的排序程序。

那里有工具/编程语言吗？例如。给定一定的约束，生成最能满足这些约束条件的C代码。

我访问了一些与“进化规划”相关的维基百科文章;那里似乎有很多理论，但找到一些你可以玩的东西似乎并不容易。

Answer 1

一个非常简单和通用的免费下载源代码是用Java实现的TinyGP。 顺便说一句..有关这方面的更多细节，你应该搜索有关“遗传编程”，而不是“进化规划”的信息。它有点令人困惑，因为有很多进化计算的子域，像“遗传算法”，“进化策略”，“进化规划”，“遗传规划”这样的名字有很小的差异......但我认为你我们讨论的实际上是遗传编程

Answer 2

本书/教程使用Ruby进行编程。

http://www.cleveralgorithms.com/nature-inspired/index.html

Answer 3

一个实际例子：

Csmith是一种工具，可以生成静态和动态适形于C99标准随机C程序。它对压力测试编译器，静态分析器和处理C代码的其他工具非常有用。 Csmith在它测试过的每一个工具中都发现了错误，我们用它来查找和报告超过400个以前未知的编译器错误。

Answer 4

典型的例子是Tierra和Avida。

相关领域是硬件演化和演化机器人技术，例如参见this page。

关于Mathematica中的进化计算，还有一个不错的book。

Answer 5

我讨厌成为一个不说话的人，但我们用进化编程做了一些测试，发现在很多问题上，穷举搜索速度更快。

有密切相关的领域喜欢遗传算法，我用它来使机器人走等我使用GALIB的。现在可能是古代了。

虽然这个想法是“酷”，但最好的方法可能是使用演化技术加上学习（即强化学习）的组合。

这更像是人类如何学习。长期的演变使得渐进的实验成为可能，而且学习可以解决问题并使系统适应环境。

但是，演化只是需要很长时间才能有效。

Answer 6

可能是创建进化程序最通用的程序是汇编器。这是我所知道的唯一一种能够覆盖其他程序并更改自己的代码的语言。你可能想看看旧的核心战争计划 - 其中一个计划的不同或更新版本可能会发展并击败竞争对手。此外，只要目录数量有限，你就有可能适者生存。

Answer 7

生成程序的进化计算领域被称为遗传编程（GP）。 GP模拟一代人的生物进化，通过许多代。通常，个体是一个程序（或其代表，通常是一个树型数据结构），它的存活和复制的机会是根据其在解决任务中的表现来衡量的。

现在你不能为日常任务生成实际的生产代码，诚实地说。相反，GP和许多其他机器学习技术在现代研究中得到了研究，并被很多大公司（例如Google，Facebook等）使用。事实上，当你知道你想要目标程序要做什么（即你知道输入的输出）时，GP方法是非常有用的，但你不知道如何（或者你很难）编写代码由你自己。

为了正确理解这个话题，您可能需要从头开始编写演化引擎并与之一起玩。从理论描述开始编写代码是完美的。这是了解这些工作如何工作的最好方式，而不是使用一些“预制软件”，即imho。另外，我建议你从遗传算法（GA）开始，因为它们通常比较简单。事实上，在遗传算法中，您通常会评估个体的基因型，即组成它们的位数，而在GP中，您可能想要将树转化为程序，执行它们，查看输出并最终测量它们的性能（不那么直接，呃？）。看看这个：http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3。

我做了硕士论文的实验室证明GP在从文本提取的例子中生成正则表达式方面表现非常出色。他们建立一个图形用户界面，以便发挥他们的引擎：http://regex.inginf.units.it/demo.html。他们还在github上分享了引擎代码：https://github.com/MaLeLabTs/RegexGenerator。 最后，我的一位朋友在他的博客中使用GP和GA（遗传算法）编码了一些有趣的视觉实验。看一看：http://www.nicassio.it/daniele/gp/enviroment/，http://www.nicassio.it/daniele/gp/santaclaus/。