如何在遗传算法中进行基于秩的选择？

Question

我正在实现一个小的遗传算法框架 - 主要是供私人使用,除非我设法做出合理的事情,我将把它作为开源发布.现在我专注于选择技术.到目前为止,我已经实施了轮盘赌选择,随机通用抽样和锦标赛选择.我的列表中的下一个是基于排名的选择.与我已经实现的其他技术相比,我在查找相关信息方面遇到了一些困难,但到目前为止,这是我的理解.

1. 如果你的人口中有你想让下一轮的合理父母,你首先要通过它,并将每个人的适应度除以人口中的总体适应度.

2. 然后你使用其他一些选择技术(如轮盘赌轮)来实际确定选择谁进行繁殖.

它是否正确？如果是这样,我是否正确地认为排名调整是一种预处理步骤,然后必须采用实际选择程序来挑选候选人？如果我误解了这一点,请纠正我.我很感激任何额外的指示.

Answer 1

你所描述的只是轮盘赌选择.在轮盘选择中:

• 根据父母的健康状况选择父母
• 染色体越好,它们被选择的机会就越多.

想象一下轮盘赌轮,人口中的所有染色体都被放置,每个染色体的位置都相应于其适应度函数,如下图所示.
当企业差异很大时,这种选择会产生问题.杰出人士会在搜索开始时引入偏见,这可能导致过早收敛和失去多样性.
例如:

如果一个初始种群包含一个或两个非常适合但不是最好的个体而其他人群不好,那么这些适合的个体将迅速占据整个人口并阻止人们探索其他可能更好的个体.这种强有力的统治导致遗传多样性的非常高的损失,这对于优化过程肯定是不利的.

但在排名选择中:

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

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

3. 在此之后,所有染色体都有机会被选中.

4. 基于秩的选择方案可以避免过早收敛.
5. 但由于它根据适合度值对群体进行排序,因此计算成本可能很高.
6. 但是这种方法会导致收敛速度变慢,因为最好的染色体与其他染色体的差别不大.

所以过程将是:

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

2. 然后,如果人口数为10,则将选择概率给予人口,如0.1,0.2,0.3,...,1.0.

3. 然后计算累积的健身和制作轮盘赌轮.
4. 接下来的步骤与轮盘赌轮相同.

我在Matlab中实现排名选择:

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 2

你所描述的是轮盘赌选择,而不是排名选择.要进行排名选择,而不是通过其健身分数对每个候选人进行加权,您可以通过其"排名"(即最佳,次佳,第三最佳等)对其进行加权.

例如,你可能给第一个加权为1/2,第二个加权为1/3,第三个加权为1/4,等等.或者最差加权为1,第二个加权加权为2,等等

重要的一点是,不考虑绝对或相对健康分数,只考虑排名.因此,最好的选择比第二好的更有可能,但是两者具有相同的选择概率,无论最佳得分是第二好的得分的十倍,还是只有略高的得分.