algorithm - 遗传编程和搜索算法

Question

遗传编程目前是否能够将一种搜索算法演变为另一种搜索算法？例如，是否有任何实验曾经从 QuickSort 培育/变异 BubbleSort（参见http://en.wikipedia.org/wiki/Sorting_algorithm）

Answer 1

您可能想看看 80 年代 W. Daniel Hillis 的作品。他花了很多时间通过基因编程创建分类网络。虽然他对解决对恒定数量对象进行排序的问题更感兴趣（近十年来，16 对象排序网络一直是一个主要的学术问题），但如果你是对遗传排序算法非常感兴趣。

在对任意长度的列表进行排序的算法的演变过程中，您可能还想熟悉协同进化的概念。我已经建立了一个协同进化系统，之前的重点是让一个遗传算法进化排序算法，而另一个 GA 开发未排序的数字列表。排序器的适应度是它的准确度（如果它是 100% 准确，加上较少比较的奖励），列表生成器的适应度是排序算法在对其列表进行排序时产生的错误数。

要回答您关于气泡是否曾经从快速进化而来的具体问题，我不得不说我会严重怀疑它，除非程序员的适应度函数既非常具体又不明智。是的，气泡很简单，所以也许一个适应度函数是准确性加程序大小的 GP 最终会找到气泡。但是，为什么程序员会选择大小而不是比较次数作为适应度函数，因为后者决定了运行时间？

通过询问 GP 是否可以将一种算法演变成另一种算法，我想知道您是否完全清楚 GP 是什么。理想情况下，每条独特的染色体定义一个独特的排序。200 条染色体的种群代表 200 种不同的算法。是的，quick 和 bubble 可能存在于某个地方，但其他 198 种可能未命名的方法也是如此。

Answer 2

没有理由说 GP 不能进化，例如任何一种算法。我不确定考虑将一个“演变成”另一个是否真的有意义。GP 将简单地进化出一个越来越接近您定义的适应度函数的程序。

如果你的适应度函数只关注排序的正确性（并假设你有合适的构建块供你的 GP 使用），那么它很可能会同时进化 BubbleSort 和 QuickSort。如果您还将效率作为适合度的衡量标准，那么这可能会影响其中哪些将被确定为更好的解决方案。

您可以使用例如 QuickSort 为 GP 播种，如果您有适当的适应度函数，它肯定最终会提出 BubbleSort - 但它也可以提出比 QuickSort 更合适的任何东西。

现在 GP 引擎需要多长时间来进行这种演变是另一个问题......

Answer 3

我不知道，您在示例中建议的特定方向似乎不太可能；这将需要一种反常的适应度函数，因为在大多数情况下，冒泡排序比快速排序更差。发生这种情况并非不可想象，但一般来说，一旦你有了一个很好理解的算法，它就已经很合适了——去另一个可能需要通过一些更糟糕的选择。

对于大多数搜索策略来说，陷入局部最小值并不是一个未知的问题。