Skip to main content
SpringerLink
Log in

Ant Colony Optimization: An Overview

  • Chapter
Essays and Surveys in Metaheuristics

Part of the book series: Operations Research/Computer Science Interfaces Series ((ORCS,volume 15))

Abstract

Ant Colony Optimization (ACO) is a class of constructive meta-heuristic algorithms sharing the common approach of constructing a solution on the basis of information provided both by a standard constructive heuristic and by previously constructed solutions. This tutorial is composed of three parts. The first one frames the ACO approach in current trends of research on metaheuristic algorithms for combinatorial optimization; the second outlines current research within the ACO framework, reporting recent results obtained on different problems, while the third part focuses on a particular research line, the ANTS metaheuristic, providing some details on the algorithm and presenting results recently obtained on the quadratic and on the frequency assignment problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley, 1989.

    MATH  Google Scholar 

  2. E. Aarts and J.K. Lenstra (editors). Local Search in Combinatorial Optimization. Wiley, 1997.

    MATH  Google Scholar 

  3. L.G. Anderson. A Simulation Study of Some Dynamic Channel Assignment Algorithms in a High Capacity Mobile Telecommunications System. IEEE Transactions on Communications, COM-21:1294–1301, 1973.

    Google Scholar 

  4. E. Bonabeau, F. Henaux, S. Guerin, D. Snyers, P. Kuntz, and G. Theraulaz. Routing in Telecommunication Networks with “Smart” Ant-Like Agents. Lecture Notes on Artificial Intelligence, 1437:60–68, 1998.

    Google Scholar 

  5. B. Bullnheimer, R.F. Hartl, and C. Strauss. An Improved Ant System Algorithm for the Vehicle Routing Problem. Annals of Operations Research, 89:319–328, 1999.

    Article  MathSciNet  MATH  Google Scholar 

  6. B. Bullnheimer, R.F. Hartl, and C. Strauss. A New Rank-Based Version of the Ant System: A Computational Study. Journal for Operations Research and Economics, 7:25–38, 1999.

    MathSciNet  MATH  Google Scholar 

  7. G. Di Caro and M. Dorigo. Antnet: A Mobile Agents Approach to Adaptive Routing. Technical Report IRIDIA/97-12, Université Libre de Bruxelles, 1997.

    Google Scholar 

  8. G. Di Caro and M. Dorigo. Antnet: Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research, 9:317-365, 1998.

    MATH  Google Scholar 

  9. W.C. Chiang and R. Russel. Hybrid Heuristics for the Vehicle Routing Problem with Time Windows. Technical Report, Department of Quantitative Methods, University of Tulsa, 1993.

    Google Scholar 

  10. N. Christofides. The Bionomic Algorithm. Presented at the Annual Conference AIRO’94, Savona, 1994.

    Google Scholar 

  11. A. Colorni, M. Dorigo, and V. Maniezzo. Distributed Optimization by Ant Colonies. Proceedings of the 1991 European Conference on Artificial Life, pages 134–142, Elsevier, 1991.

    Google Scholar 

  12. A. Colorni, M. Dorigo, V. Maniezzo, and M. Trubian. Ant System for Job-Shop Scheduling. Belgian Journal of Operation Research, Statistics and Computer Scence, 34:39–54, 1994.

    MATH  Google Scholar 

  13. D. Costa and A. Hertz. Ants Can Colour Graphs. Journal of the Operational Research Society, 48:295–305, 1997.

    MATH  Google Scholar 

  14. M. Dorigo. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano, 1992.

    Google Scholar 

  15. M. Dorigo, A. Colorni, and V. Maniezzo. Positive Feedback as a Search Strategy. Technical Report TR91-016, Politecnico di Milano, 1991.

    Google Scholar 

  16. M. Dorigo and G. Di Caro. The Ant-Colony Optimization Meta-Heuristic. In: New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, editors, pages 11–32, McGraw-Hill, 1999.

    Google Scholar 

  17. M. Dorigo and L. M. Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1:53–66, 1997.

    Article  Google Scholar 

  18. 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, 26:29–41, 1996.

    Article  Google Scholar 

  19. T.A. Feo and M.G.C. Resende. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6:109–133, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  20. L. M. Gambardella, E. Taillard, and M. Dorigo. Ant Colonies for the Quadratic Assignment Problem. Journal of the Operational Research Society, 50:167–176, 1999.

    MATH  Google Scholar 

  21. L.M. Gambardella and M. Dorigo. Ant-q: A Reinforcement Learning Approach to the Travelling Salesman Problem. Proceedings of the Twelfth International Conference on Machine Learning, Palo Alto, pages 252–260, Morgan Kaufmann, 1995.

    Google Scholar 

  22. L.M. Gambardella and M. Dorigo. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem. INFORMS Journal on Computing, 12:237–255, 2000.

    Article  MathSciNet  MATH  Google Scholar 

  23. L.M. Gambardella, E. Taillard, and G. Agazzi. Ant Colonies for Vehicle Routing Problems. In: New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, editors, pages 63–76, McGraw-Hill, 1999.

    Google Scholar 

  24. F. Glover. Heuristics for Integer Programming Using Surrogate Constraints. Decision Sciences, 8:156–166, 1977.

    Article  Google Scholar 

  25. F. Glover. Future Paths for Integer Programming and Links to Artifical Intelligence. Computers and Operations Research, 13:533–549, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  26. F. Glover. Scatter Search and Star Paths: Beyond the Genetic Metaphor. OR Spektrum, 17:125–137, 1995.

    Article  Google Scholar 

  27. F. Glover. A Template for Scatter Search and Path Relinking. Lecture Notes in Computer Science, 13363:13–54, 1997.

    Google Scholar 

  28. F. Glover and M. Laguna. Tabu Search. Kluwer, 1997.

    Book  MATH  Google Scholar 

  29. D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

    MATH  Google Scholar 

  30. H. Kawamura, M. Yamamoto, K. Suzuki, and A. Ohuchi. Multiple Ant Colonies Algorithm Based on Colony Level Interactions. IEICE Transactions Fundamentals, E83-A:371–379, 2000.

    Google Scholar 

  31. Y. Li, P.M. Pardalos, and M.G.C. Resende. A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem. In: DI-MACS Series in Discrete Mathematics and Theoretical Computer Science, 16:237–261, 1994.

    Google Scholar 

  32. S. Lin and B.W. Kernighan. An Effective Heuristic Algorithm for the Travelling Salesman Problem. Operations Research, 31:498-516, 1973.

    Article  MathSciNet  Google Scholar 

  33. V. Maniezzo. Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem. INFORMS Journal of Computing, 11:358–369, 1999.

    Article  MathSciNet  MATH  Google Scholar 

  34. V. Maniezzo and A. Carbonaro. An Ants Heuristic for the Frequency Assignment Problem. Future Generation Computer Systems, 16:927–935, 2000.

    Article  Google Scholar 

  35. V. Maniezzo, A. Carbonaro, M. Golfarelli, and S. Rizzi. An ANTS Algorithm for Optimizing the Materialization of Fragmented Views in Data Warehouses: Preliminary Results. Lecture Notes in Computer Science, 2037:80–89, 2001.

    Article  Google Scholar 

  36. V. Maniezzo, A. Carbonaro, D. Vigo, H. and Hildmann. An ANTS Heuristic for the Long-Term Car Pooling Problem. In: Proceedings of the Second International Workshop on Ant Algorithms, pages 78–81, Brussels, 2000.

    Google Scholar 

  37. V. Maniezzo and A. Colorni. The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and Data Engineering, 11:769–778, 1999.

    Article  Google Scholar 

  38. V. Maniezzo, A. Colorni, and M. Dorigo. The Ant System Applied to the Quadratic Assignment Problem. Technical Report IRIDIA/94-28, Université Libre de Bruxelles, 1994.

    Google Scholar 

  39. V. Maniezzo and R. Montemanni. An Exact Algorithm for the Radio Link Frequency Assignment Problem. Technical Report CSR99-02, 1999.

    Google Scholar 

  40. D. Merkle and M. Middendorf. An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problems. Lecture Notes in Computer Science, 1803:287–296, 2000.

    Article  Google Scholar 

  41. D. Merkle, M. Middendorf, and H. Schmeck. Ant Colony Optimization for Resource-Constrained Project Scheduling. In: Proceedings of the 2000 Genetic and Evolutionary Computation Conference, pages 893–900, Las Vegas, 2000.

    Google Scholar 

  42. R. Michel and M. Middendorf. An Island Model Based Ant System with Lookahead for the Shortest Supersequence Problem. Lecture Notes in Computer Science, 1498:692–700, 1998.

    Article  Google Scholar 

  43. C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall, 1982.

    MATH  Google Scholar 

  44. J.Y. Potvin and S. Bengio. The Vehicle Routing Problem with Time Windows — Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172, 1996.

    Article  MATH  Google Scholar 

  45. Y. Rochat and E.D. Taillard. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, 1:147–167, 1995.

    Article  MATH  Google Scholar 

  46. M. Solomon. Algorithms for the vehicle Routing and Scheduling Problem with Time Window Constraints. Operations Research, 35:254–265, 1987.

    Article  MathSciNet  MATH  Google Scholar 

  47. T. Stuetzle and M. Dorigo. Aco Algorithms for the Quadratic Assignment Problem. In: New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, editors, pages 33–50, McGraw-Hill, 1999.

    Google Scholar 

  48. T. Stuetzle and H. Hoos. Improvements on the Ant System: Introducing max — min Ant System. In: Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, G.D. Smith, N.C. Steele and R.F. Albrecht, editors, pages 245–249, Springer Verlag, 1998.

    Chapter  Google Scholar 

  49. T. Stuetzle and H. Hoos. The max — min ant System and Local Search for Combinatorial Optimization Problems: Towards Adaptive Tools for Combinatorial Global Optimization. In: Meta-Heuristics: Advanced and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, LH. Osman, and C. Roucairol, editors, pages 313–329, Kluwer, 1998.

    Google Scholar 

  50. E. Taillard. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing, 17:443–455, 1991.

    Article  MathSciNet  Google Scholar 

  51. E.D. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.Y. Potvin. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science, 31:170–186, 1997.

    Article  MATH  Google Scholar 

  52. S.R. Thangiah, LH. Osman, and T. Sun. Hybrid Genetic Algorithm Simulated Annealing and Tabu Search Methods for Vehicle Routing Problem with Time Windows. Technical Report 27, Computer Science Department, Slippery Rock University, 1994.

    Google Scholar 

  53. S. Tiourine, C. Hurkens, and J.K. Lenstra. An Overview of Algorithmic Approaches to Frequency Assignment Problem. Technical Report, T.U. Eindhoven, 1995.

    Google Scholar 

  54. H.P. van Benthem. Graph: Generating Radio Link Frequency Assignment Problems Heuristically. Master’s Thesis, Faculty of Technical Mathematics and Informatics, Technical University of Delft, 1995.

    Google Scholar 

  55. R. van der Put. Routing in Packet Switched Networks Using Agents. Technical Report RD-SV-98-276, KPN Research, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Scienze dell’ Informazione, University of Bologna, Via Sacchi 3, 47023, Cesena, Italy

    Vittorio Maniezzo & Antonella Carbonaro

Authors
  1. Vittorio Maniezzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Antonella Carbonaro
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer Science+Business Media New York

About this chapter

Cite this chapter

Maniezzo, V., Carbonaro, A. (2002). Ant Colony Optimization: An Overview. In: Essays and Surveys in Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 15. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-1507-4_21

Download citation

  • DOI: https://doi.org/10.1007/978-1-4615-1507-4_21

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4613-5588-5

  • Online ISBN: 978-1-4615-1507-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation