最近,当我尝试纠正/改进回合制策略计算机游戏的计算机对手时,遗传算法引起了我的注意。
我实现了一个简单的遗传算法,它没有使用任何交叉,只是一些随机突变。在这种情况下它似乎有效,所以我开始思考:
为什么交叉是遗传算法的一部分?变异还不够吗?
这是来自旧 AI 站点上的数据转储。提问者的 UID 为 7。
最近,当我尝试纠正/改进回合制策略计算机游戏的计算机对手时,遗传算法引起了我的注意。
我实现了一个简单的遗传算法,它没有使用任何交叉,只是一些随机突变。在这种情况下它似乎有效,所以我开始思考:
为什么交叉是遗传算法的一部分?变异还不够吗?
这是来自旧 AI 站点上的数据转储。提问者的 UID 为 7。
突变通常被定义为全局算子,即迭代突变(最终)能够到达基因组定义的向量空间中的每个点。从这个意义上说,单独的突变肯定是“足够的”。
关于交叉的动机 - 来自Metaheuristics 的精华,第 42页:
Crossover 最初是基于这样一个前提,即高度契合的个体通常具有共同的某些特征,称为积木。例如,在布尔个体 10110101 中,也许 ***101*1 可能是一个构建块
(其中 * 表示“0 或 1”)
所以这个想法是交叉通过在整个人群中快速传播构建块来起作用。
交叉方法还假设染色体上的基因之间存在某种程度的联系:也就是说,组中某些基因的设置与适应度的提高密切相关。例如,基因 A 和 B 可能仅在它们都设置为 1 时才有助于适应度:如果其中一个设置为 0,那么另一个设置为 1 的事实不会做任何事情。
另请注意,crossover 不是全局运算符。如果唯一的运算符是交叉,那么(也来自 p42):
最终人口将收敛,并且经常(不幸地)过早地收敛到同一个体的副本。在这个阶段没有逃脱:当一个人与自己交叉时,不会产生任何新的东西。
出于这个原因,交叉通常与一些全局变异算子一起使用。
交叉允许组合两个父母(与仅使用一个父母的突变相比)。在某些情况下,它很有用(例如,如果你训练一个 FPS 机器人,如果一个父母擅长射击而另一个父母擅长移动,那么将它们结合起来是有意义的)。在其他一些情况下,它不是。
在考虑跨界时,重要的是要考虑健身景观。
考虑一个假设场景,我们正在应用遗传算法来找到在 2 个任务中表现良好的解决方案。这可能来自 Franck 的 AI 示例(移动和射击),或者可能在基因机器学习场景中预测 2 个输出,但实际上大多数应用 GA 的场景是同义词(即使在解决单个任务时,也可能是要解决的任务的不同方面)。
假设我们有一个个体 1,它在两项任务中都表现得相当好,我们发现一系列突变产生了 2 个新个体 2 和 3,它们在任务 1 和 2 中的表现分别优于个体 1。现在,虽然这两个都是改进,但理想情况下,我们希望找到一个普遍良好的解决方案,因此我们希望结合我们发现有益的功能。
这就是交叉出现的地方;通过结合个体 2 和个体 3 的基因组,我们可能会发现一些新个体产生了他们的混合表现。虽然这样的个体可能是由应用于个体 2 或个体 3 的一系列突变产生的,但景观可能根本不适合这种情况(例如,在那个方向上可能没有有利的突变)。
因此,您部分正确;有时可能会出现交叉的好处可以通过一系列突变来复制。有时情况可能并非如此,交叉可能会平滑您的遗传算法的适应度,加速优化并帮助您的遗传算法摆脱局部最优。