Thursday, February 10, 2005

Literature Survey - Metahueristic Algorithms: Ant Colony Optimisation

Abstract: This literature survey focuses on the ant colony metahueristic for solving combinatorial optimisation problems. It will research different approaches to the topic and investigate the state of the art before assessing its impact and use in real computer systems today.


1 Introduction

A metaheuristic is a simple strategy where by a solution to an optimisation can be found by exploring the solution space in some way. [Dict 04]
Ant Colony Optimisation (ACO) is a metaheuristic for solving combinatorial optimization problems. It was developed by Colorni et al in the early 1990’s and is based on the way that ants convey information about route efficiency to each other. [Colorni 91]
The idea is based on the way in which ants discover the most efficient path between the colony and a food source and vice versa. This is achieved by laying a trail of pheromones at each decision point in the journey, that is, where there is more than one possible route. The shortest route will be utilised more as the time taken to cross that path will be shorter; therefore the amount of pheromone build up will be greater on this route. Other ants decide which route to take based upon the amount of pheromone detected at that decision point. The shortest route will be more often travelled and pheromone build up will be higher until eventually all ants take this route. This is a form of autocatalysis, or positive feedback. [Dorigo 99]
This paper focuses on the use of models of this strategy in various optimisation problems and their efficiency compared to existing algorithms for that field.

2 Research into ACO

This process is used to develop algorithms in the field of metaheuristics. The paper focuses on its use in modelling ant colony optimisation to find the optimal solution or solutions, or in the case of racing algorithms, the best case that can be found in a limited period of time.

2.1 ACO in the Travelling Salesman Problem

In the travelling salesman problem the aim is to calculate the most efficient route where each city in the graph is visited once, it is used for route planning both for electronic and physical traffic.
Dorigo et al conducted the first research into this field. Because of the similarity between this problem and the way that ants reinforce efficient routes to food sources, it was the first field to which an ACO metaheuristic was applied. [Dorigo 95]
The first work into ACO in the TSP was conducted in 1995 on the Ant-Q algorithm. [Dorigo 95] This algorithm was an implementation of the ACO metaheuristic, it was tested and compared to well established algorithms such as Elastic Net, Simulated Annealing and Self Organizing map.
The tests were performed using the same hardware configuration and specification on a set of 50 node graph problems (50 city maps).
The results show that Ant-Q was nearly always the best performing algorithm; this illustrates that even in the early stages of research that ACO was a very effective concept.
Although this is true, the first ACO implementation, AS, did not manage to match the performance of other available algorithms of it’s time.
Ant-Q and the similar ACS, both researched by Dorigo et al have shown that it is now extremely capable as a technique to match the efficiency of leading solutions. [Dorigo 95] [Dorigo 96] [Dorigo 97] [Dorigo 99]

2.1 Racing Algorithm Metaheuristics

Another problem where this technique that has been used is the racing algorithm for configuring metaheuristics. [Birattari 02] This technique finds either an optimal solution or the most efficient one possible to the optimisation problem within a time constraint. It does this by discarding solutions from the finite set of possible solutions by finding an equally or more efficient solution from within the solution set.
The metaheuristic used in this research is best suited to repetitive problems: “problems where many similar instances appear over time”. [Birattari 02]
The example given in the paper is that of finding the best route for a delivery driver, which is essentially the travelling salesman problem.
This is similar to what is explored in the previously mentioned papers except that instead of simply finding the best route between two points (colony and food source) there are many cities that must all be visited at least once. Visiting the cities only once is not a constraint however, as the optimal solution may be one where a city is visited more often.
In tests on the ant colony optimization problem, when compared with two other racing algorithms, one of which does not correct for multiple executions of instances (tn-race) and the other that does (tb-race), the proposed algorithm (F-race) showed promising results. Correcting for multiple instances is a good precaution for an algorithm to take especially in this case where there is a time constraint. Performing a test on a particular instance needlessly will waste execution time that could lead to the algorithm not reaching an optimal solution and resorting to provide the most efficient found before the algorithm is forced to end.
Using 1000 pseudo-samples (randomly ordered samples) the three algorithms were run. As the aim of racing algorithms is to discard results until an optimal or as near to optimal result as time allows is found, the results can be taken as the number of possible instances still in the solution space after the time period expires (in this case 10 seconds). [Birattari 02]
The results show that (on average) F-race had 7.9 possible solutions remaining after the time period, tn-race 31.1 and tb-race 253.8. Obviously the fewer remaining solutions the more efficient the final result is likely to be and the more tested the remaining solutions will be. The remaining solutions are tested in order to find which to discard next, F-race's remaining solutions were tested 77.9 times where as tb-race's where tested/run 5 times. This would make the selection of an efficient solution much more likely by the algorithm that discards solutions quicker. However, having tested but not discarded solutions means nothing after the algorithm is forced to finish. Despite this, F race (the ACO approach to solving this problem), still reduced the solution space the most and found the most efficient route when compared to the two existing approaches using the same hardware configuration.
F race is described in the paper as the 'bravest' algorithm of the three, because it discarded the most solutions. [Birattari 02]
It is clearly a viable solution to solving this time constrained problem. This could have applications in real time optimisation problems, where an optimal solution is desirable but a timely solution is vital, such as TCP/IP traffic routing.

