58

我已经非常成功地完成了大量关于遗传算法的工作，但迄今为止忽略了遗传编程。据我所知，大多数程序仍然由程序员编写，我很想知道是什么阻碍了基因编程？

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

  1. 搜索空间太大，无法在噪音中找到有用的程序
  2. 大多数实际应用程序无法提供足够的数据来对此类空间进行适应性评估。
  3. 很难将许多实际应用程序的功效降低到单一的适应度度量。换句话说，编写一个合适的适应度函数可能需要与编写实际程序相同的工作量。

有任何想法吗？

4

14 回答 14

40

这是我在自己的研究中一直在考虑的事情，我想说有很多原因：

  1. GP 领域的绝大多数研究都集中在生成公式，而不是大多数程序员开发的那种软件。该领域有很多计算机科学家，但很少有人专注于制作您所期望的那种程序，因此该领域的进展缓慢。

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

  3. 真实的程序包含循环结构，但是如果没有各种丑陋的约束来防止无限循环，循环很难在 GP 中实现。

  4. 遗传编程不能很好地扩展。对于小问题，可用语言很少，但正如您在第一点中所说的那样 - 搜索空间很快就会变得太大。

  5. 与人类程序员相比，GP 可能非常慢。然而，它非常可并行化，因此随着更多处理器内核成为常态，它可能会受益匪浅。

另一个有效的答案是很难相信代码已经自动生成。这是真的，但在实践中我怀疑这会产生多大的影响，因为 GP 一开始就无法产生正确的程序。

于 2010-12-07T20:00:06.613 回答
25

遗传编程的难点在于编写一个好的评分函数：

  • 评分函数必须正确判断算法是否具有所需的属性。这比听起来要难——比编写测试套件要困难得多。该算法可能会适应您评分函数的任何怪癖并对其进行优化。试图进化strcmp？相反，您的算法可能会发现通过/失败测试用例长度的数学模式。

  • 评分功能必须能够判断被测算法是否部分有效。基因编程依赖于“爬山”。一个微小的有益突变需要引起分数的微小增量改进。如果您的评分函数只能输出真/假，那么您是在随机搜索，而不是从基因上搜索。

如果您尝试一下，您会发现遗传编程是横向思维的终极：您的程序将倾向于以您没有想到的各种方式解决问题，其中大多数是出乎意料的并且（对于严肃的应用程序）可能无用。一个著名的案例涉及使用基本电子元件发展振荡器的尝试。判断电路是否简单，输出是否有振荡。它产生了一些如此简单的东西，研究人员确信它无法工作，但它确实做到了：它从环境中拾取和放大无线电波。

编辑引用：

格雷厄姆-罗，邓肯。“收音机从电子汤中冒出来。” 《新科学家》，第 175 卷，第 2358 期，第 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

于 2010-12-07T19:32:32.713 回答
9

我知道我参加这个聚会迟到了，但我只想说几点。我有幸与 John Koza 合作编写他的《Genetic Programming 4》一书。

我们大多数人每天都在做的那种编程——连接 GUI 事件、推送像素、数据库等，肯定不是GP 旨在构建的程序类型。

John Koza 用他的大约一百台机器（如果我没记错的话！）的集群所做的是寻找有趣问题的解决方案（想想 NP-hard）。可悲的是，我们程序员每天处理的大多数问题都不是非常有趣或困难的问题，大多只是烦人且耗时。

Ben Jackson 所说的基因工程电子振荡器是该线程中最接近 Koza 博士和团队实际所做的事情。GP系列书籍中有许多电路示例。

Tom Castle 在这里所说的关于命令式程序的内容并不完全正确。约翰和公司的开创性例子是天线设计运行。它几乎是一个 3D 绘图程序，带有诸如设计天线的 LOGO 绘图语言之类的命令。它具有 moveto、lineto 类型的命令，用于在堆栈上推送和弹出矩阵。我上周刚看的 GP 包 jgap 有直接支持：一个容器类型非终端，可以包含 void return 语句，然后在末尾有一个 return 语句。我相信它甚至有类似局部变量的东西，尽管我没有仔细看。

