×

Ant colony optimization for continuous domains. (English) Zbl 1146.90537

Summary: In this paper we present an extension of ant colony optimization (ACO) to continuous domains. We show how ACO, which was initially developed to be a metaheuristic for combinatorial optimization, can be adapted to continuous optimization without any major conceptual change to its structure. We present the general idea, implementation, and results obtained. We compare the results with those reported in the literature for other continuous optimization methods: other ant-related approaches and other metaheuristics initially developed for combinatorial optimization and later adapted to handle the continuous case. We discuss how our extended ACO compares to those algorithms, and we present some analysis of its efficiency and robustness.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization

Software:

MACS-VRPTW; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baluja, S.; Caruana, R., Removing the genetics from the standard genetic algorithm, (Prieditis, A.; Russel, S., Twelth International Conference on Machine Learning (1995), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco, CA), 38-46
[2] Bilchev, G.; Parmee, I. C., The ant colony metaphor for searching continuous design spaces, (Fogarty, T. C., Proceedings of the AISB Workshop on Evolutionary Computation, vol. 993 of LNCS (1995), Springer-Verlag: Springer-Verlag Berlin, Germany), 25-39
[3] Birattari, M., 2005. The Problem of Tuning Metaheuristics as Seen from a Machine Learning Perspective. Ph.D. thesis, vol. 292 of Dissertationen zur Künstlichen Intelligenz. Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany.; Birattari, M., 2005. The Problem of Tuning Metaheuristics as Seen from a Machine Learning Perspective. Ph.D. thesis, vol. 292 of Dissertationen zur Künstlichen Intelligenz. Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany. · Zbl 1101.68748
[4] Birattari, M.; Stützle, T.; Paquete, L.; Varrentrapp, K., A Racing Algorithm for Configuring Metaheuristics, (Langdon, W. B.; etal., Proceedings of the Genetic and Evolutionary Computation Conference (2002), Morgan Kaufman: Morgan Kaufman San Francisco, CA), 11-18
[5] Björkman, M.; Holmström, K., Global optimization using the DIRECT algorithm in Matlab, Advanced Modeling and Optimization, 1, 2, 17-37 (1999) · Zbl 1115.90300
[6] Blum, C., 2004. Theoretical and Practical Aspects of Ant Colony Optimization. Ph.D. thesis, vol. 282 of Dissertationen zur Künstlichen Intelligenz. Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany.; Blum, C., 2004. Theoretical and Practical Aspects of Ant Colony Optimization. Ph.D. thesis, vol. 282 of Dissertationen zur Künstlichen Intelligenz. Akademische Verlagsgesellschaft Aka GmbH, Berlin, Germany. · Zbl 1148.90017
[7] Blum, C.; Sampels, M., An ant colony optimization algorithm for shop scheduling problems, Journal of Mathematical Modelling and Algorithms, 3, 3, 285-308 (2004) · Zbl 1146.90405
[8] Bosman, P. A.N.; Thierens, D., Continuous iterated density estimation evolutionary algorithms within the IDEA framework, (Pelikan, M.; Mühlenbein, H.; Rodriguez, A. O., Proceedings of OBUPM Workshop at GECCO-2000 (2002), Morgan-Kaufmann Publishers: Morgan-Kaufmann Publishers San Francisco, CA), 197-200
[9] Box, G. E.P.; Muller, M. E., A note on the generation of random normal deviates, Annals of Mathematical Statistics, 29, 2, 610-611 (1958) · Zbl 0085.13720
[10] Chellapilla, K.; Fogel, D. B., Fitness distribution in evolutionary computation: Analysis of local extrema in the continuous domain, (Proceedings of the IEEE Congress on Evolutionary Computation (CEC-1999) (1999), IEEE Press: IEEE Press Piscataway, NJ), 1885-1892
[11] Chelouah, R.; Siarry, P., Enhanced continuous tabu search, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), 49-61, (Chapter 4) · Zbl 1073.90578
[12] Chelouah, R.; Siarry, P., A continuous genetic algorithm designed for the global optimization of multimodal functions, Journal of Heuristics, 6, 191-213 (2000) · Zbl 0969.68641
[13] Costa, D.; Hertz, A., Ants can colour graphs, Journal of the Operational Research Society, 48, 295-305 (1997) · Zbl 0890.90174
[14] Deb, K.; Anand, A.; Joshi, D., A computationally efficient evolutionary algorithm for real-parameter optimization, Evolutionary Computation, 10, 4, 371-395 (2002)
[15] Dorigo, M., 1992. Optimization, Learning and Natural Algorithms (in Italian). Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy.; Dorigo, M., 1992. Optimization, Learning and Natural Algorithms (in Italian). Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy.
[16] Dorigo, M.; Gambardella, L. M., Ant Colony System: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66 (1997)
[17] Dorigo, M.; Stützle, T., Ant Colony Optimization (2004), MIT Press: MIT Press Cambridge, MA · Zbl 1092.90066
[18] Dorigo, M.; Maniezzo, V.; Colorni, A., Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26, 1, 29-41 (1996)
[19] Dorigo, M.; Di Caro, G.; Gambardella, L. M., Ant algorithms for discrete optimization, Artificial Life, 5, 2, 137-172 (1999)
[20] Dréo, J.; Siarry, P., A new ant colony algorithm using the heterarchical concept aimed at optimization of multiminima continuous functions, (Dorigo, M.; Di Caro, G.; Sampels, M., Proceedings of the Third International Workshop on Ant Algorithms (ANTS’2002), vol. 2463 of LNCS (2002), Springer-Verlag: Springer-Verlag Berlin, Germany), 216-221
[21] Dréo, J.; Siarry, P., Continuous interacting ant colony algorithm based on dense hierarchy, Future Generation Computer Systems, 20, 5, 841-856 (2004)
[22] Eiben, A. E.; Bäck, T., Empirical investigation of multiparent recombination operators in evolution strategies, Evolutionary Computation, 3, 5, 347-365 (1997)
[23] Fogel, D. B.; Bayer, H. G., A note on the empirical evaluation of intermediate recombination, Evolutionary Computation, 4, 3, 491-495 (1995)
[24] Gagné, C.; Price, W. L.; Gravel, M., 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 (2002) · Zbl 1130.90326
[25] Gambardella, L. M.; Taillard, E.; Agazzi, G., MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill: McGraw-Hill UK), 63-76
[26] Golub, G.; van Loan, C., Matrix Computations (1989), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0733.65016
[27] Goss, S.; Aron, S.; Deneubourg, J.-L.; Pasteels, J., Self-organized shortcuts in the Argentine ant, Naturwissenschaften, 76, 579-581 (1989)
[28] Guntsch, M.; Middendorf, M., A population based approach for ACO, (Cagnoni, S.; Gottlieb, J.; Hart, E.; Middendorf, M.; Raidl, G., Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTim, vol. 2279 of LNCS (2002), Springer-Verlag: Springer-Verlag Berlin, Germany), 71-80 · Zbl 1044.68761
[29] Hansen, N.; Ostermeier, A., Completely derandomized self-adaptation in evolution strategies, Evolutionary Computation, 2, 9, 159-195 (2001)
[30] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning (2001), Springer-Verlag: Springer-Verlag Berlin, Germany
[31] Kennedy, J.; Eberhart, R. C., Particle Swarm Optimization, (Proceedings of IEEE International Conference on Neural Networks, vol. 4 (1995), IEEE Press: IEEE Press Piscataway, NJ), 1942-1948
[32] Kern, S.; Müller, S. D.; Hansen, N.; Büche, D.; Očenášek, J.; Koumoutsakos, P., Learning probability distributions in continuous evolutionary algorithms - A comparative review, Natural Computing, 3, 1, 77-112 (2004) · Zbl 1074.68063
[33] Mathur, M.; Karale, S. B.; Priye, S.; Jyaraman, V. K.; Kulkarni, B. D., Ant colony approach to continuous function optimization, Industrial and Engineering Chemistry Research, 39, 3814-3822 (2000)
[34] Merkle, D.; Middendorf, M.; Schmeck, H., Ant colony optimization for resource-constrained project scheduling, IEEE Transactions on Evolutionary Computation, 6, 4, 333-346 (2002)
[35] Monmarché, N.; Venturini, G.; Slimane, M., On how Pachycondyla apicalis ants suggest a new search algorithm, Future Generation Computer Systems, 16, 937-946 (2000)
[36] Očenášek, J.; Schwarz, J., Estimation distribution algorithm for mixed continuous-discrete optimization problems, (Proceedings of the 2nd Euro-International Symposium on Computational Intelligence (2002), IOS Press: IOS Press Amsterdam, Netherlands), 227-232
[37] Ostermeier, A.; Gawelczyk, A.; Hansen, N., Step-size adaptation based on non-local use of selection information, (Davidor, Y.; Schwefel, H.-P.; Männer, R., Parallel Problem Solving from Nature - PPSN III, vol. 866 of LNCS (1994), Springer-Verlag: Springer-Verlag Berlin, Germany), 189-198
[38] Pelikan, M., Goldberg, D., Sastry, K., 2000. Bayesian optimization algorithm, decision graphs, and Occam’s razor. Technical Report IlliGAL Report No. 2000020, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 2000.; Pelikan, M., Goldberg, D., Sastry, K., 2000. Bayesian optimization algorithm, decision graphs, and Occam’s razor. Technical Report IlliGAL Report No. 2000020, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 2000.
[39] Ralston, A.; Rabinowitz, P., A First Course in Numerical Analysis (1978), McGraw-Hill: McGraw-Hill New York, NY · Zbl 0408.65001
[40] Reimann, M.; Doerner, K.; Hartl, R., D-ants: Savings based ants divide and conquer the vehicle routing problems, Computers and Operations Research, 31, 4, 563-591 (2004) · Zbl 1061.90024
[41] Rumelhart, D.; Hinton, G.; Williams, R., Learning representations by backpropagation errors, Nature, 536, 323-533 (1986)
[42] Schwefel, H.-P., Numerical Optimization of Computer Models (1981), John Wiley and Sons: John Wiley and Sons New York, NY
[43] Siarry, P.; Berthiau, G.; Durbin, F.; Haussy, J., Enhanced simulated annealing for globally minimizing functions of many continuous variables, ACM Transactions on Mathematical Software, 23, 2, 209-228 (1997) · Zbl 0887.65067
[44] Socha, K.; Sampels, M.; Manfrin, M., Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, (Raidl, G.; etal., Proceedings of EvoCOP 2003 - 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization, volume 2611 of LNCS (2003), Springer-Verlag: Springer-Verlag Berlin, Germany), 334-345 · Zbl 1033.90508
[45] Storn, R., Price, K., 1995. Differential Evolution - A simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95-012, International Computer Science Institute, Berkeley, CA.; Storn, R., Price, K., 1995. Differential Evolution - A simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95-012, International Computer Science Institute, Berkeley, CA. · Zbl 0888.90135
[46] Stützle, T.; Dorigo, M., ACO algorithms for the traveling salesman problem, (Miettinen, K.; Mäkelä, M. M.; Neittaanmäki, P.; Périaux, J., Evolutionary Algorithms in Engineering and Computer Science (1999), John Wiley and Sons: John Wiley and Sons Chichester, UK), 163-183 · Zbl 0972.90056
[47] Stützle, T.; Hoos, H. H., \(MAX-MIN\) Ant System, Future Generation Computer Systems, 16, 8, 889-914 (2000)
[48] Wodrich, M.; Bilchev, G., Cooperative distributed search: The ant’s way, Control and Cybernetics, 26, 3, 413-446 (1997) · Zbl 0890.90159
[49] Yuan, B.; Gallagher, M., Playing in continuous spaces: Some analysis and extension of population-based incremental learning, (Sarker, R.; etal., Proceedings of Congress of Evolutionary Computation (CEC) (2003), IEEE Press: IEEE Press Piscataway, NJ), 443-450
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.