UNIVERSITýT LEIPZIG
Fakultät für Mathematik und Informatik Institut für Informatik
Parallelverarbeitung und Komplexe Systeme


Ameisenalgorithmen und Schwarm Intelligenz



Was sind Ameisenalgorithmen?

Ameisenalgorithmen sind naturanaloge Optimierungsverfahren, die sich Lösungsstrategien zu Nutze machen, welche Ameisen bei beispielsweise bei der Futtersuche verwenden (Ein kurzer Übersichtsartikel findet sich im Juliheft der Zeitschrift Nature, 406 (2000)). Praktischen Einsatz finden Ameisenalgorithmen bisher vor allem im Bereich der Tourenplanung, Produktionsplanung und bei der Lösung von Schedulingproblemen.

Ein Tutorial-Kapitel zu Methoden der Schwarm Intelligenz erscheint in "Introductory Tutorials in Optimisation and Search Methodologies" E. Burke, G. Kendall (Eds.), Kluwer)

Ziele unserer Forschung

Ein Ziel unserer Forschung ist die Entwicklung von neuartigen Ameisenalgorithmen, die in der Lage sind sehr komplexe Probleme zu lösen. Beispiele für Probleme mit denen wir uns beschäftigen sind die Projektplanung bei beschränkten Ressourcen, dynamisch veränderliche Optimierungsprobleme sowie Optimierungsprobleme mit mehreren Optimierungskriterien.

Desweiteren untersuchen wir die grundlegenden Mechanismen, welche das Verhalten von Ameisenalgorithmen bestimmen. Ein Beispiel hierfür ist die geeignete algorithmische Nutzung von indirekten Kommunikationsmechanismen (vergleichbar den von Ameisen genutzten Pheromonen).

Untersuchungen der Zusammenhänge zwischen Ameisenalgorithmen und Rechnerachitekturen dienen der Entwicklung besonders effizienter Varianten von Ameisenalgorithmen (vgl. DFG Projekt SIRA).


Einige Ergebnisse unserer Forschung

Ein von uns entwickelter Ameisenalgorithmus hat neue beste Lösungen für einige der größten und am häufigsten verwendeten Testprobleme für die Projektplanung bei beschränkten Ressourcen gefunden (siehe PSPLIB, Universität Kiel). Siehe hierzu den Artikel in der Zeitschrift IEEE Transactions on Evolutionary Computation.

Durch die Entwicklung von Kooperationsmechanismen zwischen mehreren Kolonien von künstlichen Ameisen konnten Probleme der Planung Machinenbelegungen bei Beachtung von zwei Optimierungskriterien (Zeiten und Kosten) erfolgreich gelöst werden. Hierzu erschien eine Arbeit auf der ersten Internationalen Konferenz über Evolutionäre Methoden für Multikriterielle Optimierung (EMO'01).

Es wurden neuartige Methoden zur Auswertung der Pheromoninformation entwickelt, die zu teilweise erheblichen Verbesserungen bei der Lösung von Optimierungsproblemen gegenüber den bisherigen rein lokalen Methoden führen.

Es wurde ein Modell für einen Ameisenalgorithmus entwickelt um analytsiche Untersuchungen an Ameisenalgorithmen durchzuführen. Siehe hierzu den Artikel in Evlutionary Computation.

Sind Sie interessiert?

Interessenten können sich gerne an uns wenden.

Für Studierende, die eine Studien- oder Diplomarbeit im Bereich Ameisenalgorithmen und Schwarm Intelligenz schreiben möchten, stehen interessante Themen zur Auswahl.

Firmen, die Interesse an einer Kooperation haben, sind willkommen.

Weitere Informationen zu unserer Arbeit

DFG-Projekt zu Ameisenalgorithmen + Schwarm Intelligenz

SIRA: Methoden der Schwarm-Intelligenz auf Rekonfigurierbaren Architekturen

Sonderheft zu Ameisenalgorithmen

  • IEEE Transactions on Evolutionary Computation: Special Issue 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

    Konferenz über Ameisenalgorithmen

    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.

    Veröffentlichungen zu Ameisenalgorithmen + Schwarm Intelliganz

    Zeitschriften

  • 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.
  • Vorversion 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.
  • Vorversion 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.
  • Vorversion 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

    Buchbeiträge

    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.
  • Vorversionen in: Proc. Fifth International Conference On Parallel Problem Solving From Nature (PPSN'98), Amsterdam, Netherlands, Springer Verlag, LNCS 1498 (1998), 692-701
    Bericht 378, Institute AIFB, University of Karlsruhe, Germany, June 1998.
    Abstract Technical-Report

    Konferenzbeiträge

  • 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.

  • 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.
    Abstract Preliminary 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.

    Tutorien

    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.

    Eingeladene Vorträge

    (nicht vollständig)

    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
    Key Note Speech at the "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 Dortmung, February 3, 2003

    Diplomarbeiten zu Ameisenalgorithmen

  • Gunnar Schau:
    in Planung

  • 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)

    Studienarbeiten zu Ameisenalgorithmen

  • Michael Kaltenbach und Frederik Nagel:
    Entwicklung eines Werkzeuges zur Lösung des HP-Proteinfaltungsproblems mit Ameisenalgorithmen.
    21.6.2001 (Uni Hannover) Short version(ppt)

    Martin Middendorf