Multivariate ant colony optimization in continuous search spaces

ABSTRACT

This work introduces an ant-inspired algorithm for optimization in continuous search spaces that is based on the generation of random vectors with multivariate Gaussian pdf. The proposed approach is called MACACO -- Multivariate Ant Colony Algorithm for Continuous Optimization -- and is able to simultaneously adapt all the dimensions of the random distribution employed to generate the new individuals at each iteration. In order to analyze MACACO's search efficiency, the approach was compared to a pair of counterparts: the Continuous Ant Colony System (CACS) and the approach known as Ant Colony Optimization in eⁿ (ACO_R). The comparative analysis, which involves well-known benchmark problems from the literature, has indicated that MACACO outperforms CACS and ACO_R in most cases as the quality of the final solution is concerned, and it is just about two times more costly than the least expensive contender.

REFERENCES

• 1: George Bilchev , Ian C. Parmee, The Ant Colony Metaphor for Searching Continuous Design Spaces, Selected Papers from AISB Workshop on Evolutionary Computing, p.25-39, April 03-04, 1995
• 2: G. E. P. Box and M. A. Muller. A note on the generation of random normal deviates. Annals. Math. Stat., 29:610--611, 1958.
• 3: F. O. de França, F. J. Von Zuben, and L. N. de Castro. Max min ant system and capacitated p-medians: Extensions and improved solutions. Informatica (Slovenia), 29(2):163--172, 2005.
• 4: M. Dorigo. Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy,1992.
• 5: Marco Dorigo , Gianni Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 6: M. Dorigo and T. Stützle. The ant colony optimization metaheuristic: Algorithms, applications, and advances. In F. W. Glover and G. A. Kochenberger, editors, Handbook of Metaheuristics, pages 251--286. Kluwer Academic Press, 2003.
• 7: J. Dréo and P. Siarry. A new ant colony algorithm using the heterarchical concept aimed at optimization
• 8: of multiminima continuous functions. In M. Dorigo, G. D. Caro, and M. Sampels, editors, Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 216--221. Springer, 2002.
• 9: Michael Guntsch , Martin Middendorf, A Population Based Approach for ACO, Proceedings of the Applications of Evolutionary Computing on EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN, p.72-81, April 03-04, 2002
• 10: I. T. Hernádvölgyi. Generating random vectors from the multivariate normal distribution. Technical Report TR-98-07, University of Ottawa, Aug. 20 1998.
• 11: G. Marsaglia and W. W. Tsang. The ziggurat method for generating random variables. Journal of Statistical Software, 5(8):1--7, 2000.
• 12: N. Monmarchè , G. Venturini , M. Slimane, On how pachycondyla apicalis ants suggest a new search algorithm, Future Generation Computer Systems, v.16 n.9, p.937-946, June 2000
• 13: S. H. Pourtakdoust and H. Nobahari. An extension of ant colony system to continuous optimization problems. In M. Dorigo, M. Birattari, C. Blum, L. M. Gambardella, F. Mondada, and T. Stutzle, editors, ANTS Workshop, volume 3172 of Lecture Notes in Computer Science, pages 294--301. Springer, 2004.
• 14: Yun-Wei Shang , Yu-Huang Qiu, A Note on the Extended Rosenbrock Function, Evolutionary Computation, v.14 n.1, p.119-126, March 2006 [doi>10.1162/106365606776022733]
• 15: K. Socha and M. Dorigo. Ant colony optimization for continuous domains. European Journal of Operational Research, In Press, Corrected Proof, 2006.
• 16: Thomas Stützle , Marco Dorigo, ACO algorithms for the quadratic assignment problem, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
ant colony optimization, continuous optimization, multivariate normal distribution