Betriebswirtschaftliche Anwendungen für Ameisen-Systeme

Diplomarbeit

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme

Eingereicht von:

Philipp Kötter

Lehrstuhl für Betriebswirtschaftslehre

und Unternehmensforschung

Lehrstuhl für Betriebswirtschaftslehre, Controlling und Produktionswirtschaft

Universität Bielefeld

Inhaltsverzeichnis

Inhaltsverzeichnis. 1

1 Einführung in das Ameisen-System.. 2
1.1 Vorgehensweise in der Natur. 2
1.2 Übertragung des Ameisen-Systems in die Informatik. 3

2 Algorithmen. 5
2.1 Ameisen-System.. 7
2.2 Ameisen-System mit Q-Lernen. 13
2.3 Ameisen-System mit unterschiedlichen Ameisen. 20
2.4 Parallelisierung. 25
2.5 Zusammenstellung. 28

3 Betriebswirtschaftliche Anwendungen. 29

3.1 Rundreisen- und Tourenprobleme. 30
3.1.1 Travelling Salesman Problem.. 30
3.1.2 Vehicle Routing Problem.. 32
3.1.3 Dependent Vehicle Routing Problem.. 38

3.2 Zuordnungsprobleme. 41
3.2.1 Ameisen-Algorithmen für das Quadratic Assignment Problem.. 43
3.2.2 Quadratic Assignment Problem als Graph für Ameisen-Systeme. 50

3.3 Reihenfolgeprobleme. 55
3.3.1 Total Tardiness Problem.. 59
3.3.2 Sequential Ordering Problem.. 61
3.3.3 Open Shop Problem.. 64
3.3.4 Flow Shop Problem.. 65
3.3.5 Job Shop Problem.. 71

4 Ausblick. 74

Abbildungsverzeichnis. II

Variablen, Parameter und Abkürzungen. III

Literaturverzeichnis. IV

Versicherung. V

1 Einführung in das Ameisen-System

Ameisen gehören zu den staatenbildenden Insekten und die Existenz jedes Einzelnen ist nur auf das Überleben der gesamten Kolonie ausgerichtet (vgl. Dorigo et al. (1998)). Obwohl die Ameisen nicht sehen können und auch nicht direkt mit ihren Artgenossen kommunizieren können, finden sie rasch kürzeste Wege zwischen Nest und Futterquelle.

1.1 Vorgehensweise in der Natur

Auf ihrer Suche nach Futter hinterlassen Ameisen Duftstoffe, sogenannte Pheromone, die den zurückgelegten Weg markieren. Allerdings verdunstet diese Duftspur nach und nach, bis sie irgendwann ganz verschwindet. Anhand dieser Markierungen orientieren sich wiederum andere Ameisen und hinterlassen ihrerseits neue Duftspuren. Während anfangs die Ameisen eher zufällig einen Weg zum Futter suchen, folgt ein Tier, das auf eine Pheromonspur trifft, dieser mit hoher Wahrscheinlichkeit, wobei stärkere Spuren bevorzugt werden. Im Laufe der Zeit führt dieser Prozess dazu, dass fast alle Ameisen den kürzesten Weg vom Bau zur Futterquelle wählen. Denn die Ameisen, die aufgrund der stärkeren Pheromonspur den kürzeren Weg nehmen, hinterlassen selbst auch Pheromone. Eine Ameise auf einem kürzeren Pfad braucht für den Hin- und Rückweg weniger Zeit als für einen längeren. Dadurch kann sie in gleicher Zeit auf dem kürzeren Weg eine intensivere Duftspur hinterlassen (vgl. Dorigo et al. (1998)).

In Abbildung 1.1 ist diese Situation dargestellt (vgl. Colorni et al. (1992b)). Auf der Suche nach Futter stoßen die Ameisen auf ein Hindernis, so dass sie die Möglichkeit haben, links oder rechts vorbeizugehen (A). Da noch keine Pheromonspur den Weg kennzeichnet, entscheiden sich die Ameisen zufällig für einen Weg, so dass sich jeweils die Hälfte der Ameisen für eine Seite entscheidet (B). Die Ameisen auf dem kürzeren Weg sind schneller wieder beim Nest und hinterlassen daher auch im Laufe der Zeit mehr Duftstoffe. Dadurch wählen immer mehr Ameisen den kürzeren Weg (C). Somit steigt die Intensität der Pheromonspur noch schneller auf diesem Weg, so dass sich rasch ein Großteil der Ameisen auf dem kürzeren Pfad bewegt (D).

C Hindernis Futter Futter

A Hindernis Nest Hindernis

B Hindernis Futter Nest

D Nest Nest Futter

Abbildung 1.1: Ameisen finden den kürzesten Weg

1.2 Übertragung des Ameisen-Systems in die Informatik

Das Prinzip der Ameisen lässt sich auch durch die Abbildung 1.2 weiter erklären (vgl. Dorigo et al. (1996)). Dabei gilt es, den kürzesten Weg von A nach B und wieder zurück zu finden. Die Entfernung zwischen den Punkten beträgt jeweils eine Längeneinheit. Die Ameisen können pro Zeiteinheit genau 1 Längeneinheit zurücklegen und hinterlassen dabei eine Pheromonspur, die bis zur Mitte des nächsten Zeitintervalls komplett verdunstet ist. Da zum Zeitpunkt t=0 noch keine Pheromonspur vorhanden ist, wählen die Ameisen am Anfang zufällig einen der beiden möglichen Wege. Am Anfang eines jeden Zeitabschnitts starten 30 Ameisen im Punkt A.

In t=1 haben die ersten Ameisen bereits eine Pheromonspur gelegt. Allerdings ist diese auf den Wegen AB und AC zu diesem Zeitpunkt noch gleich groß. Wiederum entscheiden sich die Ameisen zufällig für einen Pfad. Zur gleichen Zeit haben die Ameisen, die in t=0 den Weg AB gewählt hatten, ihr Ziel B erreicht und befinden sich nun bereits auf dem Rückweg. Dabei wählen diese Ameisen den Weg BA, da bislang nur auf diesem eine Pheromonspur vorhanden ist, an der sie sich orientieren können.

In t=2 sind die ersten Ameisen, die den Weg AB und schließlich BA gewählt haben, bereits wieder in Punkt A angekommen. Zusammen mit den Ameisen, die ihnen im Zeitpunkt t=1 gefolgt waren, haben sie auf dem Weg AB eine Pheromonspur von der Intensität t=30 hinterlassen. Die Ameisen, die den längeren Weg zum Punkt B über C gewählt haben, befinden sich erst jetzt auf dem Rückweg. Dabei wird der Weg BA aufgrund der intensiveren Pheromonsspur bevorzugt.

Im Laufe der Zeit werden etwa doppelt so viele Ameisen den Weg AB bzw. BA wählen wie den Weg ACB bzw. BCA. Dies ist darauf zurückzuführen, dass der Weg AB nur halb so lang ist wie der Weg ACB und die Ameisen auf diesem Weg in einer bestimmten Zeit doppelt so häufig laufen können. Dadurch verdoppelt sich auch die Intensität der Pheromonspur.

Das Verhalten einer Ameisen-Kolonie kann wegen der Autonomie und des Lernprozesses der Ameisen mit Multi-Agent-Systemen verglichen werden (vgl. Weiß/Sen (1996)).

Der Algorithmus, der diesem Vorgehen in der Natur wohl am nächsten kommt, wird in Dorigo/Di Caro (1999) beschrieben. Er wird als einfacher Ameisen-Kolonie-Optimierungs-Algorithmus bezeichnet („simple ant colony optimization algorithm“, S-ACS). Allerdings wurde in Experimenten gezeigt, dass bei einem Anstieg der Komplexität des Problems (z. B. bei einer Entscheidungsmöglichkeit zwischen mehr als zwei Pfaden) das Verhalten des Algorithmus instabiler wird. Daher ist dieser Algorithmus lediglich als begrenztes Beispiel anzusehen, in dem das Prinzip der künstlichen Ameisen mit der Konstruktion einer Tour, Verstärkung der Pheromonspur auf den benutzten Wegen und allmählicher Verdunstung der Spur deutlich wird.

Aufgrund der starken Beschränkung dieses Algorithmus wurden weitere Algorithmen entwickelt, die auf den gleichen Prinzipien aufbauend auch auf komplexere Probleme angewandt werden können.

2 Algorithmen

1991 entwickelten Mailänder Wissenschaftler unter Führung von Marco Dorigo Algorithmen, die auf dem Verhalten der Ameisen basieren (vgl. Dorigo et al. (1991a)). Dabei wurden bei den „künstlichen“ Ameisen einige Veränderungen vorgenommen. Die „künstlichen“ Ameisen wurden nun mit einem Speicher (Tabu-Liste) versehen, so dass sie vermerken konnten, an welchen Punkten sie bereits gewesen sind. Ebenso waren sie, im Gegensatz zu ihren Vorbildern aus der Natur, nicht „blind“, sondern konnten die Entfernungen zu noch nicht besuchten Punkten berücksichtigen. Insofern werden die Ameisen bei den verschiedenen Algorithmen als einfache Agenten („simple computational agents“, vgl. Maniezzo et al. (2004), Seite 3) betrachtet.

In diesem Abschnitt soll nun auf einige bislang entwickelte Algorithmen eingegangen werden, die sich auf die ursprüngliche Idee des Ameisen-Systems stützen, das im vorangegangenen Abschnitt beschrieben wurde. Zur besseren Veranschaulichung werden die Algorithmen zunächst anhand eines symmetrischen euklidischen Travelling Salesman Problems (TSP) vorgestellt. Dabei wird die kürzeste Rundreise einer Ameise (bzw. eines Agenten) gesucht, wobei alle n Städte genau einmal besucht werden müssen. Die Entfernung d_ij von einer Stadt i zur Stadt j ist gleich der Entfernung d_ji von der Stadt j zur Stadt i, mit_{, wobei x und y die Koordinaten der Städte sind. Der Graph ist vollständig, das heißt, dass jede Stadt von jeder Stadt aus erreicht werden kann.}

Eine hinreichende Bedingung für die Existenz einer Rundreise mit n Knoten ist in Domschke (1997) auf Seite 102 definiert:

-  In einem Digraph (wie beim asymmetrischen Travelling Salesman Problem) muss jeder einzelne Knoten i mit mindestens n/2 anderen Knoten durch eine gerichtete Kante verbunden sein. Ebenso muss von mindestens n/2 Knoten eine gerichtete Kante in diesen Knoten i führen.

-  In einem ungerichteten Graph (wie beim symmetrischen Travelling Salesman Problem) muss jeder einzelne Knoten i mit mindestens n/2 anderen Knoten verbunden sein.

Bei dieser hinreichenden Bedingung ist allerdings nur sichergestellt, dass überhaupt eine Rundreise existiert. Ebenso gibt es auch Graphen mit weniger Kanten, bei denen dennoch gültige Rundreisen möglich sind. Bei der Anwendung eines Algorithmus auf eine solche Instanz können daher auch ungültige Lösungen entstehen, indem zum Beispiel eine Tour nicht beendet werden konnte. In bezug auf die Spurenverstärkung bei den Ameisen-Algorithmen können diese ungültigen Lösungen nicht beachtet werden, um nicht zu einem „falschen“ Lernen anzuregen.

Bei den Modellen in diesem Kapitel geht man von statischen Modellen aus, bei denen sich die vorgegebenen Daten wie Entfernungen oder Anzahl der Städte im Laufe des Algorithmus nicht ändern. Zudem ist die Zeit eine diskrete Größe.

Die verschiedenen Ameisen-Algorithmen können grundsätzlich in vier Gruppen eingeteilt werden:

Abbildung 2.1: Kategorisierung von Ameisen-Algorithmen

2.1 Ameisen-System

Beim Ameisen-System („ant system“, AS) wird zum Zeitpunkt t=0 eine Initialisierungsphase eingeleitet, in der die Ameisen in verschiedene Städte gesetzt werden. Zudem werden einheitliche Startwerte für die Spurenintensität (mit t_ij(0)>0) bestimmt und die Startpunkte als erstes Element in die jeweiligen Speicher der Ameisen eingeführt. Nun bewegen sich die Ameisen von einer Stadt zur nächsten, wobei die Zielstadt j mit einer Wahrscheinlichkeit bestimmt wird, die eine Funktion aus Nähe und Spurintensität ist. Diese wird auch Übergangszustandsregel genannt („state transition rule“, „random-proportional rule“, vgl. Dorigo/Gambardella (1996c)):

  _(2.1)

Dabei ist t_ij(t) die Intensität der Pheromonspur auf dem Pfad vom Knoten i zum Knoten j zum Zeitpunkt t, während h_ij die „Sichtbarkeit“ angibt. Im Fall des Travelling Salesman Problems ist die „Sichtbarkeit“ („visibility“) die Nähe zwischen den Knoten i und j, die sich aus dem Kehrwert ihrer Entfernungen zueinander 1/d_ij ergibt. In Maniezzo (1998) (Seite 4) werden die beiden Faktoren t_ij(t) und h_ij auch  „a posteriori indication“ und „a proiri desirability“ genannt, da die Spurenstärke auf der Kante (i,j) verändert werden kann, nachdem eine Tour konstruiert wurde, wohingegen die Entfernung vorher als deterministische Größe bekannt ist und unverändert bleibt.

M_k ist der Speicher (Tabu-Liste) der k-ten Ameise, in dem alle Städte stehen, die die k-te Ameise im Laufe ihrer Rundreise bereits besucht hat. Die Tabu-Liste hat hier, im Gegensatz zu Tabu-Such-Algorithmen (vgl. Glover (1989), Glover (1990)), lediglich die Aufgabe, bereits besuchte Orte zu vermerken, um diese bei der nächsten Stadtwahl nicht mehr zu berücksichtigen. Zudem wird dadurch eine Ameise „gezwungen“, gültige Lösungen zu produzieren und Kurzzyklen zu meiden (vgl. Dorigo et al. (1991a), Seite 3).

Die Variablen a und b können den Einfluss der Spurenintensität bzw. der Entfernung zwischen zwei Städten auf die Entscheidung der Ameise verändern. Beim Setzen von a=0 wird die Spurenintensität völlig vernachlässigt, so dass man einem Greedy-Search-Algorithmus folgt und sich nur nach den kürzesten Entfernungen richtet, wohingegen b=0 bedeuten würde, dass man sich nur an der Spurenintensität orientiert. Im ersten Fall würde man in den seltensten Fällen das Optimum erreichen, im zweiten Fall würde immer ein gewisser Anteil der Ameisen einen wesentlich längeren Weg laufen.

Jede Ameise wählt im Zeitpunkt t eine neue Stadt, die sie zum Zeitpunkt t+1 erreicht, ganz gleich, wie lang dieser Weg ist. Wenn alle n Städte besucht wurden, d. h. im Zeitpunkt t = t+n, ist ein Zyklus beendet, und alle Ameisen haben eine komplette Tour konstruiert.

Der Prozess bricht ab, wenn die zuvor festgelegte maximale Zyklenanzahl NC_MAX erreicht ist oder sich alle Ameisen auf der selben Tour befinden. Dieser zweite Fall wird Stagnation genannt, da der Algorithmus aufhört, nach anderen möglichen Lösungen zu suchen. Man erhält als Ergebnis ein lokales oder globales Optimum.

Beim Ameisen-Zyklus-Algorithmus („ant cycle algorithm“) wird die konstruierte Tour der k-ten Ameise immer erst am Ende eines Zyklus (also nach n Zeiteinheiten) mit Pheromon verstärkt:

    (2.2)

mit

und

Der Parameter r Î [0,1] gibt die Stärke der Spur an, so dass durch (1-r) die Verdunstung ausgedrückt wird. _{bezeichnet die Stärke an Pheromon, die die k-te Ameise im Zeitintervall (t,t+n) auf der Kante (i,j) gelegt hat. Q ist eine wählbare Konstante und Lk die Länge der Tour der k-ten Ameise im aktuellen Zyklus. Diese lässt sich aus den Entfernungen zwischen den Städten errechnen, die am Ende einer Tour im vollen Speicher der k-ten Ameise stehen. Die Spurstärken werden neu berechnet. Zuletzt werden die Speicher, in denen die besuchten Städte stehen, wieder komplett gelöscht und es beginnt ein neuer Zyklus.}

Grundsätzlich durchläuft eine Ameise immer wieder die zwei Phasen:

-  Konstruktion einer Tour mit Hilfe von p_ij(t) und M_k

-  Aktualisierung der Spuren auf den benutzten Kanten

Der formale Algorithmus für den Ameisen-Zyklus-Algorithmus kann wie folgt dargestellt werden (vgl. Dorigo et al. (1991a), Dorigo et al. (1996)):

1. 
   Initialisierung
   setze t:=0 und NC:=0 (t ist der Zeitzähler und NC ist der Zyklenzähler);
   setze für jede Kante (i,j) einen Startwert t_ij(0) und Dt_ij:=0;
   platziere die m Ameisen auf die n Knoten;
   
2. 
   Konstruktion
   setze s:=1  (s ist der Speicher-Index);
   für k:=1 bis m tue {
   füge die Start-Stadt der k-ten Ameise in M_k(s) ein }
   
