qos选播路由的粒子群算法仿真主函数.m

QoS选播路由的粒子群算法仿真主函数 来自（http://blog.sina.com.cn/greensim）

在潘达儒的博士论文（潘达儒. 智能IP QoS路由算法的研究[D]. 华南理工大学博士学位论文, 2005, 60-72）里，潘达儒设计了离散粒子群优化PSO（Particle Swarm Optimization）算法求解QoS路由问题，将粒子群优化算法应用于QoS路由问题的求解，其提出的“算子序列”理论具有一定的新意。但是，经过我们的研究发现，但其设计的“插入算子”有可能失效（路径在“插入算子”操作前后没有发生变化），从而导致“算子序列”失败，并造成整个算法被“卡住”，此外，可以证明其“删除算子”中“退一步”的做法是冗余的。为此，我们提出了一种新的基于粒子群算法的选播路由算法，新算法中引入了一种全新的“⊕算子”，将粒子群优化（PSO）的迭代公式简化成一个，并且设计了一种称为“随机游动算子”，将基于路径的变异算子引入算法，增强算法的全局搜索能力。我们实现了该算法，并且可以提供完整源码和算法说明文档，如有需要，欢迎和GreenSim团队联系，我们保证授权是唯一的，即只提供给您一个人使用。本算法的设计和实现由GreenSim团队（http://blog.sina.com.cn/greensim）完成，下面列出的只是源码中很小的一部分。

 

 

%% QoS选播路由的粒子群算法仿真主函数

clear%清空内存

 

%% 第一步：产生网络拓扑结构

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团队原创作品，转载请注明（http://blog.sina.com.cn/greensim）

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团队原创作品，转载请注明（http://blog.sina.com.cn/greensim）

%% 输入参数列表

% 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