2.1 ACO in the Single Machine Total Tardiness Problem (SMTTP)

The use of the ACO metaheuristic in application on the Single Machine Total Tardiness Problem (SMTTP) has also been explored [Bauer 99] [Bauer 00]. SMTTP is the issue of finding the most efficient order to process tasks in a non multi-thread capable processor in order to reduce to a minimum the idle time of the processor. [Bauer 99]
Many solutions have already been devised and have been very successful - branch and bound is a well-known example. It is clear that the purpose of these algorithms is to maximise the throughput of the processor and that the solution will itself become part of the problem as it will require computation. Therefore there must exist a trade off between the processor time required to compute the next task and how much processor time is saved by using it efficiently. [Bauer 00]
To allow an ACO solution this paper proposes that the states of the processor be represented on a graph as the cities are in a travelling salesman problem, allowing it to function in a similar way. [Bauer 00]
The experiment used 250 benchmark tests containing different amounts of jobs awaiting scheduling to the processor. The results were shown as the net benefit of relocation for a job (NBR) as a percentage of overall efficiency.
An existing algorithm called M-NBR works by selecting two solutions, comparing the NBR and discarding the slower was used as a comparison. It was shown that ACO solved all problems to optimality and that M-NBR solved less than half to the most efficient solution. [Bauer 00]
The results show that in experiments with large sets of problem instances very good optimal solution times where produced: “Our approach outperformed all leading heuristics significantly.” [Bauer 99]
The use of ACO in this problem has shown to be a good solution as long as the problem size is sufficiently large. However, due to the increasing use of multiple processors and multi-thread capable processors it would be interesting to research whether ACO is suitable for these more complex challenges, as this simplified model could become obsolete in years to come.

2.1 ACO in Constraint Satisfaction Problems (CSP’s)

Constraint satisfaction programs are solved using a technique known as linear programming. Golomb and Baumert initiated development of this type of programming in 1965 when they proposed chronological backtracking. [Hemert 04]
Using ACO in CSP’s has proven to be a valid technique, a method was proposed by Hemert et al. [Hemert 04]
The finite set of solutions is slowly narrowed down in the search for the optimal solution (occasionally solutions). Before this a filtering technique is often used to cut out a set of improbable solutions to reduce the number of solutions to be examined. The use of ant colony optimisation in CSP’s is proposed to be very efficient as they do not search all possible solutions but instead follow a path through the solutions following trails of efficient solutions; this is the model of pheromone trails.
During experimentation on ACO and normal constraint programming it was shown that on small problems constraint programming was still the most effective but that as the problem size increased (over 35 variables was the transition) the ACO approach became significantly more efficient. [Hemert 04]
This shows that ACO is an effective technique for solving constraint problems providing that they are of a sufficient size, as CSP’s become exponentially more complex as more variables are added and ACO performs well in large, complex problems. [Hemert 04]
CSP’s are used for large problems such as deriving timetables for bus or train routes where there are many vehicles and destinations, or maximising the cost efficiency of mixing various grades of oil in the Industrial sector.
ACO is capable of providing a very efficient and timely method for finding the optimal solution compared to constraint programming.


3 Conclusion

