SA resolves the program of TSP issues

Sender: lonelyu (small fish ◎ direction of the sea), the letter area: AI

Title: Re: Who has an annealing program

Sending station: Drinking water thinking (January 21, 2002 21:46:45 Monday), station letters

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 BYSELF WILL Generate 20 Cities WITHIN A Unit Cube and

% Ten 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 (JMYERS @ NWU.

EDU)

EDU)

% to Comp.ai.neural-Nets. It's Obtained from The Figure

% 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.728; 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 = (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 la 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 acceptance 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> StopToldolerance,

Mine = INF;

Mine = INF;

MAXE = 0;

Trialn = 0;% Number of Trial Moves

Acceptn = 0;% Number of Actual Moves

While Trialn

NEW_PATH = PATH;

Index = Round (Rand (2, 1) * Numcity .5); Inversion_index = (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

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

This program is .m file, running in Matlab.

[In the masterpiece of Killtime (small shrimp):]

: Who has an analog annealing algorithm to solve the source program of TSP issues (preferably C language), send it to me

: One, the younger brother is grateful!

-

Worm. . . . . .

※ Source: · Drinking water Source bbs.sjtu.edu.cn · [from: 166.111.174.213]