遗传算法之轮盘赌算法

Abstracts

Fitness proportionate selection, also known as roulette wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination.

原理

轮盘赌选择法（roulette wheel selection）是最简单也是最常用的选择方法，在该方法中，各个个体的选择概率和其适应度值成比例，适应度越大，选中概率也越大。但实际在进行轮盘赌选择时个体的选择往往不是依据个体的选择概率，而是根据“累积概率”来进行选择。

算法过程

以一个实例来讲述轮盘赌选择法的具体过程，现有一个抽奖轮盘如下：

显然，当我们直接转动轮盘时抽到“参与奖”的概率最大，因为它占总体的比例最高，这也体现了“轮盘赌选择法”中所占比例越大被选中概率越高的思想。但我们一般不采用抽中“几等奖”的概率这种定性的指标来表述每个部分被选中的概率，而是引入“适应度”与“累积概率”的概念，其中每个部分被选中的概率与其适应度值成比例。设某一部分的适应度值表示为，该部分被选中的概率为，累积概率为，对应的计算公式如下

where is the number of individuals in the population.

上式中的累积概率表示每个个体之前所有个体的选择概率之和，它相当于在转盘上的“跨度”，“跨度”越大越容易选到，就相当于概率论中的概率分布函数。

算法过程

轮盘赌选择法的过程如下：

计算每个个体的被选中概率
计算每个部分的累积概率
随机生成一个数组，数组中的元素取值范围在 0 和 1 之间，并将其按从小到大的方式进行排序。若累积概率大于数组中的元素，则个体被选中，若小于，则比较下一个个体直至选出一个个体为止。
若需要转中个个体，则将步骤（3）重复次即可

看了上面的选择过程我们可能有这样的疑问：由于个体的选择是以“累积概率”为标准的，但一个个体的累积概率大并不表示它的选中也大，因为根据的计算公式我们知道累积概率表示的是每个个体之前所有个体的选择概率之和，这难道不会导致某些个体明明选中概率很小但却因为它位置靠后而导致其累积概率很大而被选中的情况发生吗？显然这与轮盘赌选择法的初衷是矛盾的啊！

为了验证上述情况是否会发生，以上面的“轮盘抽奖游戏”为例，给每个奖项给定一个编号，编号的数字代表了他在总体中的位置，如下：

由表格可以看到：“一等奖”的选中概率最小，但却因为其编号最大导致其累积概率为1，那是否会出现一等奖百分比会被选中的事件出现呢？为了验证结果，在Matlab中进行实验。进行1000次轮盘抽奖，并记录每次抽奖的编号，得到结果如下表所示:

从最终的结果可以看出，采用累积概率的方式并没有出现“抽中一等奖”事件的概率很大的结果，反而最终的结果和每个奖项的选中概率相近，这说明采用累积概率的轮盘赌选择法是切实可行的，且其选择结果误差很小。

%%% roulette wheel selection
fitvalue=[4 3 2 1]; %奖项对应的适应度值
totalf=sum(fitvalue); %适应值之和
p=fitvalue./totalf; %单个个体被选中的概率
q=cumsum(p); %每个个体的累积概率
c1=0; %用于存放编号1被选中的次数
c2=0; %用于存放编号2被选中的次数
c3=0; %用于存放编号3被选中的次数
c4=0; %用于存放编号4被选中的次数
while c1+c2+c3+c4<=1000
    fitin=1;
    newin=1;
    m=sort(rand(4,1)); %生成一组从小到大排列的随机数组
    while newin<=4
        if q(fitin)>m(newin)
            s(newin)=fitin; %s用来存放每次被选中的个体的编号
            switch s(newin)
                case 1
                    c1=c1+1;
                case 2
                    c2=c2+1;
                case 3
                    c3=c3+1;
                case 4
                    c4=c4+1;
            end
            newin=newin+1;
        else
            fitin=fitin+1;
        end
    end
end
disp('***************************************')
disp(['抽中“参与奖”的次数为：',num2str(c1)]);
disp(['抽中“参与奖”的概率为：',num2str(c1/1000)]);
disp('***************************************')
disp(['抽中“三等奖”的次数为：',num2str(c2)]);
disp(['抽中“三等奖”的概率为：',num2str(c2/1000)]);
disp('***************************************')
disp(['抽中“二等奖”的次数为：',num2str(c3)]);
disp(['抽中“二等奖”的概率为：',num2str(c3/1000)]);
disp('***************************************')
disp(['抽中“一等奖”的次数为：',num2str(c4)]);
disp(['抽中“一等奖”的概率为：',num2str(c4/1000)]);
disp('***************************************')

参考：

轮盘赌算法-知乎

Fitness proportionate selection-Wikipedia

BioStudy