31

进化编程似乎是解决许多优化问题的好方法。这个想法很简单，实施也没有问题。

我想知道是否有任何方法可以在 ruby​​/python 脚本（或任何其他语言）中进化地创建程序？

这个想法很简单：

  1. 创建程序群
  2. 执行遗传操作（轮盘赌选择或任何其他选择），从最佳程序继承创建新程序等。
  3. 循环点 2 直到找到满足我们条件的程序

但是还是有几个问题：

  1. 染色体将如何表示？例如，染色体的一个细胞应该是一行代码吗？
  2. 染色体是如何产生的？如果它们是代码行，我们如何生成它们以确保它们在语法上是正确的，等等？

可以生成的程序示例：

创建将 N 个数字作为输入并返回其均值作为输出的脚本。

如果有任何尝试创建这样的算法，我会很高兴看到任何链接/来源。

4

8 回答 8

23

如果您确定要这样做，则需要遗传编程，而不是遗传算法。GP 允许您发展树状结构的程序。你要做的就是给它一堆原始操作（while($register)、read($register)、increment($register)、decrement($register)、divide($result $numerator $denominator)、print , progn2（这是 GP 所说的“顺序执行两个命令”））。

你可以产生这样的东西：

progn2(
  progn2(
    read($1)
    while($1
      progn2(
        while($1
          progn2( #add the input to the total
            increment($2)
            decrement($1)
          )
        )
        progn2( #increment number of values entered, read again
          increment($3)
          read($1)
        )
      )
    )
  )
  progn2( #calculate result
    divide($1 $2 $3)
    print($1)
  )
)

您将使用它与实际解决方案的接近程度作为您的适应度函数。其中有一个问题，无论如何您都必须按照传统方式计算*。然后有一些东西可以将其翻译成（您选择的语言）的代码。请注意，由于其中存在潜在的无限循环，因此您必须在一段时间后切断执行（无法解决停止问题），并且它可能无法正常工作。嘘。另请注意，我提供的代码将尝试除以零。

*有一些方法可以解决这个问题，但通常不会太远。

于 2011-04-20T22:28:52.147 回答
15

它可以完成，但对于大多数类型的应用程序来说效果很差。

遗传算法仅在适应度函数连续时起作用，即您可以确定当前人群中的哪些候选人比其他人更接近解决方案，因为只有这样您才能从一代到下一代获得改进。当我有一个遗传算法在我的适应度函数中有一个强权重非连续分量时，我很难学到这一点。它支配了所有其他人，并且因为它是非连续的，所以没有逐渐向更大的适应度前进，因为在这方面几乎正确的候选人并不被认为比完全不正确的候选人更适合。

不幸的是，程序的正确性是完全不连续的。一个在 A 行因错误 X 停止的程序是否比在 B 行因错误 Y 停止的程序更好？您的程序可能距离正确只有一个字符，但仍会因错误而中止，而返回恒定硬编码结果的程序至少可以通过一项测试。

这甚至没有涉及代码本身在修改下不连续的问题......

于 2011-04-20T16:05:21.423 回答
9

嗯，这是很有可能的，@Jivlain 在他的（很好的）回答中正确地指出，遗传编程是您正在寻找的（而不是简单的遗传算法）。

遗传编程是一个尚未达到广泛受众的领域，部分原因是@MichaelBorgwardt 在他的回答中指出的一些复杂性。但那些只是复杂的事情，这是不可能做到的，这远非事实。对该主题的研究已经进行了 20 多年。

Andre Koza 是这方面的主要研究人员之一（看看他1992 年的工作），他早在 1996 年就证明了遗传编程如何在某些经典计算问题（例如用于元胞自动机同步的进化程序）上在某些情况下优于幼稚 GA ）。

这是 Koza 和 Poli 于 2003 年提供的一个很好的遗传编程教程。

对于最近的参考资料，您可能想看看遗传编程领域指南（2008 年）。

于 2011-04-25T14:29:55.157 回答
4

自从提出这个问题以来，遗传编程领域已经取得了一些进展，并且已经进行了一些额外的尝试，以在传统遗传编程的树结构之外的配置中进化代码。这里只是其中的几个：

  • PushGP - 旨在发展模块化功能，如人类编码器使用，该系统中的程序将所有变量和代码存储在不同的堆栈上（每个变量类型一个）。通过从堆栈中推送和弹出命令和数据来编写程序。
  • FINCH - 一个进化 Java 字节码的系统。这已被用于改进游戏代理。
  • 各种算法已经开始发展 C++ 代码，通常带有纠正编译器错误的步骤。这有好坏参半的结果，但并非完全没有希望。这是一个例子。
  • Avida - 代理使用非常简单的汇编代码演化程序（主要是布尔逻辑任务）的系统。基于较旧的（和不太通用的）Tierra。
于 2015-03-01T22:52:53.480 回答
1

语言不是问题。不管是什么语言，你都必须定义一些更高级别的突变，否则将需要永远学习。

例如，由于任何 Ruby 语言都可以根据文本字符串定义，因此您可以随机生成文本字符串并对其进行优化。最好只生成合法的 Ruby 程序。然而，这也需要永远。

