UNIVERSITıT LEIPZIG
Faculty of Mathematics and Computer Science Department of Computer Science
Parallel Computing and Complex Systems



Ant Colony Optimization and Swarm Intelligence



What is Ant Colony Optimzation?

Ant Colony Optimization is a metheuristic that uses strategies of real ants to solve optimization problems (A short overview can be found in the Juli issue of Nature, 406 (2000)).

Goals of our research

One goals of our research is to develope new ant algorithms that are able to solve very complex optimization problems. Examples of problems that we investigate are ressource-constraint project scheduling, dynamic optimization problems and optimization problems with multiple optimization criteria.

We also want to understand better the mechanisms that determine the behaviour of ant algorithms. One question is the best use of indirect communication mechanism in ant algorithms (similar to the use of pheromones by real ants). Another question is how several colonies of ants can work together in ACO algorithms.

Moreover, we are interested to find suitable implementations of ant algorithms on parallel architectures (see DFG-Poject SIRA).

Some results of our research

An ACO algorithm for ressource-constraint project scheduling found new best solutions for some of the largest and most often used test problems that can be found in the benchmark library PSPLIB, University of Kiel (2000). An article were the results and several features of this algorithms are described appeared in IEEE Transactions on Evolutionary Computation (2002) 6(4): 333-346.

