遗传算法中的轮盘选择

Question

有人能提供用于轮盘赌选择函数的伪代码吗？我该如何实现以下公式：

我并不真正理解如何阅读这个数学符号。我从未学习过概率或统计学。

- Sam McAfee

---

分母只是一个总和：SUM(f_j for j=1 upto N)。这意味着选择物品i的概率p_i就是其适应度f_i与所有适应度之和的比值。 - rampion

@rampion：谢谢。这种记号让我头晕，但我猜对了，你的解释证实了我的猜测 :) - jkp

有人知道即使f_i值（即适应度值）为负数，上述公式是否仍然有效吗？ - mkuse

如果您的适应度值为负数，显然是无效的。当您同时拥有正数和负数时，您的总和可能为零。 - fangmobile

Answer 1

我自己已经好几年没做这个了，但是下面的伪代码在谷歌上很容易找到。

对于所有种群成员
    总和 += 该个体的适应度
结束循环
对于所有种群成员
    概率 = 概率总和 + (适应度 / 总和)
    概率总和 += 概率
结束循环
循环直到新种群满为止
    执行两次以下操作
        数字 = 0到1之间的随机数
        对于所有种群成员
            如果数字大于概率但小于下一个概率
                那么你就被选中了
        结束循环
    结束循环
    创建后代
结束循环

如果您需要进一步了解，可以在此处找到此内容的来源网站。

- Jarod Elliott

---

你可以通过对概率数组进行二分查找（而不是迭代查找）来使这个过程更加高效。 - rampion

请注意，这个算法在最小化问题上不能按预期运行。这是使用轮盘选择（适应度比例选择）时的一个常见问题。 - gpampara

健康分数应该以更高的得分为有利的方式进行分配。对于最小化问题，通常采用倒数。例如，要最小化x和y的总和，可以编写一个健康函数，如 fitness = 1 / (x + y)。 - WSBT

在这个例子中，人口的适应度需要排序吗？ - CatsLoveJazz

还想知道它们是否应该排序。 - Zimano

Answer 2

已经有很多正确的解决方案了，但我认为这段代码更清晰。

def select(fs):
    p = random.uniform(0, sum(fs))
    for i, f in enumerate(fs):
        if p <= 0:
            break
        p -= f
    return i

此外，如果您累积fs，就可以产生更高效的解决方案。

cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]

def select(cfs):
    return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))

这既更快，而且代码非常简洁。如果您使用的是C++语言，则STL中有一个类似的二分算法可用。

- user97370

---

那个解决方案不仅比我的代码更短，而且更清晰、更高效。(Y) - noio

如果这些变量有英文名称会非常有帮助。 - Kyeotic

Answer 3

