Sending station: BBS Shuimu Tsinghua Station (WED MAY 16 11:36:04 2001) This is a program that SA resolves TSP issues.
Function OUT = TSP (LOC)% TSP Traveling Salesman Problem (TSP) Using SA (Simulate 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% for EXAMPLE:% LOC = Rand (50, 2);% TSP (LOC) ); if Nargin == 0,% The folnifer MYERS (JMYERS @ NWU. EDU) EDU)% to comp.ai.neural-nets. it's obtained from the first 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 and% To Generate Energy (Objective Function) from path% Path = Randperm (Numcity);% ENERGY = SUM (DISTANES ((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 (inversion_index)); all_de = abs (Energy - ... Sum (SUM (Diff ([new_path new_path (1)],) '. ^ 2)))); end de = max (all_de); de = max (all_de); Temp = 10 * de;% choise the temperature to be la large 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 (, 2)); Hold Off Maxtrialn = Numcity * 100;% max. # of trials at a temperature maxAcceptn = number * 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 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 max) = [% f% f] / n ', mine, maxe); fprintf (' [acceptn trialn] = [% D% D] / N / N ', Acceptn, Trialn;% Lower Temperature Temp = Temp * Tempratio; End% Print Sequential NumBers in The Graphic Window for i = 1: Numcity, Text (LOC (Path, 1) 0.01, LOC (Path, 2) 0.01, int2str, ... 'fontsize', 8); END This program is .m file, run in Matlab. 89 line error! ACCEPT IT! What do you mean? Oh, accept it jumped, it There is another one% in the previous line, and Accept IT is followed by%.
