有人能提供用于轮盘赌选择函数的伪代码吗?我该如何实现以下公式:
我并不真正理解如何阅读这个数学符号。我从未学习过概率或统计学。
有人能提供用于轮盘赌选择函数的伪代码吗?我该如何实现以下公式:
我并不真正理解如何阅读这个数学符号。我从未学习过概率或统计学。
我自己已经好几年没做这个了,但是下面的伪代码在谷歌上很容易找到。
对于所有种群成员 总和 += 该个体的适应度 结束循环
对于所有种群成员 概率 = 概率总和 + (适应度 / 总和) 概率总和 += 概率 结束循环
循环直到新种群满为止 执行两次以下操作 数字 = 0到1之间的随机数 对于所有种群成员 如果数字大于概率但小于下一个概率 那么你就被选中了 结束循环 结束循环 创建后代 结束循环
如果您需要进一步了解,可以在此处找到此内容的来源网站。
fitness = 1 / (x + y)
。 - WSBT已经有很多正确的解决方案了,但我认为这段代码更清晰。
def select(fs):
p = random.uniform(0, sum(fs))
for i, f in enumerate(fs):
if p <= 0:
break
p -= f
return i
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中有一个类似的二分算法可用。
发帖的伪代码中有一些不清晰的元素,并且它增加了生成"后代"而不是执行纯选择的复杂性。这里是该伪代码的一个简单的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
这被称为随机接受的轮盘赌选择:
/// \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;
}
}
进行一次选择所需的平均尝试次数为:
τ = fmax / avg(f)
τ 不明显依赖于种群中个体数量 (N),但比率会随着 N 的变化而改变。
然而,在许多应用程序中(其中适应度保持有界且平均适应度不会随着 N 的增加而趋近于0),τ 不会随 N 增长而无限制地增加,因此 该算法的典型复杂度为 O(1) (使用搜索算法的轮盘选择具有 O(N) 或 O(log N) 复杂度)。
该过程的概率分布确实与经典轮盘选择相同。
更多详细信息请参见:
这里是一些 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**
从上面的回答中,我得到了以下内容,比答案本身更清晰明了。
举个例子:
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 | ...
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;
}
}
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
好的,所以有两种方法可以实现轮盘赌选择: 通常和随机接受。
通常算法:
# 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 - 描述了随机接受算法。
http://www.udacity-forums.com/cs373/questions/20194/fast-resampling-algorithm
希望这能有所帮助。这是我最近为轮盘赌选择编写的紧凑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;
}