如果您尝试构建一个排序程序并且您有“交换”、“移动”等高级操作，那么您将有更高的成功机会。

理论上，一群猴子在打字机上无限敲打，就能输出莎士比亚的全部作品。在实践中，这不是写文学的实用方法。仅仅因为遗传算法可以解决优化问题并不意味着它很容易，甚至不一定是一个好方法。

于 2011-04-20T16:03:40.183 回答
0

正如您所说，遗传算法的最大卖点是它们非常简单。他们没有最好的性能或数学背景，但即使你不知道如何解决你的问题，只要你能把它定义为一个优化问题，你就能把它变成一个 GA。

程序并不真正适合遗传算法，因为代码不是很好的染色体材料。我见过有人用（更简单的）机器代码而不是 Python 做了类似的事情（尽管它更像是一个生态系统模拟，然后是一个 GA 本身），如果你使用自动机 / LISP 或类似的东西来编码你的程序，你可能会有更好的运气那。

另一方面，考虑到 GA 的魅力，以及基本上每个看着他们的人都会问同样的问题，我很确定已经有人在某个地方尝试过——我只是不知道他们中是否有人成功。

于 2011-04-20T16:06:55.967 回答
0

祝你好运。

当然，您可以编写一个“突变”程序来读取程序并随机添加、删除或更改一些字符。然后你可以编译结果，看看输出是否比原来的程序好。（但是我们定义和衡量“更好”。）当然，99.9% 的结果将是编译错误：语法错误、未定义的变量等。当然，其余的大部分都是非常不正确的。

尝试一些非常简单的问题。比如说，从一个程序开始，它读取两个数字，将它们相加，然后输出总和。假设目标是一个读取三个数字并计算总和的程序。这样的程序有多长和多复杂当然取决于语言。假设我们有一些非常高级的语言，让我们只用一行代码就可以读取或写入一个数字。那么启动程序只有 4 行：

read x
read y
total=x+y
write total

达到预期目标的最简单的程序是这样的

read x
read y
read z
total=x+y+z
write total

所以通过随机变异，我们要添加“read z”和“+z”，包括空格和换行符，一共9个字符。让我们简化我们的变异程序，假设它总是准确插入 9 个随机字符，保证它们在正确的位置，并且它从 26 个字母加上 10 个数字加上 14 个特殊字符的字符集中进行选择 = 50 个字符。它会选择正确的 9 个字符的几率是多少？50^9 中的 1 = 2.0e15 中的 1。（好吧，如果不是“read z”和“+z”，而是插入“read w”和“+w”，程序就可以工作，但是我假设它神奇地插入了正确数量的字符，这很容易并且总是把它们插在正确的地方。所以我认为这个估计还是很慷慨的。）

2.0e15 中的 1 是一个很小的概率。即使程序每秒运行一千次，并且您可以快速测试输出，机会仍然只有每秒 2.0e12 中的 1 次，或每小时 5.4e8 中的 1 次，每天 2.3e7 中的 1 次。让它运行一年，成功的机会仍然只有 62,000 分之一。

即使是一个中等能力的程序员也应该能够在十分钟内做出这样的改变？

请注意，更改必须至少出现在正确的“数据包”中。也就是说，如果一个突变产生“reax z”，那离“read z”只有一个字符，但它仍然会产生编译错误，因此会失败。

同样添加“read z”但将计算更改为“total=x+y+w”是行不通的。根据语言的不同，您会得到未定义变量的错误，或者充其量它会有一些默认值，如零，并给出不正确的结果。

我想，你可以对增量解决方案进行理论化。也许一个突变添加了新的读取语句，然后一个未来的突变更新了计算。但如果没有计算，额外的阅读是毫无价值的。如何评估程序以确定额外的读取是“朝着正确方向迈出的一步”？我认为做到这一点的唯一方法是让智能体在每次突变后读取代码，看看变化是否朝着预期目标前进。如果你有一个聪明的设计师可以做到这一点，那一定意味着他知道期望的目标是什么以及如何实现它。在这一点上，只进行所需的更改而不是等待它随机发生会更有效率。

这是一个非常简单的程序，语言非常简单。大多数程序是什么，成百上千行，所有这些都必须协同工作。编写工作程序的任何随机过程的几率都是天文数字。

在一些非常专业的应用程序中，可能有一些方法可以做类似的事情，在这些应用程序中，您并不是真正进行随机突变，而是对解决方案的参数进行增量修改。就像，我们有一个公式，其中包含一些我们不知道其值的常数。我们知道对于一小部分输入的正确结果是什么。所以我们对常数进行随机更改，如果结果更接近正确答案，则从那里更改，如果不是，则返回之前的值。但即便如此，我认为进行随机更改很少有成效。尝试根据严格的公式更改常数可能会更有帮助，例如从 1000 开始更改，然后 100 和 10 等。

于 2011-04-20T17:31:27.870 回答
0

我只想给你一个建议。我不知道你会有多成功，但也许你可以尝试用基因编程进化出一个核心战争机器人。您的健身功能很简单：让机器人在游戏中竞争。你可以从众所周知的机器人开始，也许还有一些随机的机器人，然后等着看会发生什么。

于 2011-04-21T03:12:32.367 回答