selection - 轮盘选择、等级选择和锦标赛选择有什么区别？

Question

我正在阅读有关遗传编程的幻灯片，其中有一些选择个体的方法，例如 轮盘选择 , 排名选择和 赛事选择 ，都提到了。
这三种选择方法有什么区别？

Answer 1

轮盘选择 (又名 Fitness proportionate selection)

适应度用于将选择概率与每个个体相关联。

如果 fi 是个体 i 在种群中的适应度，则其被选中的概率为:

pi = fi/Σ j(fj) for j = 1 … N(N 是总体中的个体数)

它被称为轮盘赌，因为它可以被视为赌场中的轮盘:



这可以通过以下(朴素的)算法来模拟:

计算种群中所有适应度的总和(总和 S)。

生成随机数 r在区间 [0; ]。

遍历总体并求和适应度。当总和 s 大于 r 时，停止并返回您所在的个人。

有关可能的实现，请参阅:

Roulette wheel selection algorithm

Roulette Selection in Genetic Algorithms

排名选择除了选择概率与相对适应度而不是绝对适应度成正比外，与轮盘赌选择类似。

最适合的候选人是否比下一个最适合的候选人更适合十倍或适合 0.001% 没有任何区别。在这两种情况下，选择概率是相同的。

重要的是相对于其他人的排名。

Rank selection is easy to implement when you already know on roulette wheel selection. Instead of using the fitness as probability for getting selected you use the rank. So for a population of N solutions the best solution gets rank N, the second best rank N-1, etc. The worst individual has rank 1.

( Ranking Selection in Genetic Algorithm code )

Tournament selection

从人群中随机选择几个人(锦标赛)。

选择具有最佳适应度的个体(获胜者)进行交叉。

如您所见，编码非常高效。它还适用于并行架构，并允许轻松调整选择压力(更改锦标赛中的个人数量)。

当然，这些算法有许多变体。

要进行比较，您可以阅读:

Comparison of Performance between Different Selection Strategies on Simple Genetic Algorithms (Jinghui Zhong, Xiaomin Hu, Min Gu, Jun Zhang - 2005)