12 Ant Colony Optimization, branch and bound, refinement search

Bhushan Trivedi

Introduction

Another topic which is quite popular in researchers is the Ant Colony Optimization. It is about learning from nature, build simple systems to solve complex problems by providing better and parallel methods. Again, we touch upon ACO as it helps us solving difficult problems. We will also look at another important method to help reduction in search, branch and bound and also a method called refinement search which uses branch and bound over solution search.

Ant Colony Optimization

Learning happens when you look at surrounding and find out what others doing to solve the problem you are set out to solve. When you share information that you have and receive information from others, you are likely to strengthen the understanding of both parties.Researchers looking from inspiration from nature found an interesting thing about how ants find their food. When the ants set out to find the food source from their nest, they start randomly in the initial run but then when some ants learn about some food source, others soon follow suit and make sure all of them converge to the optimum path to the food source. They also have found to adapt to the situation when the optimal path does not remain optimal, for example when an obstacle is placed along the path. The researchers have tried solving similar problems mimicking the behaviour of ants.They devised an algorithm which is capable to work with small components, each of which can share information with others and they make decision based on collective information. This algorithm is also capable to discover new optimal path again when original optimal path is no longer optimal. This algorithm is known as ant colony optimization and is used by many researchers to find solutions of many complex problems.

To understand ACO algorithm, we must first of all understand what ants do.

How ants discover optimal paths

Ants have received attention from researchers because of their ability to work in a coordinated way. A colony of ants has many ants and their primary job is to look for a food source and if found, start bringing food from food source to their nest. Not only that they find food source, but also to find the shortest path. Another good point about the behaviour of ants is that they are capable to rediscover shortest path when the original shortest path is closed due to some obstacle along the path. This seemingly complex problem solving ability is achieved by using a simple mechanism.

When ants set out to search for food, all of them start traveling in random directions first. When they travel over any path, they travel at almost constant speed and they also spray pheromone along the path in a constant manner. The pheromone sprays evaporate at constant speed too. The ants are capable to smell the pheromone along the path and can learn about the quantity of it. If another ant follow the same path, the amount of pheromone is just doubled and it smells stronger than other paths. Ants tend to follow a path with strongest pheromone. The strength of the pheromone depends on two things, number of ants travelled on that path and when. As more ants have travelled that path, as more ants means more pheromone. When the path is recently travelled it has more pheromone, as if the path is old, the pheromone would have been evaporated. This simple technique, choosing the path with stronger pheromone value, is not only able to find shortest paths, it also helps revising paths when obstacles are placed along the path.

Why this method works? For a simple reason that the ants which are successful in finding food is likely to return back using the same path and also start ferrying on the same path for other iterations. Those frequent travelling makes the path laden with more pheromone1. Suppose a new ant starts travelling for a food source, it prefers one of the trails other ants already generated. If it meets with a food source, it will return back, strengthening the pheromone and making the route more attractive. If it cannot find a food source, it won’t be coming back on the same path and thus the pheromone along the path gets evaporated and does not attract other ants. Thus the behaviour directs the search in successful directions and inhibits in unsuccessful direction.

Also, if two ants have found two different paths to food, the shorter path has more pheromone as the ant travelling on a shorter path returns back fast and thus have stronger pheromone smell. On the contrary, when the ant travelling on a longer path, makes less number of trips and thus the pheromone on that trail is comparatively less. Also when ants tend to follow such shorter paths, more and more ants follow this path and thus making it stronger with every such visit to food.

Let us try to understand this with an example. Look at figure 12.1. If we have two ants starting from a point A and reach to a point D. Assume two ants travel from A to D using two different paths, A-B-D which is travelled by ant-1 and A-C-D which is travelled by ant -2. Assume A-C-D distance is twice as large as distance covered in A-B-D route. Obviously both the ants have no idea about that. Now both ants starts ferrying food from D back to A with constant speed. While ant-1 traveling over A-B-D can take ten trips to D, the other ant can only have 5 such trips and thus the A-B-D path has more pheromone value than A-C-D path. Thus if there is another ant (let us call it ant-3) who is looking for food, will choose A-B-D route which is shorter.

Figure 12.1 two paths to D from A, via B and via C

