Ant Algorithm

Let's now look at the ant algorithm in detail to better understand how it functions for a specific problem.

Network

For this discussion, the environment in which our ants will exist is a fully connected bidirectional graph. Recall that a graph is a set of nodes (or vertices) connected via edges (or lines). Each edge has an associated weight, which we'll identify as the distance between the two nodes connected by the edge. The graph is bidirectional so that an ant can traverse the edge in either direction (see Figure 4.4).

Figure 4.4: Example of fully-connected bidirectional graph V with edge set E.

The Ant

An ant is a single agent within the ant algorithm, commonly part of a larger population (colony) used to solve a given problem. The ant is endowed with a set of simple rules that define how it chooses its path through the graph. The ant maintains a tabu list, which is simply a list of nodes that it has visited. This list is kept so that the ant moves through each node only once. A path between two vertices on a graph where each vertex is visited only once is known as a Hamiltonian path (first proposed by mathematician Sir William Hamilton).

The ant also maintains the list of nodes in its current tour in the order in which the ant has traveled. This is used later to identify the tour length through the nodes.

While in nature an ant will lay pheromone along the trail as it travels , in the ant algorithm the ant distributes pheromone on the edges of the graph once the tour is complete. The reason for this will be discussed in the section titled "Ant Tour."

Initial Population

A population of ants is created and then uniformly distributed across the nodes of the graph. Distributing the ants equally across the nodes is important because we want all nodes to have an equal chance as a starting point. Starting each ant in the same place would assume that the particular node was the optimal starting node ”something we simply don't know.

Ant Movement

Ant movement is based upon a single, very simple, probability equation. While an ant has not yet completed a tour (visited all nodes within the graph, otherwise known as a path), the following equation is used to identify the next edge to take (Equation 4.1).

(4.1)  

where ( r , u )is the intensity of pheromone on the edge between nodes r and u, ( r,u ) is a heuristic function that represents the inverse of the distance measure of the edge, ± represents a weight for the pheromone, and ² a weight for the heuristic. The ± and ² parameters define the relative importance of the two terms and how much they factor in to the probability equation. Recall that an ant travels only to nodes that have not yet been visited (as defined by tabu ). Therefore, the probability is calculated only for those edges that lead to nodes not yet visited. Variable k represents the edges that have not yet been visited.

Ant Tour

An ant tour exists when an ant has completed its visit to each of the nodes on the graph. Note that no cycles are permitted, based upon the existence of the tabu list. Once the ant tour is complete, the length of the entire tour can be computed. This is simply the sum of all distances of edges traveled by the ant. Equation 4.2 shows the amount of pheromone that is left on each edge of the tour for ant k. Variable Q is a constant.

(4.2)  

This quantity is a measure of the trail ”smaller trail lengths represent higher pheromone levels while higher tour lengths represent smaller pheromone levels. This quantity is then used in Equation 4.3 to increase the pheromone along each edge of the tour.

(4.3)  

Note that this is applied to the entire path, so that each edge is provided with pheromone at a level proportional to the shortness of the path. This is why we must wait until the tour is complete before updating the pheromone levels, otherwise the actual tour length would not be known. Constant is a value between 0 and 1.

Pheromone Evaporation

On the initial tour, each edge has the same probability of being taken. In order to slowly remove edges that are part of poor paths through the network, pheromone evaporation takes place throughout all edges of the network. Using constant from Equation 4.3, we get the evaporation Equation 4.4.

(4.4)  

Therefore, we use the inverse coefficient of trail updates for pheromone evaporation.

Restart

When the ant tour is complete, the edges updated based upon the tour lengths, and evaporation on all edges has been performed, the algorithm is restarted. The tabu list is cleared and the tour length zeroed. The ants are permitted to migrate through the network using Equation 4.1 as a guide to the next edge to be investigated.

This process can be performed for a constant number of tours, or until no changes have been seen for some number of tours . The best path is then emitted as the solution.