3. 
   wiederhole, bis die Speicher-Liste voll ist (wird (n-1)-mal wiederholt) {
   setze s:=s+1;
   für k:=1 bis m tue {
   wähle die Stadt j, in die die Ameise reist, mit der Wahrscheinlichkeit p_ij(t);
   bewege die Ameise zu dieser Stadt j;
   füge die Stadt j in M_k(s) ein}
   
4. 
   für k:=1 bis m tue {
   berechne die Länge der Tour L_k aus der Speicher-Liste M_k;
   
   _{mit }}
   
5. 
   Spurenverstärkung
   für jede Kante (i,j) berechne t_ij(t+n) gemäß der Gleichung
   t_ij(t+n) = rt_ij(t)+Dt_ij;
   setze t:=t+n und NC:=NC+1;
   für jede Kante (i,j) setze Dt_ij:=0;
   

speichere die bislang kürzeste gefundene Tour;
wenn (NC<NC_MAX) und (kein Stagnationsverhalten)
dann
leere alle Speicher;
Gehe zu Schritt 2;
sonst
gib kürzeste Tour aus und stoppe;

Es gibt noch zwei weitere Algorithmen, die dem Ameisen-Zyklus-Algorithmus sehr ähnlich sind. Diese sind eigentlich eher mit dem Vorgehen in der Natur vergleichbar, da eine Ameise eine Kante direkt nach Benutzung verstärkt. Der Unterschied zwischen diesen beiden folgenden Algorithmen liegt nun allein in der Art der Verstärkung der Spur nach der Konstruktion einer Lösung.

-  Ameisen-Dichte-Algorithmus: Beim Ameisen-Dichte-Algorithmus („ant density algorithm“) legt jede Ameise eine Pheromonspur der Stärke Q auf eine Kante, sobald sie diese benutzt hat (vgl. Dorigo et al. (1991a)). Bei diesem Verfahren wird ausschließlich die Anzahl der Ameisen berücksichtigt, die einen Weg benutzt haben. Die Entfernung zwischen den Städten i und j bleibt unberücksichtigt.

Eine benutzte Kante wird demnach verstärkt durch:

  _{(2.3)
  mit}

und

Dt_ij(t,t+1) ist die Veränderung der Spurenstärke auf dem Pfad (i,j) im Intervall (t,t+1) und Q eine wählbare Konstante, die vorab festgelegt wird. Der Parameter r_l ist die Spurenstärke, so dass (1-r_l) die Verdunstung bei einer lokalen Aktualisierung der Spurenintensitäten angibt.

-  Ameisen-Mengen-Algorithmus: Beim Ameisen-Mengen-Algorithmus („ant quantity algorithm“) hingegen wird eine benutzte Kante mit der Spurenintensität Q/d_ij verstärkt. Somit werden im Gegensatz zum Dichte-Algorithmus in erster Linie die kürzeren Kanten verstärkt. _{berechnet sich dann durch:}

  _(2.4)

Experimente in Dorigo et al. (1991a) haben jedoch gezeigt, dass der Ameisen-Zyklus-Algorithmus sowohl dem Ameisen-Dichte- wie auch dem Ameisen-Mengen-Algorithmus überlegen ist, was an der Verarbeitung der globalen Information beim Ameisen-Zyklus-Algorithmus. Die anderen beiden Algorithmen betrachten hingegen nur die lokalen Informationen. Dadurch kommt es langfristig zu einem Stagnationsverhalten, bei dem immer ein gewisser Teil einen schlechteren Weg bevorzugt.

In Colorni et al. (1992a) wurden Experimente durchgeführt, bei denen alle Ameisen von einer Stadt aus starteten, anstatt von verschiedenen Städten aus. Dabei konnte jedoch nie das bis dahin bekannte Optimum erreicht werden. Stattdessen folgten die Ameisen nach wenigen hundert Iterationen nur noch einer sehr kleinen Menge an Pfaden.

Bei der Anwendung des Ameisen-Systems können auch  nur für relativ kleine Probleme mit bis zu 50 Städten gute Ergebnisse erzielt werden, außerdem ist die Laufzeit für gute Ergebnisse ist recht hoch (Stützle/Hoos (1996), vgl. Stützle (1998b)).

Eine Weiterentwicklung des Ameisen-Systems stellt das MAX-MIN-Ameisen-System („MAX-MIN ant system“, MMAS) dar, das 1996 von Stützle/Hoos entwickelt wurde (vgl. Stützle/Hoos (1996)). Beim MAX-MIN-Ameisen-System wird nun eine obere und untere Schranke für die Spurenintensität, t^max und t^min, eingeführt, um ein Stagnationsverhalten der Ameisen zu verhindern, das durch zu geringe Erkundung neuer Pfade hervorgerufen wird. Dadurch kann eine Spur auf einem Pfad nicht so stark (schwach) werden, dass die Ameisen nur noch (nicht mehr) diesen wählen.

Die Werte für t^max und t^min können mittels der Formeln (2.5) und (2.6) berechnet werden, wobei die Festlegung der unteren Schranke Experimenten zufolge wichtiger sei (vgl. Stützle/Hoos (1996)).

  _(2.5)

  _(2.6)

Eine Ameise muss sich im Durchschnitt zwischen n/2 Städten entscheiden. Der Faktor p gibt die Wahrscheinlichkeit an, dass die Ameise nach (n-1) Entscheidungen die beste Tour gefunden hat.

In Stützle/Hoos (1998a) wird hingegen die obere Schranke t^max auf

  _(2.7)

gesetzt und für t^min ein Wert gewählt, der konstant kleiner ist als die obere Schranke. L^gb ist die bislang global beste Lösung.

In der Initialisierungsphase des Algorithmus werden alle Spuren auf den Maximalwert t^max gesetzt, um die Unterschiede zwischen den Pfaden am Anfang nicht zu stark werden zu lassen. So werden die Pfade zu Beginn von den Ameisen recht unregelmäßig besucht. Allerdings könnte man eigentlich auch einen beliebigen Wert zwischen t^min und t^min für alle Spuren wählen.

Nachdem die Ameisen wie beim Ameisen-Zyklus-Algorithmus ihre Touren konstruiert haben, werden nur die Pfade von der besten Ameise verstärkt. Es gibt zwei Möglichkeiten, diese Verstärkung anhand der Formel (2.8) vorzunehmen. Zum einen können die Pfade von der iterations-besten Ameise verstärkt werden, zum anderen ist es auch möglich, dass die global beste Ameise ihre Tour verstärkt. Allerdings kann bei längeren Durchläufen auch hier Stagnation nicht ganz vermieden werden.

  _(2.8)

mit

L^* kann die Tour der iterations- oder der global besten Ameise sein. Wenn man die iterations-beste Lösung wählt, kommt es zu einer stärkeren Erkundung neuer Wege, wohingegen die Wahl der global besten Lösung zu einer frühen Stagnation der Suche führen kann.

Da nur die beste Ameise ihre Tour verstärken darf, werden die Spuren auf allen anderen Wegen im Laufe der Zeit immer schwächer. Durch diesen Effekt können „Fehler“ aus der Vergangenheit beseitigt werden. Der Parameter r, der eine stärkere Verdunstung der Spur bewirkt, je kleiner er ist, kann somit als Lernfaktor („learning rate“) interpretiert werden (vgl. Stützle/Hoos (1996)).

Ein Nachteil vom MAX-MIN Ameisen-System ist die lange Laufzeit des Algorithmus. Diese kann durch Einführung einer Kandidatenliste verringert werden. In dieser Kandidatenliste steht für jede Stadt i eine zuvor festzulegende Anzahl an Städten, die der Stadt i am nächsten sind (vgl. Dorigo/Gambardella (1996)). Die Städte der Kandidatenliste sind nach der Nähe zur Stadt i sortiert und werden von den Ameisen bei der Wahl der nächsten Stadt ihrem Rang nach bevorzugt. Erst wenn keine Stadt aus der Kandidatenliste mehr besucht werden kann, werden die anderen noch nicht besuchten Städte berücksichtigt.

2.2 Ameisen-System mit Q-Lernen

Die Erweiterung des Ameisen-Systems durch eine veränderte Übergangszustandsregel („pseudo-random-proportional action choice rule“) bewirkt, dass zum einen aus bestehenden Daten gelernt wird („Q-learning“), zum anderen aber wieder völlig neue Daten gesammelt werden. In Abhängigkeit der vorgegebenen Parameter ergibt sich die relative Wichtigkeit der Verwendung der bestehenden Informationen (exploitation) gegenüber der Untersuchung neuer Wege (exploration) (vgl. Dorigo/ Gambardella (1996c)). Der Haupteffekt dieser Regel ist, dass man schneller sehr gute Lösungen erhält (vgl. Stützle/Hoos (1997)).

Bei Ant-Q handelt es sich um eine weitere Verbesserung des Ameisen-Systems. Dabei wird der Aspekt des Lernens berücksichtigt. Einige wesentliche Merkmale unterscheiden Ant-Q vom Ameisen-System (vgl. Gambardella/Dorigo (1995), Dorigo/Gambardella (1996a)).

Die Auswahl der nächsten Stadt wird nun durch die „pseudo-random-proportional action choice“ Regel bestimmt:

  _(2.9)

Die Ameise wählt mit der Wahrscheinlichkeit q₀ (0<q₀<1) den Knoten j, für dessen Kante das Produkt aus der Pheromonstärke und der Sichtbarkeit den höchsten Wert hat. Mit einer Wahrscheinlichkeit (1-q₀) startet die Ameise eine Erkundung der Umgebung. S ist eine Stadt, die sich wie beim Ameisen-System nach der Übergangszustandsregel aus Formel (2.1) ergibt.

Im Vergleich zum Ameisen-System ist die hier benutzte Übergangswahrscheinlichkeitsregel aggressiver (vgl. Stützle/Dorigo (1999b)).

Die Pheromonspuren auf bereits genommenen Routen werden bei erneutem Benutzen weniger verstärkt, damit auch die anderen Pfade beachtet werden. Die Änderung der Spur ergibt sich nach jeder Benutzung einer Ameise durch Formel (2.10):

  _(2.10)

mit 

Der Parameter Q ist am Anfang festzusetzen, der Zusatz _{ist eine Bewertung des Folgezustands, der als lokale Verstärkung des Pheromons auf der Kante (i,j) interpretiert werden kann. Allerdings wird dieser Wert üblicherweise auf Null gesetzt, so dass eine lokale Aktualisierung nicht stattfindet.}

Als globale Aktualisierung der Spurenintensitäten wird nach Formel (2.8) bei Ant-Q wie beim MAX-MIN-Ameisen-System nur die beste Tour verstärkt. Dabei kann entweder die iterations- oder die global beste Lösung für die Spurenverstärkung genommen werden. Experimente in Gambardella/Dorigo (1995) haben jedoch gezeigt, dass die Wahl der iterations-besten Lösung zu schnelleren Ergebnissen führt und nicht so stark auf eine Variation des Parameters g in Formel (2.10) reagiert.

In Gambardella/Dorigo (1995) wird Ant-Q unter anderem für Oliver30 getestet (vgl. Oliver et al. (1987)). Die Anzahl der Iterationen betrug 200, und es wurden durchschnittliche Längen sowie die kürzeste Tour von 15 Versuchen ermittelt. Die anderen Parameter wurden wie folgt gesetzt: d=1, b=2, t₀=1/(durchschnittliche Länge der Kanten*n), q₀=0.9, a=0.1, g=0.3, Q=10, m=n. Dabei ist t₀ der Wert, mit dem alle Kanten am Anfang bei der Initialisierung verstärkt werden. Die Anzahl an Ameisen m sollte innerhalb [0,6*n,n] liegen, wie Experimente gezeigt haben.

In Abbildung 2.2 sind die Ergebnisse für verschiedene Übergangszustandsregeln von Oliver30 zusammengefasst (vgl. Gambardella/Dorigo (1995), Seite 2ff).

Abbildung 2.2: Ant-Q bei Oliver30 für verschiedene Übergangszustandsregeln

Die „pseudo-random“ Regel ergibt sich aus der Formel (2.9), wobei S eine gleichverteilte Zufallsvariable über die Menge der noch nicht besuchten Städte ist, ausgehend von der aktuellen Stadt i. Diese Übergangszustandsregel ähnelt der Regel beim Q-Lernen.

Bei der „pseudo-random-proportional“ Regel wird die Zufallsvariable S in Formel (2.9) mit Hilfe der Formel (2.1) bestimmt. Hier ergab sich bei den Experimenten die beste Tour, ebenso war die durchschnittliche Länge der Touren hier am besten. Die beste Tour konnte innerhalb von 180 Touren (Anzahl an Iterationen des Algorithmus multipliziert mit der Anzahl an Ameisen m) gefunden werden (vgl. Dorigo/Gambardella (1996c)).

Die „random-proportional“ Regel unterscheidet sich von der „pseudo-random-proportional“ Regel lediglich durch das Setzen von q₀=0. Dadurch wird die nächste Stadt immer mit Hilfe von Formel (2.1) bestimmt. Dieses Vorgehen entspricht dem Vorgehen der Stadtwahl beim Ameisen-Zyklus-Algorithmus.

Aufbauend auf Ant-Q wurde 1996 das Ameisen-Kolonie-System („ant colony system“, ACS) entwickelt und stellt im Grunde eine Vereinfachung von Ant-Q dar (vgl. Gambardella/Dorigo (1996)). Wie auch bei Ant-Q benutzt eine Ameise zunächst den besten Pfad von Stadt i zu Stadt j mit einer konstanten Wahrscheinlichkeit q₀ anhand der „pseudo-random-proportional action choice“ Regel (2.9) (vgl. Gambardella/Dorigo (1996), Botee/Bonabeau (1998)).

Es hat sich gezeigt, dass die Kanten, die zur besten Tour gehören, zu 90% wieder gewählt werden und bei der Erkundung neuer Wege die Kanten bevorzugt werden, die innerhalb der zwei letzten Iterationen zur besten Tour gehörten (vgl. Dorigo/Gambardella (1996c)).

Wie auch bei Ant-Q gibt es eine Aufteilung der Aktualisierung der Spurenintensität in eine lokale und eine globale Berechnung, die in Dorigo/Di Caro (1999) auch als „online delayed pheromone update“ und „offline pheromone update“ bezeichnet wird. Während eines Zyklus „verdunstet“ die Spur nach jedem Schritt einer Ameise, um nachfolgende Ameisen dazu zu veranlassen, noch nicht benutzte Pfade zu testen. Die Aktualisierung der Pheromonspur auf jeder benutzten Kante errechnet sich dann durch die Formel (2.11) (vgl. Dorigo/Gambardella (1996c), Stützle/Dorigo (1999)):

  _(2.11)

Der Parameter r_l gibt die Spurenstärke für die lokale Aktualisierung an. Je öfter eine Ameise nun die Kante (i,j) benutzt, desto weniger Pheromon hinterlässt sie im Laufe der Zeit im Vergleich zum Ameisen-Zyklus-Algorithmus. Dadurch wird der Pfad für die anderen Ameisen immer unattraktiver, so dass neue noch nicht benutze Wege gesucht werden. Der einzige grundlegende Unterschied zu Ant-Q ist die Bestimmung von Dt_ij.

Der Wert für Dt_ij kann nach Dorigo/Gambardella (1996c) auf drei verschiedene Arten bestimmt werden:

• 
  In Anlehnung zu Ant-Q soll im Laufe der Zeit ein Lerneffekt. Daher kann Dt_ij durch Formel (2.12) berechnet werden:
      _(2.12)
  
• 
  Dt_ij wird auf t₀ gesetzt, wobei t₀ der Ausgangswert der Spurenstärke für die Kante (i,j) ist.
  
• 
  Dt_ij wird auf 0 gesetzt. Allerdings zeigten Experimente in Dorigo/Gambardella (1996c), dass diese Alternative die schlechteste sei.
  

In der Regel wird beim Ameisen-Kolonie-System Dt_ij=t₀ gesetzt.

Am Ende kommt es zu einer Verstärkung der Spur auf dem global besten Weg. Hier darf nur die beste Ameise mit der kürzesten Tour Pheromone abgeben:

  _(2.13)

mit

L^* kann wie auch bei Ant-Q die global- oder die iterativ beste Tour sein. Experimente in Dorigo/Gambardella (1996c) haben, anders als bei Ant-Q, gezeigt, dass die Verwendung der global besten Lösung zu minimal besseren Ergebnissen führt.

Um Rechenzeit beim Durchlauf zu sparen, kann man auch hier von einer Kandidatenliste Gebrauch machen, in der eine vorgegebene Anzahl der nächsten Städte zu jeder Stadt i steht (vgl. Gambardella/Dorigo (1996), Dorigo/Gambardella (1996c)).

In Dorigo/Gambardella (1996c) wurden zwei Experimente an der Instanz CCAO durchgeführt, um den Effekt der Kooperation der Ameisen beim Ameisen-Kolonie-System zu testen. Bei beiden Experimenten wurden kooperative mit nicht-kooperativen Ameisen verglichen. Die nicht-kooperativen Ameisen wurden „blind“ gemacht, indem die lokale und globale Spurenverstärkung (Formel (2.11) und (2.13)) deaktiviert wurde und Dt_ij=t₀=1 gesetzt wurde.

Im ersten Experiment lief der Algorithmus 10.000 Mal, und es wurde die Zeit gemessen, in der zum ersten Mal die optimale Lösung gefunden wurde. Danach wurde die Wahrscheinlichkeits-Verteilung der Zeit errechnet, die benötigt wurde, um die optimale Lösung zu finden. Wenn z. B. bei 100 Versuchen das Optimum nach genau 220 Iterationen gefunden wurde, ergibt das eine Wahrscheinlichkeit von P(220)=100/10.000. Die Anzahl der Ameisen betrug m=4. Das Ergebnis dieses Experiments ist in der Abbildung 2.3 zusammengefasst:

Dichte der Wahrscheinlichkeit

Zeit (in Sekunden)

kooperative Ameisen

nicht-kooperative  Ameisen 

Abbildung 2.3: Zeit, in der kooperative bzw. nicht-kooperative Ameisen das Optimum finden (aus Dorigo/Gambardella (1996c), Seite 11)

Im zweiten Experiment wurde die beste Lösung als eine Funktion der Zeit in Millisekunden (ms) gemessen. Die  Anzahl der Ameisen wurde wieder auf m=4 festgesetzt und der Durchschnitt von 25 Durchläufen gemessen. Während die kooperativen Ameisen die optimale Lösung stets nach 300 ms erreichten, konnten die nicht-kooperativen Ameisen selbst nach 800 ms das Optimum nicht finden. In den ersten 150 ms waren die Lösungen der nicht-kooperierenden Ameisen besser. Doch dann wurden sie durch den Lerneffekt der kooperativen Ameisen überboten, der durch die Spurenverstärkung kam. Dieser Effekt ist in Abbildung 2.4 gut zu sehen:

Länge der Touren

kooperative Ameisen

nicht-kooperative Ameisen 

Zeit (Millisekunden)

Abbildung 2.4: Kooperative Ameisen finden bessere Lösungen in kürzerer Zeit (aus Dorigo/Gambardella (1996c), Seite 11)

In Li/Gong (2003) wird ein dynamisches Ameisen-Kolonie-System („dynamic ant colony system“) beschrieben. Die Besonderheit besteht im wesentlichen in einem dynamischen Pheromon-Verdunstungs-Faktor. Aber auch die Parameter a und b, die bei der Wahl der nächsten Stadt entscheidend sind, können während eines gesamten Durchlaufs verändert werden.

In der Natur verdunsten Spuren schneller, wenn sie intensiver sind. Daran angelehnt lässt sich die Verdunstung mit der Formel (2.14) beschreiben:

  _(2.14)

Die Spurenstärke wird nun durch die Funktion _{ausgedrückt. Wenn jetzt nur die beste Tour verstärkt und eine spezielle Funktion für die Spurenstärke gewählt wird, befindet man sich wieder im MAX-MIN-Algorithmus. Somit kann man das MAX-MIN-Ameisen-System als eine Art Sonderfall dieses Algorithmus betrachten.}

Durch die Funktion g_ij können gute Lösungen schneller gefunden werden. Die Funktion g_ij ist definiert durch:

  _(2.15)

Nun werden die Spurenstärken der besten und der schlechtesten Tour aktualisiert, wobei die Spuren der besten Tour um einen festen Wert c verstärkt und die Spuren der schlechtesten Tour um c verringert werden.

Experimente in Li/Gong (2003) haben gezeigt, dass diese Modifikation bessere Ergebnisse liefert als das Ameisen-Kolonie- und das MAX-MIN-Ameisen-System.

In Stützle/Hoos (1997b) wird die Regel zur Lösungskonstruktion für das MAX-MIN-Ameisen-System so modifiziert, wie sie bei Ant-Q oder beim Ameisen-Kolonie-Algorithmus angewandt wird (vgl. Formel 2.16), um schneller Lösungen von hoher Qualität zu erhalten, wobei die Gesamtlösung am Ende eher schlechter ist  (vgl. Stützle/Dorigo (1999b)).

Bei einem hohen Wert für q₀ in Formel (2.9) müssen die Werte für t^min und t^max enger beieinander liegen. Denn für hohe q₀-Werte wird fast immer die best-mögliche Wahl getroffen, da mit der Wahrscheinlichkeit q₀ der Weg mit maximalem _{-Wert gewählt wird. Dies ist ebenso für einen kleineren q0-Wert der Fall, wenn der Unterschied zwischen t^min und t^max sehr groß ist, da auch für den Fall q>q0 der Pfad mit dem größten Wert für mit einer recht hohen Wahrscheinlichkeit gewählt wird. Dadurch kann eine Erkundung neuer Wege kaum zustande kommen.}

Um dennoch eine ausgewogene Mischung aus Zurückgreifen auf bestehende Daten und Erkundung neuer Wege zu bekommen, schlagen Stützle und Hoos vor, den Wert für t^max durch einen zu bestimmenden Faktor f zu beschränken:

t^max=c*t^min  (2.16)

Bei Experimenten in Stützle/Hoos (1997b) wurde der Faktor c=5 gesetzt.

2.3 Ameisen-System mit unterschiedlichen Ameisen

Die Idee hinter dieser Erweiterung ist, dass man Ameisen mit verschiedenen Fähigkeiten hat. In erster Linie sind diese besonderen Fähigkeiten einiger Ameisen im Bereich der Spurenverstärkung zu finden. Dabei werden einige (bzw. die besten) Ameisen bevorzugt und dürfen ihre Spuren mehr verstärken als andere. Beim rekrutierenden Ameisen-System hat man zwei Typen von Ameisen, die unterschiedliche Aufgaben haben.

Das Ameisen-System mit elitärer Strategie (AS_elite) ist eine Anlehnung an Genetische Algorithmen, in denen ebenfalls elitäre Strategien angewandt werden (vgl. Dorigo (1991a)). Die Idee dieser Strategie liegt darin, dass nach jedem Zyklus die Spur auf der bisher besten Tour stärker als beim Ameisen-Zyklus-System verstärkt wird. Somit soll die Suche aller anderen Ameisen zu einer Lösung führen, die aus einigen Kanten dieser besten Tour besteht (vgl. Bullnheimer et al. (1997)).

Dabei wird jede Kante der besten Tour wie folgt verstärkt:

  _(2.17)

mit

und

und

Die beste Route wird nun zusätzlich um einen Faktor _{verstärkt. Der Parameter e bezeichnet dabei die Anzahl der Elite-Ameisen, also der Ameisen, die auf dem besten Pfad gelaufen sind. Gibt es nur eine beste Ameise, wird nur der Pfad dieser einen Elite-Ameise verstärkt. Q ist eine Konstante, L^gb die Länge der global besten Lösung und Lk die Länge der Tour der k-ten Ameise.}

Mit dieser elitären Strategie kann jedoch das Verweilen in suboptimalen Lösungen nicht überwunden werden.

In Dorigo (1991a) wurde die Instanz Oliver30 mit 2500 Zyklen durchgeführt. Bei jedem Versuch gab es fünf Durchläufe. Es ergab sich ein optimaler Wert für die Anzahl an elitären Ameisen, wie Abbildung 2.5 zeigt:

Anzahl e an elitären Ameisen

Anzahl an Zyklen um das lokale Optimum zu erreichen

lokale Optima:

Abbildung 2.5: Anzahl der Zyklen, um ein lokales Optimum zu erreichen mit verschiedener Anzahl an elitären Ameisen (aus Dorigo et al. (1991), Seite 15)

Im Bereich 2<e<16 liegt die kürzeste gefundene Route (lokales Optimum) unter den besten Routen anderer Versuche. Bei den Versuchen mit elitären Ameisen konnte das lokale Optimum mit einer Länge von 423,74 am schnellsten mit 8 elitären Ameisen gefunden werden.

Generell haben Tests gezeigt, dass für e=n=m gute Ergebnisse erzielt werden können, wenn also genauso viele elitäre Ameisen wie Städte eingesetzt werden (vgl. Bullnheimer et al. (1997a)).

Ähnlich zum Ameisen-System mit elitärer Strategie ist das Rang-basierte Ameisen-System (AS_rank). Bei diesem System werden alle Ameisen anhand ihrer Tourlängen sortiert, die sie generiert haben (vgl. Bullnheimer et al. (1997a)). Die Menge der Pheromonverstärkung ist dann proportional zum Rang r der Ameisen. Allerdings dürfen nur die w besten (elitären) Ameisen ihre Spur verstärken. Der Parameter w wird vorher festgelegt.

Die Verstärkung der Spurenintensität lässt sich demnach nach der Formel (2.18) berechnen:

  _(2.18)

mit

und

Die global beste Lösung L^gb erhält das Gewicht w. Den (w-1) besten Touren wird, je nach ihrem Rang r in der Ordnung, ein Gewicht durch max{0,w-r} zugewiesen. L_r ist die Länge der r-ten Ameise.

Ein Vergleich mit konventionellen Ameisensystemen zeigt, dass mit diesem neuen Ansatz im Durchschnitt geringfügig bessere, im besten Fall sogar erheblich bessere Ergebnisse erreicht werden können (vgl. Stützle/Dorigo (1999)).

Ein interessanter weiterer Ansatz für Ameisen-Systeme mit unterschiedlichen Ameisen stellt das rekrutierende Ameisen-Kolonie-System dar, das auch in ähnlicher Form in der Natur vorkommt (vgl. Bonabeau/Meyer (2001), Seite 45f). Es hat einige Gemeinsamkeiten mit AS_elite und AS_rank. Allerdings wird das Ameisen-System nun um eine Rekrutierungsstrategie erweitert (vgl. Stamer (2003)).

Unter einer Rekrutierung ist in diesem Zusammenhang das Animieren einer Ameise zu einem bestimmten Verhalten zu verstehen (vgl. Stamer (2001)). So kann eine Ameise von einer anderen Ameise beispielsweise dazu motiviert werden, zu einer Futterstelle auf einem bestimmten Weg zu gehen. Bei einem sogenannten Tandemlauf wird eine Ameise dazu animiert, einer anderen zu einer Futterquelle zu folgen.

In diesem Algorithmus existieren zwei Ameisentypen mit unterschiedlichen Aufgaben:

• 
  m⁰ Suchameisen durchsuchen die Umgebung nach Futter
  
• 
  m¹ Transportameisen warten zunächst im Nest und helfen beim Transport der Nahrung, sobald eine Futterquelle gefunden wurde. Dabei folgen sie mit hoher Wahrscheinlichkeit den Wegen der Suchameisen anhand der Pheromonspur.
  

Es gibt wesentlich mehr Transport- als Suchameisen.

Der Algorithmus wird in zwei Phasen eingeteilt. In der ersten Phase konstruieren die m⁰ Suchameisen Lösungen anhand ihrer Speicher M_k⁰ und der „pseudo-random-proportional action choice rule“ (Formel (2.9)) wie beim Ameisen-Kolonie-Algorithmus (vgl. Stamer(2003)). Die Spurenverstärkung verläuft ebenso wie beim Ameisen-Kolonie-Algorithmus nach Formel (2.11) und (2.13).

Danach werden m¹ Transportameisen rekrutiert für die Wege der r₀ iterations-besten Ameisen. Die Transportameisen werden zufällig in eine Stadt gesetzt und konstruieren neue Touren, indem sie sich an ihrem Speicher M_k¹ und drei möglichen Auswahlmöglichkeiten in Formel (2.19) für die nächste Stadt orientieren. Man hat nun zwei Wahrscheinlichkeits-Parameter q₀ und r₀.

  _(2.19)

Wenn die Transportameisen bei der Konstruktion der neuen Touren bessere Lösungen finden, wird die neue beste Lösung wie beim Ameisen-Kolonie-Algorithmus nach Formel (2.13) zusätzlich global verstärkt.

Wegen der Einteilung der Ameisen in zwei Phasen, entsteht ein neuer formaler Algorithmus (vgl. Stamer (2001), Stamer (2003)):

1.  Initialisierung
Setze einheitliche Startwerte für t_ij;
Verteile m₀ Suchameisen zufällig auf die Städte;
Setze t:= 0 und NC:=0 (t ist Zeitzähler und NC ist Zyklenzähler);

2.  Konstruktion m⁰
für k=1 bis m
wiederhole, bis M_k^S voll {
wähle mit Wahrscheinlichkeit p_ij nach Formel (2.19) eine Stadt j aus, die als nächste besucht werden soll;
Berechne die Gesamtlänge L_k von der k-ten Suchameise;

3.  Spurenverstärkung m⁰
Setze die neue Pheromonintensität t_ij für alle Verbindungen;
rekrutiere jeweils r₁ Transportameisen für die r₀ besten“ Suchameisen}

4.  Konstruktion m¹
für k=1 bis m₀*m₁
wähle einen beliebigen Startpunkt;
wiederhole, bis M_k^T voll {
wähle mit Wahrscheinlichkeit q₁ die vorgegebene Route,
sonst wähle nach Formel (2.19) eine Stadt j aus, die als nächste besucht werden soll und fahre im weiteren Verlauf immer gemäß (2.19) fort;

5.  Spurenverstärkung m¹
Berechne die Gesamtlänge L_k. der k-ten Transportameise;
Setze die neue Pheromonintensität t_ij für alle Verbindungen}

6.  Lasse alle Ameisen zum Nest zurückkehren.

Der Wahrscheinlichkeits-Wert q₁ für die Wegwahl der Transportmeisen wird vorgegeben.

Dieser Algorithmus scheint recht aufwendig und zeitintensiv zu sein.

2.4 Parallelisierung

Es gibt verschiedene Ansätze, wie man Ameisen-Algorithmen parallelisieren kann. Dies hängt vor allem von der verfügbaren Rechenplattform und dem entsprechenden Algorithmus ab. In begrenztem Umfang steigt die Zeitersparnis linear zur Anzahl der eingesetzten Rechner (vgl. Colorni (1992a)). Im wesentlichen trägt eine Parallelisierung aber dazu bei, Stagnation zu vermeiden oder zumindest einzugrenzen.

Nach Stützle (1998b) liegt der einfachste Weg der Parallelisierung darin, einzelne Ameisen auf separate Ressourcen aufzuteilen. Jedoch ist eine Aufteilung in unabhängige Durchläufe nur brauchbar, wenn der Suchprozess einer zufälligen Entscheidung unterliegt. Zu den parallelisierbaren Algorithmen gehören Ameisen-Kolonie-Optimierung („ant colony optimizing“, ACO) und MAX-MIN-Ameisen-System, da der Prozess der Tourenkonstruktion stark zufallsbedingt ist.

In Dorigo/Di Caro (1999) werden drei Typen von Parallelisierung unterschieden:

• 
  Parallelisierung auf der Ebene der Ameisen
  
• 
  Parallelisierung auf der Ebene der Daten
  
• 
  funktionale Parallelisierung
  

Die häufigste Form der Parallelisierung findet auf der Ebene der Ameisen statt. Es werden mehrere Ameisen-Kolonien mit dem Lösen der gleichen Problem-Instanz beauftragt. Es wird festgelegt, ob die Kolonien zum Datenabgleich miteinander kommunizieren können.

Eine Parallelisierung auf der Ebene der Daten bedeutet zunächst eine Aufteilung des Hauptproblems in mehrere Unterprobleme. Diese werden dann von einzelnen Ameisen-Kolonien separat gelöst.

Die dritte Möglichkeit, eine funktionale Parallelisierung, kann auch in Kombination mit einer der beiden anderen Arten der Parallelisierung durchgeführt werden. Die Abläufe der Tourenkonstruktion, Verdunstung der Spuren und globale Verstärkung werden dann gleichzeitig durchgeführt, mit einem möglichen Datenabgleich.

Ein interessanter Punkt ist die Übergabe der Information über die Spurenstärken zwischen den einzelnen Kolonien. Krüger, Merkle und Middendorf schlagen für den Datenabgleich folgende Möglichkeit vor (vgl. Dorigo/Di Caro (1999)):

• 
  Der Austausch der global besten Lösung findet statt, indem jede Subkolonie die global beste Tour aller Subkolonien für die Spurenverstärkung benutzt.
  
• 
  Die lokal beste Lösung ergibt sich aus der besten lokalen Tour aller Subkolonien.
  
• 
  Die Informationen über die Spurenstärken für die einzelnen Wege werden als Durchschnittswerte der Spurenstärken aller Kolonien berechnet.
  

Durch die Parallelisierung kann das ursprüngliche Problem mit vielen Ameisen und vielen Iterationen in kleinere Probleme mit jeweils weniger Ameisen und weniger Iterationen aufgeteilt werden. Zunächst scheint dies eine Ersparnis von Aufwand und Zeit zu sein. Jedoch ist nach der Berechnung der Lösung für jede Ameise auch wiederum ein Abgleich untereinander oder aber mit einer zentralen Ressource nötig (siehe Abbildung 2.6). Dies verbraucht Zeit und Kosten für die Kommunikation, selbst wenn die Kommunikation nahezu gleichzeitig von allen Ressourcen aus erfolgen kann. Zudem können die Ermittlungen der einzelnen Lösungen unterschiedlich lange brauchen. Dadurch wird die Gesamtzeit für jede Iteration immer auf die zeitlich längste Lösungsermittlung erhöht. Im Extremfall nimmt der Anteil an Wartezeit zusammen mit der Kommunikationszeit mehr Zeit in Anspruch als die durchschnittliche Rechenzeit. Ein solches Vorgehen bezeichnet man als synchron.

Dieses Problem kann umgangen werden, indem man innerhalb einer Ressource gleich mehrere Durchläufe ohne Abgleich mit anderen Ressourcen durchführt. Dadurch gleichen sich die Rechenzeiten im Durchschnitt untereinander an und die Kommunikation untereinander wird seltener vorgenommen. Dieses Vorgehen wird asynchron genannt. Zwar führt dieses Vorgehen zunächst zu einem erheblich verbesserten Anteil von Rechenzeit, Wartezeit und Kommunikationszeit, jedoch verschlechtert ein zu seltener Austausch die Güte der Lösung maßgeblich.

Abbildung 2.6: Synchrone und asynchrone Parallelisierung (aus Bullnheimer et al. (1998), Seite 5 und Talbi et al. (2001), Seite 5)

In Bullnheimer et al. (1998) wurde die synchrone der asynchronen Parallelisierung gegenübergestellt. Es hat sich in Versuchen gezeigt, dass der Prozess für alle getesteten Problemgrößen bei der asynchronen Parallelisierung stärker beschleunigt wird als bei der synchronen Parallelisierung. Da die Häufigkeit der Kommunikation bei der asynchronen Parallelisierung verringert wird, eignet sich dieses Verfahren gerade bei kleineren Problemen.

Statt einen Algorithmus mit einer bestimmten Parametereinstellung unabhängig auf k Prozessoren laufen zu lassen, bietet es sich auch an, einen Algorithmus mit verschiedenen Such-Strategien und unterschiedlichen Parametereinstellungen auf den Prozessoren zu modifizieren (vgl. Stützle (1998b)).

2.5 Zusammenstellung

Zusammenfassend kann man die in der Literatur besprochenen Ameisen-Algorithmen in der Abbildung 2.7 darstellen.

Abbildung 2.7: Übersicht über die verschiedenen Ameisen-Algorithmen

3. Betriebswirtschaftliche Anwendungen

In diesem Kapitel sollen Verfahren für weitere Probleme aus dem Bereich der kombinatorischen Optimierung beschrieben werden, bei denen Ameisen-Algorithmen zum Einsatz kommen können.

Aus dem Bereich der Produktion und Logistik werden nun in erster Linie Rundreisen- und Touren-, Zuordnungs- und Reihenfolgeprobleme betrachtet. Unter diese drei Kategorien fallen einige Probleme, die in Abbildung 3.1 aufgelistet sind.

Abbildung 3.1: Behandelte Probleme aus der kombinatorischen Optimierung

Nach Matthäus (1978) sind die meisten Probleme der Tourenplanung wie das Vehicle Routing Problem eine Kombination aus Zuordnungsproblem und Reihenfolgeproblem (vgl. Matthäus (1978), Seite 15). Als Beispiel könnte man eine Spedition nennen, die ein bestimmtes Gut mit einer Anzahl an Fahrzeugen zu mehreren Kunden transportiert. Die Nachfragemenge der Kunden ist insgesamt größer als die Kapazität eines Fahrzeugs. Demnach muss man die Kunden Gruppen zuordnen, um sie mit mehreren Touren anzufahren. Da die Fahrzeuge auf längeren Strecken mehr Kosten verursachen als auf kürzeren (z. B. durch Benzinverbrauch), will man die Längen der Touren minimieren (wie beim Travelling Salesman Problem). Eine Tour mit minimaler Länge erhält man, indem man eine Reihenfolge der Kunden findet, durch die eine kürzeste Tour gebildet wird.

3.1 Rundreisen- und Tourenprobleme

Das Gebiet der Rundreisen- und Tourenplanung ist sehr groß. In diesem Abschnitt sollen daher nur einige weitere Aspekte angesprochen werden. Da Ameisen-Algorithmen für das euklidische Travelling Salesman Problem bereits im 2. Kapital besprochen wurden, soll auf Algorithmen für Varianten des Travelling Salesman Problems wie ein dynamisches Modell eingegangen werden.

Das Tourenplanungsproblem, das sich hauptsächlich durch eine Kapazitätseinschränkung vom Travelling Salesman Problem unterscheidet, wird im Abschnitt 3.2 beschrieben. Es werden Algorithmen gezeigt für Instanzen des Vehicle Routing Problems mit Zeitfenstern wie auch mit tageszeitlich bedingten Geschwindigkeitsbeschränkungen.

3.1.1 Travelling Salesman Problem

Im 2. Kapital wurde insbesondere auf das symmetrische Travelling Salesman Problem als statisches Modell eingegangen. Das asymmetrische Travelling Salesman Problem unterscheidet sich von der Form her kaum vom symmetrischen. Lediglich die Entfernungen zwischen einer Stadt i zu einer Stadt j sind nun nicht mehr identisch. Ansonsten erhöht sich der Rechenaufwand, und das Optimum kann nur noch für Instanzen gefunden werden, die wenige Dutzend Knoten haben (vgl. Dorigo et al. (1996)).

Im Vergleich zum statischen Modell, liegt die Besonderheit beim dynamischen Travelling Salesman Problem darin, dass einzelne Städte zwischenzeitlich entfernt oder zur Instanz hinzugefügt werden können (vgl. Guntsch et al. (2001)). In der Praxis findet man solche Probleme zum Beispiel, wenn Straßen gesperrt oder neue Brücken errichtet werden.

Wenn die Veränderung im Vergleich zum vorangegangenen Zeitpunkt nur gering ist, sollten die bestehenden Informationen über optimale Pfade erhalten bleiben, da der neue optimale Weg dem vorherigen sehr ähnlich sein kann.

Ein möglicher Algorithmus, der für das

dynamische Travelling Salesman Problem

geeignet erscheint, ist das

Ameisen-System mit elitärer Strategie

. Eine elitäre Ameise verstärkt nach jeder Iteration die bislang beste gefundene Lösung. Nach einer Veränderung der Städte ist die alte beste Lösung möglicherweise nicht mehr gültig und wird daher zu einer gültigen Lösung modifiziert, die dann zumindest eine gute Lösung für die neue Instanz darstellt.

In Guntsch et al. (2001) werden drei Strategien aufgezeigt, wie man die Pheromonwerte verändern kann, um den Einfluss der Erfahrungen zu reduzieren und auf die neue Instanz anzugleichen:

• 
  Neustart-Strategie: Alle Pheromonwerte werden bei dieser globalen Strategie auf einen gleichen Faktor neu gesetzt. Normalerweise gibt es die stärkste Veränderung der Spurenstärken in der Umgebung, in der eine Stadt eingefügt oder entfernt wurde.
  
• 
  h-Strategie: Diese eher lokal-orientierte Strategie benutzt heuristisch basierte Informationen, hier also die Entfernung zwischen den Städten, um den Faktor festzulegen, mit dem die Pheromonstärke auf den Kanten verändert wird, die zu einer eingefügten oder entfernten Stadt j führen.
  
• 
  t-Strategie: Mit Hilfe der vorhandenen Pheromonwerte wird eine Art „Nähe“ zwischen den Städten bestimmt. Die „näheren“ Städte, auf deren Weg zu einer Stadt j also am meisten Pheromon lag, werden nun am stärksten angeglichen.
  

Alle drei Strategien benötigen für die Angleichung der Pheromonwerte einen Faktor j_i Î [0,1], mit dessen Hilfe die Spuren, die zu einem Knoten i führen,  nach Formel 3.1 modifiziert werden:

  _(3.1)

Beim symmetrischen euklidischen Travelling Salesman Problem würde man als Faktor den Durchschnitt der Faktoren j_i und j_j, also (j_i+j_j)/2, statt j_i wählen. Eine eingefügte Stadt i erhält immer den Faktor j_i=1.

3.1.2 Vehicle Routing Problem

Beim Vehicle Routing Problem (VRP) werden Zeit und Kosten minimiert, wobei eine Anzahl an Fahrzeugen Fracht von einem Depot zu einer Anzahl an Kunden bringt und schließlich wieder zum Depot zurückkehren soll. Dabei darf jeder Kunde nur genau einmal von genau einem Fahrzeug beliefert werden, die gesamte Nachfrage einer Tour darf die Kapazität des Fahrzeugs nicht übersteigen und die gesamte Länge der Tour (inklusive einer eventuellen Service-Zeit) darf  bei keinem Fahrzeug die gegebene Obergrenze L überschreiten.

Das Problem kann durch einen gerichteten Graph G=(V,A,d) beschrieben werden, wobei V={v₀, v₁, ..., v_n} eine Menge an Knoten und A={(v_i,v_j):i¹j} eine Menge an Kanten ist. Der Knoten v₀ ist das Depot, die übrigen Knoten von V markieren die Städte bzw. Kunden. Jede Kante ist mit dem Wert d_ij gewichtet, also mit der Entfernung (bzw. Reisezeit oder Reisekosten) zwischen Knoten i und Knoten j. Jeder Kunde in v_i hat eine Nachfrage k_i (mit k₀=0), die befriedigt werden muss.

Beim Vehicle Routing Problem können mehrere Ziele betrachtet werden (vgl. Gambardella et al. (1999)): Zunächst soll die Anzahl an Touren (oder eingesetzten Fahrzeugen) minimiert werden, schließlich die Gesamtdauer der Fahrten. Eine Lösung mit weniger Touren wird einer Lösung mit mehr Touren stets vorgezogen, auch wenn die Gesamtdauer der Fahrten der Tour höher ist.

Das Ameisen-System wird 1997 als erster Ameisen-Algorithmus verwendet, um Instanzen vom Vehicle Routing Problem zu lösen (vgl. Bullnheimer et al. (1997b), Bullnheimer et al. (1997c)). Um eine Instanz des Vehicle Routing Problems zu lösen, konstruieren die künstlichen Ameisen Routen, indem sie noch nicht besuchte Städte auswählen. Eine neue Stadt kann nur dann gewählt werden, wenn die maximal erlaubte Streckenlänge oder die Kapazität des jeweiligen Fahrzeugs nicht überschritten wird. Sonst muss das Fahrzeug wieder ins Depot zurückkehren und eine neue Route konstruieren, bis alle Städte besucht wurden. Für die Wahl einer neuen Stadt sind die Spurenstärke t_ij auf der Kante (v_i,v_j) und die Stärke der Sichtbarkeit h_ij (mit h_ij=1/d_ij) entscheidend.

Im Vergleich zum Travelling Salesman Problem ist beim Vehicle Routing Problem nicht nur die Entfernung zwischen den Knoten v_i und v_j wichtig, sondern auch die Entfernung von Knoten v_i bzw. v_j zum Depot v₀ (vgl. Bullnheimer et al. (1997c)). Die Qualität einer Tour kann durch die Höhe der „Savings“-Werte m_ij bestimmt werden. Diese ergeben sich wiederum durch Formel (3.2):

m_ij=d_i0+d_0j-d_ij   (3.2)

Je höher die „Savings“-Werte sind, desto besser ist es, vom Knoten v_i direkt zum Knoten v_j zu gehen, anstatt über das Depot v₀ dorthin zu gelangen.

Ebenso sollte die beschränkte Kapazität, die jedem Fahrzeug auf einer Tour zur Verfügung steht, voll ausgenutzt werden. Mit K_i als gesamter Nachfrage einer Tour, inklusive der Nachfrage für den Kunden v_i, sollte die Kapazitätsauslastung k_ij möglichst groß sein. Die Kapazitätsauslastung ergibt sich durch k_ij=(K_i+k_j)/K.

Mit diesen beiden neuen Kriterien kann eine neue Wahrscheinlichkeitsformel (3.3) aufgestellt werden, anhand derer der Kunde v_j nach dem Kunden v_i beliefert wird:

  _(3.3)

Die Menge W umfasst alle möglichen Städte, die noch auf der gleichen Tour besucht werden können, mit W={v_j Î V: v_j kann noch besucht werden} Ç {v₀}. Der Parameter c gibt den Einfluss des „Savings“-Wertes auf die Wahl der nächsten Stadt an, während der Parameter d den Einfluss der Kapazitätsauslastung regelt.

Nachdem eine Ameise k eine mögliche Lösung konstruiert hat, wird die Pheromonspur auf allen benutzten Kanten (v_i,v_j) anhand der Formel (3.4) verstärkt.

  _(3.4)

mit

und

Dabei ist e die Anzahl an elitären Ameisen, die die bislang beste Lösung gefunden haben. L^gb ist die Länge der global besten Tour.

In Bullnheimer et al. (1997b) wird vorgeschlagen, die Sichtbarkeit mit Hilfe von zwei Parametern c₁ und c₂ in Anlehnung an den Savings-Algorithmus zu errechnen. Dadurch ergibt sich die Formel (3.5):

h_ij = d_i0 + d_0j – c₁d_ij + c₂|d_i0 – d_0j|  (3.5)

Die Stadt v_j wird nach dann der zufalls-proportionalen Formel (3.6) gewählt:

  _(3.6)

Ebenso wird vorgeschlagen, dass nicht alle Ameisen ihre Spur verstärken, sondern nur noch die w besten Ameisen (wie beim Rang-basierten Ameisen-System). Zuvor werden alle Ameisen nach der Länge ihrer gefundenen Tour sortiert und einem Rang r zugewiesen. Zusätzlich wird die Spur der besten (Elite-)Ameise wie zuvor verstärkt.

Die Spurenverstärkung ergibt sich dann nach der Formel (3.7):

  _(3.7)

mit

und

Nachdem die Routen konstruiert und die Spuren verstärkt wurden, kann zusätzlich eine lokale Suche stattfinden, um die bislang gefundene Lösung noch zu verbessern. In Bullnheimer et al. (1997b) wird zur lokalen Suche eine 2-opt-Heuristik verwendet, die sich an den Sweep-Algorithmus (vgl. Gillett, Miller (1974)) anlehnt. Eine Tour ist demnach 2-optimal, wenn sich durch Vertauschen von zwei Kanten keine bessere Tour ergibt.

Das Vehicle Routing Problem kann noch weiter modifiziert  werden, etwa durch die Einführung von Zeitfenstern. Bei den Zeitfenstern handelt es sich um eine gegebene Zeitperiode [b_i, e_i] für jeden Knoten v_i (i=0,...,n), innerhalb derer jeder Kunde beliefert werden muss. Der Wert b_i bezeichnet den Anfangszeitpunkt und e_i den Endzeitpunkt des Zeitfensters. Die Werte für das Depot bedeuten, dass für jedes Fahrzeug b₀ der früheste Startzeitpunkt vom und e₀ der späteste Rückkehrzeitpunkt zum Depot ist.

Die Touren werden von q Fahrzeugen durchgeführt. Die Zusatzbedingungen sind, dass die Belieferungsanfangszeit für jeden Knoten v_i (i=1,...,n) mindestens genauso groß sein muss wie b_i und die Ankunftszeit an jedem Knoten v_i nicht später sein darf als e_i. Sollte das Fahrzeug vor dem Zeitpunkt b_i am Kunden v_i ankommen, muss das Fahrzeug bis zum Beginn des Zeitfensters des Kunden warten, bevor es mit der Belieferung beginnen kann.

Eine Möglichkeit, Instanzen dieses Problems zu lösen, wurde mit dem multiplen Ameisen-Kolonie-System in Gambardella et al. (1999) beschrieben. Beim multiplen Ameisen-Kolonie-System nimmt man zwei künstliche Ameisen-Kolonien, um sowohl die Anzahl an eingesetzten Fahrzeugen q wie auch die gesamte Fahrzeit zu minimieren. Das Zusammenspiel der einzelnen Ebenen lässt sich gut mit der Abbildung 3.2 verdeutlichen:

Multiples ACS - VRP mit Zeitfenstern

Abbildung 3.2: Konstruktion des multiplen Ameisen-Kolonie-Systems für das VRP mit Zeitfenstern (aus Gambardella et al. (1999) S. 6)

Das multiple Ameisen-Kolonie-System dient hier als Verbesserungsverfahren, dem das Eröffnungsverfahren der „nearest neighbour“ Heuristik vorausgeht.

Der zugehörige Algorithmus kann wie folgt beschrieben werden (vgl. Gambardella et al. (1999)):

1.  Initialisierung
Setze L^gb als mögliche Startlösung mit Hilfe einer „nearest neighbour“ Heuristik;

2.  Durchführung
Wiederhole {
  q ß q(L^gb);
  starte ACS-Fahrzeuge(q-1);
  starte ACS-Zeit(q);
  wenn L aus ACS-Fahrzeuge oder ACS-Zeit besser ist als L^gb
  setze L^gb ß L;
  wenn q(L^gb) < q
  lösche ACS-Zeit und ACS-Fahrzeuge;
Wenn Abbruchkriterium nicht erfüllt gehe zu 2.
sonst gib L^gb aus und stoppe}.

Die Startlösung für L^gb wird mit einer „nearest neighbour“ Heuristik ermittelt. Bei dieser Heuristik startet man zunächst in einem Knoten und sucht sich den Knoten, der noch nicht besucht wurde und der die kürzeste Entfernung zum aktuellen Knoten hat, bis alle Knoten besucht wurden und man wieder zum Startknoten zurückkehrt (vgl. Kindvater et al. (1989)). Die beiden Ameisen-Kolonie-Systeme laufen im gesamten Algorithmus nahezu parallel. Die Kolonie „ACS-Fahrzeuge“ versucht, die maximale Anzahl an besuchten Kunden zu finden mit einem Fahrzeug weniger als in der vorangegangenen Lösung. Es entstehen zwei Lösungen: zum einen startet das System mit einer möglichen Lösung mit der Anzahl an Fahrzeugen aus L^gb, zum anderen bekommt man ungültige Lösungen, in denen Kunden nicht besucht wurden. Eine ungültige Lösung, in der die meisten Kunden besucht wurden, wird als L^max ebenfalls gespeichert. Bei der Kolonie „ACS-Zeit“ wird lediglich die Fahrzeit mit der gleichen Anzahl an Fahrzeugen wie bei L^gb minimiert.

In beiden Kolonien geht jede Ameise k nach dem gleichen Algorithmus vor (etwa wie beim Ameisen-Kolonie-Algorithmus für das Travelling Salesman Problem). Sie sucht nach gültigen Touren, wobei für die Wahl des nächsten noch nicht besuchten Knoten berücksichtigt wird, dass man diesen innerhalb des vorgegebenen Zeitfensters erreicht. Wenn alle k Ameisen ihre Touren konstruiert haben, findet bei der Kolonie „ACS-Zeit“ noch zusätzlich eine lokale Suche statt.

Die Spurenverstärkung der beiden Systeme erfolgt unabhängig voneinander. Bei der Kolonie „ACS-Zeit“ wird die Spur nach Formel (3.8) berechnet.

  _(3.8)

mit

Die Kolonie „ACS-Fahrzeuge“ hingegen aktualisiert die Spuren nach Formel (3.9):

  _(3.9)

mit

und

L^max und L^gb sind die Längen der Gesamtlösungen L^max bzw. L^gb. Die beste Lösung aus beiden Systemen wird übernommen und als global beste Länge L^gb des Algorithmus gespeichert. Wenn die Anzahl an Fahrzeugen dieser besseren Lösung unter der Anzahl an Fahrzeugen der bisher besten Lösung liegt, wird auch die Anzahl an zur Verfügung stehenden Fahrzeugen q aktualisiert. Die Längen der Touren werden dann bei beiden Algorithmen wieder gelöscht und der Algorithmus wird mit einem Fahrzeug weniger wiederholt, bis ein zuvor gegebenes Abbruchkriterium erfüllt ist.

Wie in Abschnitt 2.4 beschrieben, muss man hier einen geeigneten Mittelweg zwischen synchroner und asynchroner Parallelisierung finden, um die Rechenzeit möglichst gering zu halten und dennoch schnell gute Lösungen zu bekommen.

3.1.3 Dependent Vehicle Routing Problem

Eine weitere Variante des Vehicle Routing Problems stellt das Dependent Vehicle Routing System dar (vgl Malandraki/Daskin (1992)). Es berücksichtigt, dass die Reisezeit zwischen zwei Knoten von der Tageszeit abhängt, zu der das entsprechende Fahrzeug in Gebrauch ist. In der Praxis können äußere Einflüsse wie Stau oder vorübergehende Geschwindigkeitsbeschränkung zu einer Veränderung des Problems führen, so dass ein dynamisches Modell entsteht. Das Ziel ist es, die minimale Anzahl an Touren zu finden und die kürzeste absolute Fahrzeit zu berechnen. Diese wird durch die Abfahrtszeit und den Verlauf der Geschwindigkeit (s_ij(t)) auf der Kante berechnet.

Im Laufe eines Tages verändert sich die Geschwindigkeit auf den Kanten (vgl. Donati et al. (2002)). Zur Vereinfachung wird diese Veränderung für alle Kanten gleich berechnet. Ein Tagesablauf wird dann in mehrere Intervalle (Zeitabschnitte) eingeteilt, innerhalb derer die Fahrzeuge eine bestimmte Geschwindigkeit haben. In Abbildung 3.3 sind die Intervalle eingezeichnet; die Durchschnitts-Geschwindigkeit beträgt 1.0 Zeiteinheiten.

Geschwindigkeit  s_ij (in einer wählbaren Zeiteinheit)

Tageszeit

Abbildung 3.3: Verlauf der Geschwindigkeit (aus Donati et al. (2002), Seite 4)

Die Reisezeit hängt nun von der Geschwindigkeit in den einzelnen Intervallen ab. Die Entwicklung der Reisezeit ist in Abbildung 3.4 dargestellt, für den Fall, dass die Entfernung zwischen 2 Knoten 2 Längeneinheiten beträgt.

Reisezeit (d_ij*s_ij(t))

Tageszeit

Abbildung 3.4: Reisezeit für eine Kante der Länge 2 (aus Donati et al. (2002), Seite 5)

Zur Konstruktion einer Lösung mit Hilfe eines Ameisen-Kolonie-Systems steht in Anlehnung an Donati et al. (2002) die Formel (3.10) zur Verfügung, anhand derer ein nächster Kunde angefahren wird. Durch zwei vorgegebene Wahrscheinlichkeiten q₀ und r₀ gibt es insgesamt drei Möglichkeiten (greedy, wahrscheinlichkeitsbedingt, zufällig), nach der ein Knoten j in die Tour aufgenommen wird. In Donati et al. (2002) werden q₀=0.9 und r₀=0.02 als Werte für die Wahrscheinlichkeiten empfohlen.

  _(3.10)

Der Parameter z gibt den Zeitabschnitt an, der mit dem Zeitpunkt t übereinstimmt.

Der Wert für die Sichtbarkeit h_ij wird nun durch Formel (3.11) berechnet.

  _(3.11)

h_ij ist Null, wenn eine Ameise in einen Knoten j gehen möchte und dadurch eine Verletzung begehen würde. Eine Verletzung entsteht immer dann, wenn die Nachfrage von Knoten j an ein Fahrzeug höher ist als die Restkapazität dieses Fahrzeugs, die Ankunftszeit am Knoten j nach Verlassen zum Zeitpunkt t größer ist als das Ende des Zeitfensters vom Knoten j oder die maximal erlaubte Streckenlänge überschritten ist.

Das Produkt d_ij*s_ij(t) ist die Reisezeit zum Zeitpunkt t vom Knoten i zum Knoten j. t^w>0 ist die Wartezeit, die entsteht, wenn ein Fahrzeug vor Beginn des Zeitfensters von Knoten j ankommt. Je früher ein Fahrzeug an einem Knoten i ist, gemessen an der Differenz von Ende des Zeitfensters e_i und der Ankunftszeit am Knoten _{, desto attraktiver ist es, diesen Knoten in die Tour aufzunehmen.}

Nachdem alle Fahrzeuge gültige Lösungen konstruiert haben, werden die Spuren aller Kanten nach Formel (3.12) aktualisiert:

    (3.12)

mit

Die Konstante c wird in Donati et al. (2002) auf 10-100 gesetzt und der Faktor 1/L_k wird auch als „Fitness“ der k-ten Lösung bezeichnet. Je besser die Lösung ist, desto größer ist auch dieser Faktor.

Die beste Lösung wird gespeichert, und der gesamte Prozess endet, wenn eine vorgegebene Anzahl an Iterationen erreicht ist.

3.2 Zuordnungsprobleme

In diesem Abschnitt soll vor allem auf das Problem der innerbetrieblichen Standortplanung (Layoutplanung) eingegangen werden. Gründe für eine Layoutplanung können eine Neugestaltung einer Produktionsstätte, Umstellung oder Erweiterung sein. Bei der Neugestaltung liegt das Problem darin, für jedes Objekt (Maschine, Station, Anlage) einen günstigen Standort innerhalb einer vorgegebenen Fabrik oder Werkshalle zu finden, so dass „die insgesamt zu erbringende Transportleistung (ermittelt als Produkt aus Transportmenge und Transportstrecke) möglichst gering ist.“ (Günther/Tempelmeier (2003), Seite 81). Dieser Fall wird nun in erster Linie behandelt.

Als weitere Annahmen sind vorgegeben:

• 
  Potenzielle Standorte, die zur Vereinfachung alle gleich groß sind,
  
• 
  Entfernungen zwischen den potenziellen Standorten, gemessen als Luftlinienabstand oder als rechtwinklige Entfernung,
  
• 
  Transportmengen (Fluss) zwischen den Objekten,
  
• 
  Transportkosten pro Mengen- und Entfernungseinheit.
  

Ziel der Layoutplanung ist die Minimierung der Summe der Transport-, Lager- und Produktionskosten (vgl. Domschke/Drexl (1990)). Zudem können noch einige weitere Subziele verfolgt werden:

• 
  Minimierung der Transportleistung und der Transportkosten,
  
• 
  Minimierung der Zwischenlagerungskosten und der Durchlaufzeit,
  
• 
  Minimierung der Störanfälligkeit, Gewährleistung der Übersichtlichkeit,
  
• 
  Minimierung von Standortwechselkosten.
  

Wenn der Transportkostensatz für alle Transporte zwischen den einzelnen Objekten gleich ist, kann man einen Einheitstransportkostensatz pro Mengen- und Entfernungseinheit nehmen. Die gesamten Transportkosten ergeben sich dann aus dem Produkt von Transportmengen und Entfernungen zwischen den Objekten, multipliziert mit dem Einheitstransportkostensatz.

Im folgenden soll die Transportleistung minimiert werden, die sich als Produkt aus den Transportmengen und Entfernungen ergibt.

Das Modell lässt sich nun als quadratisches Zuordnungsproblem, auch Quadratic Assignment Problem (QAP) genannt, formulieren (vgl. Koopmans/Beckmann (1957), Finke et al. (1987), Morad (2000), Kistner (2003)):

Beim Quadratic Assignment Problem der Ordnung n sucht man die beste Zusammenstellung von n Objekten (Maschinen, Stationen, Anlagen) und n Orten. Zunächst soll die Anzahl an Orten gleich der Anzahl an Objekten sein, so dass man eine eindeutige Zuordnung erhält.

Gegeben sind drei Matrizen (vgl. Maniezzo et al. (1994)):

• 
  Eine Matrix der Entfernungen zwischen Ort i und h: D=[d_ih]
  
• 
  Eine Matrix des Flusses zwischen Objekt j und k: F=[f_jk]
  
• 
  Eine Matrix der Zuordnungskosten von Aktivität j an Ort i: C=[c_ij]
  

Die Entfernungen d_ih sind durch d_ih < d_il+d_lh (i,h,l = 1,...,n) definiert, so dass die Entfernung zwischen Ort i und h über einen dritten Ort l nicht kürzer ist als die direkte Verbindung. Die Zuordnungskosten (Transportkosten) c_ij werden üblicherweise in der Zielfunktion ignoriert, da sie keinen signifikanten Ausschlag bei der Lösung einer Instanz eines quadratischen Zuordnungs-Problems geben (vgl. Manniezzo et al. (1994) Seite 1, Maniezzo/Colorni (1999) Seite 1).

Im Gegensatz zum Travelling Salesman Problem nähern sich beim Quadratic Assignment Problem die beste und die schlechteste Lösung immer weiter an, wenn die Problemgröße zunimmt (vgl. Burkhard/Fincke (1983)). „Daher ist es so schwierig, aus all den Lösungen, die fast den gleichen Wert haben, die wirklich beste herauszufinden“ (Burkard (2000), Seite 205).

Eine Permutation P: iàp(i) kann als eine bestimmte Zuordnung von Objekt j=p(i) an Ort i (i=1,...,n) interpretiert werden. Gesucht ist die minimale Transportleistung, die man durch eine geeignete Permutation P findet:

min   _(3.13)

Diese Zielfunktion lässt sich auch mit Hilfe einer Matrix X darstellen. Ein Element x_ij aus der Matrix X ist 1, wenn das Objekt j dem Ort i zugeordnet wurde, und hat sonst den Wert 0.

  _(3.14)

mit

  _(j=1,...,n)

  _(i=1,...,n)

x_ij Î (0,1)  (i,j=1,...,n)

3.2.1 Ameisen-Algorithmen für das Quadratic Assignment Problem

In Maniezzo et al. (1994) wird eine Anwendung vom Ameisen-System für das Quadratic Assignment Problem beschrieben. Um eine Permutation zu konstruieren, startet man von der Spalte (Index j), die zu der Aktivität mit dem größten Fluss-Level gehört. Diese Aktivität wird dann nach der Wahrscheinlichkeits-Formel (3.15) einem Ort i zugeordnet.  In den nächsten Schritten wird die Spalte der Aktivität mit dem jeweils geringeren Fluss-Level betrachtet. Dieser Ablauf wird für alle n Spalten durchgeführt. Man erhält schließlich m Konstruktionen von den m Ameisen.

  _(3.15)

Bei der Konstruktion einer kompletten Permutation werden Orte und Aktivitäten geblockt, die bereits gekoppelt sind, bis jede Aktivität einem Ort zugewiesen wurde. Die Informationen dafür bekommen sie durch den Speicher M_k, in dem vermerkt wird, welcher Ort von der Ameise k bereits benutzt wurde und somit nicht mehr für eine Zuordnung zur Verfügung steht.

Im Gegensatz zu Problemen aus der Tourenplanung (Travelling Salesman Problem, Vehicle Routing Problem) errechnet sich h_ij jetzt nicht als Kehrwert der Entfernungen 1/d_ij, sondern als Kehrwert eines Elements aus der sogenannten Kopplungs-Matrix 1/a_ij. Durch eine Variation der Parameter a und b kann man die Lösungskonstruktionen noch zusätzlich beeinflussen.

Die potenzielle Güte („potential goodness“) der Kopplung a_ij errechnet sich nun anhand der gegebenen Matrizen der Entfernungen D und des Flusses F. Summiert man die Elemente der Zeilen, erhält man die zwei Vektoren d und f. Der Vektor d gibt die Entfernung eines Ortes i zu allen anderen Orten an, während der Vektor f den Fluss zwischen einem Objekt j und allen anderen Objekten angibt. Je niedriger der Wert d_i aus dem Vektor d ist, desto zentraler liegt dieser Ort i. Je höher der Wert f_j aus dem Vektor f ist, desto wichtiger ist dieses Objekt j für den Daten- bzw. Materialaustausch. Die Kopplungs-Matrix A wird nun durch A=d*f^T berechnet.

Eine erste Permutation kann durch eine „min-max“-Kopplung erreicht werden, indem man aus der Kopplungs-Matrix zunächst die Spalte mit dem höchsten Fluss-Level sucht und dieser Aktivität den Ort mit dem geringsten Distanz-Level zuordnet. Wenn man schließlich jeder Aktivität einen Ort zugeordnet hat, ergibt die Summe der gekoppelten Werte die gesamten potenziellen Kosten („potential cost“) der Kopplung z’:

  _(3.16)

mit

Man erhält nun normalerweise noch nicht die minimale Transportleistung. Vielmehr stellt dies eine erste Ausgangslösung dar. Die „min-max“-Regel kann als Eröffnungsverfahren genutzt werden, um eine Anfangslösung zu haben, welche als untere Schranke für weitere Lösungen dienen kann. Diese Schranke wird auch „Gilmore and Lawler bound“ genannt (vgl. Maniezzo (1998) Seite 3, Burkard et al. (1998) Seite 17f).

Wenn der Ort i einem Objekt j zugeordnet wird, wird diese Zuordnung mit Dt_ij verstärkt, so dass gilt:

  _(3.17)

mit

Q ist ein fixer Parameter und L_k der Zielfunktionswert der k-ten Ameise ist.

Der Algorithmus kann demnach folgendermaßen beschrieben werden (vgl. Maniezzo et al. (1994)):

1. 
   Initialisierung
   Setze t:=0;
   Berechne die Entfernungs- und Fluss-Level und die Kopplungs-Matrix A;
   Berechne die Werte h_ij:=1/a_ij;
   Verteile alle m Ameisen auf die Knoten i;
   
2. 
   Konstruktion
   Für k:=1 bis m
     wiederhole bis M_k voll ist (wird n-mal wiederholt) {
     (für jedes Objekt in Reihenfolge abnehmenden Fluss-Levels)
     wähle mit der Wahrscheinlichkeits-Formel (3.15) den Ort Ï M_k, dem   das Objekt zugeordnet werden soll;
     Nimm den gewählten Ort in M_k der k-ten Ameise auf.};
     Für k:=1 bis m
     Berechne L_k;
     Aktualisiere die beste gefundene Permutation;
   
3. 
   Spurenverstärkung
   Aktualisiere die Spuren-Matrix nach Gleichung (3.17);
   
4. 
   Wenn Abbruchkriterium nicht erfüllt
     Setze für jede Kopplung (i,j) Dt_ij:=0;
     Leere den Speicher aller Ameisen;
     Gehe zu 2.;
   Sonst
     Gib die beste Permutation aus und stoppe.
   

In Maniezzo (1998) wird vorgeschlagen, die Wahrscheinlichkeits-Formel (3.15) so zu modifizieren, dass der Parameter b entfernt wird, und der Parameter a als Multiplikator statt als Exponent den Einfluss von t_ij und h_ij steuert, um bessere Ergebnisse zu bekommen:

  _(3.18)

Ebenso wird die Formel für die Spurenverstärkung verändert, um einer Stagnation vorzubeugen. Sobald alle Ameisen ihre Lösungen berechnet haben, wird der Durchschnitt ihrer Lösungen _{gebildet. Jede neue Lösung zneu wird am Ende einer Iteration mit verglichen und mit allen anderen neuen Lösungen für die Berechnung des neuen Durchschnitts benutzt. Wenn zneu kleiner (größer) ist als , wird die Spurenstärke auf dem Weg, der zur aktuellen Lösung zneu gehörte, verringert (vermehrt).}

Dieser Effekt wird durch Formel (3.19) durchgeführt.

    _(3.19)

mit

Der Parameter t₀ ist der Anfangswert für die Spur der Kante (i,j) und LB bezeichnet die untere Schranke („Lower Bound“). Eine untere Schranke kann beispielsweise mittels der „min-max“-Regel berechnet werden.

Bei diesem Mechanismus gibt es keinen Faktor für die Verdunstung. Durch das dynamische Angleichen werden kleine Verbesserungen in der letzten Suchphase vernachlässigt, während gute Ergebnisse in den frühesten Stadien eher beachtet werden.

Abbildung 3.5 zeigt die lineare Funktion, die für die Spurenverstärkung verwendet wird.

t₀

-t₀

Dt

z

Abbildung 3.5: Lineares dynamisches Angleichen bei der Spurenverstärkung (aus Maniezzo (1998), Seite 7)

Im Anschluss an die Konstruktion einer Lösung kann noch eine lokale Suche stattfinden, in der die Nachbarschaft der gefundenen Tour nach besseren Lösungen untersucht wird (vgl. Maniezzo et al. (1994), Maniezzo/Colorni (1999)).

Bei der Wahl des Algorithmus für die lokale Suche sind die Geschwindigkeit und die Qualität der erzeugten Lösung wichtig. Alle lokale Suchmethoden basieren auf einer Definition der Nachbarschaftsstruktur N. Die Nachbarschaft einer Lösung ist eine Menge von Lösungen, die von der aktuellen Lösung aus in einem Schritt erreicht werden kann. Beim Quadratic Assignment Problem ist die Nachbarschaft einer Permutation P oft definiert als eine Menge an Permutationen, die sich durch Vertauschen von zwei Objekten bzw. Orten bilden lassen (vgl. Stützle (1997b)).

Es hat sich gezeigt, dass sich bei einer hohen Dominanz des Flusses und/oder der Entfernung das MAX-MIN Ameisen-System mit einer 2-opt lokalen Suche im Vergleich zu anderen Algorithmen besonders eignet (vgl. Stützle (1997b)). Wenn zum Beispiel nur wenige Aktivitäten einen großen Teil des Gesamtflusses in Anspruch nehmen, liegt eine hohe Dominanz des Flusses vor (vgl. Stützle/Dorigo (1999a)).

In Taillard/Gambardella (1997) wird ein schnelles Ameisen-System („fast ant system“, FANT) für das Quadratic Assignment Problem beschrieben. Es entstand aus dem „adaptive memory programming“ (AMP), das auch bei anderen genetischen Algorithmen wie Tabu Search Verwendung findet. Ein AMP arbeitet wie folgt: Eine neue Lösung wird konstruiert mit Hilfe der Informationen aus einem Speicher. Diese Lösung wird dann mit einer lokalen Suche überprüft. Dann wird mit dieser Lösung der Speicher aktualisiert und der Ablauf beginnt von Neuem.

Eine Besonderheit beim schnellen Ameisen-System ist, dass nur eine Ameise den Algorithmus durchläuft statt einer ganzen Kolonie. Der Vorteil dabei ist, dass die Durchführung bei der Konstruktion und der lokalen Suche ziemlich schnell abläuft.

Der Speicher besteht in diesem Fall aus der Pheromonmatrix, in der steht, wie gut eine Zuordnung von Objekt j zu einem Ort i ist. Einen Ort i und ein Objekt j, das diesem Ort zugeordnet werden soll, wählt die Ameise bei der Konstruktion zufällig.

Die Spurenverstärkung wird anhand der Formel (3.20) vorgenommen, nachdem eine gültige Lösung konstruiert wurde (vgl. Stützle/Dorigo (1999a)).

    _(3.20)

mit

und

L ist die aktuelle Lösung der Ameise und L^gb die bislang beste gefundene Permutation. Die Parameter c ist fix (in Taillard/Gambardella (1997) ist c=4 gesetzt), während der Parameter c’ im Laufe der Zeit verändert werden kann.

In diesem Modell verdunsten die Spuren nicht. Stattdessen wird die Aktualisierung der Spuren in zwei Fälle eingeteilt.

1)  Wenn die beste bislang gefundene Lösung erneut verbessert wird, werden der Parameter c’ und alle Pheromonwerte t_ij auf 1 gesetzt, um die Suche um die global beste Lösung zu verstärken.

2)  Wenn die aktuelle Lösung genauso gut ist wie die global beste, wird der Parameter c’ um 1 erhöht und alle Pheromonwerte t_ij bekommen den Wert von c’, um wieder eine größere Streuung in der Suche zu erreichen.

In Taillard/Gambardella (1997) wird noch ein weiterer Ameisen-Algorithmus für das QAP vorgestellt: ein hybrides Ameisen-System (“hybrid ant system-local search”, HAS). Neue Lösungen werden bei diesem Algorithmus ähnlich wie bei einer lokalen Suche aus bestehenden Lösungen konstruiert.

Die Permutationen für die Anfangslösungen werden zufällig gebildet. Alle Pheromonspuren haben am Anfang einen festen Wert t₀.

Eine Ameise verändert eine Lösung mit Hilfe einer schnellen lokalen Suche wie beim schnellen Ameisen-System, für die jeder Ameise eine Startlösung zugeordnet wird.

Es werden in Gambardella et al. (1999) zwei Mechanismen vorgeschlagen, nach denen eine solche Startlösung für jede Ameise gefunden werden kann:

-  Intensivierung („intensification“): Die Nachbarschaft der aktuellen Lösung wird nach weiteren guten Lösungen durchsucht. Die Ameise behält jedoch die alte Lösung, die sie zu Beginn der Iteration hatte, wenn diese mindestens genauso gut ist wie die, die sie nach einer lokalen Suche erhält.

-  Streuung („diversification“): Der Algorithmus wird teilweise neu gestartet, wenn die vorhandenen Lösungen selbst durch eine lokale Suche nicht mehr verbessert werden können. Sowohl die Spurenmatrix als auch die den Ameisen zugeordneten Lösungen werden dann reinitialisiert.

Schließlich wird die Spur der besten Ameise nach Formel (3.21) verstärkt, und der Algorithmus beginnt von vorne, bis ein Abbruchkriterium, z. B. das Erreichen einer maximalen Zyklenzahl, erfüllt ist (vgl. Stützle/Dorigo (1999a)).

  _(3.21)

mit

Ein Vorteil der beiden Algorithmen aus Taillard/Gambardella (1997) ist in der Schnelligkeit zu sehen, in der neue Lösungen gefunden werden. Andererseits läuft die Konstruktion einer Lösung sehr zufällig ab, so dass nur ein geringer Lerneffekt entsteht.

3.2.2 Quadratic Assignment Problem als Graph für Ameisen-Systeme

Eine Möglichkeit, das Layoutproblem für einen Ameisen-Algorithmus in eine Graphen-Form zu übertragen, zeigt die Abbildung 3.6 für den Fall von 5 Maschinen (m₁,...,m₅), die 5 Orten (O₁,...,O₅) zugeordnet werden sollen.

