Introduction

In nature ants are particularly adept at finding the shortest path between their nest and a food source, and are able to do this without any visual feedback. Ants initially wander randomly and upon finding food return to the colony. On an ant's return trip to the colony the ant lays down a pheromone trail. When other ants discover a pheromone trail their movements become less random and they will follow the trail. The trail will lead them to food as well and the whole process will continue. However, these pheromone trails evaporate over time, reducing the attractiveness of a particular trail to other ants.

Example in Nature

Consider two ants who are traveling in the same direction who encounter an obstacle. To the ants, both paths are equally likely to be the best path in negotiating the obstacle. Given this equal likelihood, one ant chooses the upper path and the other chooses the lower path.

Ant Example 1

The ant which chose the lower path will reach the food first and begin making the return trip before the other ant reaches the food. Since the lower path is shorter, more ants will travel it than the upper path in the same amount of time. Thus, the pheromone levels of the shorter path will be higher and more attractive to other ants. This process creates a positive feedback loop which will eventually localize an optimal path.

Ant Colony Optimization and the Traveling Salesman Problem

Ant Colony Optimization (ACO) is a class of algorithms which make an analogy between ants in nature and solving combinational optimization problems using metaheuristics. The algorithm we are going to focus on is Ant System which was initially proposed by Colorni, Dorigo and Maniezzo in 1996. Ant System is essentially the prototype for all other ACO algorithms since it conforms most truly to how ants interact in nature.

A common application of, and obvious fit for, ACO is to provide solutions for the Traveling Salesman Problem. The Traveling Salesman Problem can be defined as follows: Given a number of cities and the distances between any city to any other city, what is the shortest round- trip tour that visits every city exactly once and returns you to the city from which you began. By placing a number of ants on a fully connected graph of cities the ants can complete individual tours and eventually locate an optimum tour.

The problem however, is not that the ants can produce a solution, since solutions are produced every iteration, but which solution is best. By parallelizing the algorithm we can obtain a larger amount of solutions in the same amount of time, thus increasing the probability that we find the most optimum tour.

Ant System Details

The Algorithm


while not terminated do
	for each ant k do
		repeat
			choose in probability the state to move into
			append the chosen move to the k-th ant's tabu list
		until ant k has completed its solution
	end for
	for each ant move (i,j) do
		compute Δτij
		update the trail matrix
	end for
end while

Probability Function

Each ant utilizes a simple probability function which it uses to decide which state to move to next. The function computes the product of pheromone influence and visibility influence for the current node and divides that by the sum of the the influence products of all states available (states not in the current ant's tabu list). The constants α and β are used to control the influence pheromone vs. edge visibility (inverse of the edge length). If α > β, pheromone level will have a greater influence in the ant's decision. If β > α, edge visibility will have a greater influence.

Ant System Probability Function
Where,

Pheromone Update Function

As time progresses the algorithm must update the pheromone trails the ants have left behind. First the current pheromone level is evaporated by multiplying the current pheromone level τij by a number which will be between 0 and 1 (non-inclusive), which is dictated by a constant ρ. After evaporation, the pheromone level for the edge is increased.

Pheromone Update Function
Pheromone Deposit Amount
Where,

Implementation

I have chosen Message Passing Interface (MPI) and the C programming language to implement the Ant System. For visualization purposes I am using OpenGL and GLUT to display the final solution produced by the ants. The root process (process 0) loads a series of city coordinates from a file. The root process will then broadcasts the list of cities to all processes. All processes then act independently to produce their own set of solutions for the problem. After a predetermined number of tours the root process gathers the single best paths from all nodes and from those, finds the most optimum tour found by the program so far. This optimum tour is then broadcasted to all processes. Every process uniformly flattens their pheromone trails and highlights the best tour received from the root node. The process continues a predetermined number of times until arriving at a final solution.

Testing

The Problem

A total of 180 trial runs of the program were performed; 30 trial runs for each of 1, 2, 4, 8, 16, and 32 processes. The problem was kept the same across all test runs and the details of the problem used are:

Results

The results of the test are pleasing. By adding more processes the variability of the solutions is reduced considerably. The decrease in the standard deviation of the solutions found is fairly linear. Minimum and maximum solutions found also decrease with the increase in processes. This demonstrates a reduced width in the overall spread of solutions as we add processes. The time the individual trial runs took to run was very constant, ranging between 30-35 seconds.

Testing Results

Analysis

The reason the total run time of the program remains constant, despite the number of processes the program is run on, is a characteristic of the implementation. Each process run as an independent entity in the parallel scheme, forming its own solution. The solutions are collectively pooled every 100 tours and the best answer is distributed back to every process. In order to implement this behavior the processes must perform blocking communication which acts as a syncing mechanism in the program. This means that running the program as 1 process is the same as running it as 32 processes, with the exception of some added overhead in communicating with more processes.

The increase in the quality of answers we receive from the program are due to the adding of total solutions the program generates. Since every process generates answers independently, adding more processes will generate more solutions to choose from. The more solutions there are to choose from, the higher the possibility finding a shorter distance.

The Program

Download the Source Code

Requirements

Building

If you have OpenGL and GLUT installed on your machine call:

$ mpicc -o acotsp acotsp.c -D OPENGL -lOPENGL -lGLUT -lm

Otherwise call:

$ mpicc -o acotsp acotsp.c -lm

An alternative to using GLUT for visualizing the output is Processing. Included in the program is a way to export a script that can be pasted into Processing for display. To take advantage of this functionality, call:

$ mpicc -o acotsp acotsp.c -D PROCESSING -lm

Generating the Cities

Before running the program we need to create a list of cities for the program to use. A utility has been provided with the main program called citygen. First compile citygen by calling:

$ cc -o citygen citygen.c

To run citygen, simply call:

$ ./citygen <CITY COUNT> <MAXIMUM WIDTH> <MAXIMUM HEIGHT> <FILENAME>
Where,

Running the Program

$ mpirun -np <NUMBER OF PROCESSES> acotsp <CITIES FILENAME>
Where,

References