tsp1.m

一种随机神经网络应用在模拟退火算法中解决TSP问题

function out = tsp(loc) 
%用模拟退火算法解决货郎担问题。

if nargin == 0, 
%城市的坐标值
%rand('seed',12);
loc=10*rand(100,2);
% 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); %城市个数
distance = zeros(NumCity); %初始化距离矩阵，30行30列

%装填距离矩阵
for i = 1:NumCity, 
  for j = 1:NumCity, 
    %城市i和城市j之间的距离，既为两点间的二阶范数
    distance(i, j) = norm(loc(i, :) - loc(j, :));
    distance(i, j) = norm(loc(i, :) - loc(j, :)); 
  end 
end

%通过目标函数从路径中生成能量值，既为各个城市之间距离的和
%path = randperm(NumCity); 
%energy = sum(distance((path-1)*NumCity + [path(2:NumCity) path(1)])); 

count = 1000; 
all_dE = zeros(count, 1); 

for i = 1:count 
    path = randperm(NumCity); %随机的生成一个路径，数字为30以内
    
    %把距离定义成能量值，把所有城市之间的距离相加
    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))); 
    %sum(sum(diff(loc([new_path new_path(1)],:))'.^2)))为计算新路
    %径的各个城市间的距离的和
end

dE = max(all_dE);%记录20组能量差里面的最大值
dE = max(all_dE); 
temp = 10*dE; %选择一个最大差值作为起始温度值
fprintf('Initial energy = %f\n\n',energy); 

%初始化绘图
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; % 最大的试验温度值 ，既试验解的最大个数
MaxAcceptN = NumCity*10; % 最大的可接受的温度值，既可接受的解的最大个数 
StopTolerance = 0.005; %容忍度，既为终止温度值
StopTolerance = 0.005;  
TempRatio = 0.5; %温度下降比率
minE = inf; %初始化最小能量值
maxE = -1; %初始化最大能量值

%主要的退火循环
while (maxE - minE)/maxE > StopTolerance, 
    minE = inf; 
    minE = inf; 
    maxE = 0; 
    TrialN = 0; %试验解的个数
    AcceptN = 0; %实际可接受的解的个数
    
    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 (new_energy - energy) < 0 | rand < exp((energy - new_energy)/temp), 
              %接受，既(Δt<0) OR EXP(-Δt/T)>Random-of-[0,1]
              energy = new_energy; 
              path = new_path; 
              minE = min(minE, energy); 
              maxE = max(maxE, energy); 
              AcceptN = AcceptN + 1;%可行解个数加1 
           end 
        TrialN = TrialN + 1; 
    end

    %更新画图
    out = [path path(1)]; 
    set(h, 'xdata', loc(out(:), 1), 'ydata', loc(out(:), 2)); 
    drawnow; 
    %在控制窗口输出信息
    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); 
    %降温
    temp = temp*TempRatio; 
end

%打印一连串的数字，每个城市对应一个数字
for i = 1:NumCity, 
    text(loc(path(i),1)+0.01, loc(path(i),2)+0.01, int2str(i), ... 
    'fontsize', 8); 
end