GA中的排名选择?

编程入门行业动态更新时间:2024-10-23 17:37:17

本文介绍了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中的排名选择?