Der disjunktive Graph G=(V, A, E) ist definiert durch eine Menge an Knoten V, einer Menge an Pfeilen A und einer Menge an Kanten E. Die Menge an Knoten umfasst alle Maschinen v_j und Orte v_i, mit V={v_i,v_j} und i,j=1,...,5. Die Menge der Kanten besteht aus Kanten e_ij, wobei j der Index für eine Maschine und i der Index für einen Ort ist. Jede Maschine ist mit jedem Ort durch ein disjunktives Bogenpaar verbunden. Ein Pfeil zwischen zwei Knoten gibt eine Reihenfolgebeziehung dieser beiden Knoten zueinander an.

Abbildung 3.6: Disjunktiver Graph für ein Quadratisches Zuordnungsproblem

Zu jedem disjunktiven Bogenpaar in Abbildung 3.6 gehören zwei Pfeile, die in Abbildung 3.7 blau und rot markiert sind. Ein (blauer) Pfeil, der von einer Maschine m_j (j=1,...,5) zu einem Ort O_i (i=1,...,5) führt, hat die Länge d_i/t_ji. Der Faktor t_ji gibt die Güte an, die Maschine m_j einem Ort O_i zuzuordnen, während d_i aus Vektor d die Distanz von einem Ort zu allen anderen angibt. Je größer der Wert t_ji(t) ist, desto geringer ist die heuristische Distanz zwischen m_j und O_i. Eine Kopplung (i,j) wird dann eher gewählt. Ein (roter) Pfeil, der von einem Ort O_i in einer Maschine m_j endet, hat die Länge 1/f_j. Diese Länge entspricht dem Fluss zwischen der Maschine m_j und allen anderen Maschinen und kann aus dem Vektor f abgelesen werden. Je größer der Fluss-Level f_i von Maschine i ist, desto kürzer ist dieser Pfeil.

In Abbildung 3.7 ist ein disjunktives Bogenpaar für die Verbindung zwischen Ort O₂ und Maschine m₃ dargestellt.

Abbildung 3.7: Disjunktives Bogenpaar zwischen Maschine M₃ und Ort O₂

Zusätzlich sind noch alle weiteren Pfeile (gestrichelt) mit der jeweiligen heuristischen Distanz eingezeichnet, die vom Knoten O₂ bzw. m₃ ausgehen oder in diesem enden.

Um einen Ameisen-Algorithmus auf diesen Graph anzuwenden, bildet man zwei Mengen an Knoten V₁ und V₂, mit V₁={m₁,...m₅} und V₂={O₁,...,O₅}. Das Ziel bei dem Algorithmus ist es, einen Weg durch alle Knoten zu finden (Hamiltonweg), so dass die Summe aller Kantenbewertungen der Tour minimal ist und jeder Knoten aus der Menge V genau einmal besucht wird. Um zu verhindern, dass eine Ameise einen Knoten zweimal wählt, wird mit Hilfe des Speichers M_k jeder Knoten vermerkt, den die Ameise bereits besucht hat. Am Anfang werden alle Pheromonspuren auf einen einheitlichen Wert gesetzt, und jede Ameise wird in einen Knoten aus der Menge V₁ gesetzt.

Beim Ameisen-System in Maniezzo et al. (1994) würden alle Ameisen als erstes in den Knoten gesetzt werden, in den der Pfeil mit dem höchsten f_j-Wert führt.

Für die Konstruktion einer Lösung sucht sich eine Ameise den nächsten Knoten i bzw. j mit Hilfe von zwei Wahrscheinlichkeits-Formeln.

Mit der Wahrscheinlichkeit p_ji(t) in Formel (3.22) wählt eine Ameise den Knoten i, wenn sie sich im Knoten j befindet. Diese Entscheidung wird beeinflusst von t_ij, also der Güte der Kopplung von Maschine j und Ort i, und der Nähe der Maschine j zu allen anderen Maschinen. Die Parameter a und b können die Dominanz der beiden Faktoren t_ij und h_i noch zusätzlich beeinflussen.

  _(3.22)

mit

Wenn eine Ameise die Kante e_ji wählt, bedeutet dies, dass die Maschine j dem Ort i zugeteilt wurde.

Mit einer Wahrscheinlichkeit p_ij(t) in Formel (3.23) hingegen wählt eine Ameise den Knoten j, wenn sie sich im Knoten i befindet. Diese Formel ist eine Anlehnung an das Ameisen-System in Maniezzo et al. (1994), da die nächste zuzuordnende Maschine anhand des nächsthöchsten Fluss-Levels ausgesucht wird.

  _(3.23)

Beim schnellen Ameisen-System aus Taillard/Gambardella (1997) hingegen wird die nächste Maschine zufällig gewählt. In diesem Fall würde die Wahrscheinlichkeit, als nächstes die Maschine j zu wählen, nach Formel (3.24) berechnet werden.

  _(3.24)

Die k-te Ameise erhält am Ende eine Lösung, die sich aus ihrem Speicher M_k ergibt. In diesem stehen nun abwechselnd eine Maschine und ein Ort in einer bestimmten Reichenfolge, z. B. {m₁, O₃, m₃, O₄, m₄, O₁, m₂, O₅, m₅, O₂}. Durch diese Reihenfolge lassen sich die Zuordnungen der Maschinen zu den jeweiligen Orte vornehmen, und die Permutation ergibt sich durch:

P_k =   {m₁ wird O₃ zugeordnet; m₂ wird O₅ zugeordnet; m₃ wird O₄ zugeordnet; m₄ wird O₁ zugeordnet; m₅ wird O₂ zugeordnet}

Die Verstärkung der Spuren auf den Wegen von den Maschinen zu den Orten verläuft im Fall eines Ameisen-Systems für alle k Ameisen nach Formel (3.25).

  _(3.25)

mit

Im Falle eines schnellen Ameisen-Systems, in der nur eine Ameise die Aktualisierung vornimmt, werden die Spuren nach Formel (3.26) verstärkt.

  _(3.26)

mit

und

In der Praxis kann der Fall auftreten, dass man mehr Orte zur Verfügung hat als Maschinen. In diesem Fall kann nicht jeder Ort mit einer Maschine besetzt werden. Dieses Problem kann ebenso mit dem zuvor angesprochenen Modell dargestellt werden, wie Abbildung 3.8 zeigt. Es stehen nun 6 Orte zur Verfügung, denen 4 Maschinen zugeordnet werden sollen.

Abbildung 3.8: Disjunktiver Graph für 4 Maschinen und 6 Orte

Die einzige Veränderung gegenüber dem Modell mit gleicher Anzahl an Maschinen und Orten ist, dass man nicht mehr einen Weg sucht, bei der alle Knoten einmal besucht werden müssen. Stattdessen sucht man den besten Weg, bei dem jeder Knoten aus der Menge V₁ genau einmal besucht werden muss. Dadurch findet man für jede Maschine genau eine Zuordnung. Die Konstruktion ist beendet, wenn kein Knoten Ï M_k mehr besucht werden kann.

Bei der Konstruktion einer Lösung startet man ebenso in einem Knoten aus der Menge V₁ und wählt den nächsten Knoten nach den Formeln (3.22) und (3.24) bzw. (3.25). Die Spurenverstärkung erfolgt nach Formel (3.25) bzw. (3.26).

Der Algorithmus ist beendet, wenn ein Abbruchkriterium erfüllt ist.

3.3 Reihenfolgeprobleme

Die Reihenfolgeplanung kann als Maschinenbelegungsplanung („scheduling“) oder auch als „Ablaufplanung im engeren Sinne“ bezeichnet werden (vgl Kistner/Steven (2003)). „Maschinenbelegungsprobleme befassen sich mit der Zuordnung von Aufträgen zu Arbeitsträgern bzw. Maschinen“ (vgl. Domschke et al. (1997), Seite 279).

Das allgemeine Reihenfolgeplanungsmodell („general shop problem“) kann wie folgt definiert werden (vgl. Brucker (1998)):

Gegeben sind j Aufträge (j=1,..,J) und m Maschinen (m=1,...,M). Der j-te Auftrag besteht aus einem bestimmten Ablauf an Arbeitsgängen o_jm aus einer Menge O={...o_jm...}. Jeder Arbeitsgang o_jm Î O gehört zum Auftrag j und muss an der Maschine m für t_jm Zeiteinheiten durchgehend bearbeitet werden. Die Bearbeitungsdauern sind ganzzahlig, unabhängig von der Bearbeitungsfolge und schließen Rüstzeiten mit ein. Jeder Auftrag kann jeweils immer nur an einer Maschine bearbeitet werden. Ebenso kann jede Maschine auch nur maximal einen Auftrag zu einem bestimmten Zeitpunkt bearbeiten. Zwischen den Arbeitsgängen der Aufträge können Reihenfolgebeziehungen bestehen. Alle Aufträge sind zum Zeitpunkt 0 verfügbar und eventuell auftretende Rüstzeiten sind von der Reihenfolge unabhängig.

Bei der Maschinenbelegungsplanung kommen verschiedene Zielsetzungen in Frage, die zumeist in die Bereiche der durchlaufzeit-, kapazitäts- oder terminorientierten Ziele fallen (vgl. Domschke et al. (1997), Seite 291).

Die Ziele, die in diesem Kapitel verfolgt werden, orientieren sich an der Minimierung der Summe der Durchlaufzeit, Zykluszeit oder der Verspätung.

Die Suche nach einer optimalen Reihenfolge für n Aufträge, die alle nur an einer Maschine bearbeitet werden müssen, tritt in der Praxis nicht sehr häufig auf (vgl. Neumann (1996), Seite 130). Zwei Ein-Maschinen-Probleme, bei denen ein Ameisen-Algorithmus angewandt wurde, sollen hier jedoch in Abschnitt 3.3.1 und 3.3.2 näher erläutert werden.

Für den Fall, dass mehrere Arbeitsgänge auf mehreren verschiedenen Maschinen zu fertigen sind, wird die Maschinenbelegungsplanung weiter in Open Shop (offene Fertigung), Flow Shop (Reihenfertigung/Fließfertigung) und Job Shop (Werkstattfertigung) unterteilt.

• 
  Open Shop: Jeder Auftrag hat jede Maschine höchstens einmal zu durchlaufen in einer für alle Aufträge beliebigen Reihenfolge, d. h. dass weder Arbeits- noch Maschinenfolgen vorgegeben sind.
  
• 
  Flow Shop: Jeder Auftrag wird auf jeder Maschine in einer für alle Maschinen fest vorgegebenen Reihenfolge bearbeitet. Beim Permutations-Flow-Shop-Problem sind zusätzlich die Auftragsfolgen für alle Maschinen gleich.
  
• 
  Job Shop: Jeder Auftrag hat eine eigene fest vorgegebene Reihenfolge für die Bearbeitung auf den einzelnen Maschinen. Ein Auftrag kann einzelne Maschinen auslassen oder mehrmals bearbeitet werden, wobei zwei aufeinanderfolgende Arbeitsgänge jeweils von verschiedenen Maschinen auszuführen sind. Permutations-Job-Shop-Probleme, bei denen die Auftragsreihenfolgen für alle Maschinen gleich sind, sind durchaus möglich.
  

Das allgemeine Reihenfolgeplanungsmodell für mehrere Maschinen kann auch in einen disjunktiven Graphen G=(V,A,E) übertragen werden, mit einer Menge an Knoten V, einer Menge an Pfeilen A und einer Menge an Kanten E.

Die Menge V umfasst alle Arbeitsgänge o_jm aus der Menge O, einen Startknoten o_b und einen Endknoten o_e.

Die Menge der Kanten V besteht aus Kanten _{wobei und zwei benachbarte Knoten aus V sind, für die keine Reihenfolgebeschränkung vorliegt. Jede Kante besteht aus einem Pfeilpaar.}

Ein Pfeil zwischen zwei Knoten gibt eine Reihenfolgebeziehung dieser beiden Knoten zueinander an. Die Länge eines Pfeils zum Knoten o_jm entspricht der Bearbeitungsdauer t_jm des j-ten Auftrags an der m-ten Maschine. Ein Pfeil, der im Knoten o_e endet, hat die Länge 0.

In Abbildung 3.9 ist ein Beispiel für ein allgemeines Maschinenbelegungsmodell dargestellt für 4 Aufträge und 3 Maschinen (in Anlehnung an Latz (1997), Seite 21 und Brucker (1998), Seite 146).

Abbildung 3.9: Disjunktiver Graph für ein allgemeines Maschinenbelegungsmodell mit 4 Aufträgen und 3 Maschinen

Zur Vereinfachung sind je zwei verschiedene Knoten in jeder Maschine (in der gestrichelten Umrandung) durch eine disjunktive Kante verbunden, so dass noch keine Reihenfolgebeziehung zwischen einzelnen Aufträgen an einer Maschine besteht.

Dieser Graph lässt sich für jede Maschine noch in weitere vollständige Teilgraphen unterteilen. Ein vollständiger disjunktiver Teilgraph ist beispielhaft für die Maschine 2 in Abbildung 3.10 dargestellt.

Abbildung 3.10: Disjunktiver Teilgraph für Maschine 2

Für jede disjunktive Kante in Abbildung 3.9 sind nun zwei Pfeile eingezeichnet. Bei der Suche nach einer optimalen Maschinenbelegung, wird je ein Pfeil pro Pfeilpaar verworfen, so dass man zum Schluss eine eindeutige Reihenfolge für die Aufträge an den Maschinen erhält.

In den Abschnitten 3.3.3, 3.3.4 und 3.3.5 werden Ameisen-Algorithmen für das Open Shop, Flow Shop und Job Shop Problem vorgestellt. Alle drei Probleme lassen sich als Sonderfall aus dem allgemeinen Reihenfolgeplanungsmodell ableiten.

3.3.1 Total Tardiness Problem

Bei dem Single Machine Total Tardiness Problem (SMTTP) gibt es am Anfang keine Reihenfolgebeschränkung für die n Aufträge. Es wird von einem statischen Modell ausgegangen, so dass alle n Aufträge zum Zeitpunkt t=0 zur Verfügung stehen. Die Bearbeitungszeit des Auftrags j (j=1,...,n) auf der Maschine beträgt t_j Zeiteinheiten und der Fertigungszeitpunkt für jeden Auftrag j ist gegeben durch FZ_j. Der Fertigstellungszeitpunkt („completition time“) C_j ergibt sich durch die erhaltene Reihefolge der Aufträge. Die sich daraus ergebene Verspätungszeit T_j berechnet sich durch T_j=max{0, C_j-FZ_j} für jeden Auftrag j.

Das Ziel ist die Minimierung der gesamten Verspätungszeit, also der Summe der Verspätungen T_j aller Aufträge.

Für die Anwendung von einem Ameisen-System wird dieses Problem in eine Graphen-Darstellung übertragen (vgl. Bauer et al. (2000)). Die Knoten des Graphen symbolisieren einen Zustand („state“), der aus einer Menge an Aufträgen besteht, und die Kanten zwischen den Knoten Übergänge („transitions“). Der gerichtete Graph ist azyklisch, hat eine Quelle und eine Senke. Die Quelle ist der Anfang einer Sequenz, und die Menge der darin enthaltenen Aufträge ist leer. Bei Benutzung einer Kante bzw. eines Übergangs in einen nächsten Knoten, wird jedes Mal ein weiterer Auftrag in diese Sequenz aufgenommen, bis schließlich in der Senke alle n Aufträge in die Menge aufgenommen wurden. Jeder Pfad, der von der Quelle zur Senke führt, repräsentiert eine gültige Lösung. Abbildung 3.9 zeigt einen solchen Graphen für 3 zu bearbeitende Aufträge.

Abbildung 3.9: Graph für ein SMTTP mit 3 Aufträgen (aus Bauer et al. (2000), Seite 6)

Die Aufträge in den jeweiligen Knoten haben keine spezielle Reihenfolge, sondern stellen nur eine Menge der bislang zugeordneten Aufträge dar. Die Verspätungszeit des Auftrags, der als nächstes in die Menge aufgenommen wird, ist unabhängig von der aktuellen Sequenz.

Jede Ameise bildet eine Lösung indem sie mit einer Wahrscheinlichkeit q nach Formel (3.27) einen Auftrag j an die Stelle i setzt (vgl. Merkle/Middendorf (2000)).

  _(3.27)

Für die Berechnung des Faktors h_ij werden in Bauer et al. (2000) insgesamt vier Möglichkeiten vorgeschlagen. Die beiden einfachsten zu berechnenden Alternativen orientieren sich an der frühesten Fertigstellungs- bzw. kürzesten Bearbeitungszeit, mit h_ij=1/FZ_j bzw. h_ij=1/t_j. Eine weitere Möglichkeit, die in Merkle/Middendorf (2000) benutzt wird, ist eine Orientierung an der gesamten Bearbeitungszeit T’ der bereits ausgewählten Aufträge, mit _.

Eine lokale Suche mit einer 2-opt Heuristik ist möglich. Danach läuft die Spurenaktualisierung nach Formel (3.28) ab. Jede Ameise verstärkt dabei ihr Ergebnis.

  _(3.28)

