Sample Iteration

Now that we have the basic algorithm under our belt, let's walk through a simple iteration of the algorithm to see the equations in action. Recall from Figure 4.1 the simple scenario of two ants taking two paths to reach the same destination. Figure 4.5 provides a simplified view of this with two edges between the two nodes (V and V ₁ ). Each edge is initialized so that each is given equal probability of being selected.

Figure 4.5: Initial configuration of the sample problem.

Two ants are started at node V , and are labeled A and A ₁ . Since the probability is equal that a path will be taken, we'll ignore the path equation in this cycle. In Figure 4.6, each ant takes a separate path (ant A takes the upper path and ant A ₁ takes the lower path).

Figure 4.6: Simple ant tour completed.

Using the table provided in Figure 4.6, we can see that ant A traveled 20 steps while ant A ₁ only traveled 10 steps. Using Equation 4.2, we calculate the pheromone level that should be applied.

Tip  

We can alter the way the algorithm works by tweaking the parameters (such as , ± , and ² ). We can give more weight to the pheromone levels, or more to the actual distance between the nodes. Information on adjusting the parameters will be outlined after the source discussion.

Next, we use Equation 4.3 to calculate how much pheromone will actually be deposited. For ant A , this results in:

• = 0.1 + (0.5*0.6) = 0.4

For ant A ₁ , the pheromone result is:

• = 0.1 + (1.0*0.6) = 0.7

Next, we use Equation 4.4 to evaporate the pheromone on the trail. This results (for each trail) in:

• = 0.4*(1.0-0.6) = 0.16

• = 0.7*(1.0 - 0.6) = 0.28

These values represent the new pheromone levels for each trail (upper and lower, correspondingly). Now let's move our ants back to node V and use the probability Equation 4.1 to determine which path the ants should now take.

The probability that an ant will take the upper path (given a pheromone level of 0.16) is:

The probability that the ant will take the lower path (given a pheromone level of 0.28) is:

Given the two probabilities, with a very high likelihood , both ants will take the lower path, which also represents the most optimal path to the destination.