This will increase the amount of pheromone over the A-B-D link further and thus makes it more attractive which in turn invite more number of ants to follow that path and so on. Eventually all ants start travelling over that short path and none would travel over the longer path.

• 1 This is also true with humans. If you have lost your path in jungle, you may prefer to walk on a trail others have walked over rather than trying a random path.

An interesting twist comes when suddenly the path is blocked due to some reason. The ants travelling on the path realizes that there is no path ahead at the place where the obstacle is placed. They will have to start all over again randomly in all directions from that point.Some take the path below the obstacle and some of them choose the path above. They again start looking for stronger pheromone smell. Both outgoing and incoming ants face the same problem. Their random paths meet sometimes. When the ants travelling in different directions find each other, they are attracted to follow each other’s path (as they still have strong pheromone value) and they are again connected.

Let us again take an example. Figure 12.2 depicts the case where there is an optimal path from A to F passing through B, C, D and E is already established and ants are using it to bring the food back to their nest. Now suddenly the path is blocked by an obstacle depicted by figure 12.3. The ants hitting the obstacle try in random directions once again. In fact two directions along the obstacle are important, above and below the obstacle. Both types of ants, traveling from A to F and from F to A have to try for alternate solutions. While traveling in both directions, the path which is already explored (indicated by thicker lines, going from C to obstacle and obstacle to E) contain more pheromone and thus more likely to be chosen. Not only that, if some ants found the route at the edge of the obstacle (shown as two paths, above and below the obstacle), they are also going to attract ants coming from the opposite direction. In fact when ants coming from both sides meet at a certain point, they tend to travel along the path the opposite direction ants travelled for the simple reason that it has more pheromone. As we have already seen before, though both paths, above and below the obstacle are correct paths, the path below is little shorter, results in more pheromone being deposited by ferrying ants and thus more likely to be preferred. Thus despite obstacles, the ants can rediscover the optimal path using the same technique.

Figure 12.2 The optimal path to the food from A to F

This simple method for search has many good elements associated with it. In fact, this method invariably finds a shortest path from the food source and ants’ nest. Not only that, they will be able to generate optimal paths again when the world that they observe changes suddenly. This is an example of simple agent (the ant) with limited intelligence and collective efforts solving a difficult problem. The technique they use, leaving the pheromone trails, and deciding how good or bad based on crowdsourcing and timeliness, as the pheromone strength depends on number of ants visited that path and how recently, is proved to be quite effective.

When a computer algorithm tries to mimic the behaviour of ants to find a shortest path to a destination, we call it ant colony optimization algorithm. This algorithm is adaptive in nature as it adapts itself with the changing world2.

The ACO assumes multiple agents working on same problem. These agents tends to follow trails of other agents. Each agent travels on its own in the search space but is not only influenced by the heuristic value that it calculates for all alternatives that it has for a typical move but also by how many other agents preferred that path. This behaviour is like sharing experience. Humans are quite fond of that. Social networking sites and many e commerce websites provide an option to give rating to products that they sell or some opinion that they have about anything. A user might use his own reasoning to buy a product and also see how other reviewers comment about the same. ACO works in that fashion.

The algorithm is characterized by ability of each agent to work in parallel and pass information to each other which help them learning about better paths. This has some similarity with GA. In GA, solutions are broken apart and reconstructed based on goodness of that solution. Here agents builds on solutions produced by other agents. This is kind of crowdsourcing.

If you also find this algorithm close to Simulated Annealing, you are not far. There are multiple neighbours in both algorithms and the algorithm chooses one in both cases. In SA, the worse move also may be chosen with probability ∆E in case of SA. Sometimes the move with lesser pheromone is also allowed to be chosen in ACO based on some probabilistic calculations. In ACO, a move with more pheromone value, even if lesser than current, is allowed to be chosen. In case of no pheromone value, the next move is randomly chosen, quite similar to SA  Though the ACO algorithm is similar it is not same as any other algorithm, especially the idea of using simple systems and combining them to harness power is quite unique. In that sense one may even compare them with neural networks.

• 2 In fact there are many variants of this basic algorithm and many times it is denoted as a class of algorithms and not a single algorithm.

