突变和交叉如何与实值染色体一起工作?

人工智能 遗传算法 交叉运营商 变异算子 基因操作员
2021-10-31 00:00:54

在基于实数(而不仅仅是位)的遗传算法的上下文中,“突变”和“交叉”究竟是如何应用的?我想我理解这两个阶段是如何应用于“规范”上下文中的,其中染色体是固定长度的位串,但我无法找到其他情况的示例。这些阶段在实数域上会是什么样子?

2个回答

正如@Thomas W 所说,当您开发突变和交叉方法时,您可以很有想象力。每个问题都有自己的特点,因此需要不同的策略。

但是,根据我的经验,我想说实数基因型上 90% 的交叉和突变是使用 BLX-α 算法解决的。

交叉:

BlX-α算法范围

这个算法真的很简单。给定父母XY以及一个 α 值(在 [0,1] 范围内,通常在 0.1/0.15 左右,但这取决于问题),对于您基因型的每个基因:

  1. 提取基因xiyi
  2. 找到最小值和最大值
  3. 新基因将是区间 [min - range * α, max + range * α] 中的随机数

该算法的一个变体是 BLX-αβ,其中我们考虑了哪个父代表现更好,并使用两个常数 (α > β) 来增加新值更接近最适合的父代的概率

BLX-αβ算法范围

突变:

对于突变,情况类似:我们需要获得一个与我们的问题域相关的随机值(我们不希望突变具有破坏性!它们具有探索空间的功能)。
在这些情况下,确定突变范围并使用该范围通过 BLX-α 找到基因的新值是有用的。

在取决于基因的实际值和个体适应度函数的边界上使用 BLX-α 可以实现更复杂的变异算法。
让我们想象一下,我们个人的表现非常糟糕;在这种情况下,变异算子将用于将个体转移到搜索空间中的较远点,在那里它可能会表现得更好。
另一方面,如果个体已经很健康,我们可能不想使用突变引入一些戏剧性的变化。在这种情况下,突变范围将更加包含,并且具有调整基因型的功能,而不是探索更好的替代方案。

你有一个带有某些基因的基因组:

genome = { GeneA: value, GeneB: value, GeneC: value }

所以举个例子:

genome = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }

一些突变的例子可能是:

  • 切换两个基因:{ GeneA: 1, GeneB: 3.4, GeneC: 2.5 }
  • 从基因中添加/减去随机值:{ GeneA: 0.9, GeneB: 2.5, GeneC: 3.4 }

假设你有两个基因组:

genome1 = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }
genome2 = { GeneA: 0.4, GeneB: 3.5, GeneC: 3.2 }

交叉的一些示例可能是:

  • 取平均值:{ GeneA: 0.7, GeneB: 3.0, GeneC: 3.3 }
  • 制服(50% 几率):{ GeneA: 0.4, GeneB: 2.5, GeneC: 3.2 }
  • N点交叉:{ GeneA: 1, | CROSSOVER POINT | GeneB: 3.5, GeneC: 3.2 }

在开发变异和交叉方法时,你可以很有想象力。