早期 GP 所围绕的原始 LISP 设计有时会让人感到痛苦，这当然是真的。我认为对于将 GP 运行的输出转换为更可用的代码感到恼火，这是一种通过仪式。

TL;DR: GP 并不是真正的自动编程系统。这是一个自动化的发明系统。

于 2013-01-29T08:51:46.497 回答
5

我会说 1 和 3。

特别是关于第 3 点，我想说的是，在大多数情况下，编写实际程序比提出合适的目标函数并检查这是否导致正确或可接受的解决方案更容易（你怎么知道源自遗传编程的算法按预期工作？）

关于第 1 点，我会说搜索空间有无限个维度。

于 2010-12-07T19:33:59.047 回答
4

三件事：

  1. 正如Andre 所说，编写一个足够的适应度函数非常困难。这是测试驱动开发的终极版本。您必须编写单元测试来提供 100% 覆盖尚未编写的程序。即便如此，100% 的覆盖率本身也不太可能足够。当我们解决了正式指定复杂系统所有方面的精确行为的问题，然后验证给定程序是否满足该规范时，我们可能会有机会。
  2. 遗传编程是非确定性的，更适合生成近似解而不是精确解。
  3. 遗传编程，当应用于任何具有合理复杂性的问题时，计算成本非常高。早在 1999 年，Genetic Programming Inc 就在使用 1,000 个节点的集群进行该领域的工作。
于 2010-12-07T19:47:37.633 回答
4

GP 无法快速解决超出创建适应度函数的人的知识范围的新问题。因此，它目前只能用于解决我们已经知道如何解决的问题，但由于搜索空间的原因，不能完全解决。比如旅行推销员。这可以通过 GA 更快地解决。

原因其实很简单。为了解决新问题，你给 GP 的工具需要足够简单或足够完整，以使 GP 搜索空间成为真正的遗传学模拟。

遗传编程与真正的遗传学一样，受制于与所有平台增长系统相同的增长模式。这意味着 GP 将发展到包括核心实用程序在内的平台，它会趋于平稳，然后需要很长时间才能偶然发现新的范式以建立新的平台。

这段支持进化的视频说明了这些平台增长模式。 http://www.youtube.com/watch?v=mcAq9bmCeR0 开发新手需要很长时间，一旦开发，额外的手就会变成新事物并迅速发展为更多手的最佳示例。（我应该提一下，这个视频很可能使用的是 GA，而不是 GP，但遗传学就是遗传学）

这与奇点理论中的逻辑相同，顺便说一句。

但这对 GP 来说意味着它几乎只对研究有用，而不是在程序中的实际应用。除了一些简单的例外，这些要求比 GA 可以解决的更深入一些。比如一些调度程序。编程搜索空间非常小，解决它所需的工具很好理解，并且可以有明确定义的适应度函数。

于 2010-12-08T12:31:22.590 回答
4

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

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

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

第二个问题与程序正确性有关。在遗传编程中，通常通过示例值进行验证，这些示例值根本不构成任何正确性证明。这可与单元测试相媲美，给出了许多示例，但并非没有一般性证明。例如，如果我编写一个素数检查器，只用 3 5 7 和 11 对其进行测试，那么一个对每个奇数都返回 true 的程序将通过测试。

更进一步将是使用自动证明。算法正确性的自动证明实际上与数学自动定理证明密切相关。您使用公理化系统描述您的程序，并尝试自动证明您的陈述的正确性。在这里，您再次面临强大的理论障碍，即哥德尔不完备定理。这些定理指出，即使是非常简单的公理化系统，能够对自然数执行算术运算，也没有算法（称为有效过程）能够证明有关这些自然数的所有定理。具体来说，这意味着即使是简单的程序，您也无法证明其正确性。

