GA中的排名选择？

Question

我已经实施Roulette wheel selection了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

现在我是想实现rank selection在GA.我了解到:

• 排名选择首先对人群进行排名,然后每个染色体从该排名中获得适应性.

• 最差的将是健身1,第二差2等等,最好的将具有适应度N(人口中的染色体数量).
  

我看到了这些link1和link2,我理解的是:

1. 首先,我将对人口的健身价值进行排序.

2. 然后,如果人口数量是10,那么我将给予人口选择的概率,如0.1,0.2,0.3,...,1.0.

3. 然后我将计算累积健身像轮盘赌轮.
4. 接下来的步骤与轮盘赌轮相同.

我的实施:

  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

我理解算法错了吗？如果它是那么任何人都可以给我任何想法如何修改我的轮盘赌排名选择？

Answer 1

如果人口中有N个体,那么最好的个体就会获得排名N,而最差的个人1则是最差

TotalFitness = sum(Fitness);

应改为:

TotalFitness = (N + 1) * N / 2;

(可能TotalFitness不再是变量的正确名称,但让它去吧)

(N + 1) * N / 2 只是排名的总和:

1 + 2 + ... + N = (N + 1) * N / 2

选择的概率应改为:

ProbSelection(i) = Fitness(i) / TotalFitness;

至

ProbSelection(i) = i / TotalFitness;

这里使用等级而不是适应度,并假设人口的第一个人是最差的,最后一个是最好的(排序的人口).

因此,秩选择算法的复杂性由sort(O(N * log(N))的复杂性决定.

您可以看到最差个体的选择概率是:

1 / ((N + 1) * N / 2) = 2 / ((N + 1) * N)

并且最佳个人的概率是:

N / (((N + 1) * N / 2)) = 2 * (N + 1)

这是线性排名选择:排名呈线性进展.还有其他等级选择方案(例如指数).