%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Ant system (AS) for TSP.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;
clc;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Data
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cityLocation = LoadCityLocations();
numberOfCities = length(cityLocation);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Parameters
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
numberOfAnts = 20; % To do: Set to appropriate value.
alpha = 1.0; % To do: Set to appropriate value.
beta = 5.0; % To do: Set to appropriate value.
rho = 0.5; % To do: set to appropriate value.
% To do: Write the GetNearestNeighbourPathLength function
% nearestNeighbourPathLength = GetNearestNeighbourPathLength(cityLocation); % To do: Write the GetNearestNeighbourPathLength function
% tau0 = numberOfAnts/nearestNeighbourPathLength;
targetPathLength = 123.0;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Initialization
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
range = [0 20 0 20];
tspFigure = InitializeTspPlot(cityLocation, range);
connection = InitializeConnections(cityLocation);
pheromoneLevel = InitializePheromoneLevels(numberOfCities, tau0); % To do: Write the InitializePheromoneLevels
visibility = GetVisibility(cityLocation); % To do: write the GetVisibility function
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Main loop
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
minimumPathLength = inf;
iIteration = 0;
while (minimumPathLength > targetPathLength)
iIteration = iIteration + 1;
%%%%%%%%%%%%%%%%%%%%%%%%%%
% Generate paths:
%%%%%%%%%%%%%%%%%%%%%%%%%%
pathCollection = [];
pathLengthCollection = [];
for k = 1:numberOfAnts
path = GeneratePath(pheromoneLevel, visibility, alpha, beta); % To do: Write the GeneratePath function (and any necessary functions called by GeneratePath).
pathLength = GetPathLength(path,cityLocation); % To do: Write the GetPathLength function
if (pathLength < minimumPathLength)
minimumPathLength = pathLength;
disp(sprintf('Iteration %d, ant %d: path length = %.5f',iIteration,k,minimumPathLength));
PlotPath(connection,cityLocation,path);
end
pathCollection = [pathCollection; path];
pathLengthCollection = [pathLengthCollection; pathLength];
end
%%%%%%%%%%%%%%%%%%%%%%%%%%
% Update pheromone levels
%%%%%%%%%%%%%%%%%%%%%%%%%%
deltaPheromoneLevel = ComputeDeltaPheromoneLevels(pathCollection,pathLengthCollection); % To do: write the ComputeDeltaPheromoneLevels function
pheromoneLevel = UpdatePheromoneLevels(pheromoneLevel,deltaPheromoneLevel,rho); % To do: write the UpdatePheromoneLevels function
end