genetic-algorithm - 遗传算法中的轮盘赌选择

Question

任何人都可以为轮盘赌选择功能提供一些伪代码吗？我将如何实现这一点：

$替代文字$

我真的不明白如何阅读这个数学符号。我从不接受任何概率或统计数据。

score 39 · Accepted Answer

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

对于所有人口
    sum += 这个人的适应度
结束

对于所有人口
    概率=概率之和+（适应度/总和）
    概率之和 += 概率
结束

循环直到新的人口已满
    这样做两次
        number = 0 到 1 之间的随机数
        对于所有人口
            如果数字 > 概率但小于下一个概率
                那么你已被选中
        结束
    结尾
    创造后代
结束循环

如果您需要更多详细信息，可以在此处找到此来源的网站。

score 18 · Accepted Answer

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

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 有一个类似的二等分算法，如果这是您使用的语言。

score 12 · Accepted Answer

发布的伪代码包含一些不清楚的元素，它增加了生成后代而不是执行纯选择的复杂性。这是该伪代码的简单python实现：

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <http://stackoverflow.com/questions/177271/roulette
        -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

score 10 · Accepted Answer

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

/// \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)

score 5 · Accepted Answer

这是 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**

score 2 · Accepted Answer

从上面的答案中，我得到了以下内容，这对我来说比答案本身更清楚。

举个例子：

Random(sum) :: Random(12) 遍历总体，我们检查以下内容： random < sum

让我们选择 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;
        }
    }

score 1 · Accepted Answer

斯坦福 AI 实验室的 Thrun 教授还在 Udacity 的 CS373 期间展示了一个用 python 进行快速（呃？）重新采样的代码。谷歌搜索结果导致以下链接：

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

希望这可以帮助

score 1 · Accepted Answer

这是我最近为轮盘选择编写的一个紧凑的 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;
}

score 1 · Accepted Answer

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

score 1 · Accepted Answer

好的，轮盘选择实现有两种方法：通常和随机接受一种。

常用算法：

# 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，通常算法的机会就越大）。

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

score 0 · Accepted Answer

Based on my research ,Here is another implementation in C# if there is a need for it:


//those with higher fitness get selected wit a large probability 
//return-->individuals with highest fitness
        private int RouletteSelection()
        {
            double randomFitness = m_random.NextDouble() * m_totalFitness;
            int idx = -1;
            int mid;
            int first = 0;
            int last = m_populationSize -1;
            mid = (last - first)/2;

            //  ArrayList's BinarySearch is for exact values only
            //  so do this by hand.
            while (idx == -1 && first <= last)
            {
                if (randomFitness < (double)m_fitnessTable[mid])
                {
                    last = mid;
                }
                else if (randomFitness > (double)m_fitnessTable[mid])
                {
                    first = mid;
                }
                mid = (first + last)/2;
                //  lies between i and i+1
                if ((last - first) == 1)
                    idx = last;
            }
            return idx;
        }

score 0 · Accepted Answer

这个Swift 4数组扩展实现了加权随机选择，也就是从其元素中选择轮盘赌：

public extension Array where Element == Double {

    /// Consider the elements as weight values and return a weighted random selection by index.
    /// a.k.a Roulette wheel selection.
    func weightedRandomIndex() -> Int {
        var selected: Int = 0
        var total: Double = self[0]

        for i in 1..<self.count { // start at 1
            total += self[i]
            if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
        }

        return selected
    }
}

例如给定两个元素数组：

[0.9, 0.1]

weightedRandomIndex()将在 90% 的时间和 10% 的时间返回零。

这是一个更完整的测试：

let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
    let index = weights.weightedRandomIndex()
    results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
    print(weights[key], Double(val)/Double(n))
}

输出：

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

这个答案与Andrew Mao在这里的答案基本相同： https ://stackoverflow.com/a/15582983/74975

score 0 · Accepted Answer

这是python中的代码。此代码还可以处理适应度的负值。

from numpy import min, sum, ptp, array 
from numpy.random import uniform 

list_fitness1 = array([-12, -45, 0, 72.1, -32.3])
list_fitness2 = array([0.5, 6.32, 988.2, 1.23])

def get_index_roulette_wheel_selection(list_fitness=None):
    """ It can handle negative also. Make sure your list fitness is 1D-numpy array"""
    scaled_fitness = (list_fitness - min(list_fitness)) / ptp(list_fitness)
    minimized_fitness = 1.0 - scaled_fitness
    total_sum = sum(minimized_fitness)
    r = uniform(low=0, high=total_sum)
    for idx, f in enumerate(minimized_fitness):
        r = r + f
        if r > total_sum:
            return idx

get_index_roulette_wheel_selection(list_fitness1)
get_index_roulette_wheel_selection(list_fitness2)

确保您的健身列表是 1D-numpy 数组
将适应度列表缩放到范围 [0, 1]
将最大问题转换为最小问题 1.0 - scaled_fitness_list
随机一个介于 0 和 sum(minimizzed_fitness_list) 之间的数字
继续在最小化适应度列表中添加元素，直到我们得到大于总和的值
你可以看到适应度是否小 --> 它在最小化的适应度中具有更大的价值 --> 它有更大的机会相加并使值大于总和。

score -1 · Accepted Answer

我用 C# 编写了一个版本，并且真的在寻找它确实正确的确认：

（roulette_selector 是一个随机数，范围为 0.0 到 1.0）

private Individual Select_Roulette(double sum_fitness)
    {
        Individual ret = new Individual();
        bool loop = true;

        while (loop)
        {
            //this will give us a double within the range 0.0 to total fitness
            double slice = roulette_selector.NextDouble() * sum_fitness;

            double curFitness = 0.0;

            foreach (Individual ind in _generation)
            {
                curFitness += ind.Fitness;
                if (curFitness >= slice)
                {
                    loop = false;
                    ret = ind;
                    break;
                }
            }
        }
        return ret;

    }

genetic-algorithm - 遗传算法中的轮盘赌选择

14 回答 14

有用的资源：

Related

Reference