satsp.txt

用模拟退火算法求解旅行商问题 T(t+1)＝k×T(t) 式中k为正的略小于1.00的常数

用如下所示的降温方式： 

T(t+1)＝k×T(t) 
式中k为正的略小于1.00的常数，t为降温的次数 

使用SA解决TSP问题的Matlab程序：

function out = tsp(loc)
% TSP Traveling salesman problem (TSP) using SA (simulated annealing).
% TSP by itself will generate 20 cities within a unit cube and
% then use SA to slove this problem.
%
% TSP(LOC) solve the traveling salesman problem with cities'
% coordinates given by LOC, which is an M by 2 matrix and M is
% the number of cities.
%
% For example:
%
% loc = rand(50, 2);
% tsp(loc);
if nargin == 0,
% The following data is from the post by Jennifer Myers (http://www.madio.net/bbs/mailtjmyers@nwu.
edu)
edu)
% to comp.ai.neural-nets. It's obtained from the figure in
% Hopfield & Tank's 1985 paper in Biological Cybernetics
% (Vol 52, pp. 141-152).
loc = [0.3663, 0.9076; 0.7459, 0.8713; 0.4521, 0.8465;
0.7624, 0.7459; 0.7096, 0.7228; 0.0710, 0.7426;
0.4224, 0.7129; 0.5908, 0.6931; 0.3201, 0.6403;
0.5974, 0.6436; 0.3630, 0.5908; 0.6700, 0.5908;
0.6172, 0.5495; 0.6667, 0.5446; 0.1980, 0.4686;
0.3498, 0.4488; 0.2673, 0.4274; 0.9439, 0.4208;
0.8218, 0.3795; 0.3729, 0.2690; 0.6073, 0.2640;
0.4158, 0.2475; 0.5990, 0.2261; 0.3927, 0.1947;
0.5347, 0.1898; 0.3960, 0.1320; 0.6287, 0.0842;
0.5000, 0.0396; 0.9802, 0.0182; 0.6832, 0.8515];
end
NumCity = length(loc); % Number of cities
distance = zeros(NumCity); % Initialize a distance matrix
% Fill the distance matrix
for i = 1:NumCity,
for j = 1:NumCity,
distance(i, j) = norm(loc(i, - loc(j, );
distance(i, j) = norm(loc(i, - loc(j, );
end
end
% To generate energy (objective function) from path
%path = randperm(NumCity);
%energy = sum(distance((path-1)*NumCity + [path(2:NumCity) path(1)]));
% Find typical values of dE
count = 20;
all_dE = zeros(count, 1);
for i = 1:count
path = randperm(NumCity);
energy = sum(distance((path-1)*NumCity + [path(2:NumCity)
path(1)]));
new_path = path;
index = round(rand(2,1)*NumCity+.5);
inversion_index = (min(index):max(index));
new_path(inversion_index) = fliplr(path(inversion_index));
all_dE(i) = abs(energy - ...
sum(sum(diff(loc([new_path new_path(1)],)'.^2)));
end
dE = max(all_dE);
dE = max(all_dE);
temp = 10*dE; % Choose the temperature to be large enough
fprintf('Initial energy = %f\n\n',energy);
% Initial plots
out = [path path(1)];
plot(loc(out(, 1), loc(out(, 2),'r.', 'Markersize', 20);
axis square; hold on
h = plot(loc(out(, 1), loc(out(, 2)); hold off
MaxTrialN = NumCity*100; % Max. # of trials at a
temperature
MaxAcceptN = NumCity*10; % Max. # of acceptances at a
temperature
StopTolerance = 0.005; % Stopping tolerance
TempRatio = 0.5; % Temperature decrease ratio
minE = inf; % Initial value for min. energy
maxE = -1; % Initial value for max. energy
% Major annealing loop
while (maxE - minE)/maxE > StopTolerance,
minE = inf;
minE = inf;
maxE = 0;
TrialN = 0; % Number of trial moves
AcceptN = 0; % Number of actual moves
while TrialN < MaxTrialN & AcceptN < MaxAcceptN,
new_path = path;
index = round(rand(2,1)*NumCity+.5);
inversion_index = (min(index):max(index));
new_path(inversion_index) =
fliplr(path(inversion_index));
new_energy = sum(distance( ...
(new_path-1)*NumCity+[new_path(2:NumCity)
new_path(1)]));
if rand < exp((energy - new_energy)/temp), % 
accept
it!
energy = new_energy;
path = new_path;
minE = min(minE, energy);
maxE = max(maxE, energy);
AcceptN = AcceptN + 1;
end
TrialN = TrialN + 1;
end
end
% Update plot
out = [path path(1)];
set(h, 'xdata', loc(out(, 1), 'ydata', loc(out(, 2));
drawnow;
% Print information in command window
fprintf('temp. = %f\n', temp);
tmp = sprintf('%d ',path);
fprintf('path = %s\n', tmp);
fprintf('energy = %f\n', energy);
fprintf('[minE maxE] = [%f %f]\n', minE, maxE);
fprintf('[AcceptN TrialN] = [%d %d]\n\n', AcceptN, TrialN);
% Lower the temperature
temp = temp*TempRatio;
end
% Print sequential numbers in the graphic window
for i = 1:NumCity,
text(loc(path(i),1)+0.01, loc(path(i),2)+0.01, int2str(i), ...
'fontsize', 8);
end 

又一个相关的Matlab程序

function[X,P]=zkp(w,c,M,t0,tf)
[m,n]=size(w);
L=100*n;
t=t0;
clear m;
x=zeros(1,n)
xmax=x;
fmax=0;
while t>tf
for k=1:L
xr=change(x)
gx=g_0_1(w,x);
gxr=g_0_1(w,xr);
if gxr<=M
fr=f_0_1(xr,c);
f=f_0_1(x,c);
df=fr-f;
if df>0
x=xr;
if fr>fmax
fmax=fr;
xmax=xr;
end
else
p=rand;
if p<exp(df/t)
x=xr;
end
end
end
end
t=0.87*t
end
P=fmax;
X=xmax;
%下面的函数产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
clear m;
u=rand;
u=u*(n-2);
u=round(u);
if u<2
u=2;
end
if u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
v=1;
end
v=v+u;
if v>n
v=n;
end
pi_1(u)=pi0(v);
pi_1(u)=pi0(u);
if u>1
for k=1:(u-1)
pi_1(k)=pi0(k);
end
end
if v>(u+1)
for k=1:(v-u-1)
pi_1(u+k)=pi0(v-k);
end
end
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
end
end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1))-d(pi0(v),pi0(v+1));
end
d_f=d_f-d(pi0(u-1),pi0(u));
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k)); 
end
else
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
for k=(u+1):n
d_f=d_f-d(pi0(k),pi0(k-1)); 
end
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
end
pi_r=pi_1;