algorithm - 遗传规划和搜索算法

Question

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

Answer 1

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

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

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

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