mit

und

T^gb ist die gesamte Verspätung der besten Lösung und T^d die gesamte Verspätung, die sich nach einer berechneten Sequenz ergibt, die mit h_ij=1/d_j konstruiert wurde. Der letzte Term ist eine lokale Spurenverstärkung, der in Bauer et al. (2000) zusätzlich hinzugefügt wird.

3.3.2 Sequential Ordering Problem

Das Ziel beim Sequential Ordering Problem (SOP) ist es, eine Reihenfolge für n Aufträge zu finden, für die gewisse Reihenfolgebeziehungen vorliegen, so dass die gesamte Bearbeitungszeit minimiert wird (vgl. Gambardella/Dorigo (1997)).

Oder anders ausgedrückt, man sucht einen Hamiltonweg mit geringster Gewichtung durch einen gerichteten Graphen. Die Knoten und Kanten in dem Graphen sind gewichtet und es gibt Reihenfolgebeziehungen zwischen manchen Knoten.

Das Sequential Ordering Problem kann auch als asymmetrischen Travelling Salesman Problem formuliert werden, wenn man die Reihenfolgebeschränkungen beiseite lässt (vgl. Escudero (1988)). Zudem hat man einen vorgegebenen Start- und Endknoten.

Die Knoten V des vollständigen Graphen G=(V,A) sind gewichtet mit der Bearbeitungszeit t_j des Auftrags j. Die Kanten A haben den Wert _{. Dieser Wert entspricht einer Rüstzeit zwischen Auftrag j und Auftrag h. Die Rüstzeit kann für jedes Auftragspaar verschieden sein. In der Praxis kann man sich als Beispiel eine Lackiererei vorstellen, die zwei Objekte in verschiedenen Farben lackieren muss. Je nach Farbfolge ist die Rüstzeit zwischen Auftrag j und h verschieden lang. Die Bearbeitungs- und Rüstzeiten verursachen Kosten in Höhe ihrer Länge.}

Der Startknoten (Knoten o₀) und der Endknoten (Knoten o_e) sind mit allen anderen Knoten verbunden. Die Kante zwischen dem Startknoten und einem weiteren Knoten j ist gleich der Rüstzeit mit _{=tj und =0.}

Reihenfolgebeziehungen zwischen den Aufträgen sind in einem zusätzlichen azyklischen Digraphen P=(V,R) festgehalten. Die Knoten V aus P stimmen mit denen aus dem Graphen G überein. In der Kantenmenge R sind die Kanten (j,h) enthalten, bei denen der Auftrag j in jeder gültigen Lösung Vorgänger von Auftrag h ist.

Zusammengefasst kann man einen Graphen aufstellen, bei dem die Kanten mit c_jh=_{+tj bewertet sind. Die Bewertung der Knoten fällt weg. Eine Kante stellt dann zusätzliche Kosten dar, wenn cjh>0 ist, und sie stellt eine Reihenfolgebeziehung zwischen dem Knoten j und h her, wenn cjh=-1 ist. Bei der Berechnung der Übergangswahrscheinlichkeit, von einem Knoten j zu einem Knoten h zu gehen, würden Knoten, zu denen eine Kante mit einer negativen Bewertung führen, nicht in Betracht gezogen werden.}

Bei diesem Modell ist ein Knoten h Nachfolger, wenn von h nach j ein Pfeil mit der Bewertung –1 existiert. Ein Knoten h ist unmittelbarer Nachfolger vom Knoten j, wenn man vom Knoten j nur noch in den Knoten h über eine positiv-bewertete Kante kommen kann. Bei einem unmittelbaren Nachfolger, darf zwischen den beiden entsprechenden Aufträgen kein weiterer Auftrag in einer gültigen Reihenfolge sein.

In Abbildung 3.10 ist ein solcher Graph für 4 Aufträge dargestellt.

Abbildung 3.10: Sequential Ordering Problem, Instanz mit 4 Aufträgen

Es liegen somit Reihenfolgebeziehungen zwischen den Knoten 1 und 2, 1 und 3, sowie zwischen den Knoten 2 und 4 vor. Knoten 2 ist ein unmittelbarer Nachfolger von Knoten 1. Eine gültige Reihenfolge wäre jetzt zum Beispiel 4-1-2-3.

In Gambardella/Dorigo (1997) wurde ein hybrides Ameisen-System verwendet, um Instanzen des Sequential Ordering Problems zu lösen. Für die Konstruktion hat die Ameise in jedem Knoten eine Menge F(j) an Knoten zur Verfügung, in denen alle Knoten stehen, die zum einen noch nicht besucht wurden, zum anderen direkter oder indirekter Nachfolger vom Knoten j sind.

Demnach entscheidet sich eine Ameise nach Formel (3.29), den nächsten Knoten h zu wählen.

  _(3.29)

Der Speicher F(h) ist quasi als Ersatz für die Tabu-Liste M_k zu sehen, in der sonst die Knoten standen, die nicht mehr besucht werden durften.

Der Wert für q₀ berechnet sich nach Formel (3.30).

  _(3.30)

Der Parameter u gibt die Anzahl an Knoten an, die nach Formel (3.29) gewählt werden können. In Gambardella/Dorigo (1997) wurde dieser Parameter für Experimente allerdings auf 10 festgesetzt.

Während einer Iteration verstärken die Ameisen ihre Spuren, sobald sie eine Kante benutzt haben, mit:

  _(3.31)

Für den Parameter t₀ eignet sich nach Gambardella/Dorigo (1997) die Festsetzung auf _{, wobei L¹ die erste gefundene Lösung ist.}

Nach einer lokalen Suche durch einen 2- oder 3-Kanten-Tausch, kommt es ebenfalls zur globalen Spurenverstärkung anhand von Formel (3.32). Beim hybriden Ameisen-System darf am Ende immer nur die beste Ameise ihre Spur verstärken.

  _(3.32)

mit

3.3.3 Open Shop Problem

Die Besonderheit beim Open Shop Problem (OSP) im Vergleich zum allgemeinen Maschinenbelegungsproblem ist, dass sowohl die Reihenfolge der Aufträge wie auch die Reihenfolge der Maschinen, in der die Aufträge bearbeitet werden sollen, beliebig sind. Um ein Ameisen-System auf Maschinenbelegungsprobleme anwenden zu können, muss der Graph aus Abbildung 3.9 so modifiziert werden, wie Abbildung 3.11 zeigt. Der Knoten o_b und wurde im Vergleich zu Abbildung 3.9 weggelassen. Dafür sind jetzt alle Knoten, die zum gleichen Auftrag gehören, miteinander durch eine disjunktive Kante verbunden.

Abbildung 3.11: Graph für ein OSP mit 4 Aufträgen und 3 Maschinen

Gesucht ist ein Hamiltonweg, für den die Summe der gewichteten Kanten, die zu dem Weg gehören, minimal ist. Dieses Problem stellt wieder ein asymmetrisches Travelling Salesman Problem dar und kann nach den Algorithmen in Kapitel 2 gelöst werden. Allerdings starten alle Ameisen im Startknoten o_b.

Man erhält als Lösung eine Reihenfolge der einzelnen Arbeitsgänge für jeden Auftrag mit einer Reihenfolge für die Maschinen.

3.3.4 Flow Shop Problem

Der Graph aus Abbildung 3.8 kann für ein Flow Shop Problem (FSP) mit 4 Aufträgen und 3 Maschinen wie in Abbildung 3.12 geändert werden. Der Graph hat einen Startknoten o_b,_{auch „Dummy“-Auftrag genannt (vgl. Stützle (1997a), Seite 2). Die Reihenfolge der Maschinen ist fest vorgegeben, für alle Aufträge gleich und kann zwischendurch nicht geändert werden.}

Abbildung 3.12: Disjunktiver Graph für ein FSP mit 4 Aufträgen und 3 Maschinen

Gesucht ist die Reihenfolge, in der die 4 Aufträge auf den 3 Maschinen bearbeitet werden sollen, mit der geringsten gesamten Bearbeitungszeit.

Wenn die Reihenfolge der Aufträge für alle 3 Maschinen gleich ist, liegt ein Permutations-Flow-Shop-Problem vor. Man erhält beim Flow Shop Problem im Standardfall nur für Instanzen mit mehr als drei Maschinen bessere Ergebnisse als beim Permutations-Flow-Shop-Problem (vgl. Brucker (1998), Seite 165).

Im folgenden werden Ameisen-Algorithmen für Permutations-Flow-Shop-Probleme beschrieben. Für die Festlegung der Reihenfolge der Aufträge an allen Maschinen muss nur die Reihenfolge für eine Maschine betrachtet werden, da die Reihenfolge der Aufträge für alle Maschinen gleich ist. Das Problem lässt sich dann für den Algorithmus wie in Abbildung 3.13 beschreiben für einen Teilgraphen, der die Reihenfolgebeziehungen aller Maschinen repräsentiert.

Abbildung 3.13: Teilgraph für die Reihenfolgen der Aufträge an den Maschinen

Im Grunde liegt wieder ein asymmetrisches Travelling Salesman Problem vor. Jeder Knoten muss genau einmal besucht werden. Allerdings sind die Pfeile nicht mit einer Distanz zwischen den Knoten bewertet, sondern allein mit der Spurenstärke t_ij, die die potenzielle Güte angibt, den Auftrag j an die Position i zu setzen. Je nachdem, an welcher Position i sich der aktuelle Knoten in der bisherigen Reihenfolge befindet, bestimmt sich die Spurenstärke für die Kante, die in den nächsten Knoten führt, nach den jeweiligen Spurenstärken für die Positionen i+1.

In Stützle (1997) wird die Anwendung eines MAX-MIN Ameisen-Systems für ein Permutations-Flow-Shop-Problem beschrieben.

Die Ameisen konstruieren eine Auftragsreihenfolge, indem sie einen Auftrag j mit einer Wahrscheinlichkeit an die Position i setzen, die nach Formel (3.33) berechnet wird, bis alle Aufträge zugeordnet sind. Eine Lösung wird mittels einer Kandidatenliste ermittelt, in der eine zuvor festgelegte Anzahl an Möglichkeiten steht, welche sich aus der bislang besten gefundenen Reihenfolge ergeben. Nach Stützle (1997) scheinen 5 Kandidaten in der Liste zu guten Ergebnissen zu führen.

  _(3.33)

M_k ist der Speicher, in dem alle Aufträge stehen, die bereits zugeordnet wurden. Im Gegensatz zu anderen Anwendungen fällt hier der Einfluss der Sichtbarkeit h_ij weg.

Nachdem eine Ablaufreihenfolge erstellt und durch eine mögliche lokale Suche überprüft wurde, werden die Spuren verstärkt. Im MIN-MAX Ameisen-System darf immer nur die beste Ameise ihre Spur verstärken. Die Spurenverstärkung erfolgt anhand der Formel (3.34):

  _(3.34)

L^gb ist hier die kürzeste gesamte Produktionsdauer der besten Ameise.

Für die lokale Suche bieten sich beim Flow Shop Problem drei Verfahren an (vgl. Stützle (1997)):

• 
  Tausch-Verfahren („swap-moves“): Tausch von zwei benachbarten Aufträgen an der Position i und i+1 (i=1,..., n-1).
  
• 
  Austausch-Verfahren („interchange-moves“): Austausch von Aufträgen an der i-ten und h-ten Position.
  
• 
  Einfügungs-Verfahren („insertion-moves“): Entfernen des Auftrags an i-ter Stelle und Einfügen an die h-te Position.
  

Es hat sich gezeigt, dass das Einfügungsverfahren effektiver ist als das Austausch- oder gar das Tausch-Verfahren.

In Rajendran/Ziegler (2004) wird das zuvor vorgestellte MIN-MAX Ameisen-System erweitert, indem die Summierungsregel aus Merkle/Middendorf (2000) (Seite 290f) aus dem Total-Weighted-Tardiness Problem für eine Maschine übernommen wird. Zudem wird die Auswahlregel für den Auftrag geändert, der als nächstes an die bisherige Reihenfolge der Aufträge gefügt werden soll. Der modifizierte MIN-MAX Ameisen-System-Algorithmus wird mit M-MMAS abgekürzt.

Zur Initialisierung wurde für das Ziel der Minimierung der Gesamtbearbeitungszeit („makespan“) die NEH Heuristik (vgl. Nawaz et al. (1983)) und für das Ziel der gesamten Durchlaufzeit („Flow time“) die Rajendran Heuristik (vgl. Rajendran (1993)) verwendet. Dadurch erhält man eine erste Startlösung.

Die Grenzen der Pheromonspuren wurden auf _{und gesetzt. Zu Beginn ist L^gb das Ergebnis der Startlösung.}

Eine Ameise konstruiert eine Lösung, indem sie nach Formel (3.35) einen Auftrag j wählt, der an die nächste Position i der bisherigen Reihe gesetzt werden soll.

  _(3.35)

mit

Auch hier gibt es eine Kandidatenliste, in der die 5 besten Zuordnungen von Aufträgen an bestimmten Positionen stehen. Erst wenn kein Auftrag mehr aus der Kandidatenliste an eine Position gesetzt werden kann, werden die restlichen Aufträge betrachtet.

Nachdem eine Lösung konstruiert worden ist, wird diese durch eine „job-index-based“ lokale Suche überprüft. Ein Auftrag j wird an jede Position i der aktuellen Reihenfolge gesetzt, wobei die Reihenfolge der restlichen Aufträge unverändert bleibt. Diese Suche wird für alle Aufträge durchgeführt. Die beste Reihenfolge wird am Ende gespeichert.

Nach der lokalen Suche findet die Spurenverstärkung für die beste Reihenfolge nach Formel (3.36) statt.

  _(3.36)

mit

L^ib ist der Wert der aktuellen Reihenfolge. Die Spurenstärke _{kann nie größer (kleiner) als t^max (t^min) werden. Die Spurenstärke wird sonst an den jeweiligen Wert angeglichen.}

In Rajendran/Ziegler (2004) ebenfalls ein zweiter Ameisen-Kolonie-Algorithmus vorgeschlagen („proposed ant-colony algorithm“, PACO).

In der Initialisierungsphase werden die Werte für t_ij nach Formel (3.37) bestimmt, nachdem eine Startlösung wie zuvor mittels einer NEH Heuristik bzw. Rajendran Heuristik berechnet wurde.

  _(3.37)

Den Wert für L^gb erhält man aus dem Ergebnis der Startlösung. p(j) ist die Position, der in der Startlösung der Auftrag j zugeordnet wurde und n die Anzahl der Aufträge.

Durch diese Art der Spureninitialisierung werden Positionen, die in der näheren Umgebung von p(j) sind, mit einem höheren Pheromonwert versehen als diejenigen, die von p(j) weiter entfernt sind. Im Gegensatz zum MMAS und M-MMAS werden hier keine Grenzen für die Spurenstärken t_ij festgesetzt.

Eine neue Lösung wird anhand von Formel (3.38) konstruiert. Bei dieser dreistufigen Wahrscheinlichkeits-Formel wurden die Stufen 0.4 und 0.8 vorgeschlagen. Zu je 40% wählt eine Ameise die erste oder zweite Alternative und mit einer 20%-igen Wahrscheinlichkeit die dritte Möglichkeit, einen Auftrag j an die Position i zu setzen.

  _(3.38)

mit

Die Zuordnung p^gb(j) von Auftrag j an Position i in der ersten Wahlmöglichkeit wird aus der bislang global besten Lösung entnommen. Bei der zweiten Alternative sucht man für einen Auftrag j die Position, die mit dem höchsten t_ij-Wert belegt ist, aus einer Kandidatenliste der fünf besten Positionen für diesen Auftrag.

Die Aktualisierung der Spurenstärken erfolgt durch Formel (3.39) nach einer lokalen Suche wie beim M-MMAS, mit Unterscheidung bei der Anzahl an Aufträgen n.

  _(3.39)

mit

und

L^ib ist die Lösung der aktuellen Konstruktion vor der lokalen Suche und h ist die Position, an der der Auftrag j nach der lokalen Suche steht. Dieser Position wird die Position k gegenübergestellt, an der der Auftrag j vor der lokalen Suche stand.

Wenn das Ergebnis der aktuellen Konstruktion besser ist als die bislang beste gefundene Reihenfolge, werden beide Lösungen nach Formel (3.39) verstärkt.

Bei Experimenten in Rajendran/Ziegler (2004) mit 20-100 Aufträgen und 5-20 Maschinen konnten mit beiden Algorithmen im Vergleich zu anderen Algorithmen gute Ergebnisse erzielt werden, wobei PACO bei größeren Permutations-Flow-Shop-Problemen bessere Resultate lieferte als M-MMAS.

3.3.5 Job Shop Problem

Im Vergleich zum Flow Shop Problem ist die Reihenfolge der Maschinen beim Job Shop Problem für jeden Auftrag unterschiedlich. Die Abbildung 3.7 kann als Beispiel für ein Job Shop Problem wie in Abbildung 3.14 modifiziert werden.

Abbildung 3.14: Disjunktiver Graph für ein JSP mit 4 Aufträgen und 3 Maschinen

Die Bearbeitungszeiten und Maschinenreihenfolgen der einzelnen Aufträge für dieses Beispiel sind zur besseren Übersicht in der nachstehenden Tabelle aufgelistet. Wenn ein Auftrag auf einer Maschine nicht bearbeitet werden muss, ist die Bearbeitungszeit für diese Maschinen Null; der jeweils dazu gehörende Knoten wurde in Abbildung 3.13 weggelassen.

Jeder Kante ist ein Zahlenpaar {t_jm, h_jm} zugeordnet, wobei t_jm die Spurenstärke ist. Der Faktor h_jm kann unter anderem, je nach Zielsetzung, unterschiedlich bestimmt werden durch:

-  die kürzeste Bearbeitungszeit,

-  die längste Bearbeitungszeit,

-  die kürzeste Restbearbeitungszeit,

-  die längste Restbearbeitungszeit.

Bei der Wahl der kürzesten Bearbeitungszeit steht die Maschine wieder schnell für andere Bearbeitungen zur Verfügung, und man kann gute Kapazitätsauslastung und kurze Durchlaufzeiten erreichen (vgl. Kistner (2001), Seite 124). Es gibt noch eine Menge weiterer sogenannter Prioritätsregeln, nach denen h_jm berechnet werden könnte (vgl. Mertens (2001), Seite 173). Sie orientieren sich meistens an den Bearbeitungszeiten oder Schlupfzeiten der Aufträge, sofern diese alle von Anfang an zur Verfügung stehen. In diesem Modell wird für die Bestimmung von h_jm die längste Bearbeitungsdauer gewählt (vgl. Colorni et al. (1994)). Es gilt daher h_jm = t_jm.

Alle Ameisen starten in o_b. In den nächsten Schritten wird nach möglichen Permutationen der restlichen Knoten gesucht. Um geeignete Permutationen zu bekommen, muss man in jedem Schritt eine Menge an erlaubten Knoten definieren, die hier nicht nur anhand einer Tabu-Liste, sondern vielmehr problem-orientiert durch insgesamt drei Speicher bestimmt wird: Für jede Ameise k ist G_k die Menge der noch nicht besuchten Knoten und G’_k die Menge an Knoten, die beim nächsten Schritt erlaubt sind, mit G_k={o₁₁, o₁₂, o₁₃, o₂₁, o₂₂, o₂₃, o₃₁, o₃₂, o₄₁, o₄₃} und G’_k={o_12, o₂₁, o₃₁, o₄₃} für das gegebene Beispiel.

Die Übergangswahrscheinlichkeiten werden anhand der Formel (3.40) berechnet:

  _(3.40)

Wenn ein Knoten ausgewählt wurde, wird dieser zur Tabu-Liste M_k hinzugefügt und aus den Mengen G_k und G’_k gestrichen. Wenn der gewählte Knoten nicht der letzte des entsprechenden Auftrags ist, wird der Nachfolger des gleichen Auftrags in der Menge G’_k aufgenommen. Dieser Vorgang wird wiederholt bis G_k=Æ. Am Ende steht die Reihenfolge der Knoten in der Tabu-Liste als Lösung der k-ten Ameise.

Man erhält durch die Tabu-Liste M_k z. B. eine Reihenfolge der Knoten:

{o_b, o₁₂, o₃₁, o₁₃, o₂₁, o₄₃, o₁₁, o₃₂, o₂₂, o₂₃, o₄₁, o_e}

Dadurch bekommt man eine eindeutige Reihenfolge der Aufträge an den Maschinen. Es ergibt sich ein gerichteter Graph wie in Abbildung 3.15.

Abbildung 3.15: Beispiel für eine Reihenfolge der Aufträge für ein JSP mit 4 Aufträgen und 3 Maschinen

Im Anschluss wird die Spur der besten Ameise wie bei Ameisen-Zyklus-Algorithmus verstärkt.

Mit diesem Algorithmus wurden Job-Shop-Problem-Instanzen von einer Dimension 10x10 und 10x15 (10 Aufträge und 15 Maschinen) erfolgreich gelöst (vgl. Dorigo et al. (1996)). Die Lösung dieser Probleme war nur knapp 10% schlechter als das Optimum.

4 Ausblick

„ACO is currently the best available heuristic for the sequential ordering problem and for real-world instances of the quadratic assignment problem, and is among the most competitive approaches for the vehicle and network routing problems”, schrieben Eric Bonabeau, Marco Dorigo und Guy Theraulaz 2000 (vgl. Bonabeau et al. (2000)).

Doch die Ameisen-Algorithmen können auch durchauen weiterer Probleme mit anderen bekannten Metaheuristiken konkurrieren. In dieser Arbeit wurden unter anderem noch Algorithmen für Beispiele für Reihenfolgeprobleme vorgestellt.

Auch über den Bereich von Produktion und Logistik hinaus gibt es eine ganze Reihe von Problemen, deren Instanzen sich mittels Ameisen-Algorithmen sehr gut lösen lassen. In Dorigo (2001) sind in der Tabelle 1 auf Seite 14 einige weitere Probleme angegeben, für die ein Ameisen-System erfolgreich eingesetzt werden konnte.

