QoS组播路由问题的蚁群算法通用MATLAB源码.doc

QoS组播路由问题的蚁群算法通用MATLAB源码(2008-11-15 09:44:55)标签：杂谈 题目：QoS组播路由问题的蚁群算法通用MATLAB源码function MRT,EDGES,cost=ACA_QoS_MR(C,D,S,E,Dmax,K,M,Alpha,Beta,Gamma,Tau,Rho,Q)% Ant Colony Algorithm for QoS Multicast Routing% QoS组播路由蚁群算法% GreenSim团队原创作品，转载请注明% Email:% GreenSim团队主页：/greensim% color=red欢迎访问GreenSim算法仿真团队url=/greensim/greensim/url/color% 输入参数列表% C 费用邻接矩阵（NN）% D 延时邻接矩阵（NN）% S 源节点% E 组播目的节点（行向量）% Dmax 延时约束% K 迭代次数（指蚂蚁出动多少波）% M 蚂蚁个数（每一波蚂蚁有多少个）% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子（费用）重要程度的参数% Gamma 表征启发式因子（延时）重要程度的参数% Tau 初始信息素矩阵% Rho 信息素蒸发系数% Q 信息素增加强度系数% 输出参数列表% MRT 最优组播树（01邻接矩阵表示）% EDGES 最优组播树所有的边% cost 最优组播树的费用% 第一步：变量初始化N=size(C,1);%网络节点个数为NP=length(E);%目的节点个数为MMRT=zeros(N,N);cost=inf;ROUTES=cell(P,K,M);%用细胞结构存储到每一个目的节点的每一代的每一只蚂蚁的爬行路线DELAYS=inf*ones(P,K,M);%用三维数组存储每代每个蚂蚁爬行到各个目的节点的延时COSTS=inf*ones(P,K,M);%用三维数组存储每代每个蚂蚁爬行到各个目的节点的费用% 第二步：启动到P个目的节点的K轮蚂蚁觅食活动，每轮派出M只蚂蚁for p=1:P Tau=ones(N,N); for k=1:K for m=1:M% 第三步：状态初始化 W=S;%当前节点初始化为起始点 Path=S;%爬行路线初始化 PD=0;%爬行路线延时初始化 PC=0;%爬行路线费用初始化 TABU=ones(1,N);%禁忌表初始化 TABU(S)=0;%S已经在初始点了，因此要排除 CC=C;%费用邻接矩阵备份 DD=D;%延时邻接矩阵备份% 第四步：下一步可以前往的节点 DW=DD(W,:); DW1=find(DWinf); for j=1:length(DW1) if TABU(DW1(j)=0 DW(j)=inf; end end LJD=find(DW=1)% 第五步：转轮赌法选择下一步怎么走 PP=zeros(1,Len_LJD); for i=1:Len_LJD PP(i)=(Tau(W,LJD(i)Alpha)*(C(W,LJD(i)Beta)*(D(W,LJD(i)Gamma); end PP=PP/(sum(PP);%建立概率分布 Pcum=cumsum(PP); Select=find(Pcum=rand); to_visit=LJD(Select(1);%下一步将要前往的节点% 第六步：状态更新和记录 Path=Path,to_visit;%路径增加 PD=PD+DD(W,to_visit);%路径延时累计 PC=PC+CC(W,to_visit);%路径费用累计 W=to_visit;%蚂蚁移到下一个节点 for kk=1:N if TABU(kk)=0 CC(W,kk)=inf; CC(kk,W)=inf; DD(W,kk)=inf; DD(kk,W)=inf; end end TABU(W)=0;%已访问过的节点从禁忌表中删除 DW=DD(W,:); DW1=find(DWinf); for j=1:length(DW1) if TABU(DW1(j)=0 DW(j)=inf; end end LJD=find(DWinf);%可选节点集 Len_LJD=length(LJD);%可选节点的个数% end% 第七步：记下每一代每一只蚂蚁的觅食路线和路线长度 ROUTESp,k,m=Path; if Path(end)=E(p)&PD=Dmax DELAYS(p,k,m)=PD; COSTS(p,k,m)=PC; else DELAYS(p,k,m)=inf; COSTS(p,k,m)=inf; end end% 第八步：更新信息素 Delta_Tau=zeros(N,N);%更新量初始化 for m=1:M if COSTS(p,k,m)inf&DELAYS(p,k,m)Dmax ROUT=ROUTESp,k,m; TS=length(ROUT)-1;%跳数 Cpkm=COSTS(p,k,m); for s=1:TS x=ROUT(s); y=ROUT(s+1); Delta_Tau(x,y)=Delta_Tau(x,y)+Q/Cpkm; Delta_Tau(y,x)=Delta_Tau(y,x)+Q/Cpkm; end end end Tau=(1-Rho).*Tau+Delta_Tau;%信息素挥发一部分，新增加一部分 endend% 第九步：整理输出结果MINCOSTS=NaN*ones(1,K);allcost=zeros(1,0);for k=1:K for m=1:M COSTkm=COSTS(:,k,m); DELAYkm=DELAYS(:,k,m); if sum(COSTkm)inf&sum(DELAYkm)inf Tree=zeros(N,N); for p=1:P path=ROUTESp,k,m; RLen=length(path); for i=1:(RLen-1) Tree(path(i),path(i+1)=1; Tree(path(i+1),path(i)=1; end end TC=Tree.*C; for ii=1:N for jj=1:N if isnan(TC(ii,jj) TC(ii,jj)=0; end end end mincost=0.5*sum(sum(TC); if mincostcost MINCOSTS(1,k)=mincost; MRT=Tree; cost=mincost; end allcost=allcost,cost; end endendMM=triu(MRT);T1=find(MM=1);T2=ceil(T1/N);T3=mod(T1,N);EDGES=T3,T2;% 绘收敛曲线figure(1)COSTS2=zeros(M,K,P);DELAYS2=zeros(M,K,P);for p=1:P for k=1:K for m=1:M if COSTS(p,k,m)0); pos2=find(delays0); len1=length(pos1); len2=length(pos2); LC1(k)=sum(costs)/len1; LC2(k)=sum(delays)/len2;endplot(LC1,ko-);hold onplot(LC2,bs-);legend(费用,延时)title(路径的费用延时变化情况)figure(2)plot(allcost,b-