基于matlab的遗传算法简单实例--浅谈精英策略和轮盘赌

首先要了解遗传算法的一些基本概念：

• 基因型(genotype)：性状染色体的内部表现；
• 表现型(phenotype)：染色体决定性状的外部表现，或者说，根据基因型形成的个体；
• 进化(evolution)：逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
• 适应度(fitness)：度量某个物种对于生存环境的适应程度。
• 选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
• 复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
• 交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
• 变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
• 编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
• 解码(decoding)：基因型到表现型的映射。
• 个体（individual）：指染色体带有特征的实体；是问题的一个解
• 种群（population）：个体的集合，该集合内个体数称为种群的大小，根据适应函数选择产生的一组解。

遗传算法的精髓就在于自然选择。

算法中有三个主要算子，重组、变异、选择。重组的作用是稳定朝着最优解的方向进化。变异的作用是保证解空间的良好搜索。选择的作用是适者生存。

选择的算法有很多，如轮盘选选择、随机遍历选择、截断选择、锦标赛选择、局部选择等等

本文对选择中的轮盘赌和精英策略用一简单实例来进行对比。

从GA的整个选择策略来讲，精英选择是群体收敛到优化问题最优解的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将当前群体最佳个体或者适应度大于下一代最佳个体适应值的多个个体直接复制到下一代，随机替代或替代最差的下一代群体中的相应数量的个体。采用这种策略的遗传算法，一般称为基于精英选择模型的遗传算法。

轮盘赌选择又称比例选择算子。基本思想：个体被选中的概率与其适应度函数值成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：

设想群体全部个体的适当性分数由一张饼图来代表。群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性分数成比例，适应性分数愈高，它在饼图中对应的小块所占面积也愈大。为了选取一个染色体，要做的就是旋转这个轮子，直到轮盘停止时，看指针停止在哪一块上，就选中与它对应的那个染色体。

遗传算法的基本流程

问题：

以y=(x-15)^2，x的范围是0-31为例，求y的最小值。进行算法编程实验，选用两种以上不同的进化/淘汰机制，对遗传算法的效果进行比较。

这里x的范围0-31，我们刚好把表现型编码为00000-11111的二进制数。为方便起见，每一代取4个个体，第一代是随机生成，后面就开始选择、变异、进化。x取到的值带入算式再通过适应度函数即可算出选择所需的适应度。

function Y=genetic     %此函数是初始化加轮盘赌后的结果。
    num =5;gt =4;
    a = unifrnd(0,1,gt,num);aa = zeros(1,gt);
    for i = 1:1:gt
        for j = 1:1:num
            if a(i,j) < 0.5
                a(i,j) = 0;
            else
                a(i,j) =1;
            end
            aa(i) = aa(i) + a(i,j) * 2^(num-j);
        end
    end
    %%   适应度计算
    fitsum =0;
    for i =1:1:gt
        fitsum = 300-(aa(i)-15)^2 +fitsum;
        A1(i) = i;
    end
    for i =1:1:gt
        fits(i) = (300-(aa(i)-15)^2 )/fitsum;
    end
    for i = 1:1:gt
        A1(i) = i;

        if i == 1 
            acc(i) = fits(i);
        else
            acc(i) = fits(i)+acc(i-1);
        end
    end
    %自然选择列表记录 list的编号即为轮盘赌的结果
    while 1
        r = rand([4 1]);
        for i = 1:1:gt
            if r(i) <= acc(1) 
                list(i) = 1;
            elseif r(i) <= acc(2) 
                list(i) = 2;
            elseif r(i) <= acc(3) 
                list(i) = 3;
            else r(i) <= acc(4) 
                list(i) = 4;
            end
        end
        if list(1)~=list(2) && list(2)~=list(3) && list(1)~=list(3)
            break
        end          
    end
    A = A1';A(:,2) = aa';A(:,3) = fits';A(:,4) = acc';A(:,5) = list';
Y=A;
end

%%  轮盘赌算法    以4个个体为例
%编码后进制转换
%例子为 y = （x-15）^2 的最小值