发帖的伪代码中有一些不清晰的元素，并且它增加了生成"后代"而不是执行纯选择的复杂性。这里是该伪代码的一个简单的Python实现：

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <https://dev59.com/1HVC5IYBdhLWcg3wz0l9
        -selection-in-genetic-algorithms/177278#177278>
    """
    total_fitness = float(sum(fitnesses))
    rel_fitness = [f/total_fitness for f in fitnesses]
    # Generate probability intervals for each individual
    probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
    # Draw new population
    new_population = []
    for n in xrange(num):
        r = rand()
        for (i, individual) in enumerate(population):
            if r <= probs[i]:
                new_population.append(individual)
                break
    return new_population

- noio

Answer 4

这被称为随机接受的轮盘赌选择：

/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.

unsigned rw_selection(double f_max)
{
  for (;;)
  {
    // Select randomly one of the individuals
    unsigned i(random_individual());

    // The selection is accepted with probability fitness(i) / f_max
    if (uniform_random_01() < fitness(i) / f_max)
      return i;
  }   
}

进行一次选择所需的平均尝试次数为：

τ = f_max / avg(f)

• f_max 是种群中最高适应度值
• avg(f) 是种群的平均适应度值

τ 不明显依赖于种群中个体数量 (N)，但比率会随着 N 的变化而改变。

然而，在许多应用程序中（其中适应度保持有界且平均适应度不会随着 N 的增加而趋近于0），τ 不会随 N 增长而无限制地增加，因此 该算法的典型复杂度为 O(1) (使用搜索算法的轮盘选择具有 O(N) 或 O(log N) 复杂度)。

该过程的概率分布确实与经典轮盘选择相同。

更多详细信息请参见：

• 通过随机接受的轮盘选择 (Adam Liposki, Dorota Lipowska - 2011)

- manlio

Answer 5

这里是一些 C 代码：

// Find the sum of fitnesses. The function fitness(i) should 
//return the fitness value   for member i**

float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
    sumFitness += fitness(i);

// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;

// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;

while (randomNumber > partialSum)
{
   partialSum += fitness(memberID);
   memberID++;
} 

**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**

- Wartin

---

成员应该排序吗？ - Zimano

Answer 6

从上面的回答中，我得到了以下内容，比答案本身更清晰明了。

举个例子：

Random(sum) :: Random(12) 在对人口进行迭代时，我们检查以下内容：随机数 < 总和

让我们选择7作为随机数。

Index   |   Fitness |   Sum |   7 < Sum
0       |   2   |   2       |   false
1       |   3   |   5       |   false
2       |   1   |   6       |   false
3       |   4   |   10      |   true
4       |   2   |   12      |   ...

通过这个例子，最适合的（索引3）被选中的几率最高（33%）；因为随机数只需要落在6到10之间，它就会被选择。

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }

- deceleratedcaviar

Answer 7

转盘赌轮选择（Roulette Wheel Selection）在MatLab中的实现：

TotalFitness=sum(Fitness);
    ProbSelection=zeros(PopLength,1);
    CumProb=zeros(PopLength,1);

    for i=1:PopLength
        ProbSelection(i)=Fitness(i)/TotalFitness;
        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

- Setu Kumar Basak

Answer 8

好的，所以有两种方法可以实现轮盘赌选择: 通常和随机接受。

通常算法:

# there will be some amount of repeating organisms here.
mating_pool = []

all_organisms_in_population.each do |organism|
  organism.fitness.times { mating_pool.push(organism) }
end

# [very_fit_organism, very_fit_organism, very_fit_organism, not_so_fit_organism]
return mating_pool.sample #=> random, likely fit, parent!

随机接受算法：

max_fitness_in_population = all_organisms_in_population.sort_by(:fitness)[0]
loop do
  random_parent = all_organisms_in_population.sample
  probability = random_parent.fitness/max_fitness_in_population * 100
  # if random_parent's fitness is 90%,
  # it's very likely that rand(100) is smaller than it.
  if rand(100) < probability
    return random_parent #=> random, likely fit, parent!
  else
    next #=> or let's keep on searching for one.
  end
end

你可以选择任意一个，它们将返回完全相同的结果。

---

有用的资源：

http://natureofcode.com/book/chapter-9-the-evolution-of-code - 一个适合初学者的明晰易懂的关于遗传算法的章节。解释了轮盘赌选择，将其比喻成一桶木制字母（放入更多"A"，选中"A"的机会就越大，通常算法）。

https://en.wikipedia.org/wiki/Fitness_proportionate_selection - 描述了随机接受算法。

- Evgenia Karunus

Answer 9

斯坦福人工智能实验室的Thrun教授在Udacity的CS373课程中还展示了一段Python快速重新采样代码。谷歌搜索结果指向以下链接：

http://www.udacity-forums.com/cs373/questions/20194/fast-resampling-algorithm

希望这能有所帮助。

- Kangwon Lee

Answer 10

这是我最近为轮盘赌选择编写的紧凑Java实现，希望对您有所帮助。

public static gene rouletteSelection()
{
    float totalScore = 0;
    float runningScore = 0;
    for (gene g : genes)
    {
        totalScore += g.score;
    }

    float rnd = (float) (Math.random() * totalScore);

    for (gene g : genes)
    {   
        if (    rnd>=runningScore &&
                rnd<=runningScore+g.score)
        {
            return g;
        }
        runningScore+=g.score;
    }

    return null;
}

- NickD