10

我正在实现一个小型遗传算法框架 - 主要供私人使用，除非我设法做出合理的事情，届时我会将其作为开源发布。现在我专注于选择技术。到目前为止，我已经实现了轮盘赌选择、随机通用抽样和锦标赛选择。我列表中的下一个是基于排名的选择。与我已经实施的其他技术相比，我在查找有关该方面的信息时遇到了一些困难，但这是我迄今为止的理解。

  1. 当你有你想要为下一轮获得合理父母的群体时，你首先通过它并将每个个体的适应度除以群体中的总适应度。

  2. 然后您使用其他一些选择技术（例如轮盘赌）来实际确定选择谁进行繁殖。

这个对吗？如果是这样，我是否认为排名调整是一种预处理步骤，然后必须遵循一个实际的选择程序来挑选候选人？如果我对此有任何误解，请纠正我。我很感激任何额外的指示。

4

4 回答 4

22

您所描述的只是轮盘选择。在轮盘选择中：

  • 家长根据自己的体质挑选
  • 染色体越好，被选中的机会就越大。

想象一个轮盘赌，其中放置了种群中的所有染色体，根据其适应度函数，每个染色体都有其较大的位置，如下图所示在此处输入图像描述。
当技巧差异很大时，这种选择就会出现问题。优秀的个人会在搜索开始时引入偏见，这可能会导致过早收敛和多样性的丧失。
例如：

如果一个初始种群中包含一两个非常适合但不是最好的个体，而其余的种群都不是很好，那么这些适合的个体将很快主导整个种群，并阻止种群探索其他可能更好的个体。如此强大的支配导致遗传多样性的非常高的损失，这绝对不利于优化过程。

但在排名选择中：

  1. 排名选择首先对种群进行排名，然后每个染色体从该排名中获得适应度。

  2. 最差的将具有适应度 1，次差为 2，依此类推，而最好的将具有适应度 N（种群中的染色体数）。在此处输入图像描述

  3. 在此之后，所有的染色体都有机会被选中。

  4. 基于秩的选择方案可以避免过早收敛。
  5. 但计算成本可能很高，因为它根据适应度值对种群进行分类。
  6. 但是这种方法会导致收敛速度变慢，因为最好的染色体与其他染色体没有太大区别。

所以这个过程将是：

  1. 首先对 Population 的 Fitness 值进行排序。

  2. 然后，如果人口数为 10，则将选择概率给人口，如 0.1,0.2,0.3,...,1.0 。

  3. 然后计算累积健身并制作轮盘赌。
  4. 接下来的步骤与轮盘赌相同。

我在 Matlab 中的秩选择实现：

NewFitness=sort(Fitness);
        NewPop=round(rand(PopLength,IndLength));

        for i=1:PopLength
            for j=1:PopLength
                if(NewFitness(i)==Fitness(j))
                    NewPop(i,1:IndLength)=CurrentPop(j,1:IndLength);
                    break;
                end
            end
        end
        CurrentPop=NewPop;

        ProbSelection=zeros(PopLength,1);
        CumProb=zeros(PopLength,1);

        for i=1:PopLength
            ProbSelection(i)=i/PopLength;
            if i==1
                CumProb(i)=ProbSelection(i);
            else
                CumProb(i)=CumProb(i-1)+ProbSelection(i);
            end
        end

        SelectInd=rand(PopLength,1);

        for i=1:PopLength
            flag=0;
            for j=1:PopLength
                if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
                    SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
                    flag=1;
                    break;
                end
            end
            if(flag==0)
                SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
            end
        end

注意：您还可以在此 链接中查看我关于排名选择的问题，并在此处查看我的文章。

于 2016-01-26T13:26:32.263 回答
10

您所描述的是轮盘赌选择，而不是等级选择。要进行排名选择，而不是通过其适应度得分对每个候选人进行加权，而是通过其“排名”（即最佳、第二佳、第三佳等）对其进行加权。

例如，你可以给第一个权重 1/2，第二个权重 1/3，第三个权重 1/4，等等。或者最差的权重为 1，第二个最差的权重为 2，等等