In der Praxis finden Ameisen-Systeme Anwendung in verschiedenen Bereichen. So benutzte beispielsweise Pina Petroli Ameisen-Algorithmen, um seine Tankwagen bei der Belieferung von Privathaushalten in der Schweiz mit Heizöl zu koordinieren. Das Problem war zuvor, dass die LKW unterschiedlicher Größe waren, wie auch Länge und Durchmesser der Tankschläuche (vgl. BBT (2003)). Externe Einflüsse wie Wetterbedingungen oder Verkehrsaufkommen konnten zusätzlich zu Problemen führen. Zuletzt konnten die Bestellungen oft nicht im Voraus geplant werden, und manche Kunden konnten nur zu bestimmten Zeiten angefahren werden.

Mittlerweile wird der Heizölverbrauch jedes Kunden aufgrund der zuvor gesammelten Daten im vorhinein geschätzt. Auf kurzfristige Veränderungen kann sofort reagiert werden. Für die Berechnung einer Lieferung für eine ganze Woche mit über 100 Bestellungen werden von den Tourenplanern lediglich 2 Minuten benötigt.

In La Spezia, dem größten Containerumschlagplatz am Mittelmeer galt es, die Lade- und Entladeoperationen optimal zu planen (vgl. BBT (2003)).

Ein ähnliches Problem gab es bei Southwest Airlines in deren Frachtgeschäft, wo es Engpässe im gesamten Frachttransport- und Abfertigungssystem gab (vgl. Bonabeau/Meyer (2001)). Es wurde unnötig viel Zeit damit verbracht, Ladegut hin und her zu bewegen. Nach einer Analyse und späteren Einführung von Ameisen-Algorithmen sanken die Frachtumschlagsraten um etwa 80 Prozent, die Arbeitsbelastung ging für die Leute, die sich mit dem Frachtgut befassten, um 20 Prozent zurück und weniger Flugzeuge mussten voll beladen werden. Diese Verbesserungen ergaben insgesamt einen jährlichen Gewinnzuwachs von über zehn Millionen Dollar.

Ameisen-Algorithmen sind aber auch im Bereich von Netzwerk-Systemen, vor allem bei der Telekommunikation zu finden. Beim Forschungsinstitut von Hewlett-Packard in Boston entwickelten Wissenschaftler ein Computerprogramm, das, auf den einfachen Regeln der Ameisen aufbauend, Telefonanrufe über ein Telefonnetzwerk effizienter abwickelt sollte (vgl. Bonabeau/Meyer (2001)).

Von diesem Computerprogramm machten France Télécom, British Telecom und MCI WorldCom (USA) Gebrauch. Über die Telekommunikation hinaus, stellt das Internet einen großen Anwendungsbereich dar. Soll zum Beispiel eine E-Mail von einem Ort zum anderen geschickt werden, wird der Text zerstückelt, und jedes Datenpaket sucht sich seinen Weg von einem Knotenpunkt zum nächsten, bis zum Bestimmungsort (vgl. Factum (2001)). Dort wird die Nachricht wieder zusammengefügt. Auf dem Weg hinterlässt die E-Mail einen Programmcode, der nachfolgenden E-Mails angibt, welcher Weg der schnellste ist.

Diese Technik scheint allen anderen Routing-Methoden wie dem Internet-Protokoll überlegen zu sein, gemessen an der Maximierung des Datentransfers und der Minimierung von Verzögerungen (vgl. Bonabeau/Meyer (2001)).

Weitere Beispiele finden sich bei der Ablaufplanung der Lackier-Förderbänder bei DaimlerCrysler oder beim zweitgrößten Aluminiumhersteller Alcan für die Abstimmung von Maschinen, Schmelzöfen und Transportbändern (vgl. Schmundt (2000)). Dadurch konnte die Effizienz bei Alcan in einigen Bereichen um zehn Prozent gesteigert werden (vgl. Factum (2001)).

Ameisen-Systeme können, wie die Beispiele zeigen, in vielen Bereichen eingesetzt werden. Ein großer Vorteil der Systeme ist die Flexibilität und Anpassungsfähigkeit. Dadurch können sie auf kurzfristige bzw. dynamische Veränderungen gut reagieren. Ein Ameisen-Algorithmus kann einen „Pool“ an Alternativ-Lösungen neben der besten gefundenen Lösung haben, so dass er bei einer Veränderung des vorliegenden Problems, auf eine dieser Alternativ-Lösungen zurückreifen kann (vgl. Bonabeau et al. (2000)).

Schwierig festzusetzen ist der Faktor r, der die Stärke der Pheromonspur für die nächste Zeiteinheit festsetzt. Wird dieser zu hoch gesetzt, verdunsten die Spuren zu schnell. Bei der Konstruktion neuer Lösungen ist die Streuung dann so groß, dass der Algorithmus zu lange braucht, um sehr gute Lösungen zu finden. Diese bekommen die Ameisen normalerweise, wenn sie sich an den Pheromonspuren orientieren, mit denen vorangegangene Ameisen ihre Spuren markiert haben. Wenn man aber den Faktor r zu niedrig setzt, stagniert der Algorithmus zu schnell, und man läuft Gefahr, in suboptimalen Lösungen zu verweilen.

Im Vergleich zu anderen Heuristiken arbeiten Ameisen-Algorithmen nicht so gut bei Problemen, die komplett zufallsbedingt generiert werden müssen. Das liegt daran, dass die Ameisen-Algorithmen Teillösungen verstärken, die Teile aus vielen guten Lösungen darstellen. Je besser eine Gesamtlösung ist, der diese Teillösung angehört, desto stärker wird diese Teillösung verstärkt. Wenn es nun eine große Anzahl an Teillösungen gibt, die alle in etwa gleichgut sind und demnach alle zu guten Gesamtlösungen gehören könnten, können die Ameisen-Algorithmen nicht zwischen diesen Teillösungen differenzieren und bringen demnach auch keine guten Resultate (vgl. Bonabeau et al. (2000)).

Marco Dorigo äußert sich hingegen sehr optimistisch zu den Möglichkeiten der Ameisen-Algorithmen und traut ihnen eine große Zukunft zu, aufbauend auf den bereits zu diesem Zeitpunkt bereits vorliegenden guten Resultaten in den verschiedensten Anwendungsbereichen. „It can provide solutions to any kind of logistical problem“ (vgl. Sautter (2004)).

Abbildungsverzeichnis

Abbildung 1.1: Ameisen finden den kürzesten Weg. 3
Abbildung 1.2: künstliche Ameisen. 3
Abbildung 2.1: Kategorisierung von Ameisen-Algorithmen. 6
Abbildung 2.2: Ant-Q bei Oliver30 für verschiedene Übergangszustandsregeln. 15
Abbildung 2.3: Zeit, in der kooperative bzw. nicht-kooperative Ameisen das Optimum finden (aus Dorigo/Gambardella (1996c), Seite 11) 18
Abbildung 2.4: Kooperative Ameisen finden bessere Lösungen in kürzerer Zeit (aus Dorigo/Gambardella (1996c), Seite 11) 18
Abbildung 2.5: Anzahl der Zyklen, um ein lokales Optimum zu erreichen mit verschiedener Anzahl an elitären Ameisen (aus Dorigo et al. (1991), Seite 15) 21
Abbildung 2.6: Synchrone und asynchrone Parallelisierung (aus Bullnheimer et al. (1998), Seite 5 und Talbi et al. (2001), Seite 5) 27
Abbildung 2.7: Übersicht über die verschiedenen Ameisen-Algorithmen. 28
Abbildung 3.1: Behandelte Probleme aus der kombinatorischen Optimierung. 29
Abbildung 3.2: Konstruktion des multiplen Ameisen-Kolonie-Systems für das VRP mit Zeitfenstern (aus Gambardella et al. (1999) S. 6) 35
Abbildung 3.3: Verlauf der Geschwindigkeit (aus Donati et al. (2002), Seite 4) 38
Abbildung 3.4: Reisezeit für eine Kante der Länge 2 (aus Donati et al. (2002), Seite 5) 39
Abbildung 3.5: Lineares dynamisches Angleichen bei der Spurenverstärkung (aus Maniezzo (1998), Seite 7) 47
Abbildung 3.6: Disjunktiver Graph für ein Quadratisches Zuordnungsproblem.. 50
Abbildung 3.7: Disjunktives Bogenpaar zwischen Maschine M3 und Ort O2 51
Abbildung 3.8: Disjunktiver Graph für 4 Maschinen und 6 Orte. 54
Abbildung 3.9: Disjunktiver Graph für ein allgemeines Maschinenbelegungsmodell mit 4 Aufträgen und 3 Maschinen 57
Abbildung 3.10: Disjunktiver Teilgraph für Maschine 2. 58
Abbildung 3.9: Graph für ein SMTTP mit 3 Aufträgen (aus Bauer et al. (2000), Seite 6) 59
Abbildung 3.10: Sequential Ordering Problem, Instanz mit 4 Aufträgen. 62
Abbildung 3.11: Graph für ein OSP mit 4 Aufträgen und 3 Maschinen. 64
Abbildung 3.12: Disjunktiver Graph für ein FSP mit 4 Aufträgen und 3 Maschinen. 65
Abbildung 3.13: Teilgraph für die Reihenfolgen der Aufträge an den Maschinen. 66
Abbildung 3.14: Disjunktiver Graph für ein JSP mit 4 Aufträgen und 3 Maschinen. 71
Abbildung 3.15: Beispiel für eine Reihenfolge der Aufträge für ein JSP mit 4 Aufträgen und 3 Maschinen 73

Variablen, Parameter und Abkürzungen

A

Menge an Kanten

A

Kopplungsmatrix

a_ij

Element aus Kopplungsmatrix A

b_i

Zeitpunkt für den Beginn eines Zeitfensters

C

Kostenmatrix

C_j

Fertigstellungszeitpunkt insgesamt

c

Konstante

c’

veränderbarer Faktor

c_ij

Kosten

D

Distanzmatrix

d

Distanzvektor

d_i

Element aus Vektor d

d_ij

Distanz zwischen Knoten i und j

E

Menge an Kanten

e

Anzahl an elitären Ameisen

e_i

Zeitpunkt für das Ende eines Zeitfensters

e_ij

Kante aus der Menge E

F

Flussmatrix

F(j)

Menge an Knoten, die besucht werden können

FZ_j

Fertigstellungszeitpunkt von Auftrag j

f

Flussvektor

f_j

Element aus Vektor f

f_ij

Fluss zwischen Objekt i und j

g_ij

Funktion für zweifache Spurenaktualisierung

h, i, j, l

Laufindex

J

Anzahl an Aufträgen

K

Gesamtkapazität des Fahrzeugs

K_i

gesamte Nachfrage einer Tour

k

Index für die Ameisen

k_i

Nachfrage vom Kunden i

L^*

iterations- oder global beste Lösung

L¹

erste gefundene Lösung

LB

untere Schranke

L^gb

global beste Lösung

L^ib

iterations-beste Lösung

L_k

Lösung der k-ten Ameise

L_r

Lösung der k-ten Ameise

M

Anzahl an Maschinen

M_k

Speicher der k-ten Ameise; Tabu-Liste

M_k⁰

Speicher der Suchameisen

M_k¹

Speicher der Transportameisen

m

Anzahl an Ameisen

m⁰

Anzahl an Suchameisen

m¹

Anzahl an Transportameisen

m_j

Maschine j

NC

Zyklenzähler

NC_MAX

maximale Zyklenanzahl

n

Anzahl an Knoten/Aufträgen

O

Menge an Arbeitsgängen

O_i

Ort i

o_b

Startknoten

o_e

Endknoten

o_jm

Bearbeitung von Auftrag j an Maschine m, mit o_jm Î O

p

Wahrscheinlichkeits-Wert, mit 0<p<1

p_ij(t)

Wahrscheinlichkeit, zum Zeitpunkt t von i nach j zu gehen, mit 0<p_ij(t)<1

Q

Konstante

q₀

festgelegte Wahrscheinlichkeit, mit 0<q₀<1

q₁

gegebene Wahrscheinlichkeit

r

Rang einer Ameise

r₀

festgelegte Wahrscheinlichkeit, mit 0<r₀<1

S

Zufallsvariable, mit 0<S<1

s

Speicher-Index für den Speicher

T’

gesamte Bearbeitungszeit der bereits ausgewählten Aufträge

T^d

gesamte Verspätung

T_j

Verspätungszeit von Auftrag j

t

Zeitzähler

t_i^c

Ankunftszeit am Knoten i

t_j

Bearbeitungszeit von Auftrag j

^t_jh^w

Rüstzeit/Wartezeit zwischen Ende von Auftrag j und Anfang von Auftrag h

t_jm

Bearbeitungszeit von Auftrag j an Maschine m

t^w

Wartezeit

u

Anzahl an Knoten, die gewählt werden können

V

Menge an Knoten

V₁

Menge an Knoten mit allen Maschinen

V₂

Menge an Knoten mit allen Orten

v₀

Depot

v_i

Knoten aus der Menge V

w

Gewicht für die global beste Lösung

X

Matrix, mit _und

x_ij

Element aus Matrix X, mit x_ij Î [0;1]

z

Zielfunktionswert

z’

gesamte potenzielle Kosten

Durchschnitt der Lösungen aller Ameisen in einer Iteration

Dt_ij

Faktor für die Spurenverstärkung der Kante (i,j)

L^gb

Lösung mit minimierter Fahrzeit

L^max

ungültige Lösung mit maximierter Anzahl an Kunden in einer Tour

P

Permutation

T_ij

Summe von Spurenstärke für Auftrag j, mit

W

Menge der Städte, die noch auf der gleichen Tour besucht werden können

a

Parameter für den Einfluss der Spurenintensität

b

Parameter für den Einfluss der heuristischen Distanz

c

Parameter für den Einfluss des „Savings“-Werts, mit 0<c<1

d

Parameter für den Einfluss der Kapazitätsauslastung, mit 0<d<1

g

fixer Parameter

h_ij

Sichtbarkeit; heuristische Distanz zwischen i und j

j_i

Faktor für Angleichung der Spurenintensität, mit 0<j_i<1

k_ij

Kapazitätsauslastung

m_ij

„Savings“-Wert bei Aufnahme von Kante (v_i,v_j) in aktuelle Tour

p(j)

Zuordnung von j

p^gb(j)

global beste Zuordnung von j

q

Anzahl an eingesetzten Fahrzeugen

r

Spurenstärke, mit (1-r) = Verdunstungsfaktor der Spur, mit 0<r<1

r(t_ij^*)

Funktion für die Spurenstärke

r_l

Spurenstärke für lokale Spurenaktualisierung, mit 0<r_l<1

s_ij(t)

Geschwindigkeit zwischen Knoten i und j zum Zeitpunkt t

t₀

Startwert für die Spurenintensität

t_ij

Spur auf der Kante (i,j)

t^max

Obergrenze für Spurenintensität

t^min

Untergrenze für Spurenintensität

w

Anzahl an besten Ameisen

z

Zeitabschnitt, der mit dem Zeitpunkt t übereinstimmt

Literaturverzeichnis

Albayrak, S.; Garijo, F. J. (1998); Intelligent Agents for Telecommunication Applications, Second International Workshop, IATA ’98; Paris, France, Springer 1998

Alspector, J.; Goodman, R.; Brown, T. X. (1995); Application of Neural Networks to Telecommunications 2; Lawrence Erlbaum Publishing, Hillsdale, NJ, 1995

AntOptima (2004); http://www.antoptima.com/, Aktualisierung vom 20.07.04

Bauer, A.; Bullnheimer, B.; Hartl, R. F.; Strauss, C. (1999); An ant colony optimization approach for the single machine total tardiness problem; Proceedings of the 1999 Congress on Evolutionary Computation (CEC ’99); IEEE Press, Piscataway, NJ, 1999, Seite 1445-1450

Bauer, A.; Bullnheimer, B.; Hartl, R. F.; Strauss, C. (1999); Applying Ant Colony Optimization to solve the Single Machine Total Tardiness Problem; Report Series SFB “Adaptive Information System and Modelling in Economics and Management Science”; Volume 42, SFB Adaptive Information Systems and Modelling in Economics and Management Science, 1999

Bauer,A; Bullnheimer, B.; Hartl, R. F.; Strauss, C. (2000); Minimizing total tardiness an a single machine using ant colony optimization; Central European Journal of Operations Research; Volume 8, Issue 2, 2000, Seite 125-141

BBT (2003); Machen wir’s wie die Ameisen: Ameisenalgorithmen als Problemlöser; Bundesamt für Berufsbildung und Technologie, http://www.bbt.a dmin.ch/print/kti/ success/archiv/fh/d/idsia.htm,
Aktualisierung vom 20.07.04

Besten, M. den; Stützle, T.; Dorigo, M. (2000); Ant Colony Optimization for the Total Weighted Tardiness Problem; Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature; Schoenhauer, M.; Deb, K.; Rudolph, G.; Yao, X.; Lutton, E.; Merelo, J. J.; Schwefel, H.-S. (Eds.); Volume 1917 of Lecture Notes in Computer Science, Springer Verlag Berlin, 2000, Seite 611-620

Bianchi, L.; Gambardella, L. M.; Dorigo, M. (2002a); An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem; Proceedings of PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature; Volume 2439 of Lecture Notes in Computer Science. Springer, Berlin, Germany, 2002

Bianchi, L.; Gambardella, L. M.; Dorigo, M. (2002b); Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic; Proceedings of the Third International Workshop on Ant Algorithms; Lecture Notes In Computer Science, 2002, Seite 176 – 187

Bonabeau, E.; Henaux, F.; Guérin, S.; Snyers, D.; Kuntz, P.; Theraulaz, G. (1998); Routing in telecommunications networks with „smart“ ant-like agents; Intelligent Agents for Telecommunication Applications, Second International Workshop, IATA ’98, Albayrak, S.; Garijo, F. J.(Eds.); Paris, France, Springer 1998, Seite 60 – 71

Bonabeau, E.; Meyer, C. (2001); Schwarm-Intelligenz: Unternehmen lernen von Bienen und Ameisen; Harvard Business Manager; Volume 6, 2001, Seite 38-49

Bonabeau, E.; Dorigo, M.; Theraulaz, G. (2000); Inspiration for optimization from social insect behaviour; Nature; Volume 406, 2000, Seite 39-42

Bonabeau, E.; Dorigo, M.; Theraulaz, G. (1999); Swarm Intelligence: From Natural to Artificial Systems; Santa Fe Institute studies in the science of complexity, Oxford University Press, New York, NY, 1999

Botee, H. M.; Bonabeau, E. (1998); Evolving Ant Colony Optimization; Advances in Complex Systems; Stadler, P. F. (Ed.), Volume 1, Hermes Verlag, 1998, Seite 149 – 159

Brélaz, D. (1979); New Methods to Color the Vertices of a Graph; Management Science/Operations Research; Volume 22, Issue 4, 1979, Seite 251-256

Brucker, P. (1998); Scheduling Algorithms; 2. Auflage, Springer-Verlag Berlin Heidelberg 1998

Bullnheimer, B.; Hartl, R. F.; Strauß, C. (1997a); A new rank based version of the ant system – a computational study; Central European Journal of Operations Research and Economics, Volume 1, 1999, Seite 25 – 38

Bullnheimer, B.; Hartl, R. F.; Strauss, C. (1997b); An improved ant system algorithm for the vehicle routing problem; Annals of Operation Research: Nonlinear Economic Dynamics and Control, Volume 89, 1999, Seite 319 – 328

Bullnheimer, B. F.; Hartl, R. F.; Strauss, C. (1997c); Applying the Ant System to the Vehicle Routing Problem; Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization; Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C. (Eds.); Kluwer, 1999, S. 285 – 296

Bullnheimer, B. F.; Kotsis, G.; Strauß, C. (1998); Parallelization Strategies for the Ant System; High Perfomance Algorithms and Software in Nonlinear Optimization; Leone, R. De; Murli, A.; Pardalos, P.; Toraldo, G. (Eds.); Volume 24, Kluwer, 1998, Seite 87 – 100

Burkard, R. E.; Cela, E.; Pardalos, P. M.; Pitsoulis, L. S. (1998); The Quadratic Assignment Problem; Handbook of combinatorial optimisation; Kluwer Academic Publishers, 1998, Seite 241-337

Burkard, R. E. (2000); Zuordnungsprobleme – ein Streifzug durch die kombinatorische Optimierung; Zur Kunst des formalen Denkens; Burkard, R. E.; Maas, W.; Weibel, P. (Eds.), Passagen Verlag Wien, 2000, Seite 193-207

Burkard, R. E.; Fincke, U. (1983); The Asymptotic Probabilistic Behaviour of Quadratic Sum Assignment Problems; Zeitschrift für Operations Research; Volume 27, 1983, Seite 73-81

Burkard, R. E.; Maas, W.; Weibel, P. (2000); Zur Kunst des formalen Denkens; Passagen Verlag Wien, 2000

Chiarandini, M.; Stützle, T. (2002); An application of Iterated Local Search to Graph Coloring Problem; Proceedings of the Computational Symposium on Graph Coloring and its Generalization; Johnson, D. S.; Mehrotra, A.; Trick, M. (Eds.); Ithaca, New York, USA, 2002, Seite 112-125

Colorni, A.; Dorigo, M.; Maniezzo, V. (1992a); An investigation of some properties of an “Ant algorithm”; Proceedings of the Parallel Problem Solving from Nature Conference; Männer, R.; Manderick, B. (Eds.); Elsevier Publishing, Brussels, Belgium, 1992, Seite 509-520

Colorni, A.; Dorigo, M.; Maniezzo, V. (1992b); Distributed Optimization by Ant Colonies; Proceedings of the First European Conference on Artificial Life; Varela, F.; Bourgine, P. (Eds.); Elsevier Publishing, Paris, France, 1992, Seite 134-142

Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M. (1994); Ant system for Job-shop scheduling; JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science; Volume 34, Issue 1, 1994, Seite 39-53

Comellas, F.; Ozón, J. (1998); An Ant Algorithm for the Graph Colouring Problem; ANTS’98 – From Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization; Brussels, Belgium, 1998