%% 十进制转二进制后转为矩阵形式
function tt=tm(a) 
    s=reshape(str2num((dec2bin (a))'),[],1)';   %可能少了首位的0 这就不能与之交换
    if length(dec2bin(a)) ==1;        %移位处理
        ss = [0,0,0,0,s];
    elseif  length(dec2bin(a)) ==2;
        ss = [0,0,0,s];
    elseif  length(dec2bin(a)) ==3;
        ss = [0,0,s];
    elseif  length(dec2bin(a)) ==4;
        ss = [0,s];
    else
        ss=s;
    end
    tt =ss;
end

这里的适应度函数是

 Fi（x） = （300-（x-15）^2）/sum(F(i))
 F（i）是每个x取到值后带入表达式得到的值，把他们加起来即是sumF（i）

%% 交叉  基本遗传算法（SGA）中交叉算子采用单点交叉算子
function  cc=gen3(a)
% 开始交叉   011 |00  这样的模式  手动模式交叉完的结果是cross
cross=a;   c=0;
c = cross(1,4);  cross(1,4) = cross(2,4); cross(2,4)=c;
c = cross(1,5);  cross(1,5) = cross(2,5); cross(2,5)=c;
c = cross(3,4);  cross(3,4) = cross(4,4); cross(4,4)=c;
c = cross(3,5);  cross(3,5) = cross(4,5); cross(4,5)=c;
    for i = 1:1:4
        for j = 1:1:5
           b =rand(1);
           vary = 0.01;
           if  b


%重新评价适应度
function hello=gen2(a)
    num =5;gt =4;
    fitsum =0;
    aa = zeros(1,gt);
    for i = 1:1:gt
        for j = 1:1:num
            if a(i,j) < 0.5
                a(i,j) = 0;
            else
                a(i,j) =1;
            end
            aa(i) = aa(i) + a(i,j) * 2^(num-j);
        end
    end
    for i =1:1:gt
        fitsum = 300-(aa(i)-15)^2 +fitsum;
        A1(i) = i;
    end
    for i =1:1:gt
        fits(i) = (300-(aa(i)-15)^2 )/fitsum;
    end
    for i = 1:1:gt
        A1(i) = i;
        if i == 1 
            acc(i) = fits(i);
        else
            acc(i) = fits(i)+acc(i-1);
        end
    end
    %自然选择列表记录 list的编号即为轮盘赌的结果
    r = rand([4 1]);
    for i = 1:1:gt
        if r(i) <= acc(1) 
            list(i) = 1
        elseif r(i) <= acc(2) 
            list(i) = 2
        elseif r(i) <= acc(3) 
            list(i) = 3
        else r(i) <= acc(4) 
            list(i) = 4
        end
    end
    A = A1';A(:,2) = aa';A(:,3) = fits';A(:,4) = acc';A(:,5) = list';
    hello =A;
end

轮盘赌

clc
clear
%% 本文用迭代次数来评价选择策略的优劣程度
%  迭代的越少就达到目标值就说明策略较优
%轮盘赌选3个 怎么选 怎么淘汰
%淘汰后补位   一轮选择后    
A =genetic;
num =5;gt =4;log=0;n=1;
while 1
    k1=A(1,5);k2=A(2,5);k3=A(3,5);
    a1 =A(k1,2);a2 =A(k2,2);a3 =A(k3,2);  %轮盘赌过程
    a4 = unifrnd(0,1,1,5);
    a5=0;
     for j = 1:1:5
            if a4(j) < 0.5
                a4(j) = 0;
            else
                a4(j) =1;
            end
        a5 = a5 + a4(j) * 2^(5-j);
     end
    b =[a1,a2,a3,a5];
    
     fitsum =0;
    for i =1:1:gt
        fitsum = 300-(b(i)-15)^2 +fitsum;
        A1(i) = i;
    end
    for i =1:1:gt
        fits(i) = (300-(b(i)-15)^2 )/fitsum;
        A1(i) = i;
    end
     B = A1';B(:,2) = b';B(:,3) = fits'; %B为选择后的列表
    %% 十进制转二进制后转为矩阵形式
    for i=1:1:4
        C(i,:)=tm(b(i));
    end
    CC=gen3(C);       %交叉、变异完成后的CC矩阵
    %%
    A=gen2(CC);       %已重新评价适应度并轮盘选  此A非彼A
    n = n+1;       %n为迭代次数   
    for i =1:1:4
        if A(i,2) ==15
            log =1;
            break;
        else
            log =0;
        end
     end
     if log == 1
         break
     end
end   
n

% 第1次轮盘赌结果是迭代了11次达到最优解
% 第2次轮盘赌结果是迭代了15次达到最优解
% 第3次轮盘赌结果是迭代了4次达到最优解
% 第4次轮盘赌结果是迭代了6次达到最优解
% 第5次轮盘赌结果是迭代了9次达到最优解

精英策略

%% 精英策略
function  Y=elite
    A=genetic;   %初始化
    for i=1:1:4
        C(i,:)=tm(A(i,2));
    end
    BB =gen3(C);    %交叉+选择
    B=gen2(BB);    %再评价
    A1 =A(:,2:3);  %一代
    B1 =B(:,2:3);   %二代
    B2 =B(:,2:3);
    A2=[];
    for i =1:1:4
        if A1(i,2) > max(B1(:,2))
            A2(1,:) =A1(i,:);
            break
        end
    end
    t =1;
    for i=1:1:4   
        if min(B1(:,2)) == B1(i,2)
            break;
        else
            t =t+1;
        end
    end  
    if  isempty(A2)
        disp('无精英')
    else
        B2(t,:) =A2;
    end
    %B2是精英选择后的结果
    Y =B2;
end



%%
n=1;log=0;
while 1
    R =elite_1;     
    for i =1:1:4
        if R(i,1) ==15
            log =1;
            break;
        else
            log =0;
        end
     end
     if log == 1
         break
     end
     n = n+1;       %n为迭代次数 
end
n
% 第1次精英策略结果是迭代了6次达到最优解
% 第2次精英策略结果是迭代了3次达到最优解
% 第3次精英策略结果是迭代了2次达到最优解
% 第4次精英策略结果是迭代了3次达到最优解
% 第5次精英策略结果是迭代了4次达到最优解


由上结果观察知：本例子中选择的策略为精英策略会比轮盘赌策略的收敛性更好。


第一次写，如有出错，欢迎大佬们指教批评。