遗传算法 - 父代选择


亲代选择是选择交配和重组为下一代创造后代的亲代的过程。父母的选择对于遗传算法的收敛速度非常重要,因为好的父母会促使个体找到更好、更合适的解决方案。

然而,应注意防止一种极其适合的解决方案在几代之内接管整个种群,因为这会导致解决方案在解决方案空间中彼此接近,从而导致多样性的丧失。保持种群的良好多样性对于遗传算法的成功至关重要。这种由一个极其适合的解决方案占据整个种群的情况被称为过早收敛,并且是 GA 中的一种不良情况。

健身比例选择

健身比例选择是最流行的家长选择方式之一。在这种情况下,每个人都可以成为父母,其概率与其适应度成正比。因此,身体健康的个体有更高的机会交配并将其特征传播给下一代。因此,这种选择策略对种群中更适合的个体施加选择压力,随着时间的推移进化出更好的个体。

考虑一个圆形轮子。轮子分为n 个饼,其中 n 是种群中的个体数量。每个个体得到的圆的一部分与其适应度值成正比。

适应度比例选择的两种实现是可能的 -

轮盘赌选择

在轮盘选择中,圆形轮如前所述被划分。如图所示,在轮子圆周上选择一个固定点,然后旋转轮子。选择位于固定点前面的轮子区域作为父区域。对于第二个父母,重复相同的过程。

轮盘赌选择

显然,安装工在车轮上占有更大的份额,因此当车轮旋转时,落在固定点前面的机会更大。因此,选择个体的概率直接取决于其适应度。

在实施方面,我们使用以下步骤 -

  • 计算 S = a 技巧之和。

  • 生成 0 到 S 之间的随机数。

  • 从总体顶部开始,不断将精细度添加到部分和 P 上,直到 P<S。

  • P 超过 S 的个体是被选择的个体。

随机通用抽样 (SUS)

随机通用采样与轮盘赌选择非常相似,但是我们不是只有一个固定点,而是有多个固定点,如下图所示。因此,所有的父母都在轮子的一转中被选择。此外,这样的设置鼓励高度适合的个人至少被选择一次。

不锈钢

值得注意的是,适应度比例选择方法不适用于适应度可以取负值的情况。

赛事选择

在 K-Way 锦标赛选择中,我们从人群中随机选择 K 个个体,并从其中选择最好的个体作为父母。重复相同的过程来选择下一个父代。锦标赛选择在文学中也非常流行,因为它甚至可以与负健身值一起使用。

赛事选择

排名选择

排名选择也适用于负适应度值,并且主要在群体中的个体具有非常接近的适应度值时使用(这通常发生在运行结束时)。这导致每个人都拥有几乎相等的份额(就像适应度比例选择的情况一样),如下图所示,因此每个人无论彼此之间的适应程度如何,都有大致相同的概率被选为父母。这反过来又导致对更适应个体的选择压力的损失,使得遗传算法在这种情况下做出糟糕的父母选择。

排名选择

在此,我们在选择父代时删除了适应度值的概念。然而,群体中的每个人都是根据他们的健康状况进行排名的。父母的选择取决于每个人的等级而不是健康状况。排名较高的个人比排名较低的个人更受青睐。

染色体 健身值
A 8.1 1
8.0 4
C 8.05 2
D 7.95 6
8.02 3
F 7.99 5

随机选择

在这个策略中,我们从现有群体中随机选择父母。对于更适合的个体不存在选择压力,因此通常会避免这种策略。