The devolpment of methods for cooperation between several colonies of ants for solving multicriteria optimization problems was used to solve scheduling problems were costs and time has to be minimized. This work was presented at the First International Conference on Evolutionary Multi-Criterion Optimization (EMO'01).

A modelling approach to study the behaviour of ACO has been proposed in Evolutionary Computation (2002) 10(3):235-262.

Further informationen about our research

DFG-Project on Ant Algorithms

SIRA: Methods of Swarm-Intelligence on Reconfigurable Architectures

Special issue on Ant Colony Optimization

  • IEEE Transactions on Evolutionary Computation: Special Section on "Ant Algorithms and Swarm Intelligence"
    Guest Editorial 6(4): 317-320, 2002.
    Guest Editors: M. Dorigo, L.M. Gambardella, M. Middendorf, and T. Stützle

    Conference on Ant Colony Optimization

    ANTS'2000 - From Ant Colonies to Artificial Ants: 2nd International Workshop on Ant Algorithms

    Marco Dorigo, Martin Middendorf, and Thomas Stützle (Eds.):
    Abstract Proceedings of ANTS'2000 - From Ant Colonies to Artificial ANTS: Second International Workshop on Ant Colony Optimization.
    Brussels, Belgium, September 7--9, 2000.

    Publications on Ant Colony Optimization + Swarm Intelligence

    Journal articles

  • A. Brutschy, A. Scheidler, D. Merkle, M. Middendorf:
    Learning from House-Hunting Ants: Collective Decision-Making in Organic Computing Systems
    accepted for 6th International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS 2008), September 22-24, 2008.

  • M. Geis, M. Middendorf:
    Creating Melodies and Baroque Harmonies with Ant Colony
    accepted for International Journal of Intelligent Computing and Cybernetics.

  • S. Janson, D. Merkle, M. Middendorf:
    A Decentralization Approach for Swarm Intelligence Algorithms in Networks Applied to Multi Swarm PSO
    International Journal of Intelligent Computing and Cybernetics, 1(1), to appear, 2008.

  • S. Janson, D. Merkle, M. Middendorf:
    Molecular Docking with Multi-Objective Particle Swarm Optimization
    Applied Soft Computing, 8(1): 666-675, 2007.

  • S. Janson, M. Middendorf:
    A Hierarchical Particle Swarm Optimizer for Noisy and Dynamic Environments
    Genetic Programming and Evolvable Machines, 7(4):, 329-354, 2006.

  • S. Janson, M. Middendorf, M. Beekman:
    Searching for a new home - scouting behaviour of honeybee swarms
    Behavioral Ecology , 18(2):384-392, 2007.

  • S. Janson, M. Middendorf:
    A Hierarchical Particle Swarm Optimizer and its Adaptive Variant
    IEEE Systems, Man and Cybernetics - Part B, 32(6): 1272- 1282, 2005.
    Preliminary version in Proceedings of the Congress on Evolutionary Computation (CEC 2003), IEEE Press, 770--776, (2003).

  • D. Merkle, M. Middendorf:
    On solving permutation scheduling problems with ant colony optimization
    International Journal of Systems Science, 36(5): 255-266, 2005

  • S. Janson, M. Middendorf, M. Beekman:
    Honey bee swarms: How do scouts guide a swarm of uninformed bees?
    To appear in Animal Behavior.

  • B. Scheuermann, K. So, M. Guntsch, M. Middendorf, O. Diessel, H. ElGindy, H. Schmeck:
    FPGA Implementation of Population-based Ant Colony Optimization
    Applied Soft Computing 4: 303-322, 2004.

  • S. Janson, D. Merkle, M. Middendorf, H. ElGindy, H. Schmeck:
    On Enforced Convergence of ACO and its Implementation on the Reconfigurable Mesh Architecture Using Size Reduction Tasks.
    Journal of Supercomputing, 26(3): 221-238,2003.
    Preliminary version in:Proceedings of the Second International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'02), Las Vegas, CSREA Press, 2002, 3-9.

  • D. Merkle and M. Middendorf:
    An ant algorithm with global pheromone evaluation for scheduling a single machine.
    Applied Intelligence, 18(1): 105-111, 2003.
  • Preliminary version in: S. Cagnoni et al. (Eds.), Real-World Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2000, Edinburgh, 17. April 2000, Springer Verlag, LNCS 1803 (2000) 287-296.
    Abstract EvoSTIM-Paper

    D. Merkle and M. Middendorf:
    Modelling the Dynamics of Ant Colony Optimization Algorithms
    Evolutionary Computation 10(3): 235-262, 2002.
    Preliminary version in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), New York, 2002.

  • D. Merkle and M. Middendorf:
    Fast Ant Colony Optimization on Runtime Reconfigurable Processor Arrays.
    Genetic Programming and Evolvable Machines, 3(4):345-361 , 2002.
  • Preliminary version in: Proceedings of the 8th Reconfigurable Architectures Workshop 2001 (RAW 2001), San Francisco, 2001.

  • D. Merkle, M. Middendorf, and H. Schmeck:
    Ant Colony Optimization for Resource-Constrained Project Scheduling.
    IEEE Transactions on Evolutionary Computation, 6(4): 333-346, 2002.
  • Preliminary version in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), Las Vegas, Nevada, July 8-12 2000, Morgan Kaufmann, (2000) 893-900.
    GECCO-Paper

  • M. Middendorf, F. Reischle, and H. Schmeck;
    Multi Colony Ant Algorithms.
    Journal of Heuristics (special issue on Parallel Metaheuristics), 8(3): 305-320, 2002.
  • Preliminary version in: J. Rolim (Ed.) Parallel and Distributed Computing, Proceedings of the 15 IPDPS 2000 Workshops, Third Workshop on Biologically Inspired Solutions to Parallel Processing Problems (BioSP3), Mai 1-5 2000, Cancun, Mexico, Springer-Verlag, LNCS 1800 (2000), 645-652.
    Abstract BioSP3-Paper

    Contributions to books

    D. Merkle, M. Middendorf:
    Ant Colony Optimization: Biological Motivation, Phase Structure, and Modelling
    Proc. I International Symposium on Mathematical and Computational Biology (BIOMAT 2004), Ilheus, Brasilien, to appear.

  • S. Janson, D. Merkle, M. Middendorf:
    Parallel Ant Algorithms
    in E. Alba (Ed.), Parallel Metaheuristics, Wiley Book Series on Parallel and Distributed Computing, to appear

  • D. Merkle, M. Middendorf:
    Swarm Intelligence
    to appear in E. Burke, G. Kendall (editors), Introductory Tutorials in Optimisation, Search and Decision Support Methodology, Kluwer, 2003.

  • R. Michels, and M. Middendorf:
    An Ant System for the Shortest Common Supersequence Problem.
    In: D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization, McGraw-Hill, (1999) 51-61.
  • Preliminary versions in: Proc. Fifth International Conference On Parallel Problem Solving From Nature (PPSN'98), Amsterdam, Netherlands, Springer Verlag, LNCS 1498 (1998), 692-701
    Technical Report 378, Institute AIFB, University of Karlsruhe, Germany, June 1998.
    Abstract Technical-Report


    Conference proceedings

  • S. Janson, M. Middendorf:
    Flexible Particle Swarm Optimization Taks for Reconfigurable Processor Arrays
    Accepted subject to revision for The 8th International Workshop on Nature Inspired Distributed Computing (NIDISC’05), Denver, Colorado, 2005

  • B. Scheuermann, M. Middendorf:
    Counter-based Ant Colony Optimization as a Hardware-oriented Meta-Heuristic
    Accepted for 2nd European Workshop on Evolutionary Computer in Hardware Optimisation (EvoHOT 2005), Lausanne, 2005

  • D. Merkle, M. Middendorf:
    Competition Controlled Pheromone Update for Ant Colony Optimization
    Proc. Fourth International Workshop ANTS 2004, Springer, LNCS 3172, 95-105, 2004

  • S. Janson, M. Middendorf:
    A Hierarchical Particle Swarm Optimizer for Dynamic Optimization Problems
    Accepted for 1st European Workshop on Evolutionary Algorithms in Stochastic and Dynamic Environments, Coimbra, Portugal, 2004.

  • D. Merkle, M. Middendorf:
    Competition Controlled Pheromone Update for Ant Colony Optimization
    Proc. Fourth International Workshop ANTS 2004, Springer, LNCS 3172, 95-105, 2004

  • B. Scheuermann, M. Guntsch, M. Middendorf, H. Schmeck:
    Time-Scattered Heuristic Guidance for a Hardware Implementation of ACO
    Proc. Fourth International Workshop ANTS 2004, Springer, LNCS 3172, 250-261, 2004

  • S. Janson, M. Middendorf:
    A Hierarchical Particle Swarm Optimizer
    Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), IEEE Press, 770-776, 2003.

  • M. Guntsch, M. Middendorf:
    Solving Multi-Objective Permutation Problems with Population Based ACO
    Proceedings of the Second International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), C.M. Fonseca, P.J. Fleming, E. Zitzler, K. Deb, L. Thiele (Eds.), Springer, LNCS 2636, 2003, 464-478.

  • O. Diesel, M. Guntsch, M. Middendorf, B. Scheuermann, H. ElGindy, H. Schmeck, K. So:
    Population based Ant Colony Optimization on FPGA
    Proceedings 2002 IEEE International Conference on Field-Programmable Technology (FPT'02), P. Leong, W. Luk (Eds.), IEEE, Hong Kong, 2002, 125-132.

  • M. Guntsch, M. Middendorf:
    Applying Population Based ACO to Dynamic Optimization Problems
    Ant Algorithms, Proceedings of Third International Workshop ANTS 2002, Brussels, Belgium, Springer Verlag, LNCS 2463, 2002, 111-122.

  • D. Merkle, M. Middendorf:
    Modelling ACO: Composed Permutation Problems
    Ant Algorithms, Proceedings of Third International Workshop ANTS 2002, Brussels, Belgium, Springer Verlag, LNCS 2463, 2002, 149-162.

  • S. Janson, D. Merkle, M. Middendorf, H. ElGindy, H. Schmeck:
    On Enforced Convergence of ACO and its Implementation on the Reconfigurable Mesh Architecture Using Size Reduction Tasks
    Proceedings of the Second International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'02), Las Vegas, CSREA Press, 2002, 3-9.

  • M. Guntsch, and M. Middendorf:
    A Population Based Approach for ACO
    Proceedings 2nd European Workshop on Evolutionary Computation in Combinatorial Optimization (EvoCOP-2002), Kinsale, Ireland, Springer Verlag, LNCS 2279, 2002, 72-81.

  • D. Merkle, and M. Middendorf:
    Ant Colony Optimization with the Relative Pheromone Evaluation Method
    Proc. 3rd European Workshop on Scheduling and Timetabling and 3rd European Workshop on Evolutionary Methods for AI Planning (EvoSTIM/EvoPLAN-2002), Kinsale, Ireland, LNCS 2279, 2002, 325-333.
    Abstract Preliminary version (postscript)

  • D. Merkle, and M. Middendorf:
    Collective Optimization: The Artificial Ants Way
    Abstract Proceedings of the workshop From Worker to Colony: Understanding the Organisation of Insect Societies, Isaac Newton Institute, Cambridge, 2001.

  • D. Merkle, and M. Middendorf:
    On the Behaviour of Ant Algorithms: Studies on Simple Problems
    In: Proceedings of the 4th Metaheuristics International Conference (MIC`20001), Porto, 2001, 573-577.

  • M. Guntsch, M. Middendorf, and H. Schmeck:
    An Ant Colony Optimization Approach to Dynamic TSP.
    In: L. Spector et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, CA: Morgan Kaufmann Publishers, 2000, 860-867.
    Abstract

  • D. Merkle and M. Middendorf:
    Prospects for Dynamic Algorithm Control: Lessons from the Phase Structure of Ant Scheduling Algorithms.
    In: Robert B. Heckendorn (Ed.), Proceedings of the 2000 Genetic and Evolutionary Computation Conference -- Workshop Program. Workshop "The Next Ten Years of Scheduling Research", San Francisco, CA, July 7, 2001, 121-126.
    Abstract

  • M. Guntsch and M. Middendorf:
    Pheromone Modification Strategies for Ant Algorithms applied to Dynamic TSP.
    In: E.J.W. Boers et al. (Eds.) Applications of Evolutionary Computing: Proceedings of EvoWorkshops 2001, Lake Como, Italy, Springer Verlag, LNCS 2037 (2001) 213-222.
    Abstract Preliminary version (postscript)

  • D. Merkle and M. Middendorf:
    A New Approach to Solve Permutation Scheduling Problems with Ant Colony Optimization.
    In: E.J.W. Boers et al. (Eds.) Applications of Evolutionary Computing: Proceedings of EvoWorkshops 2001, Lake Como, Italy, Springer Verlag, LNCS 2037 (2001) 484-493.
    AbstractPreliminary version (postscript)

  • S. Iredi, D. Merkle, and M. Middendorf:
    Bi-Criterion Optimization with Multi Colony Ant Algorithms.
    In: E. Zitzler et al. (Eds.) Evolutionary Multi-Criterion Optimization, First International Conference (EMO'01), Zurich, Springer Verlag, LNCS 1993 (2001) 359-372.
    Abstract

  • M. Merkle, M. Middendorf, and H. Schmeck:
    Pheromone Evaluation in Ant Colony Optimization.
    Proceedings of the 26th Annual Conference of the IEEE Electronics Society IECON-2000 (2000 IEEE International Conference on Industrial Electronics, Control and Instrumentation), Third Asia-Pacific Conference on Simulated Evolution and Learning (SEAL2000), October 22-28, 2000, Nagoya, Japan, IEEE Press, 2726-2731.
    SEAL-Paper

  • M. Guntsch, J. Branke, M. Middendorf, and H. Schmeck:
    ACO Strategies for Dynamic TSP.
    In: Abstract Proceedings of the ANTS'2000 - From Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms, Brussels, Belgium, September 8-9, 2000, 59-62.

  • D. Merkle, M. Middendorf, and H. Schmeck:
    Ant Colony Optimization for the RCPSP using Weighted Summation Evaluation.
    In: Abstract Proceedings of the ANTS'2000 - From Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms, Brussels, Belgium, September 8-9, 2000, 84-87.

  • R. Michels and M. Middendorf:
    An Ant System for Plan Merging.
    First International Workshop on Ant Colony Optimization (Ants'98), Brussels, Belgium, 1998.

    Tutorials

    M. Middendorf:
    Tutorial on Ant Colony Optimization.
    Tutorial Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2003), Chicago, 2003.

    D. Merkle and M. Middendorf:
    Tutorial on Ant Colony Optimzation
    The Seventh Intenational Conference on Parallel Problem Solving from Nature (PPSN2002), Granada, Spain, September 7 - 11, 2002.

    M. Middendorf (invited):
    Tutorial on Multiobjective Optimization with Ant Colony Systems
    Workshop on Multiple Objective MetaHeuristics (MOMH) (a joint PM2O - EU/ME meeting), Paris, November 4-5, 2002.

    M. Middendorf:
    Tutorial on Ant Colony Optimization.
    Tutorial Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2002), New York, 416-436, 2002.

    Martin Middendorf:
    Tutorial on Ant Colony Optimization.
    In: Tutorial Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, 236-255, 2001.

    Invited Talks

    (not complete) M. Middendorf:
    Ant Colony Optimization: Biological Motivation, Phase Structure and Modelling.
    Key Note Speech at I International Symposium on Mathematical and Computational Biology (BIOMAT 2004), Ilheus, Brazilia, November, 2004.

    M. Middendorf:
    The Use of Models for Social Insects in Computer Science to Solve Optimization Problems
    XXII International Congrees of Entology, Section on Social Insects, Brisbane, Australia, March 19, 2004

    M. Middendorf:
    Ant Colony Optimization
    Friday-Talks on Operations Research - Machine Learning, University of Osnabrück, June 11, 2004

    M. Middendorf:
    Traces of Ants in Computer Science
    Integrated Studies on the Economy of Insect Societies, European INSECTS Meeting, Laufen, March 28 - April 1, 2003

    M. Middendorf:
    Modelling the Dynamics of Ant Colony Optimization
    Colloquium Computational Intelligence, University of Dortmund, February 3, 2003

    Diploma thesises on Ant Colony Optimzation

  • Michael Erdmann:
    Clustering mittels einfacher autonomer Agenten in einer unbekannten Umgebung.
    19.11.2001 (Uni Hannover)

  • Steffen Iredi:
    Belegungsplanung für ein Einmaschinenproblem mit Hilfe eines Ameisenalgorithmus.
    6.10.2000 (Uni Hannover)

  • Frank Reischle:
    Parallelisierung von Ameisenalgorithmen.
    17.8.1999 (Uni Karlsruhe)

  • Frank Rühl:
    Einsatzplanung von Fahrzeugen mittels Ameisenalgorithmen (mit Fa. LOCOM, Karlsruhe).
    7.8.1999 (Uni Karlsruhe)

  • Carsten Pester:
    Analyse von Ameisenalgorithmen.
    13.5.1999 (Uni Karlsruhe)

  • Rene Michel:
    Ameisenalgorithmen für das Plan Merging Problem.
    6.7.1998 (Uni Karlsruhe)

    Semester thesises on Ant Colony Optimzation

  • Michael Kaltenbach und Frederik Nagel:
    Entwicklung eines Werkzeuges zur Lösung des HP-Proteinfaltungsproblems mit Ameisenalgorithmen.
    A Tool for Solving the Protein Folding problem in the HP-Model with Ant Algorithms.
    21.6.2001 (Uni Hannover) Short version(ppt)

    Martin Middendorf