为什么专门使用它?
我知道它增加了变化,这可能有助于探索问题空间,但它增加了多少及时找到最佳解决方案/配置的可能性?它还有其他好处吗?
它是否一定总是有帮助,或者在某些情况下会增加找到最佳解决方案所需的时间?
正如帕特里克·特伦廷(Patrick Trentin)所说,交叉提高了收敛的速度,因为它允许结合人群中已经发现的良好基因。
但是,对于神经进化来说,交叉面临着"排列问题",也被称为"竞争约定问题"。当两个父母是同一网络的排列时,那么,除了极少数情况外,他们的后代总是具有较低的适应性。因为网络的同一部分被复制到两个不同的位置,因此后代正在失去这两个位置之一的活基因。
例如,网络 A、B、C、D 和 D、C、B、A 是同一网络的排列。后代可以是:
A,B,C,D (copy of parent 1)
D,C,B,A (copy of parent 2)
A,C,B,D OK
A,B,C,A
A,B,B,A
A,B,B,D
A,C,B,A
A,C,C,A
A,C,C,D
D,B,C,A OK
D,C,B,D
D,B,B,A
D,B,B,D
D,B,C,D
D,C,C,A
D,C,C,D
因此,对于此示例,2/16 的后代是父母的副本。 2/16 是没有重复项的组合。12/16有重复的基因。
出现排列问题的原因是,排列网络与另一个网络具有相同的适应性。因此,即使对于精英GA,如果一个被选为父母,另一个也经常会被选为父母。
排列可能只是部分的。在这种情况下,结果比完全排列要好,但在许多情况下,后代的适应度仍然低于父母。
为了避免排列问题,我听说了基于相似性的交叉,它计算神经元及其连接突触的相似性,在最相似的神经元之间进行交叉,而不是基于基因座的交叉。
在发展网络的拓扑结构时,一些NEAT专家认为排列问题是更广泛问题的一部分:"可变长度基因组问题"。NEAT似乎通过网络形态来避免这个问题,当两个网络的拓扑和权重差异太大时,它们不允许配对。因此,NEAT算法似乎认为排列网络差异太大,并且不允许它们配对。
一个关于NEAT的网站也说:
然而,从另一种意义上说,可变长度的基因组问题永远无法"解决",因为它是任何产生解决相同问题的不同结构的系统所固有的。例如,鸟和蝙蝠都代表了飞行问题的解决方案,但它们并不兼容,因为它们是做同一件事的不同惯例。同样的情况可能发生在NEAT中,可能会出现做同样事情的非常不同的结构。当然,这样的结构不会交配,避免了后代受损的严重后果。尽管如此,可以说,由于不同的表征可以同时存在,因此不相容的基因组仍然存在,因此问题没有"解决"。 归根结底,问题是否得到解决是主观的。这取决于您认为的解决方案。然而,至少可以说,"避免了可变长度基因组的问题"。
编辑:回答您的评论。
您可能适合基于相似性的交叉,我不确定它是否完全避免了排列问题。
关于交叉的最终目标,在不考虑排列问题的情况下,我不确定它对神经网络的演化是否有用,但我的想法是:如果我们把一个神经网络分成几个部分,每个部分都有助于适应度,所以两个适应度高的网络可能有不同的好部分。将这些部分结合起来应该会创建一个更好的网络。有些后代当然会继承坏的部分,但其他一些后代会继承好的部分。
就像Ray建议的那样,试验有和没有交叉的神经网络的进化可能是有用的。由于进化中存在随机性,因此问题是运行大量测试,以计算平均进化速度。
关于进化神经网络以外的其他东西,我发现了一篇论文,说使用交叉的算法在解决全对最短路径问题(APSP)时优于仅突变算法。
编辑 2:
即使排列问题似乎只适用于神经进化等某些特定问题,我认为我们不能对交叉说同样的话,因为也许我们遗漏了一些似乎不适合交叉的问题。
我找到了一篇关于基于相似性的神经进化交叉的论文的免费版本,它表明:
使用朴素交叉的算法比仅突变算法的性能更差。
使用基于相似性的交叉,对于所有测试案例,它的性能优于仅突变算法。
NEAT 算法有时比仅突变算法表现更好。
交叉很复杂,我认为缺乏将其与仅突变算法进行比较的研究,可能是因为它的有用性在很大程度上取决于:
其工程,函数于特定问题,如排列问题。因此,我们使用的交叉类型(基于相似性,单点,均匀,边缘复合等)。
和交配算法。例如,本文表明,在解决TSP时,性别遗传算法的性能优于非性别遗传算法。对于解决另外两个问题,该算法的表现并不明显,但它比非性别的 GA 更好。在这个实验中,雄性是根据他们的健康状况选择的,雌性是根据他们产生良好后代的能力来选择的。不幸的是,这项研究没有将结果与仅突变算法进行比较。