The TSP that we have seen during our discussion during module 8 can also be solved using ACO. Let us learn how that is done.

Solving TSP problem using ACO

The Travelling salesman problem can be solved using ACO. The strategy is quite simple

1. Each segment between each pair of cities is initialized with pheromone value of 0.
2. Each agent is given the job of finding out the tour in parallel, choosing a random city to start with.
3. Once the tour is completed, the ant looks at the distance it has to travel for that tour
4. For all the segments of that tour (for each pair of cities travelled),

• Pick up the first segment
• The agent places pheromone value inversely proportional to the length of the tour
• If the segment is last segment quit
• segment = next segment
• go to b

5. When this phase is over, each segment visited will have some pheromone value set, while visited by multiple agents, it will have a cumulative value of pheromone
6. If the terminating criteria is reached (for example any tour with total distance less than some value is found), we will terminate, otherwise continue
7. Each agent is asked to start all over again from any random city, segment by segment, like in a previous case.
8. Each agent might encounter multiple paths during the tour while visiting a particular city.
9. In that case each segment between city i and city j contains collective pheromone value of all agents travelled through it. (This does not happen in the first iteration as the segments do not contain pheromone values. In first iteration all agents travel randomly. )
10. To choose next city in turn, it checks the pheromone value of all neighbouring cities. It will use probability based decision making process. The probability of choosing a city with more pheromone is higher than the lesser one.
11. If the current city is not the last on the tour go to 8
12. Each agent calculates the tour cost and update the pheromone values accordingly.
13. The pheromone value is also decreased by a constant amount for edge containing each pair of cities. This indicate evaporation of pheromone.
14. Go to 6

Calculating the pheromone value

One typical query may be on how pheromone values are updated. Usually they are updated periodically. At the end of each period, the values are updated as follows.

The pheromone value for next period = the pheromone value of previous period * (1 – decrement in that period) + new pheromone vaue added in current period The value of the previous period is not taken as it is. The pheromone is constantly evaporated and thus the value of the previous period is reduced by a constant value. The pheromone value for the next period is thus less by that margin. So we multiply the value by (1 – decrement) to get the remaining pheromone value. We also have to add new pheromone produced by ants travelling over that link during this period. So the next term indicates so. The decrement of pheromone is described by variable ρ, the pheromone values are indicated by variable τ so the equation is usually written as

τt+1 = τt(1 – ρ) + ∆τt+1

Where the term∆τt+1 indicates the amount of pheromone added during the period between time t and time t + 1. If there are n ants who contributed to the addition of the pheromone value for that duration, the term ∆τt+1 is basically a summation of all such contribution. It is written as

∆τt+1 = ∑     ∆τt+1,i

Where ∆τt+1,i is contribution from ant number i.

This value is most important for solving the problem. Let us take our travelling salesman problem once again. The pheromone for each of the links across the path must be calculated for each tour. For example we might be interested in calculating pheromone value of the link B-C which might appear in many tours including A-B-C-D-E-F-G-H. Obviously the ants not traveling over that line the value of ∆τt+1,n is 0. What is the value for the ants travelling on that line? One good solution is to make it inversely proportional to the length of the tour through that link. Thus a shorter tour adds more pheromone to that link. A usual calculation is performed based on following formula

∆τt+1,i= C/length where C is a constant value and length is the length of the tour (only for ants travelling over that link)

What if that link appears in more than one tour? The pheromone value is more and thus the link has higher priority than others.

