sga_tsp.m

标准GA算法解决TSP问题的Matlab源代码

function SGA_TSP()
%旅行商问题的遗传算法解法


disp('此次计算的距离矩阵如下')
%此矩阵为一个演示矩阵，上面的代码产生了一个随机的距离矩阵，但又被此矩阵暂时覆盖
distance=[  Inf    76    45    81    34    99    12    70    10    21
    76   Inf    61    72     2     9   100    84    19     5
    45    61   Inf    44    15    96    83    86    80    40
    81    72    44   Inf    98    21    53    46    41    16
    34     2    15    98   Inf    23     8    99    13    57
    99     9    96    21    23   Inf    70    87    89     8
    12   100    83    53     8    70   Inf    73    24    84
    70    84    86    46    99    87    73   Inf    90    82
    10    19    80    41    13    89    24    90   Inf    41
    21     5    40    16    57     8    84    82    41   Inf];  %输出距离矩阵
 

guimo=10;
%遗传算法开始
gen_len=guimo; %基因长度
cross_probability=0.01;%交叉概率
mutate_probability=0.005;%变异概率
Maxgen=300;  %最大遗传代数
NIND=gen_len*10;    %个体数目



%生成初始种群 关键是生成可行解
Chrom=rand(NIND,gen_len);
for i=1:NIND
    [a indexa]=sort(Chrom(i,:));%排序值是不会重复的
    Chrom(i,:)=indexa; 
end

%计算目标函数值
Obj(1:NIND)=0;
for j=1:NIND
    for i=1:9
        Obj(j)=Obj(j)+distance(Chrom(j,i),Chrom(j,i+1));
    end
    Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1));
end

%记录每一代的最小值,平均值
ma(1,1)=1;
[ma(1,2) index]=min(Obj);
most_min=ma(1,2);%全局最优值
most_min_index=1;
%种群平均值
ma(1,3)=round(mean(Obj));
ma(1,4:3+gen_len)=Chrom(index,:);
for gen=1:Maxgen
    %终止判断
    %最近30代的最优值都比前面的最优值大则结束
    if gen>29+most_min_index & gen>100
        [m n]=find(ma(gen-30:gen,2)>most_min);
        if length(n)>29
            break;
        end
    end
    %计算适应度
    mmm=max(Obj)+1;
    Obj=mmm-Obj+1;
    sumObj=sum(Obj);%所有个体的目标函数值之和
    fitness=Obj/sumObj;%每个个体的选择概率
    fitness2=cumsum(fitness);%累计概率
    
    %轮盘选择
    tempChrom=Chrom;%储存一个原始的个体值 父代
    index=1;
    for k=1:NIND
        for j=1:NIND
            if rand<fitness2(j)
                Chrom(index,:)=tempChrom(j,:);
                index=index+1;
                break;
            end
        end
    end
    %交叉运算    关键是如何产生可行解
    n1=0;
    for i=1:NIND
        if rand(1)<cross_probability 
            if n1==0
                n1=1;
                temindex=i;%纪录第一个交叉个体
                continue;
            else %选够两个个体则交叉
                temp1=Chrom(temindex,:);%记录父代1
                temp2=Chrom(i,:);%%记录父代2
                Chrom(i,:)=tsp_cross_func1(temp1,temp1,distance);%TSP的一个启发式交叉算法函数产生一个子代
                %另一个子代从父代中继承一个较好的
                if Obj(i)>Obj(temindex)
                    Chrom(temindex,:)=temp2;
                else
                    Chrom(temindex,:)=temp1;
                end
                n1=0;
            end
        end
    end
    %Chrom  %检查交叉运算是否正确,解是否可行解
    %变异运算 实际上是交换位置
    for i=1:NIND
        for j=1:gen_len
            if rand<mutate_probability
                value=round(rand*(gen_len-1))+1;
                tt=Chrom(i,value);
                Chrom(i,value)=Chrom(i,j);
                Chrom(i,j)=tt;
            end
        end
    end
    %计算目标函数值
    Obj(1:NIND)=0;
    for j=1:NIND
        for i=1:9
        Obj(j)=Obj(j)+distance(Chrom(j,i),Chrom(j,i+1));
        end
        Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1));
    end
    %记录每一代的最小值,平均值
    ma(gen+1,1)=gen+1;
    [ma(gen+1,2) index]=min(Obj);
    %各代种群平均值
    ma(gen+1,3)=round(mean(Obj));
    ma(gen+1,4:3+gen_len)=Chrom(index,:);
    [most_min index]=min(ma(:,2));
    most_min_index=index;

end

disp('计算过程中的最优值记录')
disp('代数       最优值       平均值          ||||最优解---------------')
disp(num2str(ma))

[best_Y ]=min(ma(:,2));
str=['最短路径为: ' num2str(best_Y)  ];
disp(str)

X=ma(index,4:3+gen_len);
str=['最优解为:   ' num2str(X)  '代数： ' num2str(index)];
disp(str)


function child=tsp_cross_func1(father1,father2,distance)
%TSP的一个启发式交叉算法函数
%该算法以一定概率计算出一个比父代好的子代
%算法思路：F1：10 4 3 2 9 7 8 1 5 6  F2：9 1 3 5 2 6 7 8 4 10 。
%随机确定交叉点，如4,F1中第四位为2。
%将F1向左旋转3位，使第四位在成为第一位 F1：2 9 7 8 1 5 6 10 4 3。
%在F2中找到2所在位置，进行旋转2成为第一个 F2：2 6 7 8 4 10 9 1 3 5。
%然后比较disance(2-9)  disance(2-6),取比较小的如2-6所在父代F2,F2不变,
%将F1的后9位旋转,使6在第2位  成为F2: 2 6 10 4 3 9 7 8 1 5
%这样就形成了2 6 *********的模式,如此往复,

%演示的例子
%distance=[  Inf    76    45    81    34    99    12    70    10    21
%    76   Inf    61    72     2     9   100    84    19     5
%    45    61   Inf    44    15    96    83    86    80    40
 %   81    72    44   Inf    98    21    53    46    41    16
%    34     2    15    98   Inf    23     8    99    13    57
%    99     9    96    21    23   Inf    70    87    89     8
%    12   100    83    53     8    70   Inf    73    24    84
%    70    84    86    46    99    87    73   Inf    90    82
%    10    19    80    41    13    89    24    90   Inf    41
%    21     5    40    16    57     8    84    82    41   Inf];
%father1=[10 4 3 2 9 7 8 1 5 6];
%father2=[9 1 3 5 2 6 7 8 4 10];



len=length(father1);

pos=round(rand*(len-1))+1;%交叉点
%pos=3;

pos2=find(father2==father1(pos));

%以下完成第一次旋转移动
tem1=father1(pos:len);
tem2=father1(1:pos-1);
father1=[tem1 tem2];

tem1=father2(pos2:len);
tem2=father2(1:pos2-1);
father2=[tem1 tem2];

%一下完成剩下的旋转移动生成一个后代
for i=2:len
    if distance(father1(i-1),father1(i))<=distance(father2(i-1),father2(i))  
        pos2=find(father2==father1(i));
        tem0=father2(1:i-1);
        tem1=father2(pos2:len);
        tem2=father2(i:pos2-1);
        father2=[tem0 tem1 tem2];
    else
        pos2=find(father1==father2(i));
        tem0=father1(1:i-1);
        tem1=father1(pos2:len);
        tem2=father1(i:pos2-1);
        father1=[tem0 tem1 tem2];
    end
end
child=father1;