302006
e = 5;
Maxtime = 200; n = length(D); m = n;
Ta = Tao0*ones(n,n) - Tao0*eye(n); TM = []; LM = 100000; ant = zeros(m,n+1); ata = zeros(m,n); for i = 1:m for j = i+1:n
ata(i,j) = 1/D(i,j); ata(j,i) = ata(i,j); end end
for time = 1:Maxtime for k = 1:m
city(k,:) = 1:n; end s = 1; for i = 1:m
ant(i,s) = unidrnd(n); ant(i,n+1) = ant(i,s); city(i,ant(i,s)) = 0; end while s < n
p = zeros(m,n); for i = 1:m A(i) = 0; for j = 1:n
if city(i,j) ~= 0
A(i) = A(i) + (Ta(ant(i,s),j)^alpha)*(ata(ant(i,s),j)^beta); end end
for j = 1:n
if city(i,j) ~= 0
p(i,j) = (Ta(ant(i,s),j)^alpha)*(ata(ant(i,s),j)^beta)/A(i); end end
pp = unifrnd(0,1); j = 1; while pp>0
pp = pp - p(i,j); j = j + 1;
最佳旅游路线设计
25
302006
end j = j - 1; ant(i,s+1) = j; for k = 1:n
if city(i,k) == j; city(i,k) = 0; break; end end end s = s + 1; end
L = compu(ant,D); [Lmin,t] = min(L); if Lmin < LM LM = Lmin; TM = ant(t,:); end
deltaTa = zeros(m,n); for i = 1:m for j = 1:n-1
deltaTa(ant(i,j),ant(i,j+1)) = deltaTa(ant(i,j),ant(i,j+1)) + Q/L(i); end end
for j = 1:n-1
deltaTa(TM(j),TM(j+1)) = deltaTa(TM(j),TM(j+1)) + Q/LM; end for i = 1:m for j = 1:n
Ta(i,j) = rho*Ta(i,j) + deltaTa(i,j); end end
trace(time) = LM; end figure(1); plot(trace); toc;
function D = Distance(C) n = length(C); D = zeros(n,n); for i = 1:n for j = i+1:n
D(i,j) = norm(C(:,i) - C(:,j));
最佳旅游路线设计
26
302006
D(j,i) = D(i,j); end end
function L = compu(ant,D); for i = 1:length(D) L(i) = 0;
for j = 1:length(ant)-1
L(i) = L(i) + D(ant(i,j),ant(i,j+1)); end end
程序3：问题一的MATLAB遗传算法程序 function [ y , road ] = GATSP1 % 程序说明：
% 本程序为遗传算法求解旅行商问题 %
% 变量说明： % 输入：
% D：城市位置矩阵n*2。 % 输出：
% y：近似最短路径的总长度； % road：近似最短路径。 % tic D=[
0.00 6.73 15.97
28.96 32.82 29.87 33.02 35.14 36.21 37.55 18.03 22.27
9.90 12.02
36.58
11.03 37.49
12.97 39.14 6.98 14.58 12.20 10.15
21.39
22.23 24.29
29.25 22.25
29.85 29.27
18.91
13.71
21.31
26.06
35.98 34.47
7.00 14.60 17.75
35.72 29.65 27.53 26.46 38.15 25.05 22.87
37.37
18.22
25.40
32.42
34.54 35.61
31.30
12.27 13.34
19.87 20.94
16.10 15.03
27.52 28.59
29.18 28.11
5.13 3.01 1.94 0.00 20.48 28.40 25.65 31.46
30.05
17.47 13.34
18.54 15.28
20.48
0.00 5.20 10.38
22.81
34.24 31.54
34.32
5.20 0.00 7.60 20.03
15.25
15.35 12.27
15.28
22.88
16.97
30.53
6.73 0.00 9.24 3.17 5.29 6.36 8.30 12.18 15.97
9.24 0.00 6.07 8.19 9.26 11.20
9.90 3.17 6.07 0.00 2.12 3.19 5.13 15.35 12.02 11.03 12.97 18.91 13.71
5.29 8.19 2.12 0.00 1.07 3.01 17.47 6.36 9.26 3.19 1.07 0.00 1.94 18.54 8.30 11.20 12.18
12.20
6.98 7.00 10.15
最佳旅游路线设计
27
302006
21.31 14.58 14.60 17.75 19.87 20.94
22.88
10.38
7.65 14.67 15.27 23.86 23.94 26.06 21.39 24.29 18.22 16.10 15.03 16.97
22.81
0.00 20.08 22.35 21.75 11.43 13.08 28.96 22.23 22.25 25.40 27.52 28.59
30.53
18.03
20.08 0.00 7.02 7.62 21.07 16.29 35.98 29.25 29.27 32.42 34.54 35.61
37.55
25.05
22.35 7.02 0.00 0.60 14.05 9.27 36.58 29.85 29.87 33.02 35.14 36.21
38.15
25.65
21.75 7.62 0.60 0.00 13.45 8.67 37.49 32.82 35.72 29.65 27.53 26.46 28.40 34.24 11.43 21.07 14.05
13.45
0.00 4.78
39.14
34.47
37.37
31.30
29.18
28.11
30.05
34.32
13.08
16.29
9.27 8.67 4.78 0.00
];
NIND = 100; %种群数量； MAXGEN = 500; %最大遗传代数； pc = 0.8; %交叉概率； pm = 0.1; %变异概率；
N = length(D(:,1)); %求城市数量 %随机生成初始种群 for i = 1:NIND B(i,:) = manu(N);
F(i) = Distance(B(i,:),N,D); end SelCh = B; F = F';
FitnV = (10000./F); %计算适应度
for gen = 1:MAXGEN
for t=1:floor(NIND/30) %寻找每代的一部分最优群种以便遗传给下一代 for i = 1:NIND if F(i) == min(F)
bestSelCh(t,:) = SelCh(i,:); bestFit(t) = F(i); break; end end end
SelCh = select ('rws', SelCh, FitnV); %选择
for i = 1:0.1*NIND %生成一部分子代 Chrom(i,:) = manu(N);
C(i) = Distance(Chrom(i,:),N,D); G(i) = 10000/C(i); 最佳旅游路线设计
7.60 0.00 12.43
20.03
12.43
15.25
7.65
22.27
14.67
22.87
15.27
31.46 23.86 31.54
23.94
28
302006
end
SelCh = reins(SelCh,Chrom,1,1,F,G'); %插入 SelCh = Crossover (SelCh,N,NIND,pc); %交叉 SelCh = Muta (SelCh,N,NIND,pm); %变异 for i = 1:NIND
F(i) = Distance(SelCh(i,:),N,D); end
for t=1:floor(NIND/30) %遗传的最优个体替换适应度最差的新个体 for i = 1:NIND if F(i) == max(F)
SelCh(i,:) = bestSelCh(t,:); F(i) = bestFit(t); break; end end end
FitnV = (10000./F); %计算适应度 trace (gen, 1) = min(F); %寻找每一代的最优值 for i = 1:NIND
if F(i) == trace (gen, 1) key = SelCh(i,:); break; end end
trace (gen, 2) = mean(F); %寻找每一代的平均值 if gen == 1
y = trace (gen, 1); road = key; else
if y > trace (gen, 1) y = trace (gen, 1);
road = key; %寻找当前最优路径 end end end toc
%作图，观察遗传代数与路径长度的关系 figure(2); hold on;
plot(trace(:,1)); plot(trace(:,2),'r'); title('性能追踪'); xlabel('进化代数');
最佳旅游路线设计
29