Ant Colony Optimization
The Ant Colony Optimization (ACO) framework exploits the collective mechanisms behind the shortest path behavior observed in ant colonies to define a population-based Nature-inspired metaheuristic for optimization.
ACO features a multi-agent organization, stigmergic communication among the agents, distributed operations, use of a stochastic decision policy to construct solutions, stigmergic learning of the parameters of the decision policy. It has been applied with success to a large variety of problems in the context of optimization, networking, data mining, robotics.
I gave a fundamental contribution to the definition and analysis of ACO. In 1999, when I was at IRIDIA, with my supervisor Prof. M. Dorigo, we defined the metaheuristic as an a posteriori metaheuristic, taking into account his initial seminal work (dating back to 1991) and the number of algorithms designed after this work. The two following papers is where ACO was first formally defined and extensively reviewed:
My thesis reports the complete formal definition of ACO and an extensive discussion on its many implementations and applications, with a special focus on routing problems in dynamic networks. The thesis includes both the definition of ACO as well as the definition of the ACO routing algorithms AntNet and AntHocNet (developed in collaboration with Frederick Ducatelle in the BISON project). These algorithms are de facto reference algorithms for the application of the principles of ACO or Swarm Intelligence to routing problems in dynamic networks.
The thesis is an outgrowth of my research work from 1998 to 2004. During those years I had (post-doc) research positions in several laboratories, namely, IRIDIA, in Brussels (Belgium), ATR (Advanced Telecommunications Research Institute), in Kyoto (Japan), and IDSIA, in Lugano (Switzerland). I discussed my Ph.D. dissertion at the Université Libre de Bruxelles (ULB), Brussels, Belgium, in 2004. Prof. Marco Dorigo was my supervisor.
Up-to-date information and resources about ACO can be found in the official Ant Colony Optimization page maintained at IRIDIA, ULB.
ACO features a multi-agent organization, stigmergic communication among the agents, distributed operations, use of a stochastic decision policy to construct solutions, stigmergic learning of the parameters of the decision policy. It has been applied with success to a large variety of problems in the context of optimization, networking, data mining, robotics.
I gave a fundamental contribution to the definition and analysis of ACO. In 1999, when I was at IRIDIA, with my supervisor Prof. M. Dorigo, we defined the metaheuristic as an a posteriori metaheuristic, taking into account his initial seminal work (dating back to 1991) and the number of algorithms designed after this work. The two following papers is where ACO was first formally defined and extensively reviewed:
- Dorigo M., Di Caro G. A., Gambardella L.M., Ant Algorithms for Discrete Optimization, Artificial Life, Vol. 5, N. 2, 1999 [BibTeX]
- Dorigo M., Di Caro G. A., The Ant Colony Optimization Meta-Heuristic, in Corne D., Dorigo M., Glover F., "New Ideas in Optimization", McGraw-Hill, 1999. [BibTeX]
My thesis reports the complete formal definition of ACO and an extensive discussion on its many implementations and applications, with a special focus on routing problems in dynamic networks. The thesis includes both the definition of ACO as well as the definition of the ACO routing algorithms AntNet and AntHocNet (developed in collaboration with Frederick Ducatelle in the BISON project). These algorithms are de facto reference algorithms for the application of the principles of ACO or Swarm Intelligence to routing problems in dynamic networks.
The thesis is an outgrowth of my research work from 1998 to 2004. During those years I had (post-doc) research positions in several laboratories, namely, IRIDIA, in Brussels (Belgium), ATR (Advanced Telecommunications Research Institute), in Kyoto (Japan), and IDSIA, in Lugano (Switzerland). I discussed my Ph.D. dissertion at the Université Libre de Bruxelles (ULB), Brussels, Belgium, in 2004. Prof. Marco Dorigo was my supervisor.
Up-to-date information and resources about ACO can be found in the official Ant Colony Optimization page maintained at IRIDIA, ULB.
My Ph.D. thesis on Ant Colony OptimizationThe thesis lays the formal foundations of the Ant Colony Oprimization (ACO) metaheuristic and introduces its application to routing problems in dynamic telecommunication networks.
|
Material for a course on ACOSlides on Ant Colony Optimization theory and practice given during the course on Optimization Heuristics at USI Master students.
|
Introduction to
|