GA中的排名选择是什么？

Question

GA中的排名选择是什么？

3

我在遗传算法中实现了轮盘赌选择。

   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

现在我正在尝试在遗传算法中实现排名选择。我了解到：

排名选择首先对种群进行排名，然后每个染色体从这个排名中获得适应度。
最差的将拥有适应度1，第二差的适应度为2等等，而最好的将拥有适应度N（种群中染色体的数量）。

我看到了这些链接1和链接2，我所理解的是：

首先，我将对种群的适应度值进行排序。
然后，如果种群数量为10，则我将为种群分配选择概率，如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

我是否误解了算法？如果是这样，有人能否给我任何修改我的轮盘赌选择方法的想法吗？

- Setu Kumar Basak

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- manlio · Accepted Answer

如果总人口为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;

to

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)

这是一种线性排名选择：排名按线性递进方式。还有其他排名选择方案（例如指数）。