遗传算法中的轮盘选择

Question

任何人都可以为轮盘选择功能提供一些伪代码吗？我该如何实现这个:

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

Answer 1

自从我自己完成这项工作已有几年了,但是谷歌上发现了以下伪代码.

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
    do this twice
        number = Random between 0 and 1
        for all members of population
            if number > probability but less than next probability 
                then you have been selected
        end for
    end
    create offspring
end loop

如果您需要更多详细信息,可以在此处找到它来自的网站.

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具有类似的二分算法.

Answer 3

发布的伪代码包含一些不清楚的元素,它增加了生成后代的复杂性,而不是执行纯粹的选择.这是一个伪代码的简单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

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是人口的最大适应度
• 平均(f)是平均适应度

τ并不明确地依赖于群体中个体的数量(N),但该比率可以随N而变化.

然而,在许多应用中(适应性仍然有限且平均适应度不会减小到0以增加N)τ不会随着N无限增加,因此该算法的典型复杂度是O(1)(轮盘选择使用搜索算法具有O(N)或O(log N)复杂度.

该程序的概率分布确实与经典轮盘选择中的概率分布相同.

详情请见:

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

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