Mathematical runtime analysis of ACO algorithms: survey on an emerging issue

Baluja, S., & Caruana, R. (1995). Removing the genetics from the standard genetic algorithm. In A. Prieditis & S. Russell (Eds.), Proceedings of the 12th international conference on machine learning (ML-95) (pp. 38–46). Palo Alto: Kaufmann.

Birattari, M., Pellegrini, P., & Dorigo, M. (2007, in press). On the invariance of ant colony optimization. IEEE Transactions on Evolutionary Computation.

Blum, C., & Dorigo, M. (2004). The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems Man and Cybernetics Part B, 34(2), 1161–1172.

Blum, C., & Dorigo, M. (2005). Search bias in ant colony optimization: on the role of competition-balanced systems. IEEE Transactions on Evolutionary Computation, 9(2), 159–174.

Borisovsky, P. A., & Eremeev, A. V. (2003). A study on performance of the (1+1)-evolutionary algorithm. In Proceedings of the foundations of genetic algorithms 7. San Francisco: Kaufmann.

Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). A new rank–based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics, 7(1), 25–38.

Doerr, B., Neumann, F., Sudholdt, D., & Witt, C. (2007). On the influence of pheromone updates in ACO algorithms. Technical Report CI-223/07, University of Dortmund, SFB 531, to appear in Proc. GECCO 2007.

Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: a survey. Theoretical Computer Science, 344, 243–278.

Dorigo, M., & Di Caro, G. (1999). The Ant colony optimization metaheuristic. In D. Corne, M. Dorigo, & F. Glover (Eds.), New ideas in optimization (pp. 11–32). Maidenhead: McGraw–Hill.

Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1, 53–56.

Dorigo, M., & Stützle, T. (2004). Ant colony optimization. Cambridge: MIT.

Dorigo, M., Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy. Technical Report TR-POLI-91-016, Dipartimento di Elletronica, Politecnico di Milano, Milan, Italy.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, 26, 1–13.

Droste, S., Jansen, T., & Wegener, I. (2002). On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276, 51–81.

Gonzalez, C., Lozano, J. A., & Larrañaga, P. (2000). Analyzing the PBIL algorithm by means of discrete dynamical systems. Complex Systems, 4, 465–479.

Gonzalez, C., Lozano, J. A., & Larrañaga, P. (2001). The convergence behavior of the PBIL algorithm: a preliminary approach. In Proceedings of the 5th international conference on artificial neural networks and genetic algorithms (ICANNGA ’01) (pp. 228–231). Berlin: Springer.

Gutjahr, W. J. (2000). A graph-based ant system and its convergence. Future Generation Computer Systems, 16, 873–888.

Gutjahr, W. J. (2002). ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters, 82, 145–153.

Gutjahr, W. J. (2005). Theory of ant colony optimization: status and perspectives. In MIC ’05 (6th metaheuristics international conference). Proceedings CD-ROM.

Gutjahr, W. J. (2006). On the finite-time dynamics of ant colony optimization. Methodology and Computing in Applied Probability, 8, 105–133.

Gutjahr, W. J. (2007, in press). First steps to the runtime complexity analysis of ant colony optimization. Computers and Operations Research.

Gutjahr, W. J., & Sebastiani, G. (2007). Runtime analysis of Ant colony optimization. Technical Report, Consiglio Nazionale delle Ricerche, Rome. Available under: http://www.mat.uniroma1.it/people/sebastiani/preprints.htm .

Kallel, L., Naudts, B., & Reeves, C. R. (1998). Properties of fitness functions and search landscapes. In Kallel, Naudts, & Rogers (Eds.), Theoretical aspects of evolutionary computing (pp. 174–206) Berlin: Springer.

Merkle, D., & Middendorf, M. (2002). Modeling the dynamics of ant colony optimization. Evolutionary Computation, 10, 235–262.

Neumann, F., & Witt, C. (2006a). Runtime analysis of a simple ant colony optimization algorithm. In Lecture notes in computer science : Vol. 4288. Proceedings ISAAC ’06 (pp. 618–624). Berlin: Springer.

Neumann, F., & Witt, C. (2006b). Ant colony optimization and the minimum spanning tree problem. Technical Report CI-220/06, University of Dortmund, SFB 531.

Norman, F. (1972). Markov processes and learning models. New York: Academic Press.

Sebastiani, G., & Torrisi, G. L. (2005). An extended ant colony algorithm and its convergence analysis. Methodology and Computing in Applied Probability, 7, 249–263.

Stützle, T. Dorigo, M. (2002). A short convergence proof for a class of ACO algorithms. IEEE Transactions on Evolutionary Computation, 6, 358–365.

Stützle, T., & Hoos, H. H. (1997). MAX-MIN Ant System and local search for the travelling salesman problem. In T. Baeck, Z. Michalewicz & X. Yao (Eds.), Proceedings ICEC ’97 international conference on evolutionary computation (pp. 309–314). New York: IEEE.

Stützle, T., & Hoos, H. H. (2000). MAX-MIN Ant system. Future Generation Computer Systems, 16, 889–914.

Zlochin, M., Birattari, M., Meuleau, N., & Dorigo, M. (2004). Model-based search for combinatorial optimization: a critical survey. Annals of Operations Research, 131, 373–379.