Ryan Goldsmith

The UI of the project is made completely using WPF, I chose WPF as I have experience with it and it is a simple solution to making an effective UI. As the projects outcome is to compare results the UI is an added benefit, and is very helpful when debugging. It can be argued that the application could just be a console application returning results however I wanted to create a more interactive application with visual feedback.

The benefit of WPF is I can easily drag and drop a element onto the application, give it a name and the appropriate data it needs, then use it within the code either giving a button a click event or taking the data from a text box.

Ants

There are a few key differences with Ant Colony Optimisation algorithms and the way it has been implemented within my project these are as follows:

> Artificial Ants - The ants within my project have memory and need to have memory as we do not want them to travel to nodes they have already travelled too. They are also more aware of their surroundings, meaning they know the distance to the next nodes.

> No "main" Nest - Meaning when the ants are created within the algorithm they are scattered between the nodes, meaning each node should have a equal amount of ants at each of them for when the algorithm starts

public void Initialise(List nodes)
{
	originalMap = new List<.TSPGraphNode>(nodes);
	paths.Clear();
	antColony.Clear();
	bestAntPerIteration.Clear();
	lastBestDistance = double.MaxValue;
	iterationsSinceBestChange = 0;
	totalIterations = 0;

	for(int i = 0; i < nodes.Count; i++)
	{
		
		for(int j = 0; j < antPerNode; j++)
		{
			Ant ant = new Ant(this);
			ant.currentTour.Add(nodes[i]);
			antColony.Add(ant);
		}
	}
}
							

public void AddPheromone()
{
	double totalDistance = GetTotalDistance();

	Path pathToDecay = null;
	for (int i = 0; i < currentTour.Count - 1; i++)
	{

		pathToDecay = manager.GetPath(currentTour[i], currentTour[i + 1]);

		pathToDecay.pheromoneLevel += manager.pheromoneConstant / totalDistance;
	}

	pathToDecay = manager.GetPath(currentTour.Last(), currentTour.First());
	pathToDecay.pheromoneLevel += manager.pheromoneConstant / totalDistance;
}
							

Pheromones

The way that ants communicate to each other is through the environment by leaving pheromones, within this application the ants drop a level of pheromones on a "Path" where a path is two nodes. These paths are then analysed when the ant comes to choose which node to travel to, the more pheromones on a path the more influence a ant feels to take that path.

To incorporate pheromone decay I utilised a constant value to multiply the pheromone level by, also as the application is running per iteration we have no "Time" therefore we need to add pheromones dependant on the distance the ant has travelled as opposed to the time it took.

Due to the time constraints of the project I only attempted to optimise one of the programs, I did 2 attempts of optimising the genetic algorithm.

First optimisation I tried implementing a dynamic population size for the genetic algorithm however this lead to inaccurate final results and was deemed a failure.

The second optimisation I tried was to add elitism to the algorithm, where the best chromosomes of the previous population are placed into the next population, this ultimately lowered the time it took to get to a final result as adding elitism is encouraging a much stronger population.