Admin: 1 Version: Eine alte Version der Wiki ist hier her gezogen (3)

2011-11-06T17:56:33Z

1 Version: Eine alte Version der Wiki ist hier her gezogen (3)

← Nächstältere Version

Version vom 6. November 2011, 17:56 Uhr

Chge: /* Parameter */

2011-10-24T09:08:02Z

Parameter

Neue Seite

[[File:AntsOnCrack-Logo.png|50px|right]]
Zielsetzung dieses Projektes ist es, ein Programm zu erstellen, um das Traveling Salesman Problem mit dem Ameisenalgorithmus zu lösen. Was der Algorithmus können muss und wie dieser eingesetzt wird um das TSP-Problem zu lösen soll hier erklärt werden:

[[Image:tsp_deutschland.png|thumb|Breitepx|TSP: Kürzester Rundreiseweg durch die 15 größten Städte Deutschlands. Insgesamt sind 14!/2 = 43 589 145 600 verschiedene Wege möglich. (Quelle: wikipedia.de)]]
===Traveling Salesman Problem===
Das Traveling Salesman Problem (TSP, dt. Problem des Handlungsreisenden) ist ein [http://de.wikipedia.org/wiki/P-NP-Problemvollständiges NP-Problem] in der kombinatorischen Optimierung der theoretischen Informatik. 
Gegeben ist eine Liste von Städten mit Koordinaten; gesucht ist die kürzeste Route, in der jede Stadt einmal besucht wird und die Startstadt gleich der Endstadt ist. 
Um die Problemstellung des TSP graphisch zu veranschaulichen, repräsentieren die Städte Knoten und Wege zwischen zwei Städten Kanten.
 
 
Weitere Informationen finden Sie [http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden hier].

===Ameisenalgorithmus Therorie===
In der Informatik ist der Ameisenalgorithmus (engl. Ant Colony Optimization, ACO) eine Metaheuristik, die sich auf das Schwarmverhalten von Ameisen auf Futtersuche stützt.

In der Natur wandern Ameisen zunächst zufällig, bis sie Futter gefunden haben und kehren anschließend zu ihrer Kolonie zurück, wobei sie Pheromonspuren hinterlassen. Sobald andere Ameisen einen Pfad mit Pheromonspuren finden, wandern sie nicht mehr zufällig, sondern folgen dem Pfad und verstärken ihn dadurch, bis sie schließlich das Futter finden. Währenddessen verdunsten die Pheromonspuren und verringern somit die Attraktivität des Pfades. Je länger eine Ameise für einen Weg braucht, desto mehr verdunsten die Pheromone auf dem Pfad. Wenn ein Pfad kurz ist, wird dieser öfters genutzt und die Pheromonspur wird stärker. Somit werden kurze Wege den längeren Wegen vorgezogen. 
Wenn eine Ameise einen attraktiven (oder kurzen) Weg zwischen der Kolonie und der Futterquelle findet, ist es wahrscheinlicher, dass andere Ameisen ebenso diesen Pfad folgen und somit positives Feedback produzieren, bis alle Ameisen, einem einzigen Weg folgen (Ameisenstraße). 

[[Image:ant_optimization.png||Breitepx|]] 
1) Die erste Ameise findet die Futterquelle (F) über einen zufälligen Weg, kommt zurück zum Nest (N) und hinterlässt eine Pheromonspur 
2) Die Ameisen folgen einen der 4 möglichen Wegen. Die Verstärkung der Wege macht den kürzesten Weg am attraktivsten 
3) Die Ameisen folgen den kürzesten Weg, die Pheromonspuren der längeren Wege verdunsten.
 
 
Der Ameisenalgorithmus soll dieses Verhalten in der Natur simulieren, so dass damit die Lösung für den kürzesten Weg in einem Graph gefunden werden kann.
 
 
Weitere Informationen über den Ameisenalgorithmus finden Sie [http://de.wikipedia.org/wiki/Ameisenalgorithmus hier].

===Praktische Umsetzung im Programm===
Der Ameisenalgoritmus kann folgendermaen umgesetzt werden:
*es wird eine bestimmte Anzahl von Ameisen bereitgestellt
*diese Ameisen laufen nacheinander los
*jede Ameise erhält entweder einen zufälligen oder festgelegten Startpunkt
*es werden alle Wege ermittelt, die diese Ameise von diesem Punkt aus gehen kann
*die möglichen Optionen werden mit Hilfe einer Formel und verschiedenen Parametern (siehe unten) bewertet
*es wird nun zufällig ein Wert aus der Bewertungsskala ermittelt. (das heißt Optionen mit einer höheren Bewertung werden auch mit einer höheren Wahrscheinlichkeit ausgewählt)
*es wird festgehalten, welche Koordinate die Ameise nun abgelaufen ist
*ist eine Ameise fertig (alle Punkte wurden einmal benutzt), kann die nächste Ameise loslaufen
*sind alle Ameisen gelaufen, kann mit Hilfe aller von den Ameisen ermittelten Strecken ein Pheromonupdate durchgeführt werden
*ist dies geschehen kann eine Iteration als vollendet betrachtet werden
*die Iterationen können beliebig oft durchgeführt werden (siehe Stoppkriterium)
Das folgende Diagramm zeigt den gewünschten Programmablauf:
 
[[Image:Ablauf_des_AmeisenAlgorithmus.png]]
 

Abwandlungen: 
Zu dieser Vorgehensweise können verschiedene Abwandlungen gemacht werden: Beispielsweise könnten ein Pheromonupdate schon durchgeführt werden, nachdem eine einzelne Ameise gelaufen ist. Auch wäre es möglich, gezielt Startwerte einzusetzen, bei denen die Ameisen loslaufen sollen.

===Bewertung einer Strecke===
Um zu entscheiden, welchen Weg eine Ameise gehen soll, müssen zunächst alle noch möglichen Strecken ermittelt werden. Sind alle möglichen Strecken ermittelt, wird mit einer Formel ein Wahrscheinlichkeitswert für jede Strecke ausgerechnet. Dieser Wert bezieht die Streckenlänge und den Pheromonanteil mit ein. Mit Hilfe von den Parametern Alpha und Beta wird dann festgelegt, inwiefern die Streckenlänge oder der Pheromonwert benutzt werden soll.

Die Formel lautet:

Beschreibung: Für eine Strecke wird der anliegende Pheromonwert hoch Alpha gerechnet. Dieser Wert wird mit dem Ergebnis multipliziert, der bei der Rechnung herauskommt, wenn man die Streckenlänge hoch Beta rechnet. Das Ergebnis stellt dann den Dividenden dar. Der Divisor ergibt sich, wenn für jede noch mögliche Strecke ebenfalls die Rechnung, analog der des Dividenden, durchgeführt wird. Abschließend werden alle Ergebnisse zusammengerechnet (=Divisor).

===Pheromon-Aktualisierung===
Damit eine dynamische Verteilung der Ameisen gewährleistet wird muss in bestimmten Abständen der Pheromonwert korrigiert werden. Der Pheromonwert existiert für jeden Weg zwischen zwei Punkten. Initial soll dieser existieren (tau0). In der Natur ist es so, dass beim Betreten eines Weges die Ameise ihr Pheromon direkt versprüht. Für den Algorithmus findet dieses Vorgehen aber nicht in der Form Anwendung.
Dieser geht folgendermaßen vor: Alle Ameisen suchen ihre persönliche beste Tour. Erst dann erfolgt eine Aktualiserung der Pheromonwerte. Für jede Strecke, die von den Ameisen gelaufen wurde, wird mit einer Berechnungsvorschrift der Pheromonwert aufaddiert. Alle anderen Wege erhalten eine Verdunstung des Pheromonwertes.

Berechnung des Verdunstungsfaktors:

Für einen besuchten Weg:

Alternativ kann die Pheromon-Aktualisierung auch direkt nach einem kompletten Ameisendurchlauf erfolgen. Diese Methode beeinflusst dann die Wahrscheinlichkeiten der Wege für die nächste Ameise.

===Stopp-Kriterien für den Algorithmus===
Der Algoritmus könnte theoretisch unendlich laufen, deswegen werden bestimmte Stopp-Kriterien definiert:
*Stoppen nach einer bestimmten Anzahl an Iterationen
*Stoppen bei Erreichen eines bestimmten Schwellwertes (z.B. kürzeste Tour <= Wert)
*Stoppen nachdem der optimale Weg bekannt ist (das setzt das Wissen für eine optimale Tour voraus und kann dazu führen dass der Algorithmus ewig läuft, wenn die Parameter entsprechend gesetzt wurden)

===Parameter===
Für den Algorithmus, wie er in dieser Ausprägung vorliegt können mehrere Parameter eingeführt werden:
*α: Dieser Parameter gibt an, inwiefern der Pheromongehalt einer Strecke in die Gesamtberechnung der Wahrscheinlichkeiten der Wege mit einbezogen werden soll. Dabei kann α einen Wert zwischen 0 und 1 annehmen. (0 < α ≤ 1)

*β: Dieser Parameter gibt an, inwiefern die Länge einer Strecke in die Gesamtberechnung der Wahrscheinlichkeiten der Wege mit einbezogen werden soll. Dabei kann β einen Wert zwischen 0 und 1 annehmen. (0 < β ≤ 1) Dieser Parameter ist somit das Gegenstück zu α.

*ρ: Für das reelle Abbilden der Pheromongehalte gibt es den Verdunstungsfaktor ρ. Mit diesem wird angegeben, wie viel Pheromon verdunsten kann auf einer Strecke zwischen zwei Koordinaten. Auch hier gilt: (0 < ρ ≤ 1)

*τ0: Dieser Wert beschreibt den Anfangswert des Pheromons auf einer Strecke. Es gilt lediglich die Einschränkung (τ0 > 0). Ein zu hoher Wert wäre aber nicht sinnvoll.

*Q: Der Parameter Q gibt an, inwiefern sich der Pheromonwert verändern kann, wenn eine Ameise über eine Strecke gelaufen ist. (Q > 0)

TSP-Ameisenalgorithmus: Erklärung Ameisenalgorithmus - Versionsgeschichte

Admin: 1 Version: Eine alte Version der Wiki ist hier her gezogen (3)

Chge: /* Parameter */