Comellas, F.; Ozón, J. (1995); Graph Coloring Algorithms for Assignment Problem in Radio Networks; Application of Neural Networks to Telecommunications 2; Alspector, J.; Goodman, R.; Brown, T. X. (Eds.); Lawrence Erlbaum Publishing, Hillsdale, NJ, 1995, Seite 49-56

Corne, D.; Dorigo, M.; Glover, F. (1999); New Ideas in Optimization; McGraw-Hill, 1999

Corsten, H. (2000); Produktionswirtschaft: Einführung in das industrielle Produktionsmanagement; 9. Auflage, Oldenbourg Wissenschaftsverlag 2000

Costa, D.; Hertz, A. (1997); Ants Can Colour Graphs; The Journal of the Operational Research Society; Volume 48, Issue 3, 1997, Seite 295-305

Di Caro, G.; Dorigo, M. (1998); An adaptive multi-agent routing algorithm inspired by ants behavior; Proceedings of PERT98 – Fifth Annual Australasian Conference on Parallel and Real-Time Systems; Adelaide, Australia, 1998

Di Caro, G.; Dorigo, M. (1999); AntNet: A mobile agents approach to adaptive routing; A Quarterly in Artificial Intelligence; Volume 12, Issue 3-4, 1999, Seite 2-37

Diestel, R. (1996); Graphentheorie; Springer-Verlag Berlin Heidelberg 1996

Dörner, K.; Gronalt, M.; Hartl, R. F.; Reimann, M.; Strauss, C.; Stummer, M. (2002); SavingsAnts for the Vehicle Routing Problem; EvoWorkshop 2002, LNCS 2279; Springer-Verlag Berlin Heidelberg, 2002, Seite 11-20

Domschke, W. (1997); Logistik: Rundreisen und Touren; 4. Auflage, R. Oldenbourg Verlag München, 1997

Domschke, W.; Drexl, A. (1990); Logistik: Standorte; 3. Auflage, R. Oldenbourg Verlag München, 1990

Domschke, W. (1995); Logistik: Transport; 4. Auflage, R. Oldenbourg Verlag München, 1995

Donati, A. V.; Gambardella, L. M.; Rizzoli, A. E.; Casagrande, N.; Montemanni, R. (2002); Time Dependent Vehicle Routing Problem with an Ant Colony System; Technical Report IDSIA-02-03; Istituto Dalle Molle di Studi sull'Intelligenza Artficiale, 2002

Dorigo, M. (2001); Ant Algorithms Solve Difficult Optimization Problems; Advances in Artificial Life, Proceedings of the Sixth European Conference on Artificial Life, LNAI 2159; Springer-Verlag, 2001, Seite 11-22

Dorigo, M.; Di Caro, G. (1999); The Ant Colony Optimization Meta-Heuristic; New Ideas in Optimization; Corne, D.; Dorigo, M.; Glover, F. (Eds.); McGraw-Hill, 1999, Seite 11-32

Dorigo, M.; Di Caro, G.; Gambardella, L. M. (1998); Ant Algorithms for Discrete Optimization; Artificial Life; Volume 5, Issue 2, The MIT Press, 1999, Seite 137-172

Dorigo, M.; Di Caro, G.; Sampels, M. (2002a); Ant Algorithms, Third International Workshop, ANTS 2002; Lecture Notes in Computer Science, Volume 2463, Springer 2002

Dorigo, M.; Gambardella, L. M. (1996a); A study of some properties of Ant-Q; Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature; Voigt, H.-M.; Ebeling, W.; Rechenberg, I.; Schwefel, H.-S. (Eds.); Springer-Verlag, Berlin, Germany, 1996, Seite 656-665

Dorigo, M.; Gambardella, L. M. (1996b); Ant colonies for the traveling salesman problem; BioSystems, Volume 43, 1997, Seite 73-81

Dorigo, M.; Gambardella, L. M. (1996c); Ant colony system: A cooperative learning approach to the traveling salesman problem; IEEE Transactions on Evolutionary Computation; Volume 1, Issue 1, 1997, Seite 53-66

Dorigo, M.; Maniezzo, V.; Colorni, A. (1991a); Ant system: An autocalatytic optimizing prozess; Technical Report No. 91-016 Revised; Politencnico di Milano, Italy; 1991

Dorigo, M.; Maniezzo, V.; Colorni, A. (1991b); Positive feedback as a search strategy; Technical Report No. 91-016; Politecnico di Milano, Italy, 1991

Dorigo, M.; Maniezzo, V.; Colorni, A. (1996); The Ant System: Optimizaion by a colony of cooperating agents; IEEE Transactions on Systems, Man, and Cybernetics-Part B; Volume 26, Issue 1, 1996, Seite 29-41

Dorigo, M.; Stützle, T. (2001); An Experimental Study of the Simple Ant Colony Optimization Algorithm; Proceedings of 2001 WSES International Conference on Evolutionary Computation (EC’01); Mastorakis, N. (Ed.), WSES-Press International, 2001, Seite 253-258

Dorigo, M.; Zlochin, M.; Meuleau, N.; B. (2002b); Updating ACO Pheromones Using Stochastic Gradient Ascent and Cross-Entropy Methods; EvoWorkshops 2002, LNCS 2279; Springer-Verlag Berlin Heidelberg 2002, Seite 21-30

Escudero, L. F.(1988); An inexact algorithm for the sequential ordering problem; System Science; Forth EURO Summer Institute Special Issue; European Journal of Operations Research; Mercer, A.; C. Tilanus, B.; Zimmermann, H.-J. (Eds.); Volume 37; Elsevier Science Publishers, North Holland, 1988, Seite 236-249

Eiben, A. E.; Bäck, T.; Schoenauer, M.; Schwefel, H.-P. (1998); Proceedings of Parallel Problem Solving from Nature – PPSN-V; Volume 1498, Amsterdam, Springer-Verlag, 1998

FactumOnline (2001); Ameise als Vorbild; http://www.factum- magazin ch/whats_new/news.cgi?v= archive&c=Internet&id=12211 004522.shtml, Aktualisierung vom 20.07.04

Fidanova, S. (2002); ACO Algorithm with Additional Reinforcement; Ant Algorithms, Third International Workshop, ANTS 2002; Dorigo, M.; Di Caro, G.; Sampels, M. (Eds.): Brussels, Belgium, Lecture Notes in Computer Science, Volume 2463, Springer 2002, Seite 292-293

Finke, G.; Burkard, R. E.; Rendl, F.(1987); Quadratic Assignment Problems; Annals of Discrete Mathematics: Surreys in Combinatorial Optimization; Martello, S.; Caporte, G.; Minoux, M.; Riberio ,C. (Eds.); Volume 31, Elsevier Science Publishers, 1987, Seite 61-82

Gambardella, L. M.; Dorigo, M. (2000); An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem; INFORMS Journal on Computing; Volume 12, Issue 3, 2000, Seite 237-255

Gambardella, L. M.; Taillard, E. D. (1999); Dorigo, Marco; Ant Colonies for the Quadratic Assignment Problem; Journal of the Operational Research Society; Volume 50, 1999, Seite 167-176

Gambardella, L. M.; Dorigo, M. (1995); Ant-Q: A Reinforcement Learning approach to the traveling salesman problem; Twelfth International Conference on Machine Learning; Morgan Kaufmann, 1995, Seite 252-260

Gambardella, L. M.; Dorigo, M. (1997); HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem; Technical Report IDSIA; Volume 11, Lugano, Switzerland, 1997

Gambardella, L. M.; Dorigo, M. (1996); Solving Symmetric and Asymmetric TSPs by Ant Colonies; ICEC96, Proceedings of the IEEE Conference on Evolutionary Computation; Nagoya, Japan, 1996

Gambardella, L. M.; Taillard, E.; Agazzi, G.(1999); MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows; New Ideas in Optimization; Corne, D.; Dorigo, M.; Glover, F. (Eds.); McGraw-Hill, London, UK, 1999, Seite 63-76

Garey, M. R.; Johnson, D. (1979); Computers and Intractability: A Guide to the Theory of NP-Completeness; Bell Telephone Laboratories, 1979

Gillett, B. E.; Miller, L. R. (1974); A Heuristic Algorithm for the Vehicle-Dispatch Problem; Operations Research; Volume 22, Issue 2, 1974, Seite 340-349

Glover, F. (1989); Tabu Search – Part I; ORSA Journal an Computing; Volume 1, Issue 3, 1989, Seite 190-206

Glover, F. (1990); Tabu Search – Part II; ORSA Journal on Computing; Volume 2, Issue 1, 1990, Seite 4-32

Günther, H.-O.; Tempelmeier, H. (2003); Produktion und Logistik; 5. Auflage, Springer-Verlag Berlin Heidelberg, 2003

Guntsch, M.; Middndorf, M.; Schmeck, H. (2001); An Ant Colony Optimization Approach to Dynamic TSP; Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001); San Fransisco, Californien, Morgan Kaufmann, 2001, Seite 860 – 867

Johnson, D. S.; Mehrotra, A.; Trick, M. (2002); Proceedings of the Computational Symposium on Graph Coloring and its Generalization; Ithaca, New York, USA, 2002

Kawamura, H.; Yamamoto, M.; Suzuki, K.; Ohuchi, A. (2000); Multiple Ant Colonies Algorithm Based on Colony Level Interactions; IEICE Transactions on Fundamentals; Volume E83-A, Issue 2, 2000, Seite 371-379

Kindvater, G. A. P.; Lenstra, J. K. (1989); The Parallel Complexity of TSP Heuristics; Journal of Algorithms; Volume 10, 1989, Seite 249-270

Kistner, K.-P. (2003); Optimierungsmethoden, Einführung in die Unternehmensforschung für Wirtschaftswissenschaftler; 3. Auflage, Physica-Verlag Heidelberg, 2003

Kistner, K.-P.; Steven, M. (2001); Produktionsplanung; 3. Auflage, Physica-Verlag Heidelberg, 2001

Koopmans, T. C.; Beckmann M. (1957); Assignment Problems and the Location of Economic Activities; Econometrica; Volume 25, Issue 1, 1957, Seite 53-76

Latz, T. (1997); Entscheidungsmodelle der Ablaufplanung; Mathematische Programme für Shop-Scheduling-Probleme; Deutscher Universitäts-Verlag, Gabler Verlag Wiesbaden, 1997

Leone, R. De; Murli, A.; Pardalos, P.; Toraldo, G. (1998); High Perfomance Algorithms and Software in Nonlinear Optimization; Kluwer, 1998

Li, Y.; Gong, S. (2003); Dynamic ant colony optimisation for TSP; The International Journal of Advanced Manufacturing Technology; Volume 22, Issue 7-8, Springer-Verlag London, 2003, Seite 528 – 533

Männer, R.; Manderick, B. (1992); Proceedings of the Parallel Problem Solving from Nature Conference; Elsevier Publishing, Brussels, Belgium, 1992

Mainzer, K. (2003); Im Zeitalter der denkenden Maschinen; Technology Review; Volume 12, 2003, Seite 87-97

Malandraki, C.; Daskin, M. S. (1992); Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms; Transportation Science; Volume 26, Issue 3, Operations Research Society of America, 1992, Seite 185-200

Maniezzo, V. (1998); Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem; Technical Report CSR 98-1, C. L. In Science dell’Informtione; Bologna, Italy, 1998

Maniezzo, V.; Colorni, A. (1999); The ant system applied to the quadratic assignment problem; IEEE Transactions on Knowledge and Data Engineering; Volume11, Issue 5, 1999, Seite 769-778

Maniezzo, V.; Corloni, A.; Dorigo, M. (1994); The Ant System applied to the Quadratic Assignment Problem; Technical Report 94/28, IRIDIA; Université de Bruxelles, Bruxelles, Belgium, 1994

Maniezzo, V.; Gambardella, L. M.; Luigi, F. de (2004); Ant Colony Optimization; New Optimization Techniques in Engineering; Onwubolu, G. C.; Babu, B. V. (Eds.); Springer-Verlag Berlin Heidelberg, 2004, Seite 101-117

Martello, S.; Caporte, G.; Minoux, M.; Riberio ,C. (1987); Annals of Discrete Mathematics: Surreys in Combinatorial Optimization; Volume 31, Elsevier Science Publishers, 1987

Mastorakis, N. (2001); Proceedings of 2001 WSES International Conference on Evolutionary Computation (EC’01); WSES-Press International, 2001

Mastrolilli, M.; Gambardella, L. M. (2000); Effective Neighborhood Functions for the Flexible Job Shop Problem; Journal of Scheduling, Volume 3, Issue 1, 2000, Seite 3-20

Matthäus, F. (1978); Tourenplanung: Verfahren zur Einsatzdisposition von Fuhrparks; Toeche-Mittler Verlag Darmstadt, 1978

Mercer, A.; C. Tilanus, B.; Zimmermann, H.-J (1988); System Science; Forth EURO Summer Institute Special Issue; European Journal of Operations Research; Volume 37; Elsevier Science Publishers, North Holland, 1988

Merkle, D.; Middendorf, M. (2000); An Ant Algorithm with a new Pheromone Evaluation Rule for Total Tardiness Problems; Real-World Applications of Evolutionary Computing: Proceedings of EvoWorkhops 2000; Springer Verlag, 2000, Seite 287 – 296

Mertens, P. (2001); Integrierte Informationsverarbeitung 1: Operative Systeme in der Industrie; 13. Auflage, Betriebswirtschaftlicher Verlag Gabler, Wiesbaden 2001

Middendorf, M.; Reischle, F.; Schmeck, H. (2000); Information Exchange in Multi Colony Ant Algorithm; Parallel and Distributed Computing: Proceeding of the Fifteenth IPDPS Workshop 2000; Springer Verlag, 2000, Seite 645-652

Montemanni, R.; Gambardella, L. M.; Rizzoli, A. E.; Donati, A. V. (2003); A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System; Proceedings of ODYSSEUS 2003, Palermo, Italy, 2003

Montgomery, J. (2002); Towards a Systematic Problem Classification Scheme for Ant Colony Optimisation; Technical Report TR02-15; Faculty of Information Technology, Bond University, Australia, 2002

Montgomery, J.; Randall, M. (2002a); Alternative Pheromone Applications for Ant Colony Optimisation; Technical Report TR02-07; Faculty of Information Technology, Bond University, Australia, 2002

Montgomery J.; Randall, M. (2002b); Anti-pheromone as a Tool for Better Exploration of Search Space; Proceedings of the Third International Workshop on Ant Algorithms, ANTS 2002; Brussels, Belgium, 2002

Morad, N. (2000); Genetic Algorithms Optimization for the Machine Layout Problem; International Journal of the Computer, the Internet and Management; Volume 8 Issue 1, 2000

Nawaz, M.; Enscore Jr., E. E.; Ham, I. (1983); A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem; OMEGA, The International Journal of Management Science; Volume 11, Issue 1, Pergamon Press Ltd. 1983, Seite 91-95

Neumann, K. (1996); Produktions- und Operations-Management; Springer-Verlag Berlin Heidelberg 1996

Oliver, I. M.; Smith, D.J.; Holland, J. R. C. (1987); A study of permutation crossover operators an the traveling salesman problem; Genetic Algorithms and their Applications: Proceedings of the Second International Conference an Genetic Algorithm; Camebridge, Massachusetts, 1987

Onwubolu, G. C.; Babu, B. V. (2004); New Optimization Techniques in Engineering; Springer-Verlag Berlin Heidelberg, 2004

Rajendran, C. (1993); Heuristic algorithm for scheduling in a flowshop to minimize total flowtime; International Journal of Production Economics; Volume 29, Elsevier Science Publishers, 1993

Rajendran, C.; Ziegler, H. (2004); Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs; European Journal of Operations Research; Volume 155, 2004, Seite 426-438

Randall, M.; Montgomery, J. (2002); Candidate Set Strategies for Ant Colony Optimisation; Proceedings of the Third International Workshop on Ant Algorithms, ANTS 2002; Brussels, Belgium, 2002

Reimann, M.; Doerner, K.; Hartl, R. F. (2003); Analyzing a Unified Ant System for the VRP and Some of Its Variants; Applications of Evolutionary Computing: EvoWorkshops 2003: EvoBIO, EvoCOP, EvolASP, EvoMUSART, EvoROB, and EvoSTIM. Proceedings; Essex, UK, Springer-Verlag, 2003, Seite 300-310

Russell, S.; Norvig, P. (2003); Artificial Intelligence, A Modern Approach; 2. Auflage, Pearson Education, Inc., Upper Soddle River, New Jersey, 2003

Sautter, U. (2004); Insect Power; http://www.time.com/europe/ specials/ff/trip4/ants.html, Aktualisierung vom 20.07.04

Schmundt, H. (2000); Duft der Daten; Der Spiegel, Volume 46, 2000, Seite 264

Schoenhauer, M.; Deb, K.; Rudolph, G.; Yao, X.; Lutton, E.; Merelo, J. J.; Schwefel, H.-S. (2000); Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature; Volume 1917 of Lecture Notes in Computer Science, Springer Verlag Berlin, 2000

Smith, G. D.; Steele N. C.; Albrecht, R. F. (1998); Proceedings of Artificial Neural Nets and Genetic Algorithms 1997; Springer Verlag Wien, 1998

Stadler, P. F. (1998); Advances in Complex Systems; Volume 1, Hermes Verlag, 1998

Stamer, H. (2001); Ant Algorithmen für kombinatorische Optimierungsprobleme; Seminararbeit, Institut für Informatik, Universität Leipzig, 2001

Stamer, H. (2003); Recruiting Ant Colony System (RACS); http://gaos.org/~ stamer/ Aktualisierung vom 24.03.04

Stützle, T. (1997a); An Ant Approach to the Flow Shop Problem; Proceedings of EUFIT’98; Aachen, 1998, Seite 1560-1564

Stützle, T. (1998a); Applying Iterated Local Search to the Permutation Flow Shop Problem; Technical Report AIDA-98-04; Darmstadt University of Technology, Computer Science Department, Intellectics Group, 1998

Stützle, T. (1997b); MAX-MIN, Ant System for Quadratic Assignment Problems; Technical Report AIDA-97-04; Darmstadt University of Technology, Computer Science Department, Intellectic Group, 1997

Stützle, T. (1998b); Parallelization Strategies for Ant Colony Optimization; Proceedings of Parallel Problem Solving from Nature – PPSN-V; Eiben, A. E.; Bäck, T.; Schoenauer, M.; Schwefel, H.-P. (Eds.); Volume 1498, Amsterdam, Springer-Verlag, 1998, Seite 722-731

Stützle, T.; Dorigo, M. (1999a); ACO Agrithms for the Quadratic Assignment Problem; New Ideas in Optimization; Corne, D.; Dorigo, M. Glover, F. (Eds.); McGraw-Hill, 1999

Stützle, T.; Dorigo, M. (1999b); ACO Algorithms for the Traveling Salesman Problem; Evolutionary Algorithms in Engineering and Computer Science; 1999, Seite 163-183

Stützle, T.; Hoos, H. H. (1998a); Ameisenalgorithmen zur Lösung kombinatorischer Optimierungsprobleme; Leipziger Informatiktage (LIT’98); 1998

Stützle, T.; Hoos, H. (1996); Improving the Ant System: A Detailed Report on the MAX-MIN Ant System; Technical Report AIDA-96-12; Darmstadt University of Technology, Computer Science Department, Intellectics Group, 1996

Stützle, T.; Hoos, H. (1998b); Improvements on the Ant-System: Introducing the MAX-MIN Ant-System; Proceedings of Artificial Neural Nets and Genetic Algorithms 1997; Smith, G. D.; Steele N. C.; Albrecht, R. F. (Eds.); Springer Verlag Wien, 1998, Seite 245-249

Stützle, T.; Hoos, H. (1999); MAX-MIN Ant System; Future Generation Computer System; Volume 16, Issue 8, 2000, Seite 889-914

Stützle, T.; Hoos, H. (1997a); Max-Min Ant System and local search for the traveling salesman problem; Proceedings of the IEEE International Conference on Evolutionary Computation; Indianapolis, USA, 1997, Seite 308-313

Stützle, T.; Hoos, H. (1997b); Max-Min Ant system and local search for combinatorial optimization problems; Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization; Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C. (Eds.); Kluwer Acadamic Publishers, 1998, Seite 313-329

Sumpter, D. J. T.; Blanchard, G. B.; Broomhead, D. S. (2001); Ants and Agents: a Process Algebra Approach to Modelling Ant Colony Behaviour; Bulletin of Mathematical Biology; Volume 63, 2001, Seite 951-980

Taillard, E. D.; Gambardella, L. M. (1997); Adaptive Memories for the Quadratic Assignment Problem; Technical Report IDSIA-87-97; IDSIA, Lugano, Switzerland, 1997

Talbi, E.; Roux, O.; Fonlupt, C.; Robillard, D. (2001); Parallel Ant Colonies for Combinatorial Optimization Problems; Future Generation Computer Systems; Volume 17, 2001, Seite 441-449

Varela, F.; Bourgine, P. (1992); Proceedings of the First European Conference on Artificial Life; Elsevier Publishing, Paris, France, 1992

Voigt, H.-M.; Ebeling, W.; Rechenberg, I.; Schwefel, H.-S. (1996); Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature; Springer-Verlag, Berlin, Germany, 1996

Volkmann, L. (1991); Graphen und Digrapen: Eine Einführung in die Graphentheorie; Springer-Verlag Wien, 1991

Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C. (1999); Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization; Kluwer, 1999

Weiß, G.; Sen, S. (1996); Adaption and Learning in Multi-Agent Systems: IJCAI’95 Workshop, Montréal, Canada, 1995, Proceedings; Lecture notes in computer science; Volume 1042; Springer-Verlag Berlin Heidelberg, 1996

Weiß, G. (1999); Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence; Massachusetts Institute of Technology Press, Cambridge, Massachusetts, London, England, 1999

Zwaan, S. van der; Marques, C. (1999); Ant Colony Optimization for Job Shop Scheduling; Proceedings of the third Workshop on Genetic Algorithms and Artificial Life; 1999