重要的一点是不考虑绝对或相对适应度分数，只考虑排名。所以最好的比第二好的更有可能被选中，但是无论最好的得分是第二好的分数的十倍，还是只有稍高的分数，两者被选中的概率都是相同的。

于 2013-11-29T17:39:02.397 回答
2

我也对使用线性排名选择时如何计算概率的各种来源感到有些困惑，有时也称为“排名选择”，如此处所述。至少我希望这两个指的是同一件事。

对我来说难以捉摸的部分是似乎在大多数资料中被省略或至少没有明确说明的等级总和。在这里，我展示了一个简短但冗长的 Python 示例，说明如何计算概率分布（您经常看到的那些漂亮的图表）。

假设这些是一些示例个体 fintesses：10、9、3、15、85、7。

排序后，按升序分配排名：第 1：3，第 2：7，第 3：9，第 4：10 ，第5：15，第6：85

所有等级的总和为 1+2+3+4+5+6 或使用高斯公式 (6+1)*6/2 = 21。

因此，我们将概率计算为：1/21、2/21、3/21、4/21、5/21、6/21，然后您可以将其表示为百分比：

使用等级选择选择个体的概率分布

请注意，这不是在遗传算法的实际实现中使用的，只是一个帮助脚本，可以为您提供更好的直觉。

您可以使用以下方法获取此脚本：

curl -o ranksel.py https://gist.githubusercontent.com/kburnik/3fe766b65f7f7427d3423d233d02cd39/raw/5c2e569189eca48212c34b3ea8a8328cb8d07ea5/ranksel.py

#!/usr/bin/env python

"""
Assumed name of script: ranksel.py

Sample program to estimate individual's selection probability using the Linear
Ranking Selection algorithm - a selection method in the field of Genetic
Algorithms. This should work with Python 2.7 and 3.5+.

Usage:

./ranksel.py f1 f2 ... fN

Where fK is the scalar fitness of the Kth individual. Any ordering is accepted.

Example:

$ python -u ranksel.py 10 9 3 15 85 7
Rank Fitness Sel.prob.
   1    3.00     4.76%
   2    7.00     9.52%
   3    9.00    14.29%
   4   10.00    19.05%
   5   15.00    23.81%
   6   85.00    28.57%

"""

from __future__ import print_function
import sys

def compute_sel_prob(population_fitness):
  """Computes and generates tuples of (rank, individual_fitness,
     selection_probability) for each individual's fitness, using the Linear
     Ranking Selection algorithm."""
  # Get the number of individuals in the population.
  n = len(population_fitness)

  # Use the gauss formula to get the sum of all ranks (sum of integers 1 to N).
  rank_sum = n * (n + 1) / 2

  # Sort and go through all individual fitnesses; enumerate ranks from 1.
  for rank, ind_fitness in enumerate(sorted(population_fitness), 1):
    yield rank, ind_fitness, float(rank) / rank_sum


if __name__ == "__main__":
  # Read the fitnesses from the command line arguments.
  population_fitness = list(map(float, sys.argv[1:]))

  print ("Rank Fitness Sel.prob.")
  # Iterate through the computed tuples and print the table rows.
  for rank, ind_fitness, sel_prob in compute_sel_prob(population_fitness):
    print("%4d %7.2f %8.2f%%" % (rank, ind_fitness, sel_prob * 100))
于 2018-01-30T00:54:35.730 回答
0

根据 J. Palma 一书，正确的方法是：

  1. 排序每个排名的列表。第一个位置是适合度较高的染色体。
  2. 选择一个1<=Amax<=1.2，通常我们使用Amax = 1.2
  3. Amin = 2-Amax，所以如果我们选择 Amax = 1.2 那么 Amin = 0.8
  4. Pi = (Amax - (Amax-Amin)·(rank-1)/(m-1))·1/m

m = 列表元素的总数 rank = 在列表中的位置

例如，使用 Amax=1.2、Amin=0.8 和 m=3，因为我们有 3 条染色体。

例子

之后，您可以应用与比例选择相同的系统。

于 2020-12-01T06:34:42.630 回答