Abstract
Ant colony optimization (ACO) is a metaheuristic that was originally introduced for solving combinatorial optimization problems. In this chapter we present the general description of ACO, as well as its adaptation for the application to continuous optimization problems. We apply this adaptation of ACO to optimize the weights of feed-forward neural networks for the purpose of pattern classification. As test problems we choose three data sets from the well-known PROBEN1 medical database. The experimental results show that our algorithm is comparable to specialized algorithms for feed-forward neural network training. Furthermore, the results compare favourably to the results of other general-purpose methods such as genetic algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Key words
References
Alba, E., and Chicano, J.F, 2004, Training Neural Networks with GA Hybrid Algorithms, in: Proceedings of Genetic and Evolutionary Computation–GECCO 2004, Part 1, Lecture Notes in Computer Science, vol. 3102, K. Deb et al, eds., Springer-Verlag, Berlin, Germany, pp. 852–863.
Battiti, R., and Tecchiolli, G., 1996, The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization, Annals of Operations Research 63:153–188.
Bilchev, G., and Parmee, I. C, 1995, The ant colony metaphor for searching continuous design spaces, in: Proceedings of the AISB Workshop on Evolutionary Computation, Lecture Notes in Computer Science, vol. 993, T.∼C. Fogarty, ed., Springer-Verlag, Berlin, Germany, pp. 25–39.
Birattari, M., 2004, The Problem of Tuning Metaheuristics as Seen from a Machine Learning Perspective, Ph.D. thesis, ULB, Brussels, Belgium.
Birattari, M., Stützle, T., Paquete, L., and Varrentrapp, K., 2002, A Racing Algorithm for Configuring Metaheuristics, in: Proceedings of Genetic and Evolutionary Conference, W. B. Langdon et al. eds., Morgan Kaufmann, San Francisco, CA, USA, pp. 11–18.
Blum, C, 2005, Beam-ACO—Hybridizing ant colony optimization with beam search: An application to open shop scheduling, Computers & Operations Research 32(6): 1565–1591.
Blum, C, and Roli, A., 2003, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys 35(3):268–308.
Blum, C, and Sampels, M., 2004, An ant colony optimization algorithm for shop scheduling problems, Journal of Mathematical Modelling and Algorithms 3(3):285–308.
Blum, C, 2005, Beam-ACO—Hybridizing ant colony optimization with beam search: An application to open shop scheduling, Computers & Operations Research 32(6): 1565–1591.
Bonabeau, E., Dorigo, M., and Theraulaz, G., 1999, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, New York, NY.
Box, G. E. P., and Muller, M. E, 1958, A note on the generation of random normal deviates. Annals of Mathematical Statistics 29(2):610–611.
Černý, V., 1985, A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm, Optimization Theory and Applications 45:41–51.
Chelouah, R., and Siarry, P., 2000, A continuous genetic algorithm designed for the global optimization of mulitmodal functions, Journal of Heuristics 6:191–213.
Chelouah, R., and Siarry, P., 2000, Tabu search applied to global optimization, European Journal of Operational Research 123:256–270.
Chelouah, R., and Siarry, P., 2003, Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions, European Journal of Operational Research 148:335–348.
Costa, D., and Hertz, A., 1997, Ants can color graphs, Journal of the Operational Research Society 48:295–305.
den Besten, M. L., Stützle, T., and Dorigo, M., 2000, Ant colony optimization for the total weighted tardiness problem, in: Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 1917, M. ∼Schoenauer et al., eds., Springer Verlag, Berlin, Germany, pp. 611–620.
Deneubourg, J.-L., Aron, S., Goss, S., and Pasteels, J.-M., 1990, The self-organizing exploratory pattern of the argentine ant, Journal of Insect Behaviour 3:159–168.
Dorigo, M., 1992, Optimization, Learning and Natural Algorithms (in Italian), PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy.
Dorigo, M., and Gambardella, L. M, 1997, Ant Colony System: A cooperative learning approach to the travelling salesman problem, IEEE Transactions on Evolutionary Computation l(l):53–66.
Dorigo, M., Maniezzo, V., and Colorni, A., 1991, Positive feedback as a search strategy, Technical Report 91–016, Dipartimento di Elettronica, Politecnico di Milano, Italy.
Dorigo, M., Maniezzo, V., and Colorni, A., 1996, Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics — Part B 26(1):29–41.
Dorigo, M., and Stützle, T., 2004, Ant Colony Optimization, MIT Press, Cambridge, MA.
Dréo, J., and Siarry, P., 2002, A new ant colony algorithm using the heterarchical concept aimed at optimization of multiminima continuous functions, in: Proceedings of ANTS 2002—From Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms, Lecture Notes in Computer Science, vol. 2463 of LNCS, M. Dorigo et al., eds., Springer Verlag, Berlin, Germany, pp. 216–221.
Fogel, L. J., Owens, A. J., and Walsh, M. J., 1966, Artificial Intelligence through Simulated Evolution, Wiley.
Gagné, C, Price, W. L., and Gravel, M., 2002, Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times, Journal of the Operational Research Society 53:895–906.
Gambardella, L. M., and Dorigo, M., 2000, Ant Colony System hybridized with a new local search for the sequential ordering problem, INFORMS Journal on Computing 12(3):237–255.
Gambardella, L. M., Taillard, É. D., and Agazzi, G., 1999, MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows, in: New Ideas in Optimization, D. Corne et al., eds., McGraw Hill, London, UK, pp. 63–76.
Glover, F., 1989, Tabu search—Part I, ORSA Journal on Computing 1(3): 190–206.
Glover, F., 1990, Tabu search—Part II, ORSA Journal on Computing 2(l):4–32.
Glover, F., and Kochenberger, G., 2002, Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA.
Glover, F., and Laguna, M., 1997, Tabu Search, Kluwer Academic Publishers.
Goldberg, D. E., 1989, Genetic algorithms in search, optimization, and machine learning, Addison Wesley, Reading, MA.
Golub, G. H., and van Loan, C. F., 1989, Matrix Computations, 2nd ed., the John Hopkins University Press, Baltimore, MD, USA.
Guntsch, M., and Middendorf, M., 2002, A population based approach for ACO, in: Applications of Evolutionary Computing, Proceedings of EvoWorks hops 2002: EvoCOP, EvoIASP, EvoSTim, vol. 2279, S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, and G. Raidl, eds., Springer-Verlag, Berlin, Germany, pp. 71–80.
Hagan, M. T., and Menhaj, M. B., 1994, Training Feedforward Networks with the Marquardt Algorithm, IEEE Transactions on Neural Networks 5:989–993.
Hastie, T., Tibshirani, R., and Friedman, J., 2001, The Elements of Statistical Learning, Springer-Verlag, Berlin, Germany.
Holland, J. H., 1975, Adaption in natural and artificial systems, The University of Michigan Press, Ann Harbor, MI.
Hoos, H. H., and Stützle, T., 2004, Stochastic Local Search: Foundations and Applications, Elsevier, Amsterdam, The Netherlands.
Kern, S., Müller, S. D., Hansen, N., Büche, D., Očenášek, J., and Koumoutsakos, P., 2004, Learning probability distributions in continuous evolutionary algorithms—A comparative review, Natural Computing 3(1):77–112.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P., 1983, Optimization by simulated annealing, Science 220(4598):671–680.
Maniezzo, V., 1999, Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem, INFORMS Journal on Computing 11(4):358–369.
Maniezzo, V., and Colorni, A., 1999, The Ant System applied to the quadratic assignment problem, IEEE Transactions on Data and Knowledge Engineering 11(5):769–778.
Mathur, M, Karale, S. B., Priye, S., Jyaraman, V. K., and Kulkarni, B. D., 2000, Ant colony approach to continuous function optimization, Industrial & Engineering Chemistry Research 39:3814–3822.
McGill, R., Tukey, J. W., and Larsen, W. A., 1978, Variations of box plots, The American Statisticia 32:12–16.
Merkle, D., Middendorf, M., and Schmeck, H., 2002, Ant Colony Optimization for Resource-Constrained Project Scheduling, IEEE Transactions on Evolutionary Computation 6(4):333–346.
Monmarché, N., Venturing G., and Slimane M., 2000, On how Pachycondyla apicalis ants suggest a new search algorithm, Future Generation Computer Systems 16:937–946.
Nelder, J. A., and Mead, R., 1965, A simplex method for function minimization, Computer Journal 7:308–313.
Papadimitriou, C. H., and Steiglitz, K., 1982, Combinatorial Optimization—Algorithms and Complexity, Dover Publications, Inc., New York.
Papliński, A.P., 2004, Lecture 7—Advanced Learning Algorithms for Multilayer Perceptrons, available online at http://www.csse.moHash.edu.au/courscware/cse530l/04/L07.pdf.
Prechelt, L., 1994, Probenl—A Set of Neural Network Benchmark Problems and Benchmarking Rules. Technical Report 21, Fakultät für Informatik, Universität Karlsruhe, Karlsruhe, Germany.
Rechenberg, I., 1973, Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Frommann-Holzboog.
Reimann, M., Doerner, K., and Hartl, R. F., 2004, D-ants: Savings based ants divide and conquer the vehicle routing problems, Computers & Operations Research 31(4):563–591.
Rumelhart, D., Hinton, G., and Williams, R., 1986, Learning Representations by Backpropagation Errors, Nature 323:533–536.
Siarry, P., Berthiau, G., Durbin, F., and Haussy, J., 1997, Enhanced simulated annealing for globally minimizing functions of many-continuous variables, ACM Transactions on Mathematical Software 23(2):209.228.
Socha, K., 2003, The Influence of Run-Time Limits on Choosing Ant System Parameters, in Proceedings of GECCO 2003—Genetic and Evolutionary Computation Conference, Lecture Notes in Computer Science, vol. 2723, E. Cantu-Paz et al., eds., Springer-Verlag, Berlin, Germany, pp. 49–60.
Socha, K., 2004, Extended ACO for continuous and mixed-variable optimization, in: Proceedings of ANTS 2004—Fourth International Workshop on Ant Algorithms and Swarm Intelligence, Lecture Notes in Computer Science, M. Dorigo et al., eds., Springer Verlag, Berlin, Germany, pp. 35–46.
Socha, K., Sampels, M., and Manfrin, M., 2003, Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, in: Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2003, vol. 2611, G. Raidl et al., eds., pp 334–345.
Storn, R., and Price, K., 1997, Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization 11:341–359.
Stützle, T., 1998, An Ant Approach to the Flow Shop Problem, in: Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing, EUFIT’98, pp 1560–1564.
Stützle, T., and Hoos, H. H., 2000, MAX-MIN Ant System, Future Generation Computer Systems 16(8):889–914.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Socha, K., Blum, C. (2006). Ant Colony Optimization. In: Alba, E., Martí, R. (eds) Metaheuristic Procedures for Training Neutral Networks. Operations Research/Computer Science Interfaces Series, vol 36. Springer, Boston, MA . https://doi.org/10.1007/0-387-33416-5_8
Download citation
DOI: https://doi.org/10.1007/0-387-33416-5_8
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-33415-8
Online ISBN: 978-0-387-33416-5
eBook Packages: Business and EconomicsBusiness and Management (R0)