ACO is used to solve many other problems. It is basically a multi-agent algorithm using probability distribution which can be applied to any case where it is applicable. Ant Colony optimization has found its usage in solving a vehicle routing problem, assignment problem (where jobs are assigned to machines to optimize machine usage and other things), set problem (for example if we can determine if a set S can be partitioned into two distinct sets S1 and S2 where summation of the elements of S1 and S2 are equal, image processing which highly parallel processing (for example detecting an edge from an image, like determining the boundary of India from a satellite image obviously not containing any boundaries). The biggest advantage of ACO is the ability of the algorithm to dynamically adapt to the changing situation. For example traffic congestion is a continuously varying problem so the solution demands that dynamism.

Branch and bound

Branch and bound is denoted as a search algorithm but it is also a way to optimize the search paths. To understand the idea, let us pick up travelling salesman problem once again. Let us assume we have already explored some tours and have got some candidate solutions with tour length being 56,38 and 34. Now we know that so far the best tour so far is 34. Now if the new tour is being processed and midway we find the total distance going beyond 34. Is there a point to proceed further? No. Whatever this tour will produce will be worse than the best so far solution. We have to eliminate this option and stop exploring this tour.

In fact unless we are at the final city, we are eliminating multiple tours. For example we have already found one tour with distance 34 and after exploring 4 out of 7 cities we found the path going beyond

34.   Let us assume that the tour is A-B-C-D is being explored with cost > 34. When we stop our search, we do not only eliminate one but all tours beginning with A-B-C-D; including A-B-C-D-E-F-G, A-B-C-D-F-E-G, A-B-C-D-G-F-E,…We can stop exploring that tour right when it exceeds the current lower bound. It can be applied in a constructive search like TSP in earlier example or can also be using a solution space search. In fact branch and bound is just independent of how you proceed with your search, it is a method of making sure you do not explore known longer paths.

The algorithm works like this

1. Pick up the next city from the list of all cities. Start a new tree with that node designating it as a root node and execute a tod for a complete tour.

• Pick up the cheapest solution or node, for example D in case of tourbeginning from A-B-C.
• Refine solution with the addition of that node, calculate the total distance to be covered, if the distance goes beyond the best so far (minimum so far), abort the tour and start with a parent node after going to a
• If the complete solution is not found go to 2 (that means if the city is not the last in the tour we will go to next city for that tour).
• If the city is the leaf nod(that means it is the last city of the tour), return the solution when we reach to final city, add this solution to the list of solutions.
• Go to the parent node of the current node and go to a, if no node left (all tours under the given city is explored) go to 1

2. Return the best solution from the list of solutions.

The idea is simple. The branch and bound algorithm has to look for cheapest path always and ignore the sections of search space known to be expensive. This is quite analogous to our nearest neighbour algorithm which we discussed in module 8. The biggest difference is that the nearest neighbour algorithm is for TSP only while branch and bound is applicable in other situations as well.

Let us take a problem to understand the difference. Suppose we are interested in finding a shortest path between any two cities. (A little different problem than travelling salesman). Suppose we have to find out shortest path between cities A and E. Suppose there are a few alternatives and we may choose one at random. Look at figure 12.1. The path chosen as the first move is A-B-C-E and the length comes out to be 225 km. Now we pick up next alternative, say A-B-D-E and the A-B-D cost comes out to be 250, should we explore it further? No, it will not be shorter than the earlier path. If the path A-F comes out to be 225, both A-F-D route paths and A-F-G route paths are just ignored. If we are lucky and the path chosen earlier is better than most, we save lot of time and computation by using this simple method.

Another difference is, the nearest neighbour does not give any guarantee of providing the best (optimal) path, the branch and bound does provide the guarantee that it will find the cheapest path as it won’t allow any path with lower cost than the proposed path.

Figure 12.4 The shortest path between two cities

Refinement search

The branch and bound technique applies to solution search as well. When it is applied to solution search, it is called refinement search. Let us see how it works. The method is same as we have seen in the previous segment but now we are applying it at the complete solutions.

Suppose if we try to apply the branch and bound technique to the TSP. Now let us assume that we have seven cities as shown in the module no.8 and different paths between them are available like in module 8.

One typical way to use refinement search for TSP is to pick up a city as a root node and have all other cities connected as children. Thus each child represent a city other than the root. The first level of tree depicts first move from starting city to all other cities

From those cities, we have second level of the tree, they have similar children indicating cities other than the parent and itself. This second level describes second leg of the tour. We can complete the entire tree like this. The tree is as long as the tours and thus the maximum number of levels a tree can have is the length of the tour. In other words the tree describes each possible tour begins from the city described as the root node. This tree, in a way, describes a solution space for all solutions begin from root. We now need to search in this solution space and get the cheapest path.

For solving the complete TSP problem, we need to have as many trees as the number of cities. For example if we have seven cities A,B,C,D,E,F,G then we will have seven trees, one tree with root node as A, another with root node as B and so on. Each tree contains other cities as nodes at the second level. Each branch starting from the root node indicates the tour. The edges of the tree is weighted and the number indicates the distance between the cities. These seven trees describe the complete solution space for the TSP we have described. Let us see how we search through it to find out the cheapest solution. We will show how we can get cheapest path for one tree. We can do the same thing for all other trees. Now we can compare all solutions that we have got so far and select the cheapest from the lot.

Look at figures 12.2 and table 12.1. The distances are depicted as weights of the arcs in the graph in figure 12.23. Suppose now we assume one of the city as a root and draw a tree with every city being a children. In case if we decide the root to be A, figure 12.3 showcases how a tree indicating partial tours can be drawn. We can easily see that even with this trivial case with seven cities, number of combinations are overwhelming.

At any given point of time, the tour cost so far can be calculated. For example, according to the figure 12.3, the cost of the tour A-B-C-D is so far= 220+250+150 = 620. If we want to estimate the total distance of tour A-B-C-D-E-F-G, the cost of remaining part may be estimated using some assumption. One method to do so is to find out two shortest distances in a given row for a city yet to be visited and divide it by two. For example if we pick up city E, two of the shortest distances are 150 and 250 which sums up to 400 dividing by two yields 200. We are assuming, by picking up two shortest values, that the city is connected with others using nearest neighbours, something we have already explored in module 8. Based on these estimated values, all tours can be measured as summation of two components, one, which is already calculated, and other, which is estimated. We can pick up the shortest tour and when revise the estimate by replacing the estimate of the next level by a correct value. We may need to refine estimates of each tour connected with that edge. For example if now we have a revised distance for D-E, we may need to change estimates of both tours A-B-C-D-E-F-G, A-B-C-D-E-G-F. Similarly, on the other hand, if currently B-D sound least cost, and out estimation is 200 +150 /2 =175. Now we get the actual value to be 150, we will have to revise estimation of all tours which starts with A-B-D. This might continue till we get a complete tour with lowest actual value.

Figure 12.5 The TSP with weight of the edge represent the distance.

Table 12.1 The distance matrix for the TSP depicted in figure 12.2

One may argue that we can calculate all tour correct values rather than taking estimates. In our case of 7 cities, it is actually possible and we do not need to go for branch and bound. Unfortunately it is not so for a real case of larger number of cities. We cannot have all values calculated beforehand. We need to proceed with exploring children in this fashion.

Also, we are exploring the cases where the origin of the tour is A, what we will get at the end is the shortest tour starting from A. We must take all possible cities as root nodes and apply refinement search on them to find out shortest tours starting from other cities like tours starting from B, tours starting from C and so on. At the end, we have to pick up the best tour based on shortest tours that we found originating from all other cities.

This branch and bound helps us picking up shorter paths and avoid longer path, without using any heuristic. This search is basically a blind search but little better than breadth first search as we estimate and try going in right direction rather than looking for all options.

Figure 12.6 partial graph for the TSP depicted in 12.2 and table 12.1

Does branch and bound possible to be used where one can use Breadth First? Not advisable in all cases. Let us take the figure 12.1. We want to find shortest path between two cities, say A and E. If we use refinement search, the algorithm tend to travel to cities which are nearer to the originating city, i.e. A. Assume F is nearest to A, the search travels in that direction, next may be F to D which is shortest and so on. Eventually the search algorithm realizes that this is a bad path and take the next nearest neighbour but it wastes lot of time if the cities are situated in a way that there are many nearer cities to the originating city and the destination city is quite far from all of them. The refinement search tries to look for shortest path without knowing anything about the direction of the destination city. That is the problem. A breadth first search probably yields answer faster.

Summary

We started this module with an interesting algorithm derived from the behaviour of ants. Ants find the shortest path to food source by using a simple technique by depositing pheromone over the path it travels and prefer a path with higher value of pheromone. This simple algorithm not only is good enough to find a shortest path but also able to adjust to the situation when the shortest changes due to some external influence. This is a multi-agent, parallel algorithm more suited for multi core architecture. Brach and bound is a search method which keeps the log of cheapest path so far and avoid path which are longer than cheapest path. When Branch and bound is applied to solution space, it is known as refinement search.