gatsp530.m

免疫遗传算法用于搜索全局最优解,经验证具有很好的效率和收敛性

% 遗传算法求解 TSP--多个体交叉

clear all
% 系统初始参数
xylabel=[3.64,2.68   %beijing
    4.18,1.76   %shanghai
    3.71,2.60   %tianjin
    2.77,1.50   %chongqing
    1.33,3.30   %wulumuqi
    4.20,2.96   %shenyang
    4.39,3.43   %haerbing
    3.92,1.82   %nanjing
    4.26,1.07   %taibei
    2.55,1.64   %chengdu
    2.37,1.02   %kunming
    3.43,2.09   %zhengzhou
    3.54,0.70   %xianggang
    3.51,1.62   %wuhan
    3.44,0.80   %guangzhou
    3.24,2.77   %huhehaote
    2.38,2.32   %xiling
    2.56,2.24   %lanzhou
    3.01,2.03   %xian
    2.79,2.51   %yinchuan
    3.33,2.44   %taiyuan
    2.94,0.76   %nanling
    3.39,1.36   %changsha
    3.49,2.46   %shijiazhuang
    2.78,1.17   %guiyang
    3.14,0.45   %haikou
    4.31,3.21   %changcun
    3.72,2.32   %jinan
    4.06,1.63   %hangzhou
    3.78,1.79   %hefei
    3.68,1.42   %nancang
    4.03,1.16   %fuzhou
    3.47,0.70   %aomen
    1.30,1.69]; %lasha

