2

我正在尝试根据 Gregory Chaitin 的代谢生物学模型破解进化模拟。

给定一个返回整数的算法，我需要随机对其进行变异，以尝试获得另一种语法正确并最终停止的算法。如果突变是真正随机的，则不可能确保您获得的是一个有效的算法，它将停止。

我的问题是：

  • 执行此操作的最佳图灵完备语言是什么？
  • 是否有任何基因编程技术已经解决了这个问题？

提前致谢

我在想这样的事情：

x <- x + 1
x <- x - 1
y <- x
if x != 0 goto label

这是图灵完整的，很容易修改。你怎么看？

4

4 回答 4

1

如果突变是真正随机的，则不可能确保您获得的是一个有效的算法，它将停止。

正如罗伯特 B 指出的那样，一组图灵完备的函数将满足您的第一部分，但是对于允许循环可能性的问题没有解决方案。但是，如果您有可能删除循环，那么您可以生成一个表达式树，每次您为其提供一些输入时，它都可以为您提供输出。表达式树具有有限的大小并保证终止，或者以另一种方式考虑它：获得具有无限运行时间的表达式树将需要表达式树具有无限的节点（这将需要您有无限的 RAM 或磁盘）。

有一些修剪表达式树的策略，以便为问题提供最小的解决方案，其中一些策略涉及使树的大小成为适应度函数的一部分。换句话说，在计算适应度时，要考虑表达式树的大小：当其他一切都相等时（即两个解决方案具有相同的精度），较小的解决方案优于较大的解决方案。

于 2011-12-12T21:26:11.893 回答
0

好吧，您问题的第一部分是关于有效的算法。如果您定义了尽可能多的函数以确保图灵完备（例如，+、-、*、/、X、Y、Retval、循环、if），那么您已经满足了第一部分。我建议使用更高级的函数，因为某些结构会不断地不断进化，如果你把它放在开始的函数列表中，你会加速进化。例如，循环可以分解为 if 和 goto，但是使用循环可以节省宝贵的进化能量，并确保有效性。

但是，您的第二部分是关于最终停止的算法。这个已知无解。一种替代方法是对程序可以执行的指令数量设置限制，如果违反该限制，则中止程序，并给予高额惩罚。或者，如果您有一个终端需要程序加载一个答案（例如 Retval），您可以暂停程序并检查该终端。

于 2011-12-08T15:06:19.577 回答
0

您在这里寻找的是“语法进化”，这将是遗传编程在不断发展的工作计算机程序中的应用。这是一个很好的网站：http ://www.grammatical-evolution.com/ 。此外，您可以通过在 Google 中输入“FPGA 遗传编程”来了解更基本的计算机制（如 FPGA）的演变。

于 2011-08-11T02:16:29.720 回答
0

口齿不清。好吧，任何谐音语言。但是LISP。阅读 Koza 的书籍http://www.genetic-programming.com/

于 2011-07-30T19:13:57.913 回答