GA中的排名选择? [英] Rank Selection in GA?
问题描述
我已经在GA中实现了Roulette wheel selection.
I have implemented Roulette wheel selection in GA.
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
现在我正在尝试在GA中实现rank selection.我了解到:
Now i was trying to implement rank selection in GA. I learned that:
-
等级选择首先对种群进行排名，然后每个染色体都从该排名中获得适合度.
Rank selection first ranks the population and then every chromosome receives fitness from this ranking.
最差的将具有适应性1，其次是最差的2以此类推，而最好的将具有适应性N(种群中的染色体数).
The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population).
我看到了这些 link1 和 link2 ，据我了解，这是:
I saw these link1 and link2 and what i understood is that:
-
首先，我将对总体"的适应性"值进行排序.
First i will sort the Fitness value of the Population.
然后，如果人口总数"为10，则我将给人口选择概率为0.1,0.2,0.3，...，1.0.
Then if the Population number is 10 then i will give the probability of selection to the Population like 0.1,0.2,0.3,...,1.0 .
我的实现:
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
我是否了解算法错误??如果可以的话，谁能给我任何想法，如何修改我的轮盘赌来对选择进行排名?
Am i understanding the algo wrong?? If it is then can anyone give me any idea how to modify my roulette wheel to rank selection??
推荐答案
如果人口中有N个人，则最佳个人的排名为N，最差个人的排名为1
If the population has N individuals, the best individual gets rank N and the worst 1 then
TotalFitness = sum(Fitness);
应通过以下方式更改:
TotalFitness = (N + 1) * N / 2;
(可能TotalFitness不再是变量的正确名称，但是放开它吧)
(probably TotalFitness isn't anymore the right name for the variable, but let it go)
(N + 1) * N / 2只是等级的总和:
1 + 2 + ... + N = (N + 1) * N / 2
应将选择的概率从以下位置更改:
The probability of selection should be changed from:
ProbSelection(i) = Fitness(i) / TotalFitness;
到
ProbSelection(i) = i / TotalFitness;
这里使用等级代替适合度，并假设人口中的第一个人是最差的，而最后一个是最好的(排序后的人口).
Here using the rank instead of the fitness and assuming that the first individual of the population is the worst and the last is the best (sorted population).
因此，排序选择算法(O(N * log(N))决定了排名选择算法的复杂性.
Hence the complexity of the rank selection algorithm is dominated by the complexity of the sorting (O(N * log(N)).
您会看到选择最差的个人的概率为:
You can see that the probability of selection for the worst individual is:
1 / ((N + 1) * N / 2) = 2 / ((N + 1) * N)
获得最佳个人的概率为:
and the probability for the best individual is:
N / (((N + 1) * N / 2)) = 2 * (N + 1)
这是线性排名选择:排名呈线性增长.排名选择还有其他方案(例如指数级).
This is a linear rank selection: the ranks are in a linear progression. There are other schemes of rank selection (e.g. exponential).
这篇关于GA中的排名选择?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