即使没有经过验证的正确性，使用样本测试用例来验证遗传程序也很容易出现过度专业化，这种现象在机器学习中被称为过度拟合。也就是说，学习的程序在提供的测试用例上会做得很好，但对于其他一些输入可能会完全弹道。

于 2013-02-17T11:50:22.660 回答
2

也许大多数程序员都是程序员，而不是计算机科学家？

基因编程需要认真的智慧。您需要能够适当地分解问题，并且需要从适当的问题开始。而且您需要足够了解才能知道遗传算法是一种选择。并且问题需要没有一个众所周知的解决方案。

并非一切都需要一个花哨的算法。在世界上编写的所有代码中，“标准”网络应用、操作系统、设备编程真的需要遗传算法吗？

归根结底，大多数编程工作都致力于解决不需要复杂方法的简单问题。

于 2010-12-07T19:12:46.330 回答
2

我认为很大一部分原因是风险管理。请耐心等待：当程序员坐下来编写程序时，他们至少知道需要多长时间以及可以做什么。

相反，当程序员坐下来编写将生成程序的程序（使用基因编程）时，不确定性会突飞猛进：不清楚这个过程需要多长时间，也不清楚最终程序能有多好。

其他地方也存在不确定性：后期调整程序，或者修复bug，会有多容易？生成的代码几乎无法调试。

于 2010-12-07T19:29:52.010 回答
1

原始汤是可疑的和令人反胃的。对于我的生产代码，我更喜欢智能设计。

于 2010-12-08T19:47:52.210 回答
1

在大学进行了几年的 GP 研究并随后关注该领域后，我的个人观点： GP 无法扩展。

简单的适应度函数代表的简单问题 GP 都可以解决。但如前所述 - 使用经典方法几乎不可能制定一个描述进化 strcmp 或计算器甚至简单文本编辑器任务的适应度函数。

我确实喜欢 GP 适应度函数是完美的 TDD 的概念，虽然 :-) 也许有聪明的人有一天会想出一种更好的方法来指导模拟进化，但这还没有发生。

在我目前正在进行一些“私人研究”的隐式适应度函数领域，我对 GP 抱有一些希望。我们会看到它会走多远！

干杯，杰伊

于 2011-12-11T12:23:11.983 回答
1

GP中有一些项目解决了上述问题。一个例子是 opencog MOSES

于 2013-10-12T07:47:49.603 回答
0

如今，编程正在以机器可读的方式定义精细规范。你告诉程序你想要它做什么以及结果应该是什么样子。它已经不多了。这意味着如果您想通过例如遗传编程来生成结果，您仍然必须以适应度函数的形式进行这种机器可读的精细规范。这将导致至少相同但可能更大的工作量。所以它只是遗传编程的错误领域，它是为易于定义但难以达到规范的问题而设计的。

编辑：您现在可以说，在大多数项目中，这个精细的规范无论如何都是以测试的形式完成的。我会说，对于基因编程方法，测试是不精确地指定您的需求的方式。它们是基于示例的，不像基于正式规范语言的编程。遗传编程可能会产生适合测试用例的结果，并在具有新输入的实际情况下表现错误。因此，要获得与使用编程语言的规范一样精确的测试规范级别，您将需要针对每种可能性的大量测试用例。所以最后你会做比编程更多的工作。

于 2012-03-11T10:56:29.690 回答
0

GP 和 GA，或者一般来说进化算法更像是爱好。它们不用于现实生活中的应用程序，除非有例外。原因是这些算法是基于随机性的。没有把握得到一个好的答案。

此外，该领域充斥着低于标准的研究工作，因为与其他数学密集型技术相比，它易于理解和实施。所以学生们只要找到一个目标来优化一些工程或科学应用，你就有了一个新的工作——出版。

只需将其会议的赞助商与其他 AI/ML/优化会议的赞助商进行比较。它们在工业中的“当前”重要性将一目了然。

但它是一个研究领域，我们要让它发挥作用。目前只是一种爱好！

于 2016-11-17T11:33:05.957 回答