mcrgsa.m

MCRGSA------组播路由问题遗传模拟退火算法 ％M-----------遗传算法进化代数 ％N-----------种群规模

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  MCRGSA------组播路由问题遗传模拟退火算法  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%M-----------遗传算法进化代数
%N-----------种群规模，取偶数
%Pm----------变异概率调节参数
%K-----------同一温度下状态跳转次数
%t0----------初始温度
%alpha-------降温系数
%beta--------浓度均衡系数
%ROUTES------备选路径集
%Num---------到各节点的备选路径数目
%Cost--------费用邻接矩阵
%Source------源节点标号
%End---------目的节点标号组成的向量
%MBR---------各代最优路径编码
%MBF---------各代最优路径
function [MBR,MBF]=MCRGSA(M,N,Pm,K,t0,alpha,beta,ROUTES,Num,Cost,Source,End)
%第一步:常用变量声明，以及种群初始化
Num_end=length(End);%组播目的节点个数
farm=zeros(N,Num_end);%种群
for i=1:Num_end
    farm(:,i)=unidrnd(Num(i),N,1);%随机生成初始种群
end
m=1;
t=t0;
MBR=zeros(M,Num_end);
MBF=zeros(M,1);

while m<=M%设置停止条件
    
    %第二步：按照变异概率调节参数进行变异以及退火选择
    P=Num./sum(Num);
    P=Pm.*P;
    for i=1:N%对每一个个体都执行
        Code=farm(i,:);%临时取出
        k=1;
        while k<=K%每一个温度下改变K次
            for j=1:Num_end
                if rand<P(j)
                    Bit=randperm(Num(j));
                    pos=find(Bit~=Code(j));
                    Code(j)=Bit(pos(1));
                end
            end
            fit1=ShiYinZhi(ROUTES,Cost,farm(i,:));%计算适应值
            fit2=ShiYinZhi(ROUTES,Cost,Code);
            if fit2<fit1
                farm(i,:)=Code;
            elseif rand<exp((fit1-fit2)/(fit1*t));
                farm(i,:)=Code;
            else
                Code=farm(i,:);
            end
            k=k+1;
        end
    end
    
    %第三步：交叉算法
    Farm=zeros(size(farm));
    for i=1:2:(N-1);
        a=farm(i,:);
        b=farm(i+1,:);
        pos=unidrnd(Num_end-1);
        A=[a(1,1:pos),b(1,(pos+1):end)];
        B=[b(1,1:pos),a(1,(pos+1):end)];
        Farm(i,:)=A;
        Farm(i+1,:)=B;
    end
    FARM=[farm;Farm];
    
    %第四步：选择复制操作
    fitness=zeros(1,2*N);
    for i=1:(2*N)
        fitness(i)=ShiYinZhi(ROUTES,Cost,FARM(i,:));
    end
    maxfitness=max(fitness);
    minfitness=min(fitness);
    pos=find(fitness==maxfitness);
    MBR(m,:)=FARM(pos(1),:);
    MBF(m)=minfitness;
    for i=1:(2*N)
        fitness(i)=((maxfitness-fitness(i))/(maxfitness-minfitness+0.00005))^beta;
    end
    fitness=fitness./(sum(fitness)+0.000000005);
    FITNESS=zeros(size(fitness));
    Sgn=FITNESS;
    for i=1:(2*N)
        FITNESS(i)=sum(fitness(1:i));
    end
    while sum(Sgn)<N
        Pos=find(FITNESS>=rand);
        if length(Pos)>0
          Sgn(Pos(1))=1;
        end
    end
    POS=find(Sgn==1);
    for i=1:N
        farm(i,:)=FARM(POS(i),:);
    end
    farm(unidrnd(N),:)=MBR(m,:);
    
    %更新参数
    m=m+1
    t=t*alpha;
end
plot(MBF)
title('遗传模拟退火算法收敛图')
xlabel('进化代数')
ylabel('费用')
%译码计算适应值的函数
%ROUTES--------备选路径集
%Cost----------费用邻接矩阵
%Code----------组播树的编码
%fit-----------组播树的总代价作为适应值
function fit=ShiYinZhi(ROUTES,Cost,Code)
CC=zeros(size(Cost));
for i=1:length(Code)
    R=ROUTES{i}{Code(i)};
    J=length(R)-1;
    for j=1:J
        a=R(j);
        b=R(j+1);
        CC(a,b)=Cost(a,b);
    end
end
fit=sum(sum(CC));