您所在位置：主题：[原创]选播路由问题的粒子群优化算法MATLAB源码
greensim
[专家分：0] 发布于 2009-07-26 17:28:00
选播路由问题的粒子群优化算法MATLAB源码
%% QoS选播路由的粒子群算法仿真主函数
%% 第一步：产生网络拓扑结构
BorderLength=10; %正方形区域的边长，单位：km
NodeAmount=30; %网络节点的个数
Alpha=10; %网络特征参数，Alpha越大，短边相对长边的比例越大
Beta=5; %网络特征参数，Beta越大，边的密度越大
PlotIf=1; %是否画网络拓扑图，如果为1则画图，否则不画
FlagIf=0; %是否标注参数，如果为1则将标注边的参数，否则不标注
[Sxy,AM,Cost,Delay,DelayJitter,PacketLoss]=NetCreate(BorderLength,NodeAmount,Alpha,Beta,PlotIf,FlagIf);
%% 第二步：使用粒子群算法搜索最优路径，存储数据，输出最优结果和收敛曲线
% GreenSim团队原创作品，转载请注明
% GreenSim团队长期从事算法设计、代写程序等业务
% 欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url]
%%%%%%%%%%%%%%%%% 以 下 是 参 数 设 置 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
S=[2,4]; %源节点的集合，用向量存储
T=[25,27,29]; %目的节点的几何，用向量存储
Alpha=1; %适应值计算式中费用的系数
Beta=5e5; %适应值计算式中延时的系数
Gamma=3e6; %适应值计算式中延时抖动的系数
Delta=1000; %适应值计算式中丢包率的系数
QoSD=100e-6; %延时的QoS约束
QoSDJ=100e-6; %延时抖动的QoS约束
QoSPL=0.02; %丢包率的QoS约束
r1=0.1; %单个粒子的历史最优个体对当前粒子的影响系数，0<r1<=1
r2=0.3; %粒子群的全局最优个体对当前粒子的影响系数，0<r2<=1
r3=0.2; %粒子随机游动的影响系数，0<=r3<=1，r3可以为0，这时将关闭随机游动功能
P=10; %粒子的个数
Q=20; %迭代次数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
m=length(S);
n=length(T);
AllRoutes=cell(m,n);%各粒子经过的全部路径
AllFitness=cell(m,n);
HistoryBestRoutes=cell(m,n);%各粒子的历史最优路径
HistoryBestFitness=cell(m,n);
AllBestRoutes=cell(m,n);%全局最优路径
AllBestFitness=cell(m,n);
for i=1:m
for j=1:n
s=S(i);
t=T(j);
[ROUTEst,FitFlag,HR,HFF,AR,AFF]=PSOUC(s,t,r1,r2,r3,P,Q,AM,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta);
AllRoutes{i,j}=ROUTEst;
AllFitness{i,j}=FitFlag;
HistoryBestRoutes{i,j}=HR;
HistoryBestFitness{i,j}=HFF;
AllBestRoutes{i,j}=AR;
AllBestFitness{i,j}=AFF;
end
end
%下面整理最优结果
SYZ=Inf;
FinalRoute=[];%最终的最优路由
FinalFitness=[];%最终的最优路由对应的参数
LearnCurve1=zeros(1,Q);%收敛曲线
LearnCurve2=zeros(1,Q);%收敛曲线
for q=1:Q
TT=[];
for i=1:m
for j=1:n
ABR=HistoryBestRoutes{i,j};
ABF=HistoryBestFitness{i,j};
for p=1:P
ABRq=ABR{p,q};
ABFq=ABF{p,q};
TT=[TT,ABFq(1,1)];
if ABFq(1,1)<SYZ
FinalRoute=ABRq;
FinalFitness=ABFq;
SYZ=ABFq(1,1);
end
end
end
end
LearnCurve1(q)=mean(TT);
LearnCurve2(q)=min(TT);
end
figure(2)
plot(LearnCurve1,'bs-')
xlabel('迭代次数')
ylabel('平均适应值')
figure(3)
plot(LearnCurve2,'bs-')
xlabel('迭代次数')
ylabel('最优粒子适应值')
function [ROUTEst,FitFlag,HR,HFF,AR,AFF]=PSOUC(s,t,r1,r2,r3,P,Q,AM,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta)
%% 使用粒子群算法求源节点s到目的节点t的满足QoS约束的最小费用路径，将这些路径及其参数记录下来
% GreenSim团队原创作品，转载请注明
% GreenSim团队长期从事算法设计、代写程序等业务
% 欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url]
%% 输入参数列表
% s 单个的源节点
% t 单个的目的节点
% r1 单个粒子的历史最优个体对当前粒子的影响系数，0<r1<=1
% r2 粒子群的全局最优个体对当前粒子的影响系数，0<r2<=1
% r3 粒子随机游动的影响系数，0<=r3<=1，r3可以为0，这时将关闭随机游动功能
% P 粒子的个数
% Q 迭代次数
% AM 01形式存储的邻接矩阵
% Cost 边的费用邻接矩阵
% Delay 边的时延邻接矩阵
% DelayJitter 边的延时抖动邻接矩阵
% PacketLoss 边的丢包率邻接矩阵
% QoSD 延时的QoS约束
% QoSDJ 延时抖动的QoS约束
% QoSPL 丢包率的QoS约束
% Alpha 适应值计算式中费用的系数
% Beta 适应值计算式中延时的系数
% Gamma 适应值计算式中延时抖动的系数
% Delta 适应值计算式中丢包率的系数
%% 输出参数列表
% ROUTEst P×Q的细胞结构，存储所有粒子经历过的从s到t的路径
% FitFlag P×Q的细胞结构，存储与ROUTEst对应的Fitness和Flag数据
% HR P×Q的细胞结构，存储所有粒子的历史最优路径
% HFF P×Q的细胞结构，存储所有粒子的历史最优路径对应的参数
% AR 1×Q的细胞结构，存储全局最优路径
% AR 1×Q的细胞结构，存储全局最优路径对应的参数
%% 粒子群初始化
ROUTEst=cell(P,Q);
FitFlag=cell(P,Q);
HR=cell(P,Q);%各粒子的历史最优路径
HFF=cell(P,Q);%各粒子的历史最优路径对应的参数
AR=cell(1,Q);%全局最优路径
AFF=cell(1,Q);%全局最优路径对应的参数
TRACK=Initialize(AM,s,P);
for p=1:P
Route=TRACK{p};
pos=find(Route==t);
Route=Route(1:pos(1));
Route=Fresh(Route);
ROUTEst{p,1}=Route;
HR{p,1}=Route;
[Fitness,Flag]=Fit(Route,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta);
FitFlag{p,1}=[Fitness;Flag];
HFF{p,1}=[Fitness;Flag];
end
SYZ=Inf;
for p=1:P
Route=HR{p,1};
FF=HFF{p,1};
if FF(1,1)<SYZ
AR{1}=Route;
SYZ=FF(1,1);
AFF{1}=FF;
end
end
%%
for q=2:Q
%按照粒子群迭代公式计算各个粒子的下一个位置
for p=1:P
Route=ROUTEst{p,q-1};
OptRoute1=HR{p,q-1};
OptRoute2=AR{1,q-1};
Route=SpecialAdd(Route,OptRoute1,r1,Cost);%向自己的历史最优位置靠近
Route=SpecialAdd(Route,OptRoute2,r2,Cost);%向全局历史最优位置靠近
Route=RandMove(Route,r3,AM);%随机游动
[Fitness,Flag]=Fit(Route,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta);
ROUTEst{p,q}=Route;
FitFlag{p,q}=[Fitness;Flag];
end
%更新各粒子的历史最优位置
for p=1:P
F1=HFF{p,q-1};
F2=FitFlag{p,q};
if F2(1,1)<F1(1,1)
HR{p,q}=ROUTEst{p,q};
HFF{p,q}=FitFlag{p,q};
else
HR{p,q}=HR{p,q-1};
HFF{p,q}=HFF{p,q-1};
end
end
%更新全局历史最优位置
for p=1:P
Route=HR{p,q};
FF=HFF{p,q};
if FF(1,1)<SYZ&&FF(2,1)==1
AR{q}=Route;
SYZ=FF(1,1);
AFF{q}=FF;
else
AR{q}=AR{q-1};
AFF{q}=AFF{q-1};
end
end
end
%% QoS选播路由的粒子群算法仿真主函数
%% 第一步：产生网络拓扑结构
BorderLength=10; %正方形区域的边长，单位：km
NodeAmount=30; %网络节点的个数
Alpha=10; %网络特征参数，Alpha越大，短边相对长边的比例越大
Beta=5; %网络特征参数，Beta越大，边的密度越大
PlotIf=1; %是否画网络拓扑图，如果为1则画图，否则不画
FlagIf=0; %是否标注参数，如果为1则将标注边的参数，否则不标注
[Sxy,AM,Cost,Delay,DelayJitter,PacketLoss]=NetCreate(BorderLength,NodeAmount,Alpha,Beta,PlotIf,FlagIf);
%% 第二步：使用粒子群算法搜索最优路径，存储数据，输出最优结果和收敛曲线
% GreenSim团队原创作品，转载请注明
% GreenSim团队长期从事算法设计、代写程序等业务
% 欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url]
%%%%%%%%%%%%%%%%% 以 下 是 参 数 设 置 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
S=[2,4]; %源节点的集合，用向量存储
T=[25,27,29]; %目的节点的几何，用向量存储
Alpha=1; %适应值计算式中费用的系数
Beta=5e5; %适应值计算式中延时的系数
Gamma=3e6; %适应值计算式中延时抖动的系数
Delta=1000; %适应值计算式中丢包率的系数
QoSD=100e-6; %延时的QoS约束
QoSDJ=100e-6; %延时抖动的QoS约束
QoSPL=0.02; %丢包率的QoS约束
r1=0.1; %单个粒子的历史最优个体对当前粒子的影响系数，0<r1<=1
r2=0.3; %粒子群的全局最优个体对当前粒子的影响系数，0<r2<=1
r3=0.2; %粒子随机游动的影响系数，0<=r3<=1，r3可以为0，这时将关闭随机游动功能
P=10; %粒子的个数
Q=20; %迭代次数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
m=length(S);
n=length(T);
AllRoutes=cell(m,n);%各粒子经过的全部路径
AllFitness=cell(m,n);
HistoryBestRoutes=cell(m,n);%各粒子的历史最优路径
HistoryBestFitness=cell(m,n);
AllBestRoutes=cell(m,n);%全局最优路径
AllBestFitness=cell(m,n);
for i=1:m
for j=1:n
s=S(i);
t=T(j);
[ROUTEst,FitFlag,HR,HFF,AR,AFF]=PSOUC(s,t,r1,r2,r3,P,Q,AM,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta);
AllRoutes{i,j}=ROUTEst;
AllFitness{i,j}=FitFlag;
HistoryBestRoutes{i,j}=HR;
HistoryBestFitness{i,j}=HFF;
AllBestRoutes{i,j}=AR;
AllBestFitness{i,j}=AFF;
end
end
%下面整理最优结果
SYZ=Inf;
FinalRoute=[];%最终的最优路由
FinalFitness=[];%最终的最优路由对应的参数
LearnCurve1=zeros(1,Q);%收敛曲线
LearnCurve2=zeros(1,Q);%收敛曲线
for q=1:Q
TT=[];
for i=1:m
for j=1:n
ABR=HistoryBestRoutes{i,j};
ABF=HistoryBestFitness{i,j};
for p=1:P
ABRq=ABR{p,q};
ABFq=ABF{p,q};
TT=[TT,ABFq(1,1)];
if ABFq(1,1)<SYZ
FinalRoute=ABRq;
FinalFitness=ABFq;
SYZ=ABFq(1,1);
end
end
end
end
LearnCurve1(q)=mean(TT);
LearnCurve2(q)=min(TT);
end
figure(2)
plot(LearnCurve1,'bs-')
xlabel('迭代次数')
ylabel('平均适应值')
figure(3)
plot(LearnCurve2,'bs-')
xlabel('迭代次数')
ylabel('最优粒子适应值')
function [ROUTEst,FitFlag,HR,HFF,AR,AFF]=PSOUC(s,t,r1,r2,r3,P,Q,AM,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta)
%% 使用粒子群算法求源节点s到目的节点t的满足QoS约束的最小费用路径，将这些路径及其参数记录下来
% GreenSim团队原创作品，转载请注明
% GreenSim团队长期从事算法设计、代写程序等业务
% 欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url]
%% 输入参数列表
% s 单个的源节点
% t 单个的目的节点
% r1 单个粒子的历史最优个体对当前粒子的影响系数，0<r1<=1
% r2 粒子群的全局最优个体对当前粒子的影响系数，0<r2<=1
% r3 粒子随机游动的影响系数，0<=r3<=1，r3可以为0，这时将关闭随机游动功能
% P 粒子的个数
% Q 迭代次数
% AM 01形式存储的邻接矩阵
% Cost 边的费用邻接矩阵
% Delay 边的时延邻接矩阵
% DelayJitter 边的延时抖动邻接矩阵
% PacketLoss 边的丢包率邻接矩阵
% QoSD 延时的QoS约束
% QoSDJ 延时抖动的QoS约束
% QoSPL 丢包率的QoS约束
% Alpha 适应值计算式中费用的系数
% Beta 适应值计算式中延时的系数
% Gamma 适应值计算式中延时抖动的系数
% Delta 适应值计算式中丢包率的系数
%% 输出参数列表
% ROUTEst P×Q的细胞结构，存储所有粒子经历过的从s到t的路径
% FitFlag P×Q的细胞结构，存储与ROUTEst对应的Fitness和Flag数据
% HR P×Q的细胞结构，存储所有粒子的历史最优路径
% HFF P×Q的细胞结构，存储所有粒子的历史最优路径对应的参数
% AR 1×Q的细胞结构，存储全局最优路径
% AR 1×Q的细胞结构，存储全局最优路径对应的参数
%% 粒子群初始化
ROUTEst=cell(P,Q);
FitFlag=cell(P,Q);
HR=cell(P,Q);%各粒子的历史最优路径
HFF=cell(P,Q);%各粒子的历史最优路径对应的参数
AR=cell(1,Q);%全局最优路径
AFF=cell(1,Q);%全局最优路径对应的参数
TRACK=Initialize(AM,s,P);
for p=1:P
Route=TRACK{p};
pos=find(Route==t);
Route=Route(1:pos(1));
Route=Fresh(Route);
ROUTEst{p,1}=Route;
HR{p,1}=Route;
[Fitness,Flag]=Fit(Route,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta);
FitFlag{p,1}=[Fitness;Flag];
HFF{p,1}=[Fitness;Flag];
end
SYZ=Inf;
for p=1:P
Route=HR{p,1};
FF=HFF{p,1};
if FF(1,1)<SYZ
AR{1}=Route;
SYZ=FF(1,1);
AFF{1}=FF;
end
end
%%
for q=2:Q
%按照粒子群迭代公式计算各个粒子的下一个位置
for p=1:P
Route=ROUTEst{p,q-1};
OptRoute1=HR{p,q-1};
OptRoute2=AR{1,q-1};
Route=SpecialAdd(Route,OptRoute1,r1,Cost);%向自己的历史最优位置靠近
Route=SpecialAdd(Route,OptRoute2,r2,Cost);%向全局历史最优位置靠近
Route=RandMove(Route,r3,AM);%随机游动
[Fitness,Flag]=Fit(Route,Cost,Delay,DelayJitter,PacketLoss,QoSD,QoSDJ,QoSPL,Alpha,Beta,Gamma,Delta);
ROUTEst{p,q}=Route;
FitFlag{p,q}=[Fitness;Flag];
end
%更新各粒子的历史最优位置
for p=1:P
F1=HFF{p,q-1};
F2=FitFlag{p,q};
if F2(1,1)<F1(1,1)
HR{p,q}=ROUTEst{p,q};
HFF{p,q}=FitFlag{p,q};
else
HR{p,q}=HR{p,q-1};
HFF{p,q}=HFF{p,q-1};
end
end
%更新全局历史最优位置
for p=1:P
Route=HR{p,q};
FF=HFF{p,q};
if FF(1,1)<SYZ&&FF(2,1)==1
AR{q}=Route;
SYZ=FF(1,1);
AFF{q}=FF;
else
AR{q}=AR{q-1};
AFF{q}=AFF{q-1};
end
end
end