www.pudn.com > GA.rar > GA_TSP.m, change:2014-11-03,size:2676b


%遗传算法求解TSP问题(为选择操作从新设计后程序) 
%输入: 
%D       距离矩阵 
%NIND    为种群个数 
%X       参数是中国34个城市的坐标(初始给定) 
%MAXGEN  为停止代数,遗传到第MAXGEN代时程序停止,MAXGEN的具体取值视问题的规模和耗费的时间而定 
%m       为适值淘汰加速指数,最好取为1,2,3,4,不宜太大 
%Pc      交叉概率 
%Pm      变异概率 
%输出: 
%R       为最短路径 
%Rlength 为路径长度 
clear 
clc 
close all 
%% 加载数据 
X=[114.00 128.00;110.40 186.40;55.20 153.39;30.69 139.06;59.12 109.17;148.62 144.18;185.80 141.10;145.60 176.00;91.12 110.40; 
149.70 104.29;143.96 131.09;209.60 148.60;160.00 179.20;93.38 134.96;108.80 88.66;187.73 96.02;109.76 150.40;153.73 86.43; 
188.93 34.18;100.80 73.60;86.32 170.85;190.20 108.80;171.20 212.72;38.74 94.35;64.37 127.06;93.71 204.80;216.94 96.88;58.98 53.41; 
174.40 128.00;222.21 23.06;182.61 174.83;25.17 57.44;33.60 170.85;132.28 86.40;188.50 125.55;131.20 62.42;160.00 153.60;172.80 51.47; 
131.20 182.40;57.14 208.00;54.22 70.10;89.78 84.80;137.33 29.17;182.60 65.55;64.94 91.20;54.90 182.40; 
146.42 66.93;129.60 217.60;184.82 207.36;140.80 206.40]; 
 
D=Distanse(X);  %生成距离矩阵 
N=size(D,1);    %城市个数 
%% 遗传参数 
NIND=50;       %种群大小 
MAXGEN=30;     %最大遗传代数 
Pc=0.9;         %交叉概率 
Pm=0.05;        %变异概率 
GGAP=0.9;       %代沟 
%% 初始化种群 
Chrom=InitPop(NIND,N); 
%% 画出随机解的路径图 
DrawPath(Chrom(1,:),X) 
pause(0.0001) 
%% 输出随机解的路径和总距离 
disp('初始种群中的一个随机值:') 
OutputPath(Chrom(1,:)); 
Rlength=PathLength(D,Chrom(1,:)); 
disp(['路径总长度:',num2str(Rlength)]); 
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~') 
%% 优化 
gen=0; 
figure; 
%hold on;box on 
xlim([0,MAXGEN]) 
title('优化过程') 
xlabel('迭代次数') 
ylabel('最优值') 
ObjV=PathLength(D,Chrom);  %计算路径长度 
preObjV=min(ObjV); 
while gen<MAXGEN 
    %% 计算适应度 
    ObjV=PathLength(D,Chrom);  %计算路径长度 
    % fprintf('%d   %1.10f\n',gen,min(ObjV)) 
    line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001) 
    preObjV=min(ObjV); 
    FitnV=Fitness(ObjV); 
    %% 选择 
    SelCh=Select(Chrom,FitnV,GGAP); 
    %% 交叉操作 
    SelCh=Recombin(SelCh,Pc); 
    %% 变异 
    SelCh=Mutate(SelCh,Pm); 
    %% 逆转操作 
    SelCh=Reverse(SelCh,D); 
    %% 重插入子代的新种群 
    Chrom=Reins(Chrom,SelCh,ObjV); 
    %% 更新迭代次数 
    gen=gen+1 ; 
end 
%% 画出最优解的路径图 
ObjV=PathLength(D,Chrom);  %计算路径长度 
[minObjV,minInd]=min(ObjV); 
DrawPath(Chrom(minInd(1),:),X) 
%% 输出最优解的路径和总距离 
disp('最优解:') 
p=OutputPath(Chrom(minInd(1),:)); 
disp(['路径总长度:',num2str(ObjV(minInd(1)))]); 
disp('-------------------------------------------------------------')