d=dist(xylabel,xylabel');
Num_v = size(d,1);

gen = 1;    % 初始化当前代数
sumfitness = 0;

% 打开输出文件，若不能打开，退出
outfp=fopen('gatsp530.txt','w');
if(outfp == -1)
    stderr('Cannot open output file');
    exit
end

% 输入 GA 运行参数
maxruns = input('请输入总运行次数(1-5):');    % 总运行次数
for run = 1:maxruns
    % 运行初始参数
    popsize = input('请输入种群大小(50-200):');
    if(mod(popsize,2) ~= 0)     % 种群大小须为偶数以便于交叉
        fprintf(outfp,'种群大小已设置为偶数！\n');
        popsize = popsize + 1;
    end   
    lchrom = Num_v;
    maxgen = input('请输入最大世代数(100-500):');
    pcross = input('请输入初始交叉率(0.5-0.9):');
    pmutationb = input('请输入初始变异率(0.05-0.2):');
    pmutation = pmutationb/lchrom;

    % 初始化最佳个体
    bestfit.fitness = 0;
    bestfit.generation = 0;
    % 初始化种群中的个体
    for j = 1:popsize
        for k = 1:lchrom  
            oldpop(j).chrom(k) = k;      
        end
        oldpop(j).parent = [0,0];    % 初始化父个体信息        
        oldpop(j).xsite = 0;        % 初始化交叉位置
        oldpop(j).fitness = objfunc(oldpop(j).chrom,d); % 计算初始适应度
    end
    % 随机抽取1-18中数,按其坐标顺序分别与1、2 ……中元素交换,共3次
    for l = 1:3
        for j = 1:popsize
            for k = 1:lchrom  
                exloc = ceil(rand(1,1)*lchrom);
                tempex = oldpop(j).chrom(k);
                oldpop(j).chrom(k) = oldpop(j).chrom(exloc);
                oldpop(j).chrom(exloc) = tempex;
            end
        end
    end
    [sumfitness,bestfit] = statistics(oldpop,bestfit,gen,outfp);  % 统计种群的适应度
    newpop = oldpop;   % 初始化 newpop
    % 输出文件的头部
    fprintf(outfp,'            基本GA参数:\n');
    fprintf(outfp,'--------------------------------------------\n');
    fprintf(outfp,'    种群大小(popsize)      = %8.0f\n',popsize);
    fprintf(outfp,'    染色体长度(lchrom)     = %8.0f\n',lchrom);
    fprintf(outfp,'    最大进化代数(maxgen)   = %8.0f\n',maxgen);
    fprintf(outfp,'    交叉概率(pcross)       = %8.2f\n',pcross);
    fprintf(outfp,'    变异概率(pmutation)    = %8.2f\n',pmutation);
    fprintf(outfp,'--------------------------------------------\n');
    
    for gen = 1:maxgen
        fprintf(outfp,'当前代为： %8.0f\n',gen);
  
        % 遗传操作
        for j = 1:2:popsize

            %*********** 交叉操作1 -- two gen  ************
            if(0)
            % 轮盘赌选择要交叉的个体
            mate1 = select(sumfitness,oldpop,gen,maxgen);
            mate2 = select(sumfitness,oldpop,gen,maxgen);
            
            newpop(j).parent = [oldpop(mate1).chrom,oldpop(mate2).chrom];
            newpop(j+1).parent = [oldpop(mate1).chrom,oldpop(mate2).chrom];
            
            if(rand(1,1) <= pcross)
                loccross = round(rand(1,1)*(lchrom-2)) + 1; % 随机产生交叉位置[1到(lchrom-1)]
                newpop(j).xsite = loccross;
                newpop(j+1).xsite = loccross;
                [newpop(j).chrom,newpop(j+1).chrom] = jcross417(oldpop,mate1,mate2,loccross,d);
            end
            end
            %*********************************************
            
            %*********** 交叉操作2 -- three gen **********
            if(0)
            mate1 = select(sumfitness,oldpop,gen,maxgen);
            mate2 = select(sumfitness,oldpop,gen,maxgen);
            mate3 = select(sumfitness,oldpop,gen,maxgen);
            
            newpop(j).parent = [oldpop(mate1).chrom,oldpop(mate2).chrom];
            newpop(j+1).parent = [oldpop(mate1).chrom,oldpop(mate2).chrom];
            
            if(rand(1,1) <= pcross)
                loccross = round(rand(1,1)*(lchrom-2)) + 1; % 随机产生交叉位置[1到(lchrom-1)]
                newpop(j).xsite = loccross;
                newpop(j+1).xsite = loccross;
                [newpop(j).chrom,newpop(j+1).chrom] = jcross417(oldpop,mate1,mate2,loccross,d);
            end
            end
            %*********************************************
            
            %*********** 交叉操作3 -- four gen **********
            if(0)
            mate1 = select(sumfitness,oldpop,gen,maxgen);
            mate2 = select(sumfitness,oldpop,gen,maxgen);
            
            newpop(j).parent = [oldpop(mate1).chrom,oldpop(mate2).chrom];
            newpop(j+1).parent = [oldpop(mate1).chrom,oldpop(mate2).chrom];
            
            if(rand(1,1) <= pcross)
                loccross = round(rand(1,1)*(lchrom-2)) + 1; % 随机产生交叉位置[1到(lchrom-1)]
                newpop(j).xsite = loccross;
                newpop(j+1).xsite = loccross;
                [newpop(j).chrom,newpop(j+1).chrom] = jcross417(oldpop,mate1,mate2,loccross,d);
            end
            end
            %*********************************************
            
            % 变异操作-随机选取两个位置交换其间城市号
            for k = 1:lchrom
                if(rand(1,1) <= pmutation)
                    locpmut1 = ceil(rand(1,1)*lchrom);
                    locpmut2 = ceil(rand(1,1)*lchrom);
                    if locpmut1 > locpmut2
                        temploc = locpmut1;
                        locpmut1 = locpmut2;
                        locpmut2 = temploc;
                    end
                    temppart = newpop(j).chrom(locpmut1:locpmut2);
                    newpop(j).chrom(locpmut1:locpmut2) = fliplr(temppart);
                end
            end
            for k = 1:lchrom
                if(rand(1,1) <= pmutation)
                    locpmut1 = ceil(rand(1,1)*lchrom);
                    locpmut2 = ceil(rand(1,1)*lchrom);
                    if locpmut1 > locpmut2
                        temploc = locpmut1;
                        locpmut1 = locpmut2;
                        locpmut2 = temploc;
                    end
                    temppart = newpop(j+1).chrom(locpmut1:locpmut2);
                    newpop(j+1).chrom(locpmut1:locpmut2) = fliplr(temppart);
                end
            end
            % 解码并计算适应度
            newpop(j).fitness = objfunc(newpop(j).chrom,d); % 计算初始适应度
            newpop(j+1).fitness = objfunc(newpop(j+1).chrom,d);
            
            % 输出新个体
            if(0)
            fprintf(outfp,'\n  新个体 %2.0f 为：',j);
            fprintf(outfp,'[');
            for i = 1:length(newpop(j).chrom)
                fprintf(outfp,'%3.0f',newpop(j).chrom(i));
            end
            fprintf(outfp,']\n');
            
            fprintf(outfp,'\n  新个体 %2.0f 为：',j);
            fprintf(outfp,'[');
            for i = 1:length(newpop(j+1).chrom)
                fprintf(outfp,'%3.0f',newpop(j+1).chrom(i));
            end
            fprintf(outfp,']\n');
            end    
        end
        [sumfitness,bestfit] = statistics(newpop,bestfit,gen,outfp);  % 统计种群的适应度
        bestobj(bestfit.chrom,d,outfp);
        oldpop = newpop;
    end            
end

hold on
for i = 1:Num_v
    plot(xylabel(i,1),xylabel(i,2),'+r');
end
xy_order=xylabel(bestfit.chrom,:);
xy_order(size(xy_order,1)+1,:) = xy_order(1,:);
plot(xy_order(:,1),xy_order(:,2))
hold off

fclose(outfp);