带有QoS约束的组播路由问题是一个NP完全问题，遗传模拟退火算法是遗传算法和模拟退火算法的一种融合，可以为这类问题提供一个解决方案，下面的程序是GreenSim团队核心成员在本科期间所做的
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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));
