什么是遗传编程？
我已经做了相当多的遗传algorithm的工作，相当成功，迄今为止忽视遗传编程。 据我所知，大多数程序仍然是由程序员写的，我很想知道什么是遗传编程？
我想到的一些可能的解释是：
- search空间太大，无法在噪声中find有用的节目
- 大多数真实的应用程序不能提供足够的数据来允许对这种空间进行适应性评估
- 将许多实际应用的功效降低到单一的适应性测量是困难的。 换句话说，写一个合适的适应度函数可能需要写与实际程序相同的工作量。
有任何想法吗？
这是我在自己的研究中一直在考虑的事情，我想说有很多原因：
-
GP领域的绝大多数研究集中在制作公式上，而不是大多数程序员制作的那种软件。 这个领域有很多计算机科学家，但是很less有人专注于制作你所期望的那种程序，所以在这方面的进展很慢。
-
LISP的使用过于重视，因为它可以产生好的树结构，这些结构很容易被操纵，而不幸的是必须的程序被忽略了，因为它们涉及到解决一些棘手的问题。 GP要被程序员认真对待，就必须制定必要的程序。
-
真正的程序包含循环结构，但循环很难在GP中实现，没有各种丑陋的约束来防止无限循环。
-
遗传编程不能很好地扩展。 对于一些小问题来说，使用一种可用的小语言就没有问题，但正如你在第一点中所说 – search空间变得非常快。
-
与人类程序员相比，GP可能非常慢。 然而，它是非常可并行的，所以可能会大幅受益，因为大量的处理器核心已成为常态。
另一个有效的答案是信任代码很难自动生成。 这是事实，但实际上，我怀疑这样做会产生多大的影响，因为GP首先无法制定正确的计划。
关于遗传编程的难点在于写一个好的评分函数：
-
评分函数必须正确判断algorithm是否具有所需的属性。 这比听起来更难 – 比写testing套要困难得多。 该algorithm可以适应你的评分函数的任何怪癖和优化。 试图发展
strcmp？ 你的algorithm可能会发现你的通过/失败testing用例的长度的math模式。 -
评分函数必须能够判断被测algorithm是否部分工作。 遗传编程依赖于“爬山”。 一个微小的有益突变需要导致分数的微小增量改善。 如果你的得分function只能输出真/假，那么你是随机search，而不是基因。
如果你尝试一下，你会发现基因编程是横向思维的终极目标：你的程序将倾向于用你没有想到的方式解决问题，其中大多数是意想不到的（对于严重的应用程序）可能无用。 一个着名的例子涉及使用基本电子元件演变振荡器的尝试。 它是在电路的简单性和输出是否振荡的基础上进行判断的。 研究人员确信这种方法很简单，但确实无法工作，但确实如此：它正在收集和放大环境中的无线电波。
编辑引用：
Graham-Rowe，邓肯 “无线电从电子汤中冒出来。” “新科学家”，第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
我知道我迟到了，但我只想提几点。 我有不可思议的好运与约翰·科扎（John Koza）在“遗传编程4”（Genetic Programming 4）一书中合作。
我们大多数人每天都在做的程序 – 连接graphics用户界面（GUI）事件，推动像素，数据库等等，肯定不是 GP想要build立的程序types。
约翰·柯萨（JohnKoza）对他的大约一百台机器（如果我没有记错的话）所做的就是寻找有趣问题的解决scheme（认为是NP-hard）。 这很令人伤心，但程序员日常工作中的大部分问题并不是很有趣或困难的问题，大多只是令人烦恼和费时。
本jackson所说的基因工程电子振荡器与科扎博士和团队实际所做的工作最接近。 GP系列书中有许多电路的例子。
汤姆·卡斯特在这里所说的强制性项目并不完全正确。 来自John和公司的这个开创性的例子就是天线的devise运行。 这几乎是一个3D绘图程序，像LOGO绘图语言的devise天线的命令。 它有moveto，linetotypes命令，用于在堆栈上推送和popupmatrix。 我刚才看到的GP包，jgap，有直接的支持：一个容器types的非终结符，可以包含void返回语句，然后在最后有一个返回语句。 我相信它甚至有一些像局部variables一样的东西，尽pipe我没有仔细看。
早期GP运行的原始LISPdevise是时不时的，这当然是真实的。 我认为，将GP运行的输出翻译成更多可用的代码是令人厌烦的。
TL; DR：GP并不是一个真正的自动编程系统。 这是一个自动化的发明系统。
我会说1和3。
特别是关于第3点，我想说的是，在大多数情况下，编写实际的程序要比提出一个合适的目标函数更容易 ， 并检查这导致了正确的还是可接受的解决scheme（你怎么知道从遗传编程得到的algorithm如预期的那样工作？）
关于第一点，我想说的是search空间的维度是无限的。
三件事：
- 正如安德烈所说 ，写一个足够的健身function是非常困难的。 这是testing驱动开发的最终版本。 你必须编写unit testing，提供100％覆盖尚未写入的程序。 即使如此，100％的覆盖面本身也不足以应付。 当我们解决了正式指定一个复杂系统所有方面的精确行为的问题，然后validation一个给定的程序满足这个规范的时候，那么我们可能会有一个机会。
- 遗传编程是非确定性的，更适合于生成近似的解决scheme，而不是精确的解决scheme。
- 遗传编程在应用于任何合理复杂的问题时，在计算上是非常昂贵的。 早在1999年， 遗传编程公司就在这个领域使用了一个1000节点的集群 。
GP不能快速解决创造适应度函数的人以外的新问题。 所以，目前只能用来解决我们已经知道如何解决的问题，但是由于search空间的原因，不能完全解决。 比如旅行推销员。 GA可以更快地解决这个问题。
原因其实很简单。 为了解决新的问题，您给GP的工具需要足够简单或足够完整，以使GPsearch空间成为真正的遗传学的真正模拟。
遗传规划和真正的遗传学一样，都受到与所有平台增长系统相同的增长模式的支配。 这意味着一个GP将会进展到一个点，在这个点上，核心的公用设施会碰到一个平台，然后平稳下来，然后花上很长的时间，才会蹒跚进入一个新的平台，build立一个新的平台。
这个亲进化的video展示了这些平台增长模式。 http://www.youtube.com/watch?v=mcAq9bmCeR0开发一只新手需要很长时间，一旦掌握了，另一只手变成新手，并迅速进入更多手的最佳范例。; （我应该提到，这个video最有可能使用GA，而不是GP，但遗传学是遗传学）
这与奇点理论中的逻辑完全相同。
但是这对于GP来说意味着它对于研究来说非常有用，而不是在程序中的实际应用。 除了一些简单的例外情况，其要求比遗传algorithm可以解决的要稍微深入些。 比如一些调度程序。 编程search空间非常小，以及解决这个问题所需的工具的理解程度，以及哪里可以有一个明确定义的适应度函数。
这只是因为它已经被certificate是理论上不可能的（至less对于正确的程序）。
让我们假设你有一个无限的计算能力，放弃search空间大小和慢度问题和其他'速度'的东西。 现在只有两个问题： – 生成的程序会停止吗？ – 如何确保生成的程序按照我希望的方式运行？
第一个问题是可计算性理论中的一个中心问题，被称为暂停问题 。 图灵在1936年certificate了这个问题对于所有的程序input对是不可判定的。 这意味着在某些情况下是可能的，但不是全部。 没有可以确定程序是否停止的自动化过程。 所以为此，你做不了多less;）
第二个问题涉及程序的正确性。 在遗传编程中，validation通常是通过示例值来完成的，它完全不构成任何正确的certificate。 这与unit testing相差无几，给出了很多例子，但不是没有一般的certificate。 例如，如果我编写一个质数检查器，只用3 5 7和11来testing，那么对于每个奇数都返回true的程序将通过testing。
更进一步的是使用自动化的certificate。 algorithm正确性的自动certificate实际上与math自动定理certificate密切相关。 您使用公理化系统描述您的程序，并尝试自动certificate您的陈述的正确性。 在这里，你又面临着强大的理论障碍，这就是哥德尔不完全性定理 。 这些定理说明了甚至对于甚至是非常简单的公理化系统，能够对自然数进行算术，没有能够certificate关于这些自然数的所有定理的algorithm（称为有效过程）。 具体而言，即使是简单的程序，也不能certificate其正确性。
即使没有经过validation的正确性，使用样本testing用例来validation遗传程序是非常容易过度专业化的现象，称为过度拟合机器学习。 也就是说，学习的程序在提供的testing用例上可以做得很好，但对其他一些input可能完全是弹道的。
也许大多数程序员是程序员，而不是计算机科学家？
遗传编程需要严肃的智慧。 您需要能够适当地解决问题，并且需要一个适当的问题来开始。 你需要知道足够的知道遗传algorithm是一种select。 而这个问题还没有一个众所周知的解决scheme。
并非所有的东西都需要花哨的algorithm 在世界上所有编写的代码中，做'标准'webapps，操作系统，设备编程，真的需要遗传algorithm吗？
当涉及到它时，大多数编程工作都致力于解决不需要复杂方法的简单问题。
我认为很大一部分原因是风险pipe理。 忍耐一下：当一个程序员坐下来写一个程序，他们至less有一些想法，要花多长时间，他们可以做什么。
当一个程序员坐下来编写一个程序来生成一个程序（使用遗传编程）时，不确定性就会发生，目前还不清楚这个过程需要多长时间，目前还不清楚最终程序有多好。
在其他地方也有不确定性：稍后调整程序或修复错误会有多容易？ 生成的代码几乎不可能debugging。
原始汤是可疑和不愉快的。 对于我的产品代码，我更喜欢智能devise。
我个人的看法是在大学GP研究几年之后，之后的领域是：GP未能成规模。
简单的健身function所代表的简单问题GP可以解决所有问题。 但是正如前面提到的那样，使用经典的方法来制定描述不断发展的strcmp或计算器甚至简单的文本编辑器的任务几乎是不可能的。
我确实喜欢GP健身function是完美的TDD的概念，尽pipe： – 也许一些聪明的头脑会想出一个更好的方式来指导模拟的进化，但有一天还没有发生。
我在GP目前正在进行一些“私人研究”的隐式适应function方面有一些希望。 我们将看到它会得到多远！
干杯，杰伊
有些项目解决了GP中的上述问题。 一个例子就是opencog MOSES
现在编程是以机器可读的方式定义精细的规范。 你告诉程序员你到底想要做什么以及结果应该如何。 它不再更多了。 这意味着，如果你想通过遗传编程来产生结果，你还是必须以适应度函数的forms来做这个机器可读的精细规范。 这将导致至less相同但可能更大的工作量。 所以它只是遗传程序devise的错误领域，这个领域是为了易于定义但难以达到的规范而提出的。
编辑：现在你可以说，在大多数项目中，这个精细的规范无论如何都是以testing的forms完成的。 我想说的遗传编程方法testing是不精确的方式来指定你的需求。 它们是基于示例而不是基于正式规范语言的编程。 遗传编程可能会产生适合testing用例的结果，并在新的input情况下在实际情况下performance错误。 因此，要获得一个规范级别的testing，就像使用编程语言的规范一样精确，您将需要大量的testing用例来处理每个可能的事件。 所以最后你会做比编程的东西更多的工作。
GP和GA，或者一般而言，演化algorithm更像是爱好。 它们不能用于实际应用，除非有例外。 原因是这些algorithm是基于随机性的。 没有确定的答案。
此外，这个领域充斥着次级研究工作，因为它比其他math密集的技术相比易于理解和实施。 所以学生们只是在一些工程或者科学应用中find一个优化的目标，而且你有一个新的工作 – 出版。
只需将其会议的发起人与其他AI / ML /优化会议的发起人进行比较。 对于他们在工业中的“当前”重要性将是清楚的。
但它是一个研究领域，它决定了它的工作。 目前它只是一个爱好！
