Abstract
This paper reviews the theory and applications of ant algorithms, new methods of discrete optimization based on the simulation of self-organized colony of biologic ants. The colony can be regarded as a multi-agent system where each agent is functioning independently by simple rules. Unlike the nearly primitive behavior of the agents, the behavior of the whole system happens to be amazingly reasonable. The ant algorithms have been extensively studied by European researchers from the mid-1990s. These algorithms have successfully been applied to solving many complex combinatorial optimization problems, such as the traveling salesman problem, the vehicle routing problem, the problem of graph coloring, the quadratic assignment problem, the problem of network-traffic optimization, the job-shop scheduling problem, etc. The ant algorithms are especially efficient for online optimization of processes in distributed nonstationary systems (for example, telecommunication network routing).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
REFERENCES
Zakharov, A.A., Muravei, semya, koloniya (Ant, Family, Colony), Moscow: Nauka, 1978.
Dorigo, M., Optimization, Learning, and Natural Algorithms, PhD Thesis, Dipartimento di Elettronica, Politechnico di Milano (Italy), 1992.
Dorigo, M., Maniezzo, V., and Colorni, A., The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Systems, Man Cybernetics, Part B, 1996, vol. 26, no.1, pp. 29–41.
Levanova, T.V. and Loresh, M.A., Ant Colony Algorithm and Simulated Annealing for the Problem of p-Median, Avtom. Telemekh., 2004, no. 3, pp. 80–88.
Shtovba, S.D., Ant Algorithms, Exponenta Pro. Matematika v prilozheniyakh, 2003, no. 4, pp. 70–75.
Bonavear, E. and Dorigo, M., Swarm Intelligence: from Natural to Artificial Systems, Oxford Univ. Press, 1999.
Dorigo, M., Swarm Intelligence, Ant Algorithms and Ant Colony Optimization, Reader for CEU Summer University Course “Complex System,” Budapest: Central European University, 2001, pp. 1–38.
Shvetsova, N., Evolutionary Biology and High Technologies: Future Symbiosis, http://www.cnews.ru/newcom/index.shtml?2002/09/27/136108.
Goss, S., Aron S., Deneubourg J.L., and Pasteels, J.M., Self-Organized Shortcuts in the Argentine Ant, Naturwissenschaften, 1989, no. 76, pp. 579–581.
TSPLIB, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
Gen, M. and Cheng, R., Genetic Algorithms and Engineering Design, Wiley, 1997.
Bullnheimer, B., Hartl, R.F., and Strauss, C., A New Rank-Based Version of the Ant System: A Computational Study, Cent. Eur. J. Oper. Res. Econ., 1999, vol. 7, no.1, pp. 25–38.
Dorigo, M., and Gambardella, L.M., Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Trans. Evolutionary Computation, 1997, vol. 1, no.1, pp. 53–66.
Stutzle, T., and Hoos, H.H., MAX-MIN Ant System, Fut. Generation Comput. Syst., 2000, vol. 16, no.8, pp. 889–914.
Cordon, O., Fernandez de Viana, I., and Moreno, L., A New AGO Model Integrating Evolutionary Concepts: The Best-Worst Ant System, Proc. of ANTS2000—From Ant Colonies to Artificial Ants: A Series of Int. Workshops on Ant Algorithms, Brussels, 2000, pp. 22–29.
Cordon, O., Fernandez de Viana, I., and Herrera, F., Analysis of the Best-Worst Ant Systems and Its Variants on the QAP, Lecture Notes in Computer Science (Proc. III Int. Workshop on Ant Algorithms ANTS 2002), Berlin: Springer, 2002, no. 2463, pp. 228–234.
Reinelt, G., The Traveling Salesman: Computational Solutions for TSP Applications, Lecture Notes in Computer Science, Berlin: Springer, 1994, vol. 840.
Gambardella, L.M. and Dorigo, M., Solving Symmetric and Asymmetric TSPs by Ant Colonies, Proc. IEEE Conf. on Evolutionary Computation—ICEC96, Piscataway, USA, 1996, pp. 622–627.
Reimann, M., Shtovba, S., and Nepomuceno, E., A Hybrid Ant Colony Optimization and Genetic Algorithm Approach for Vehicle Routing Problems Solving, Student Papers of Complex Systems Summer School-2001, Budapest, 2001, pp. 134–141.
Pilat, M. and White, T., Using Genetic Algorithm to Optimize ACS-TSP, Lecture Notes in Computer Science (Proc. III Int. Workshop on Ant Algorithms ANTS 2002), Berlin: Springer, 2002, no. 2463, pp. 282–287.
Acan, A., GAACO: A GA + ACO Hybrid for Faster and Better Search Capability, Lecture Notes in Computer Science (Proc. III Int. Workshop on Ant Algorithms ANTS 2002), Berlin: Springer, 2002, no. 2463, pp. 300–301.
Lucic, P., Modeling Transportation Problems Using Concepts of Swarm Intelligence and Soft Computing, PhD Thesis, Civil Engineering Department, Virginia Polytechnic Institute and State University, Virginia, USA, 2002.
Reimann, M., Ant Based Optimization in Good Transportation, PhD Thesis, University of Vienna, Vienna, Austria, 2002.
Gutiahr, W.J., A Converging ACO Algorithm for Stochastic Combinatorial Optimization, Lecture Notes in Computer Science (Proc. of SAFA-2003 (Stochastic Algorithms: Foundations and Applications)), Berlin: Springer, 2003, no. 2827, pp. 10–25.
Mariano, C.E. and Morales, E., MOAQ: An Ant-Q Algorithm for Multiple Objective Optimization Problems, Proc. of Genetic and Evolutionary Computation Conf. (GECCO-99), San-Francisco, 1999, vol. 1, pp. 894–901.
Maier, H.R., Simpson, A.R., Zecchin, A.C., Wai Kuan Foong, Kuang Yeow Phang, Hsin Yeow Seah, and Chan Lim Tan, Ant Colony Optimization for Design of Water Distribution Systems. J. Water Resources Planning Manag., vol. 129, no.3, pp. 200–209.
Hussian Aziz Saleh, Ants Can Successfully Design GPS Surveying Networks, http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=30690&pa geID=1&sk=&date=. Translated under the title Povedenie murav’ev mozhno uspeshno ispol’zovat’ dlya razrabotki s’emochnykh setei GPS optimal’noi struktury, http://www.agp.ru/projects/ants/.
Liang Yun-Chia and Smith, A.E., An Ant System Approach to Redundancy Allocation, Proc. Cong. Evolutionary Computation (CEC-99), 1999, vol. 2.
Eggers, J., Feillet, D., Kehl, S., Wagner, M.O., and Yannou, B., Optimization of the Keyboard Arrangement Problem Using an Ant Colony Algorithm, Eur. J. Operational Res., 2003, no. 148, pp. 672–686.
Rodrigues, A., Application of Ant Colony Optimization to Data Distribution in Memory in Computer Systems, Proc. VII Annual Swarm Researchers Meeting “Swarm-Fest-2003,” Notre Dame, USA, 2003, http://www.nd.edu/arodrig6/.
Rajesh, J., Gupta, K., Kusumakar, H.S., Jayaraman, V.K., and Kulkarni, B.D., Dynamic Optimization of Chemical Processes Using Ant Colony Framework, Comput. Chem., 2001, vol. 25, no.6, pp. 583–595.
Socha, K., Knowles, J., and Samples, M., A MAX-MIN Ant System for the University Course Timetabling Problem, Lecture Notes in Computer Science (Proc. III Int. Workshop on Ant Algorithms ANTS 2002), Berlin: Springer, 2002, no. 2463, pp. 1–13.
De Jong, J., Multiple Ant Colony Systems for the Busstop Allocation Problem, MS Thesis, Department of Philology, University of Utrecht, Utrecht, Holland, 2001.
Shmygelska, A. and Hoos, H., An Improved Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem, Proc. XVI Canadian Conf. Artificial Intelligence (AI-2003), Canada, 2003.
Gueret, C., Monmarche, N., and Slimane, M., Ants Can Play Music, Lecture Notes in Computer Science (Proc. of IV Int. Workshop on Ant Colony Optimization and Swarm Intelligence ANTS-2004), Berlin: Springer, 2004, no. 3172, pp. 310–317.
Aupetit, S., Bordeau, V., Monmarche, N., Slimane, M., and Venturini, G., Interactive Evolution of Ant Paintings, Proc. of IEEE Cong. on Evolutionary Computation, Canberra: IEEE Press, 2003, pp. 1376–1383.
De Campos, L.M., Gamez, J.A., and Puerta, J.M., Learning Bayesian Networks by Ant Colony Optimization: Searching in Two Different Spaces, Mathware & Soft Computing, 2002, no. 9.
Raspinelli, J.M., Lopes, H.S., and Freitas, A.A., Data Mining with an Ant Colony Optimization Algorithm, IEEE Trans. Evolutionary Computation (Special issue on Ant Colony Algorithms), 2002, vol. 6, no.4, pp. 321–332.
Cassillas, J., Cordon, O., and Herrera, F., Learning Fuzzy Rules Using Ant Colony Optimization Algorithms, Proc. of ANTS2000—From Ant Colonies to Artificial Ants: A Series of Int. Workshops on Ant Algorithms, Brussels, 2000, pp. 13–21.
Cassillas, J., Cordon, O., Fernandez de Viana, I., and Herrera, F., Learning Cooperative Linguistic Fuzzy Rules Using the Best-Worst Ant System Algorithm, Int. J. Intelligent Sys., 2005, vol. 20, pp. 433–452.
Component Transport Follows the Ant Trail, http://www.siemens.com. September 23, 2004.
Caro, G.D. and Dorigo, M., Anet: A Mobile Agents Approach to Adaptive Routing, Tech. Rep. IRIDA 97-12, Brussels: Univ. Libre de Brusseles, 1997.
Dorigo, M. and Stutzle, T., The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, in Handbook of Metaheuristics, Glover, F. and Kochenberger, G., Eds., Norwell: Kluwer, 2002.
Cordon, O., Herrera, F., and Stutzle, T., A Review on the Ant Colony Optimization Metaheuristic: Basis, Models and New Trends, Mathware & Soft Computing, 2002, no. 9.
Dorigo, M. and Stutzle, T., Ant Colony Optimization, Bradford Book, 2004.
Author information
Authors and Affiliations
Additional information
__________
Translated from Programmirovanie, Vol. 31, No. 4, 2005.
Original Russian Text Copyright © 2005 by Shtovba.
Rights and permissions
About this article
Cite this article
Shtovba, S.D. Ant Algorithms: Theory and Applications. Program Comput Soft 31, 167–178 (2005). https://doi.org/10.1007/s11086-005-0029-1
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11086-005-0029-1