Betriebswirtschaftliche Anwendungen für Ameisen-Systeme


Diplomarbeit, 2004
98 Seiten, Note: 3,0

Gratis online lesen

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 dij von einer Stadt i zur Stadt j ist gleich der Entfernung dji 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 tij(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 tij(t) die Intensität der Pheromonspur auf dem Pfad vom Knoten i zum Knoten j zum Zeitpunkt t, während hij 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/dij ergibt. In Maniezzo (1998) (Seite 4) werden die beiden Faktoren tij(t) und hij 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.

Mk 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 NCMAX 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 pij(t) und Mk

-  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 tij(0) und Dtij:=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 Mk(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 pij(t);
    bewege die Ameise zu dieser Stadt j;
    füge die Stadt j in Mk(s) ein}

  4. für k:=1 bis m tue {
    berechne die Länge der Tour Lk aus der Speicher-Liste Mk;

    mit }

  5. Spurenverstärkung
    für jede Kante (i,j) berechne tij(t+n) gemäß der Gleichung
    tij(t+n) = rtij(t)+Dtij;
    setze t:=t+n und NC:=NC+1;
    für jede Kante (i,j) setze Dtij:=0;

speichere die bislang kürzeste gefundene Tour;
wenn (NC<NCMAX) 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

Dtij(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 rl ist die Spurenstärke, so dass (1-rl) 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/dij 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, tmax und tmin, 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 tmax und tmin 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 tmax auf

  (2.7)

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

In der Initialisierungsphase des Algorithmus werden alle Spuren auf den Maximalwert tmax 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 tmin und tmin 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 q0 (0<q0<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-q0) 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, t0=1/(durchschnittliche Länge der Kanten*n), q0=0.9, a=0.1, g=0.3, Q=10, m=n. Dabei ist t0 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 q0=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 q0 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 rl 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 Dtij.

Der Wert für Dtij 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 Dtij durch Formel (2.12) berechnet werden:
        (2.12)

  • Dtij wird auf t0 gesetzt, wobei t0 der Ausgangswert der Spurenstärke für die Kante (i,j) ist.

  • Dtij 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 Dtij=t0 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 Dtij=t0=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 gij können gute Lösungen schneller gefunden werden. Die Funktion gij 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 q0 in Formel (2.9) müssen die Werte für tmin und tmax enger beieinander liegen. Denn für hohe q0-Werte wird fast immer die best-mögliche Wahl getroffen, da mit der Wahrscheinlichkeit q0 der Weg mit maximalem -Wert gewählt wird. Dies ist ebenso für einen kleineren q0-Wert der Fall, wenn der Unterschied zwischen tmin und tmax 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 tmax durch einen zu bestimmenden Faktor f zu beschränken:

tmax=c*tmin  (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 (ASelite) 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, Lgb 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 (ASrank). 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 Lgb 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. Lr 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 ASelite und ASrank. 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:


  • m0 Suchameisen durchsuchen die Umgebung nach Futter

  • m1 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 m0 Suchameisen Lösungen anhand ihrer Speicher Mk0 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 m1 Transportameisen rekrutiert für die Wege der r0 iterations-besten Ameisen. Die Transportameisen werden zufällig in eine Stadt gesetzt und konstruieren neue Touren, indem sie sich an ihrem Speicher Mk1 und drei möglichen Auswahlmöglichkeiten in Formel (2.19) für die nächste Stadt orientieren. Man hat nun zwei Wahrscheinlichkeits-Parameter q0 und r0.

  (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 tij;
Verteile m0 Suchameisen zufällig auf die Städte;
Setze t:= 0 und NC:=0 (t ist Zeitzähler und NC ist Zyklenzähler);

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

3.  Spurenverstärkung m0
Setze
die neue Pheromonintensität tij für alle Verbindungen;
rekrutiere jeweils r1 Transportameisen für die r0 besten“ Suchameisen}

4.  Konstruktion m1
für k=1 bis m0*m1
wähle einen beliebigen Startpunkt;
wiederhole, bis MkT voll {
wähle mit Wahrscheinlichkeit q1 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 m1
Berechne die Gesamtlänge Lk. der k-ten Transportameise;
Setze die neue Pheromonintensität tij für alle Verbindungen}

6.  Lasse alle Ameisen zum Nest zurückkehren.

Der Wahrscheinlichkeits-Wert q1 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 ji Î [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 ji und jj, also (ji+jj)/2, statt ji wählen. Eine eingefügte Stadt i erhält immer den Faktor ji=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={v0, v1, ..., vn} eine Menge an Knoten und A={(vi,vj):i¹j} eine Menge an Kanten ist. Der Knoten v0 ist das Depot, die übrigen Knoten von V markieren die Städte bzw. Kunden. Jede Kante ist mit dem Wert dij gewichtet, also mit der Entfernung (bzw. Reisezeit oder Reisekosten) zwischen Knoten i und Knoten j. Jeder Kunde in vi hat eine Nachfrage ki (mit k0=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 tij auf der Kante (vi,vj) und die Stärke der Sichtbarkeit hij (mit hij=1/dij) entscheidend.

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

mij=di0+d0j-dij   (3.2)

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

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

Mit diesen beiden neuen Kriterien kann eine neue Wahrscheinlichkeitsformel (3.3) aufgestellt werden, anhand derer der Kunde vj nach dem Kunden vi 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={vj Î V: vj kann noch besucht werden} Ç {v0}. 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 (vi,vj) 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. Lgb ist die Länge der global besten Tour.

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

hij = di0 + d0j – c1dij + c2|di0 – d0j|  (3.5)

Die Stadt vj 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 [bi, ei] für jeden Knoten vi (i=0,...,n), innerhalb derer jeder Kunde beliefert werden muss. Der Wert bi bezeichnet den Anfangszeitpunkt und ei den Endzeitpunkt des Zeitfensters. Die Werte für das Depot bedeuten, dass für jedes Fahrzeug b0 der früheste Startzeitpunkt vom und e0 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 vi (i=1,...,n) mindestens genauso groß sein muss wie bi und die Ankunftszeit an jedem Knoten vi nicht später sein darf als ei. Sollte das Fahrzeug vor dem Zeitpunkt bi am Kunden vi 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
Lgb als mögliche Startlösung mit Hilfe einer „nearest neighbour“ Heuristik;

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

Die Startlösung für Lgb 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 Lgb, 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 Lmax ebenfalls gespeichert. Bei der Kolonie „ACS-Zeit“ wird lediglich die Fahrzeit mit der gleichen Anzahl an Fahrzeugen wie bei Lgb 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

Lmax und Lgb sind die Längen der Gesamtlösungen Lmax bzw. Lgb. Die beste Lösung aus beiden Systemen wird übernommen und als global beste Länge Lgb 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 (sij(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  sij (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 (dij*sij(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 q0 und r0 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 q0=0.9 und r0=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 hij wird nun durch Formel (3.11) berechnet.

  (3.11)

hij 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 dij*sij(t) ist die Reisezeit zum Zeitpunkt t vom Knoten i zum Knoten j. tw>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 ei 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/Lk 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=[dih]

  • Eine Matrix des Flusses zwischen Objekt j und k: F=[fjk]

  • Eine Matrix der Zuordnungskosten von Aktivität j an Ort i: C=[cij]

Die Entfernungen dih sind durch dih < dil+dlh (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) cij 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 xij 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)

xij Î (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 Mk, 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 hij jetzt nicht als Kehrwert der Entfernungen 1/dij, sondern als Kehrwert eines Elements aus der sogenannten Kopplungs-Matrix 1/aij. 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 aij 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 di aus dem Vektor d ist, desto zentraler liegt dieser Ort i. Je höher der Wert fj 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*fT 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 Dtij verstärkt, so dass gilt:

  (3.17)

mit

Q ist ein fixer Parameter und Lk 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 hij:=1/aij;
    Verteile alle m Ameisen auf die Knoten i;

  2. Konstruktion
    Für k:=1 bis m
      wiederhole bis Mk 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 Ï Mk, dem   das Objekt zugeordnet werden soll;
      Nimm den gewählten Ort in Mk der k-ten Ameise auf.};
      Für k:=1 bis m
      Berechne Lk;
      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) Dtij:=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 tij und hij 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 t0 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.

t0

-t0

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 Lgb 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 tij 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 tij 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 t0.

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 (m1,...,m5), die 5 Orten (O1,...,O5) 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 vj und Orte vi, mit V={vi,vj} und i,j=1,...,5. Die Menge der Kanten besteht aus Kanten eij, 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 mj (j=1,...,5) zu einem Ort Oi (i=1,...,5) führt, hat die Länge di/tji. Der Faktor tji gibt die Güte an, die Maschine mj einem Ort Oi zuzuordnen, während di aus Vektor d die Distanz von einem Ort zu allen anderen angibt. Je größer der Wert tji(t) ist, desto geringer ist die heuristische Distanz zwischen mj und Oi. Eine Kopplung (i,j) wird dann eher gewählt. Ein (roter) Pfeil, der von einem Ort Oi in einer Maschine mj endet, hat die Länge 1/fj. Diese Länge entspricht dem Fluss zwischen der Maschine mj und allen anderen Maschinen und kann aus dem Vektor f abgelesen werden. Je größer der Fluss-Level fi von Maschine i ist, desto kürzer ist dieser Pfeil.

In Abbildung 3.7 ist ein disjunktives Bogenpaar für die Verbindung zwischen Ort O2 und Maschine m3 dargestellt.

Abbildung 3.7: Disjunktives Bogenpaar zwischen Maschine M3 und Ort O2

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

Um einen Ameisen-Algorithmus auf diesen Graph anzuwenden, bildet man zwei Mengen an Knoten V1 und V2, mit V1={m1,...m5} und V2={O1,...,O5}. 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 Mk 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 V1 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 fj-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 pji(t) in Formel (3.22) wählt eine Ameise den Knoten i, wenn sie sich im Knoten j befindet. Diese Entscheidung wird beeinflusst von tij, 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 tij und hi noch zusätzlich beeinflussen.

  (3.22)

mit

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

Mit einer Wahrscheinlichkeit pij(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 Mk ergibt. In diesem stehen nun abwechselnd eine Maschine und ein Ort in einer bestimmten Reichenfolge, z. B. {m1, O3, m3, O4, m4, O1, m2, O5, m5, O2}. Durch diese Reihenfolge lassen sich die Zuordnungen der Maschinen zu den jeweiligen Orte vornehmen, und die Permutation ergibt sich durch:

Pk =   {m1 wird O3 zugeordnet; m2 wird O5 zugeordnet; m3 wird O4 zugeordnet; m4 wird O1 zugeordnet; m5 wird O2 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 V1 genau einmal besucht werden muss. Dadurch findet man für jede Maschine genau eine Zuordnung. Die Konstruktion ist beendet, wenn kein Knoten Ï Mk mehr besucht werden kann.

Bei der Konstruktion einer Lösung startet man ebenso in einem Knoten aus der Menge V1 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 ojm aus einer Menge O={...ojm...}. Jeder Arbeitsgang ojm Î O gehört zum Auftrag j und muss an der Maschine m für tjm 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 ojm aus der Menge O, einen Startknoten ob und einen Endknoten oe.

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 ojm entspricht der Bearbeitungsdauer tjm des j-ten Auftrags an der m-ten Maschine. Ein Pfeil, der im Knoten oe 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 tj Zeiteinheiten und der Fertigungszeitpunkt für jeden Auftrag j ist gegeben durch FZj. Der Fertigstellungszeitpunkt („completition time“) Cj ergibt sich durch die erhaltene Reihefolge der Aufträge. Die sich daraus ergebene Verspätungszeit Tj berechnet sich durch Tj=max{0, Cj-FZj} für jeden Auftrag j.

Das Ziel ist die Minimierung der gesamten Verspätungszeit, also der Summe der Verspätungen Tj 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 hij 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 hij=1/FZj bzw. hij=1/tj. 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

Tgb ist die gesamte Verspätung der besten Lösung und Td die gesamte Verspätung, die sich nach einer berechneten Sequenz ergibt, die mit hij=1/dj 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 tj 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 o0) und der Endknoten (Knoten oe) 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 cjh=+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 Mk zu sehen, in der sonst die Knoten standen, die nicht mehr besucht werden durften.

Der Wert für q0 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 t0 eignet sich nach Gambardella/Dorigo (1997) die Festsetzung auf , wobei L1 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 ob 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 ob.

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 ob,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 tij, 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)

Mk 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 hij 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)

Lgb 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 Lgb 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

Lib ist der Wert der aktuellen Reihenfolge. Die Spurenstärke kann nie größer (kleiner) als tmax (tmin) 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 tij 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 Lgb 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 tij 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 pgb(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 tij-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

Lib 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 {tjm, hjm} zugeordnet, wobei tjm die Spurenstärke ist. Der Faktor hjm 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 hjm 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 hjm die längste Bearbeitungsdauer gewählt (vgl. Colorni et al. (1994)). Es gilt daher hjm = tjm.

Alle Ameisen starten in ob. 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 Gk die Menge der noch nicht besuchten Knoten und G’k die Menge an Knoten, die beim nächsten Schritt erlaubt sind, mit Gk={o11, o12, o13, o21, o22, o23, o31, o32, o41, o43} und G’k={o12, o21, o31, o43} 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 Mk hinzugefügt und aus den Mengen Gk 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 Gk=Æ. 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 Mk z. B. eine Reihenfolge der Knoten:

{ob, o12, o31, o13, o21, o43, o11, o32, o22, o23, o41, oe}

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

aij

Element aus Kopplungsmatrix A

bi

Zeitpunkt für den Beginn eines Zeitfensters

C

Kostenmatrix

Cj

Fertigstellungszeitpunkt insgesamt

c

Konstante

c’

veränderbarer Faktor

cij

Kosten

D

Distanzmatrix

d

Distanzvektor

di

Element aus Vektor d

dij

Distanz zwischen Knoten i und j

E

Menge an Kanten

e

Anzahl an elitären Ameisen

ei

Zeitpunkt für das Ende eines Zeitfensters

eij

Kante aus der Menge E

F

Flussmatrix

F(j)

Menge an Knoten, die besucht werden können

FZj

Fertigstellungszeitpunkt von Auftrag j

f

Flussvektor

fj

Element aus Vektor f

fij

Fluss zwischen Objekt i und j

gij

Funktion für zweifache Spurenaktualisierung

h, i, j, l

Laufindex

J

Anzahl an Aufträgen

K

Gesamtkapazität des Fahrzeugs

Ki

gesamte Nachfrage einer Tour

k

Index für die Ameisen

ki

Nachfrage vom Kunden i

L*

iterations- oder global beste Lösung

L1

erste gefundene Lösung

LB

untere Schranke

Lgb

global beste Lösung

Lib

iterations-beste Lösung

Lk

Lösung der k-ten Ameise

Lr

Lösung der k-ten Ameise

M

Anzahl an Maschinen

Mk

Speicher der k-ten Ameise; Tabu-Liste

Mk0

Speicher der Suchameisen

Mk1

Speicher der Transportameisen

m

Anzahl an Ameisen

m0

Anzahl an Suchameisen

m1

Anzahl an Transportameisen

mj

Maschine j

NC

Zyklenzähler

NCMAX

maximale Zyklenanzahl

n

Anzahl an Knoten/Aufträgen

O

Menge an Arbeitsgängen

Oi

Ort i

ob

Startknoten

oe

Endknoten

ojm

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

p

Wahrscheinlichkeits-Wert, mit 0<p<1

pij(t)

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

Q

Konstante

q0

festgelegte Wahrscheinlichkeit, mit 0<q0<1

q1

gegebene Wahrscheinlichkeit

r

Rang einer Ameise

r0

festgelegte Wahrscheinlichkeit, mit 0<r0<1

S

Zufallsvariable, mit 0<S<1

s

Speicher-Index für den Speicher

T’

gesamte Bearbeitungszeit der bereits ausgewählten Aufträge

Td

gesamte Verspätung

Tj

Verspätungszeit von Auftrag j

t

Zeitzähler

tic

Ankunftszeit am Knoten i

tj

Bearbeitungszeit von Auftrag j

tjhw

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

tjm

Bearbeitungszeit von Auftrag j an Maschine m

tw

Wartezeit

u

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

V

Menge an Knoten

V1

Menge an Knoten mit allen Maschinen

V2

Menge an Knoten mit allen Orten

v0

Depot

vi

Knoten aus der Menge V

w

Gewicht für die global beste Lösung

X

Matrix, mit und

xij

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

z

Zielfunktionswert

z’

gesamte potenzielle Kosten

Durchschnitt der Lösungen aller Ameisen in einer Iteration

Dtij

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

Lgb

Lösung mit minimierter Fahrzeit

Lmax

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

P

Permutation

Tij

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

hij

Sichtbarkeit; heuristische Distanz zwischen i und j

ji

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

kij

Kapazitätsauslastung

mij

„Savings“-Wert bei Aufnahme von Kante (vi,vj) in aktuelle Tour

p(j)

Zuordnung von j

pgb(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(tij*)

Funktion für die Spurenstärke

rl

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

sij(t)

Geschwindigkeit zwischen Knoten i und j zum Zeitpunkt t

t0

Startwert für die Spurenintensität

tij

Spur auf der Kante (i,j)

tmax

Obergrenze für Spurenintensität

tmin

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

98 von 98 Seiten

Details

Titel
Betriebswirtschaftliche Anwendungen für Ameisen-Systeme
Hochschule
Universität Bielefeld
Note
3,0
Autor
Jahr
2004
Seiten
98
Katalognummer
V109503
Dateigröße
804 KB
Sprache
Deutsch
Anmerkungen
In der Diplomarbeit wird das Prinzip von Ameisen Systemen (Ant-Systems) erklärt sowie Anwendungen auf diverse Probleme der Betriebswirtschaft, wie dem Travelling Salesman Problem, dem Quadratic Assignment Problem oder dem Job/Flow/Open Shop Problem.
Schlagworte
Betriebswirtschaftliche, Anwendungen, Ameisen-Systeme
Arbeit zitieren
Philipp Kötter (Autor), 2004, Betriebswirtschaftliche Anwendungen für Ameisen-Systeme, München, GRIN Verlag, https://www.grin.com/document/109503

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Betriebswirtschaftliche Anwendungen für Ameisen-Systeme


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden