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. 那么如果 Population 数量是 10，那么我将给出选择 Population 的概率，例如 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;

这里使用排名而不是适应度，并假设种群中的第一个个体是最差的，最后一个个体是最好的（排序种群）。

因此，排名选择算法的复杂度由排序的复杂度决定（

O(N * log(N)

）。

可以看到，选择最差个体的概率为：

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

最佳个体的概率为：

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

这是一个线性排名选择：排名呈线性进展。还有其他排名选择方案（例如指数）。

Answer 2

如果任意两个适应度值相同怎么办？您为两者分配相同的值吗？