ga_routing.asv

遗传算法在路由优化中的应用:多服务质量的最小路径的算法.

% 本算法用遗传算法实现路由问题

% 算法调用参数：

% 算法返回参数:

% 调用函数：

function GA_routing(V,E,B,D,A0,B0,pc,pm)
tic;
format long

%Step 0: 根据已知的节点和链路初始化网络拓扑图,并进行预处理(删除不满足带宽要求的链路)
         tuoputu=init_tuoputu(V,E,B);  % V为节点集合,是一元数组; E为链路集合,是二元数组; B为要求带宽
%Step 1: 对原始网络拓扑图进行优化处理,生成新的网络拓扑图;
%Step 2: 设定遗传代数及群体大小,并随机生成初始群体;
        dieDaiNum=200;   %遗传代数为200 
        populationNum=100;  %种群大小为100
        vs=1; % vs为源结点
        vd=5; % vd为目的结点        
        [codeRodeList,codeLength,population]=createPopulation(populationNum,vs,vd,tuoputu);  % 生成初始群体
        
%Step 3: 初始化染色体编码集chromosome和优化函数F值集;
        chromosome=zeros(1,codeLength);  % chromosome记录染色体  
        jieNum=0;   % jieNum记录解的个数
        %p=cell(1,1); % p记录染色体的路径,
        %delay(1)=0;  % delay记录染色体的延迟,        
        %F(1)=0;  % F记录染色体的函数值
        
    for i=1:dieDaiNum      
%Step 4: 计算适应度函数fitness。对群体中的每个染色体,判断F1=0,ps,j=1,pi,d=1和F2=0。如果存在这样的染色体,那么将该染色体及F的值存入解集中;
        [chromosome,p,delay,F,fitness]=caculateFitness(population,chromosome,populationNum,D,codeRodeList,tuoputu,codeLength,vs,vd,jieNum,p,delay,F,B,A0,B0);
          % chromosome记录染色体,p记录染色体的路径,delay记录染色体的延迟,F记录染色体的函数值(这几个参数都只记录合格的路径),
          % fitness记录当前群体的适应度值,
        
%Step 5: 进行选择、交叉、变异操作,以产生下一代群体;
        %选择 (采用最佳个体保存方法和赌轮选择相结合的方法,即先选出最佳个体,直接遗传到子代种群中,其余的个体则采用赌轮选择机制进行选择
              [population,fitness]=relect(population,fitness,populationNum);
        %交叉
              population=cross(population,pc,populationNum,codeLength,fitness);
        %变异
              population=mutation(population,pm,populationNum,codeLength);

%Step 6: 如果遗传代数超过了设定值,则转入Step 7,否则执行Step 4;
    end
%Step 7: 在解集中找出使得F值最小的染色体作为解输出chromosomei∈chromosome使得Fi∈F为最小。
    [g,index]=min(F);
    chromosome(index,:)
    celldisp(p{index,:})
    delay(index)
    g
%应用上述算法对图2进行了仿真,实验时具体参数选择为: 遗传代数为200,初始种群大小为100,交叉概率pc=0.95,变异概率pm=0.05,A0=1,B0=500,编码长度为29,源节点为1,目的节点为5,结果如表1所示。
toc;