logo标签列表

遗传编程的瓶颈是什么？

algorithmgenetic-programmingevolutionary-algorithm
58

我已经成功地使用遗传算法进行了相当多的工作，但到目前为止忽略了遗传编程。据我所知，大多数程序仍然是由程序员编写的，我很好奇是什么阻碍了遗传编程的发展？

我想到了一些可能的解释：

  1. 搜索空间太大了，在噪声中找到有用的程序很困难。
  2. 大多数实际应用程序无法提供足够的数据来评估这样的空间。
  3. 很难将许多实际应用的有效性归纳为单一的适应度度量。换句话说，编写合适的适应度函数可能需要与编写实际程序相同的工作量。

你有任何想法吗？

这个问题应该在人工智能堆栈交换上提问，但不幸的是，9-10年前它还不存在。 - nbro
14个回答
40

我在自己的研究中一直在考虑这个问题，我想说有很多原因：

  1. GP领域中绝大部分研究都集中在生成公式上，而不是大多数程序员所生成的软件类型。该领域有很多计算机科学家，但很少有人专注于生成预期的程序类型，因此在该领域的进展缓慢。

  2. 过于强调使用LISP，因为它可以生成易于操作的树形结构，而不幸的是命令式程序被忽视了，因为它们涉及解决一些棘手的问题。要让程序员认真对待GP，它必须生成命令式程序。

  3. 真实程序包含循环结构，但循环在GP中难以实现，需要采用各种丑陋的约束条件以防止无限循环。

  4. 遗传编程不具有可扩展性。对于小问题和较小的可用语言来说，它很好，但正如您在第一点中提到的，搜索空间很快变得太大。

  5. 与人类程序员相比，GP可能会非常慢。但它非常可并行化，因此随着大量处理器核心成为常态，它很可能会获得实质性的好处。

另一个有效的答案是很难相信代码已经自动生成。这是正确的，但实际上我怀疑这并没有太大的影响，因为GP一开始就无法生成正确的程序类型。

1
在我的经验中，大多数程序员制作的是数据输入/输出/计算应用程序，其中所有逻辑都相对简单。我认为软件开发的主要瓶颈（至少是商业软件开发）与寻找特定任务更有效的算法无关。点＃1加1。 - John Bledsoe
26
遗传编程的难点在于编写一个良好的得分函数：
  • 得分函数必须正确评估算法是否具有所需的特性。这比听起来要困难得多——比编写测试套件要困难得多。算法可能会适应得分函数的任何怪癖并优化它。试图进化strcmp？你的算法可能会发现你的通过/失败测试用例长度的数学模式。
  • 得分函数必须能够判断被测试的算法是否部分工作。遗传编程依赖于“攀岩”。微小的有益变异需要导致得分的微小增量改进。如果你的得分函数只能输出真/假，则您是在随机搜索，而不是在遗传。

如果你亲自尝试一下，你会发现遗传编程是最终的横向思维：你的程序倾向于以你没有想到的每种方式解决问题，其中大部分都出乎意料，（对于严肃的应用）可能是无用的。有一个著名案例试图使用基本电子元件进化振荡器。它根据电路的简单性和输出的振荡来评估。它产生了如此简单的东西，研究人员确信它不可能工作，但它确实起作用：它正在从环境中接收和放大无线电波。

编辑引用：

 

Graham-Rowe，Duncan。 “Radio emerges from the electronic soup。”《New Scientist》，vol.175，no.2358，p.19（2002年8月31日）。可在http://www.newscientist.com/news/news.jsp?id=ns99992732上在线获取。

然而，该链接现在似乎已经损坏了。

新链接是http://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.html

点赞，因为这是将GA应用于实际问题的好例子。它指引了GA在许多领域中的应用方向。 - user922475
10

我知道我来晚了，但我想指出几点。我非常幸运地与John Koza合作他的《遗传编程4》书。

我们大多数人日常工作中所做的编程——连接GUI事件、推动像素、数据库等等——绝对不是GP旨在构建的类型。

John Koza用他的一百台机器群（如果我没记错的话！）寻找有趣问题的解决方案（想想NP难度）。可悲的是，我们程序员每天处理的大多数问题都不是很有趣或困难的问题，大多数只是令人恼怒和耗费时间的问题。

Ben Jackson关于基因工程电子振荡器的说法是这个主题中最接近Dr. Koza和团队实际工作的事情。GP系列书中有许多电路的例子。

