logo标签列表

如何在遗传算法中执行基于排名的选择？

selectiongenetic-algorithmstochasticroulette-wheel-selection
10

我正在实现一个小的遗传算法框架，主要供私人使用，除非我能够开发出一些有用的东西，到那时我将其发布为开源。现在我正在关注选择技术。到目前为止，我已经实现了轮盘赌选择、随机通用抽样选择和锦标赛选择。接下来，我要实现排名选择。相较于我已经实现的其他技术，我在这方面找到的信息要多一点，但以下是我目前理解的内容。

  1. 当您从种群中获取下一轮合适的父母代表时，首先需要对每个个体的适应度除以种群中所有个体的适应度之和。

  2. 然后使用某种其他的选择技术（例如轮盘赌）来实际确定进行繁殖的个体。

这是正确的吗？如果是这样，我是否正确地认为，排名调整是一种预处理步骤，随后必须跟随一个实际的选择过程来挑选候选者？如果我对其中任何内容有误解，请纠正我。我感谢任何额外的指导。

4个回答
21
你所描述的是轮盘赌选择算法。
在轮盘赌选择中：
  • 根据适应度选择父代。
  • 染色体适应度越高，被选中的几率就越大。
想象一下一个轮盘赌，所有种群中的染色体都被放置在上面，每个染色体的位置大小都与其适应度函数相对应，就像以下图片所示enter image description here。当适应度差异很大时，这种选择会出现问题。杰出的个体会在搜索开始时引入偏差，可能导致过早收敛和多样性的丧失。
例如：

如果初始种群包含一个或两个非常适合但不是最好的个体，而其他人不太好，那么这些适合的个体将很快支配整个种群，并阻止种群探索其他潜在更好的个体。这种强烈的支配导致遗传多样性的严重丧失，这绝对不利于优化过程。

但在排名选择中：

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

  2. 最差的染色体适应度为1，次劣的为2等，最佳染色体的适应度为N（种群中染色体的数量）enter image description here

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

  4. 基于排名的选择方案可以避免过早收敛。
  5. 但是这可能会导致计算成本较高，因为它基于适应度值对种群进行排序。
  6. 但这种方法可能导致收敛速度变慢，因为最佳染色体与其他染色体相比差异不大。

因此，流程将是:

  1. 首先对种群的适应度值进行排序。

  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

注意: 您也可以在此链接中查看我关于排名选择的问题，以及我的文章这里。

10

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

例如，你可以给第一个人一个1/2的权重，第二个人一个1/3的权重，第三个人一个1/4的权重，以此类推。或者最差的得到1的权重，第二差的得到2的权重，等等。

重要的是绝对或相对适应度分数都不会被考虑，只有排名。因此最优秀的被选中的概率比次优秀的更高，但无论最佳者的分数是第二名的十倍还是稍微高一点，它们被选中的概率相同。

如果我理解正确的话，我只需根据适应度对染色体进行排序就可以得到排名？然后我可以更新每个染色体的适应度来表示其排名而不是绝对适应度？如果这是真的，那么我该如何从列表中选择人作为父母呢？我是否只需要使用其他选择算法之一？ - Philip Bennefall
1
你使用“加权随机选择”。轮盘赌选择也是“加权随机选择”，只不过权重是从适应度而不是排名中派生出来的。 - Sneftel
我已经编写了以下代码，似乎可以产生正确的结果（在0到1之间的线性序列）。void linear_rank_fitness_adjustment(chromosome* population) { std::sort(population, population+population_size, chromosome_compare);for(int i=0;i<population_size;i++) population[i].fitness=(float)(i+1)/population_size; }应用这种过滤/预处理步骤，然后让用户选择任何其他选择算法来挑选实际的父代，这样做是否合理？ - Philip Bennefall
非常抱歉这个格式看起来很混乱，我不确定该如何修复它。 - Philip Bennefall
我能不能使用轮盘赌来进行加权随机化呢？既然我将适应度更新为实际的排名而不是原始的绝对适应度，这样行得通吗？此外，请您在这个上下文中详细解释一下“归一化”这个术语好吗？在对列表进行排序并设置排名后，我该如何对其进行归一化？目前，在运行函数后，我得到了一个介于0.0和1.0之间的值列表。我应该做些什么更多的事情吗？ - Philip Bennefall
显示剩余6条评论
2
我也对使用线性排名选择（有时也称为“排名选择”）计算概率的不同来源感到有些困惑，至少我希望这两个术语指的是同一件事情。对我来说比较难理解的部分是排名之和，在大多数来源中似乎已被省略或至少没有明确说明。下面我将介绍一个简短但详细的 Python 示例，展示如何计算概率分布（通常看到的漂亮图表）。假设以下是一些个体适应度的示例值：10、9、3、15、85、7。排序后，按升序分配排名：第1名：3，第2名：7，第3名：9，第4名：10，第5名：15，第6名：85。所有排名之和为1+2+3+4+5+6，即21，也可以使用高斯公式（6+1）×6/2进行计算。
因此，我们计算出的概率是：1/21、2/21、3/21、4/21、5/21、6/21，你可以将其表示为百分比：

Probability distribution of selecting an individual using Rank Selection

请注意，这并不是遗传算法实际实现中所使用的内容，仅是一个帮助脚本，以便让您更好地理解。
您可以使用以下命令获取此脚本：
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))
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 条染色体组成的种群。

示例

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接