algorithm - 遗传算法代码中的排序选择

Question

我需要 ranking selection method 的代码关于遗传算法。我已经创建了轮盘赌和锦标赛选择方法，但现在我需要排名，但我被卡住了。

我的轮盘赌代码在这里(我正在为遗传原子使用原子结构):

const int roulette (const atom *f)
{
  int i;
  double sum, sumrnd;

  sum = 0;
  for (i = 0; i < N; i++)
    sum += f[i].fitness + OFFSET;

  sumrnd = rnd () * sum;

  sum = 0;
  for (i = 0; i < N; i++) {
    sum += f[i].fitness + OFFSET;
    if (sum > sumrnd)
      break;
  }

  return i;
}

其中原子:

typedef struct atom
{
  int geno[VARS];
  double pheno[VARS];
  double fitness;
} atom;

Answer 1

当您已经知道轮盘选择时，排名选择很容易实现。不是使用适应度作为被选中的概率，而是使用排名。因此，对于 N 个解决方案的群体，最好的解决方案排名 N，第二好的排名 N-1，依此类推。最差的个人排名 1。现在使用轮盘并开始选择。

最佳个体被选中的概率为 N/( (N * (N+1))/2 ) 或大致为 2/N，最差个体被选中的概率为 2/(N*(N+1) ) 或大约 2/N^2。

这称为线性排名选择，因为排名形成线性级数。您还可以认为排名形成一个几何级数，例如 1/2^n，其中 n 的范围从 1 代表最好的个人到 N 代表最差的个人。这当然会为最好的个体提供更高的概率。

可以看HeuristicLab中一些选择方法的实现.