Tom Castle在这里提到的命令式程序并不完全正确。 John和公司的开创性例子是天线设计。它几乎是一个三维绘图程序，具有诸如LOGO绘图语言的命令，用于设计天线。它有moveto、lineto类型的命令，用于在栈上推送和弹出矩阵。我上周看过的GP软件包jgap直接支持：一个可以包含void返回语句的容器类型非终端，然后在结尾有一个返回语句。我相信它甚至有类似本地变量的东西，虽然我没有仔细看。

早期GP运行围绕的原始LISP设计有时确实很痛苦，这当然是真的。将GP运行的输出转换为更可用代码的任务可能是一种成年礼。

简而言之：GP实际上并不是自动编程系统。它是自动发明系统。

猜测一个“刚刚”的百头贝奥武夫是最初基于DEC-Alpha的小型原型。他的主要研究任务在一个更大的玩具上演变，即 ~1000 双 CPU 无磁盘机器按照层次结构连接成 GNU/Beowulf 簇。无论如何，“与J.R.Koza一起工作肯定是一个很棒的时光”，很酷能找到时间在这里提到你的个人经验。感谢@fletch。 - user3666197
5
我认为第一点和第三点都很重要。
特别是对于第三点，我认为在大多数情况下，编写实际程序甚至比构思适当的目标函数并检查它是否导致正确或可接受的解决方案更容易（你怎么知道从遗传编程中得出的算法是否按预期工作？）。
关于第一点，我认为搜索空间具有无限数量的维度。
好的观点，尽管我认为只有在将程序视为潜在无限长时，它才具有无限维度。如果我们将程序视为100位二进制字符串，则有2^100个程序，你可以说有100个维度。当然，我们可能不知道程序会有多大。 - zenna
4

这是因为它已被证明在理论上是不可能的（至少对于正确的程序）。

假设您拥有无限的计算能力，放弃搜索空间大小、速度等其他“速度”问题。现在只面临两个问题： - 生成的程序是否会停止？ - 如何确保生成的程序按照我想要的方式运行？

第一个问题是可计算性理论中的一个核心问题，被称为停机问题。图灵在1936年证明了该问题对于所有程序输入对都是不可判定的。 这意味着在某些情况下可能是可以实现的，但并非所有情况都可以。没有自动化过程可以确定程序是否停止。 对于这个问题，您无能为力;)

与程序正确性相关的第二个问题。在遗传编程中，通常通过示例值进行验证，这根本不构成任何正确性证明。 这类似于单元测试，只对一些示例给出正确结果，但是不能提供一般的证明。例如，如果我编写一个素数检查器，并仅使用3、5、7和11进行测试，则对于每个奇数返回true的程序将通过测试。

进一步的做法是使用自动化证明。算法正确性的自动化证明实际上与数学自动定理证明密切相关。您可以使用公理化系统描述程序，并尝试自动证明语句的正确性。
在这里，您再次面临强大的理论障碍，即哥德尔不完备定理。这些定理表明，即使对于能够在自然数上执行算术运算的非常简单的公理化系统，也没有算法（称为有效过程）能够证明关于这些自然数的所有定理。
具体来说，这意味着即使对于简单的程序，您也将无法证明其正确性。
即使没有经过验证的正确性，使用样本测试用例来验证遗传程序非常容易出现过度特化，这种现象在机器学习中被称为过拟合。也就是说，学习到的程序在提供的测试用例上表现良好，但可能对其他输入完全失控。
这个答案经常被踩，欢迎添加有建设性的评论！ - Julien
停机问题是一个理论性问题。一个在实际超时时间内无法停止的程序（停机解决方案:P）可能没有太大用处。今天使用的大量软件远非任何人所衡量的“正确”。如果GP能够比人更便宜地演化软件，并达到相同或更好的质量，那么它可能会获得更广泛的关注。目前，纯理论的正确性和演化方法过于困难，就像许多AI领域一样。与“软件工程”视角相结合的大数据方法对机器学习的发展可能会有所帮助。 - Brendan Cody-Kenny
这个问题有点老了，但我认为你回答的主要问题在于你把它表述成了事实：“是因为”，而实际上它只是一个猜测（在我看来并不差）。当然，你提出了一些事实，但问题是“为什么它没有流行起来”？这可能是因为存在这些缺陷，但这些缺陷也同样适用于普通编程，尽管如此，普通编程仍然做得很好。 - Mike Wise
我认为这不是一个猜想，而是在大多数编程情况下都成立的事实。请看接受的答案中无限循环的问题，这只是停机问题的一个例子。无论你喜不喜欢，在计算机科学理论中，就像物理学中的自然规律一样，总会告诉你真相。与普通编程的区别在于，你不是随机生成程序，而是（应该）遵循某种合理的方法来完成编程任务。在我看来，形式化方法比遗传编程更实用。 - Julien
4

