simulatedannealing.m

Traveling Salesman Problem (TSP) has been an interesting problem for a long time in classical optim

function s = simulatedannealing(inputcities,initial_temperature,...
cooling_rate,threshold,numberofcitiestoswap)
% SIMULATEDANNEALING
% S = SIMULATEDANNEALING(inputcities,initial_temperature,cooling_rate)
% returns the new configuration of cities with an optimal solution for the
% traveling salesman problem for n cities.
%
%The input arguments are
% INPUTCITIES - The cordinates for n cities are represented as 2
% rows and n columns and is passed as an argument for
% SIMULATEDANNEALING.
% INITIAL_TEMPERATURE - The initial temperature to start the
% simulatedannealing process.
% COOLING_RATE - Cooling rate for the simulatedannealing process.
% Cooling rate should always be less than one.
% THRESHOLD - Threshold is the stopping criteria and it is the
% acceptable distance for n cities.
% NUMBEROFCITIESTOSWAP- Specify the maximum number of pair of cities to
% swap. As temperature decreases the number of cities
% to be swapped decreases and eventually reaches one
% pair of cities.
global iterations;
temperature = initial_temperature;
initial_cities_to_swap = numberofcitiestoswap;
iterations = 1;
complete_temperature_iterations = 0;
while iterations < threshold
previous_distance = distance(inputcities);
temp_cities = swapcities(inputcities,numberofcitiestoswap);
current_distance = distance(temp_cities);
diff = abs(current_distance - previous_distance);
if current_distance < previous_distance
inputcities = temp_cities;
plotcities(inputcities);
if complete_temperature_iterations >= 10
temperature = cooling_rate*temperature;
complete_temperature_iterations = 0;
end
numberofcitiestoswap = round(numberofcitiestoswap...
*exp(-diff/(iterations*temperature)));
if numberofcitiestoswap == 0
numberofcitiestoswap = 1;
end
iterations = iterations + 1;
complete_temperature_iterations = complete_temperature_iterations + 1;
6 ARAVIND SESHADRI
else
if rand(1) < exp(-diff/(temperature))
inputcities = temp_cities;
plotcities(inputcities);
numberofcitiestoswap = round(numberofcitiestoswap...
*exp(-diff/(iterations*temperature)));
if numberofcitiestoswap == 0
numberofcitiestoswap = 1;
end
complete_temperature_iterations = complete_temperature_iterations + 1;
iterations = iterations + 1;
end
end
clc
fprintf(’\t\t\tIterations = %d\n’,iterations);
fprintf(’\t\t\tTemperature = %3.8f\n’,temperature);
fprintf(’\t\t\tIn current temperature for %d times\n’,...
complete_temperature_iterations);
end
previous_distance