Ant Colony Optimisation is a very versatile metaheuristic. Since it’s conception in the early 1990's it has been successfully used in travelling salesman problems, processor job scheduling and vehicle routing, as well as many other applications not touched on by this paper. It has been the subject of many research papers and its efficiency has improved greatly from it’s first implementation, AS [Dorigo 95]. It is now a real contender to many established benchmark algorithms.
One issue that seems to have arisen in the use of ACO on several different problems is that they do not perform particularly well on small problems; in CSP’s and SMTTP’s in particular this became evident. [Birattari 02] [Bauer 99] [Bauer 00]
This is due mostly to the period at the start of computation where the algorithm is in a state of disarray as not enough pheromone data has yet been computed. In this state progress is relatively slow when compared to progress towards the end of computation where much of the possible solutions have been discarded. In real ant behaviour this phase can last several minutes and is called the transitory phase, but after this order starts to emerge and a more efficient route starts to become default to the ants. [Dorigo 99]
This overhead is the cause for their unsuitability for small problems, by the time that transitory phase is over other algorithms have made headway in finding an optimal solution. It is only in larger problems that this overhead can be offset by the more efficient method of solving the problem.
Considering this restriction on the use of ACO, two things become obvious. Firstly, it is clear that they are not useful for small problems with a limited number of instances although they are evidently able to outperform established algorithms on large scale problems. Secondly, that if they are to become competitive on smaller scale problems that the transitory phase must be reduced or eliminated to allow the efficient later phase of computation to start earlier. Existing techniques to solve CSP’s often utilise filtering techniques to crop improbable areas of the solution space prior to attempting to find an optimal solution, a technique similar to this could be employed in ACO techniques in order to promote faster calculation. Another possibility is the creation of some pre-existing pheromone trails along promising routes calculated by past experience in order to reduce the transitory phase.
The results shown in this paper make it clear that ACO is already being used in a number of applications and that research is being carried out into its suitability for many more. One interesting paper that was not included was the use of ACO in cutting stock levels and packing bins, showing that even a supermarket has a need and use for advanced metaheuristic algorithms such as ACO. [Levine 03]



References

[Dorigo 99] M. Dorigo & G. Di Caro, The Ant Colony Optimization Meta-Heuristic, In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, McGraw-Hill, pp. 11-32 (1999).

[Dorigo 96] M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 26(1):29--41, 1996.

[Dorigo 97] M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53--66, 1997.

[Birattari 02] M. Birattari, T. Stutzle, L. Paquete, and K. Varrentrapp. A racing algorithm for configuring metaheuristics. Technical report, Intellektik, Technische Universitat Darmstadt, Darmstadt, Germany, 2002.

[Bauer 00] A. Bauer, B. Bullnheimer, R.F. Hartl, and C. Strauss. Minimizing total tardiness on a single machine using Ant Colony Optimization. Central European Journal of Operations Research, 8:125--141, 2000.

[Bauer 99] A. Bauer, B. Bullnheimer, R. F. Hartl, and C. Strauss. An ant colony optimization approach for the single machine total tardiness problem. In CEC99: Proceedings of the Congress on Evolutionary Computation, pages 1445--1450, July 1999.

[Colorni 91] A. Colorni, M. Dorigo, V. Maniezzo. Distributed Optimization by Ant Colonies, Proceedings of European Conference on Artificial Life ECAL '91, Paris, France, Elsevier, pp. 134-142, 1991

[Hemert 04] J. Hemert & C. Solnon. A study into Ant Colony Optimisation, Evolutionay Computation and Constraint Programming on Binary Constraint Satisfaction Problems, 2004, http://citeseer.ist.psu.edu/659158.html

[Levine 03] Levine, J. and Ducatelle, F. (2003). Ant colony optimisation and local search for bin packing and cutting stock problems. Journal of the Operational Research Society. (forthcoming).

[Handl 03] Handl J. and Dorigo M., 2003. On the Performance of Ant-based Clustering. Proc. of the 3 Int. Conf. on Hybrid Intelligent Systems, IOS Press, Dec. 03, Australia.

[Dict 04] www.dictionary.com, 19th November 2004

[Dorigo 95] Gambardella L. and M. Dorigo, 1995. Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252--260.

0 Comments:

Post a Comment

<< Home