遗传算法生成代码

Question

进化编程似乎是解决许多优化问题的好方法.这个想法非常简单,实施不会产生问题.

我想知道是否有任何方法可以进化创建ruby/python脚本(或任何其他语言)的程序？

这个想法很简单:

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

但仍然存在一些问题:

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

可生成的程序示例:

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

如果有任何尝试创建此类算法,我会很高兴看到任何链接/来源.

Answer 1

如果你确定要这样做,你需要遗传编程,而不是遗传算法.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)
  )
)  

作为您的适应度函数,您将使用它与真实解决方案的接近程度.其中有一个问题,你必须在传统上计算*.然后有一些东西将其翻译成代码(您选择的语言).请注意,由于你在那里有一个潜在的无限循环,你将不得不在一段时间后切断执行(没有办法解决暂停问题),它可能无法工作.哪里哪里.另请注意,我提供的代码将尝试除以零.

*有很多方法,但通常不是很远.

Answer 2

它可以完成,但对于大多数类型的应用程序非常糟糕.

遗传算法仅在适应度函数是连续的时才起作用,即您可以确定当前群体中哪些候选者比其他候选者更接近解决方案,因为只有这样,您才能从一代到下一代获得改进.当我在健身功能中使用一个强加权非连续分量的遗传算法时,我学到了很多.它主宰了所有其他人,并且因为它是不连续的,所以没有逐步向更大的适应度发展,因为在这方面几乎正确的候选人不被认为比完全不正确的候选人更合适.

不幸的是,程序的正确性是完全不连续的.A行上的错误X停止的程序是否比停在B行的错误Y的程序更好？你的程序可能是一个字符远离正确,并仍然中止错误,而返回恒定硬编码结果的程序至少可以通过一个测试.

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

Answer 3

嗯,这是非常可能的,@ Jivlain在他的(好的)答案中正确地指出遗传编程是你正在寻找的(而不是简单的遗传算法).

遗传编程是一个尚未达到广泛受众的领域,部分原因是由于迈克尔·博格沃德在答案中指出的一些复杂因素.但这些仅仅是并发症,这是不可能做到的.关于该主题的研究已经持续了20多年.

安德烈讲座是关于这方面的主要研究人员(看看他的一个1992年的工作),他证明了早在1996年在某些情况下编程如何基因可以超越天真赤霉素对一些经典的计算问题(如演进方案胞自动同步).

这是来自Koza和Poli 2003年的一个很好的遗传编程教程.

对于最近的参考,您可能想看看遗传编程的野外指南(2008).

Answer 4

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

• PushGP - 设计的目标是像人类编码员一样发展模块化功能，该系统中的程序将所有变量和代码存储在不同的堆栈上（每种变量类型一个）。程序是通过从堆栈中压入和弹出命令和数据来编写的。
• FINCH - 一个演化 Java 字节码的系统。这对于进化游戏代理起到了巨大的作用。
• 各种算法已经开始改进 C++ 代码，通常会包含纠正编译器错误的步骤。其结果好坏参半，但并非完全没有希望。这是一个例子。
• Avida - 一个代理使用非常简单的汇编代码演化程序（主要是布尔逻辑任务）的系统。基于较旧的（且通用性较差）Tierra。