三件事情：

  1. 正如安德烈所说，编写足够的适应度函数非常困难。这是测试驱动开发的终极版本。您必须编写单元测试，以提供尚未编写的程序的100％覆盖率。即使如此，仅有100％的覆盖率可能还不足够。当我们解决了正式指定复杂系统所有方面的精确行为，并验证给定程序是否符合该规范的问题时，我们可能才有机会。
  2. 遗传编程是非确定性的，更适合生成近似解而不是精确解。
  3. 将遗传编程应用于任何具有合理复杂性的问题都需要大量计算资源。早在1999年，Genetic Programming Inc使用了一个由1000个节点组成的集群来进行该领域的工作。
4
GP无法快速解决那些超出创建适应函数人员知识范围的新问题。因此，它目前只能用于解决我们已经知道如何解决但由于搜索空间而不能完全解决的问题，例如旅行商问题。这个问题可以使用GA更快地解决。
原因其实很简单。要解决新问题，给GP的工具必须足够简单或完整，使得GP的搜索空间成为真正的基因模拟。
遗传编程和真正的基因一样，受到所有平台增长系统相同的生长模式的影响。这意味着GP将进展到一个核心实用程序达到平台的点，然后水平稳定，并且在跌倒到新典范以建立新平台之前需要很长时间。
这个进化视频说明了这些平台增长模式。 http://www.youtube.com/watch?v=mcAq9bmCeR0 开发一个新手需要很长时间，一旦完成后，额外的手就成为新事物并迅速发展成更多手的最佳示例。（我应该提到，这个视频最可能使用GA而不是GP，但遗传是遗传）
这与奇点理论的相同逻辑有关。
但这对GP意味着它几乎只适用于研究，而不适用于程序内的实际应用。有一些简单的例外情况，要求比GA稍微深入一些。例如一些调度程序，在那里编程搜索空间相当小，需要解决它的工具已经被充分理解，并且可以定义一个明确定义的适应函数。
2
也许大多数程序员只是程序员，而不是计算机科学家？
遗传编程需要严谨的智力。您需要适当地分解问题，并需要一个适当的问题来开始。您需要了解足够的知识以知道遗传算法是一种选择。并且该问题不能已经有一个众所周知的解决方案。
并非所有东西都需要高端算法。在全球编写的所有代码中，“标准” Web 应用程序、操作系统和设备编程是否真的需要遗传算法呢？
而当真正需要时，大部分编程工作都致力于解决简单问题，而不需要复杂的方法。
无论这是否属实，该陈述仍然表明存在计算机科学家，因此并没有真正回答问题。 - Kendrick
@kendrick，我认为至少在修辞上是这样的。如果有什么被阻止了，那是为什么呢？是因为没有足够多的人知道如何做吗？ - hvgotcodes
我同意你的观点。我的看法是，计算机科学领域已经有足够多的人在工作，如果这个领域足够有趣和/或者应用资源的价值被认为足够高，那么可以投入更多的资源。 - Kendrick
2
我认为其中一个重要原因是风险管理。请耐心听我解释：当程序员开始编写程序时，他们至少有一些想法，知道需要多长时间以及能做些什么。
相反，当程序员开始编写生成程序的程序（使用遗传编程），不确定性会大大增加：不清楚这个过程需要多长时间，也不清楚最终程序的质量如何。
还有其他方面的不确定性：调整程序或修复错误会有多容易？生成的代码可能难以调试。
1

原始汤看起来可疑又不可口。在我的生产代码里，我更喜欢智能设计。

1
我想知道是否有人成功地使用遗传算法/遗传规划来生成高质量的用户界面？例如使用平均任务成功率、粘性指数和访客转化率等指标。 - DampeS8N
有趣的想法，dampe。我认为这是遗传算法可以解决的问题，但大部分工作必须由程序员完成，遗传算法可能只是改变元素的位置或大小。如果您可以使用遗传编程从头编写HTML / CSS，那将是一件了不起的事情。 - zenna
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接