遗传编程和搜索算法

Question

遗传编程当前是否能够将一种类型的搜索算法进化成另一种类型的搜索算法？例如，是否曾经有实验从快速排序（参见http://en.wikipedia.org/wiki/Sorting_algorithm）中繁殖/突变出冒泡排序。

- Josh Reuben

---

你可能想看一下这个问题，讨论遗传编程可以或不能做什么-->https://dev59.com/sm025IYBdhLWcg3w6KOO - JohnIdol

Answer 1

你可能需要了解80年代W. Daniel Hillis的工作。他花费了大量时间通过遗传编程创建排序网络。虽然他更关心解决对一定数量对象进行排序的问题（16个对象的排序网络已成为近十年来重要的学术难题），但如果你真的对基因排序算法感兴趣，熟悉他的工作是一个好主意。

在演化用于排序任意长度列表的算法过程中，你可能也需要了解协同演化的概念。我以前构建过一个协同演化系统，其中一个遗传算法演化排序算法，而另一个GA则开发未排序的数字列表。排序器的适应度是其准确性（如果100％准确，则加上较少比较的奖励），而列表生成器的适应度是排序算法在对其列表进行排序时出现错误的次数。

回答你具体的问题，即是否曾经从快速排序演化出冒泡排序，我必须说我非常怀疑，除非程序员的适应度函数既非常特定又不明智。是的，冒泡排序非常简单，因此可能会找到一个适应度函数是准确性加程序大小的GP最终找到冒泡排序。但是，当决定运行时间的是后者时，为什么程序员会选择大小而不是比较次数作为适应度函数呢？

通过询问GP是否可以将一个算法演化成另一个算法，我想知道你是否完全清楚GP的概念。理想情况下，每个唯一的染色体定义了一个独特的排序方法。一个由200个染色体组成的群体代表着200种不同的算法。是的，快速排序和冒泡排序可能在其中某处，但还有198种其他未命名的方法。

- Sniggerfardimungus

Answer 2

没有理由说遗传编程无法演化出两种算法中的任何一种。我不确定将其中一种算法“演化为”另一种是否有意义。遗传编程将简单地演化一个程序，使其逐渐接近您定义的适应函数。

如果您的适应函数只考虑排序的正确性（并且假设您拥有适合遗传编程使用的适当构建块），那么它很可能会演化出BubbleSort和QuickSort。如果您还将效率作为适应度的衡量标准，那么这可能会影响确定哪个算法是更好的解决方案。

您可以使用QuickSort等进行遗传编程的种子，并且如果您有适当的适应函数，它肯定最终可以想出BubbleSort - 但是它也可能想出比QuickSort更适合的任何其他解决方案。

现在，遗传编程引擎完成这种演化需要多长时间，这是另一个问题...

- G__

Answer 3

我不知道有这样的算法存在，而且你在示例中提出的特定方向似乎不太可能实现；这需要一种奇怪的适应性函数，因为冒泡排序在大多数情况下都比快速排序更差。虽然这种情况并非不可想象，但通常情况下，一旦你掌握了一个被广泛理解的算法，它已经相当适合使用了——转向另一个算法可能需要经历一些更糟糕的选择。

对于大多数搜索策略来说，陷入局部最小值是一个常见问题。

- Charlie Martin

---

Charlie，只是好奇，你会如何繁殖下一代？我似乎无法理解交叉<something>排序和<something-else>排序来创建新算法的事实。排序算法在其整个任务处理方法上有所不同，而不仅仅是可以玩弄的参数。 - pnt

这确实是关键问题。请记住，遗传算法的核心是通过进行大量随机变化并寻找适应度函数中“更好”的一个来取得进展。生物进化也面临同样的问题——你可能从鱼进化成鸟，但任何让你更接近鸟的变化都会在繁殖前淹死。 - Charlie Martin

另一个很好的例子是熊猫：它非常适合两件事--吃竹子和可爱。安静的竹林生态系统正在消失，因此它们处于濒危状态。另一方面，也许正是“可爱”这个特征确保了其持续生存。 - Charlie Martin

是的，但遗传算法如何在排序算法中进行随机更改呢？实际上，可以设置的属性并不多，并且它们在不同的算法中差异很大，因此不能采用统一的方法，通过使用第一个算法的属性“A”和第二个算法的属性“B”来创建一个新算法。您可以拥有一个池并基于性能评分函数从中选择，但是如何在语义上和纯语法上将它们组合成新的品种呢？ - pnt

啊，但我是一个理论家，那是一个实现问题。说真的，你可以只将程序字符串作为指令或甚至ASCII文本进行随机更改；只是要花很长时间才能得到有用的结果。没有经过深思熟虑，我会考虑使用排序网络作为基础的“密码子”http://en.wikipedia.org/wiki/Sorting_network。至少这样你每次都会得到一个“排序算法”，即使它不是特别高效或有用。 - Charlie Martin

但这仍然是一个真正的问题 - GA通常是一种爬山算法。如果您已经拥有一个好的算法，比如快速排序，那么任何随机突变都很可能比其突变后代“不适合”。 - Charlie Martin