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

Bepf: /* Auswahl einer TSP-Karte (Traveling Salesman Problem Karte) */

2011-10-30T11:38:51Z

Auswahl einer TSP-Karte (Traveling Salesman Problem Karte)

Neue Seite

==Kurzeinführung ANTS ON CRACK==
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 in ihre Kolonie zurück, während sie Pheromonspuren hinterlassen. Falls andere Ameisen einen Pfad mit Pheromonspuren finden, wandern sie nicht mehr zufällig, sondern folgen den Pfad und verstärken ihn dadurch, bis sie schließlich das Futter finden. Währenddessen verdunsten die Pheromonstpuren 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.
Falls 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, einen einzigen Weg folgen (Ameisenstraße).
 
Der Ameisenalgorithmus soll dieses Verhalten in der Natur simulieren, sodass die Lösung für den kürzesten Weg in einem Graph gefunden werden kann.
 
ANTS ON CRACK ist ein Studienprojekt der Hochschule für Wirtschaft und Recht, das diesen Algorithmus implementiert hat.

==Benutzung der Oberfläche==
Wenn das Programm gestartet wurde erscheint das Hauptfenster mit leeren Eingabfeldern. 
Durch das Menü müssen verschiedene Aktionen durchgeführt werden um das Programm zu benutzen:

[[Datei:AoCHome.png]]
===Auswahl einer TSP-Karte (Traveling Salesman Problem Karte)===
Damit überhaupt ein Weg berechnet werden kann muss eine TSP-Datei geladen werden.
Die Auswahl dieser Datei erfolgt über das Menü: 
'''''Datei --> Öffnen''''' 
[[Datei:AoCOpenMenue.png]] 

Es öffnet sich dann ein Auswahlmenü über das, wie allgemein gewohnt, der Pfad der Datei ausgewählt werden kann.
[[Datei:AoCOpenDialog.png]]

{| class="box" border="1"
|+ Wichtig für das Dateiformat
! Das Einlesen des Dateiformats kann nur erfolgen, wenn die Datei den Normen entspricht. 
Die Normen lassen sich [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ hier nachlesen]. 
Es muss außerdem beachtet werden, dass ausschließlich 2-dimensionale TSP-Karten verarbeitet werden können.! 
Das bedeutet, dass zu einem Koordinatennamen (bzw. Nummer) nur 2 Koordinaten-Werte existieren dürfen.
|}

Wenn eine Koordinatenkarte geladen wurde, kann die Anzeigegröße durch einen Schieberegler oder 2 Buttons angepasst werden. 
[[Datei:AoCZoom.png]]

===Verändern der Koordinaten-Karte===
Im Programm ist es möglich durch Klicken auf die Koordinatenzeichenfläche neue Koordinaten hinzuzufügen. 
Es öffnet sich ein neues Fenster, in dem dieser neuen Koordinate ein Name zugeordnet werden kann, 
und außerdem die exakten X- und Y-Werte bestimmt werden können. 

Dieser Vorgang ist nur möglich, wenn vorher eine TSP-Karte aus einer Datei geladen wurde. 
Das speichern dieser neuen Karte ist auch möglich (siehe unten).

===Speichern einer TSP-Karte===
Wenn neue Koordinaten hinzugefügt wurden, kann über einen Menüpunkt ein neues TSP-File erzeugt werden. 
Der Menüpunkt: 
'''''Datei-->TSP Speichern''''' 
öffnet eine Dateiauswahlmaske, in der nun in der Ordnerstruktur navigiert werden kann. 
Es muss dann ein Name angegeben werden. 
Beim klicken auf "Speichern" wird die Datei gespeichert, die Dateiendung wird automatisch erzeugt. 
[[Datei:AoCNewCoordinate.png]]

===Speichern einer TSP-Tour===
Wenn eine Tour gefunden wurde (egal ob optimal oder nicht), kann diese ebenfalls abgespeichert werden.
Der Menüpunkt: 
'''''Datei-->Tour Speichern''''' 
öffnet eine Ordner-Navigationsmaske, in der der Speicherort angegeben wird. 
Der Speichervorgang läuft genauso ab, wie in "Speichern einer TSP-Datei" beschrieben ist. 
Die Datei wird gemäß der [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ Norm] gespeichert. 
Im Kopfbereich der Datei wird zusätzlich gespeichert, welche Parameter benutzt wurden und die Längen der besten und durchschnittlichen Touren.

===Parameter mit Zufallswerten belegen===
Um ein wenig die Parameter auszuprobieren, mit welchen man am Besten zum Ergebnis kommt,
gibt es den Menüpunkt: 
'''''Datei-->Zufallsparameter''''' 
Es werden alle Parameter für den Algorithmus zufällig belegt, selbstverständlich nur innerhalb ihres Wertebereichs. 
Auch die Anzahl der Ameisen wird zufällig festgelegt (Maximal 150)
Es wird aber kein Stoppkriterium zufällig generiert.

===Zufallsszenario erstellen===
Um zufällige Koordinaten zu generieren, gibt es den Menüpunkt: 
'''''Datei-->Zufallszenario''''' 
Zusätzlich zum zufälligen setzen der Parameter und der Ameisenanzahl werden auch Koordinaten generiert. 
Die Koordinaten werden innerhalb eines bestimmten Rahmens generiert, es gibt aber einen Schwerpunkt, in dem die meisten Koordinaten liegen sollen, um ein mögliches Stadtzentrum zu simulieren. (Vorher geladene Koordinaten werden gelöscht)
Das Stoppkriterium wird auf "Anzahl der Iterationen" gesetzt und mit einem Zufallswert belegt. 
Im Gegensatz zum Menüpunkt "Zufallswerte" bietet "Zufallsszenario" also ein komplettes, zufälliges Szenario,
das ohne irgendwelche zusätzlichen Benutzerangaben berechnet werden kann.
[[Datei:AoCRandomScenario.png]]

==Erklärung der Eingabe==
Sind die Koordinaten erfolgreich geladen, müssen nun verschiedene Parameter eingestellt werden. 
(Oder sie werden über den Menüpunkt Datei-->Zufallsparameter zufällig ausgewählt)

Erst danach kann der Algorithmus einen Weg finden.
Sind alle Parameter gesetzt kann der Start-Button den Algorithmus beginnen lassen, "Stop" unterbricht dann den Vorgang.

[[Datei:AoCKonfig.png]]

===Konfiguration der Parameter===
Im rechten Teil des Hauptfensters gibt es Menü zum eingeben der Parameter. 
Sind keine, bzw. falsche Werte in den Feldern eingegeben, erscheint das Feld rot, der Algorithmus kann nicht ausgeführt werden. 
Eine Detaillierte Beschreibung der Parameter findet sich im Programm selbst, durch ToolTips (wenn die Maus über das Feld positioniert wird) werden weitere Informationen gezeigt.

===Auswahl eines Stoppkriteriums===
Eine wichtige Angabe ist das Stoppkriterium. Der Algorithmus könnte theretisch ewig nach einer besten Tour suchen.
Deshalb stehen 3 Stoppkriterien zur Auswahl: 
*Anzahl der Iterationen: Der Algorithmus wird solange ausgeführt, bis die Zahl der Iterationen erreicht ist.
*Schwellwert erreicht: Der Algorithmus arbeitet so lange, bis die best gefundene Tour kleiner ist (vom Weg her), als der angegebene Schwellwert. Es sollte beachtet werden, dass ein zu kleiner Schwellwert zu einer Endlosschleife führt.
*Lösung gefunden: Der Algorithmus läuft solange, bis die optimale Tour gefunden wurde. Das setzt natürlich vorraus, dass eine Lösung bekannt ist und zur Verfügung steht. Über einen Button gelangt man zur Dateiauswahl, mit der das .tour File eingelesen werden kann. Es gelten die selben Normen wie beim Unterpunkt "TSP-Datei einlesen".

==Erklärung der Ausgabe==
Unterhalb der Parametereingabe befindet sich eine Statusanzeige, die die aktuellen Städte (Koordinaten) anzeigt.
Außerdem werden jeweils pro Iteration und global die Länge der Besten und der durchschnittlichen Tour angezeigt.
Natürlich nur wenn das Programm arbeitet.
Ein Ladebalken zeigt zusätzlich an, wie weit das Programm schon fortgeschritten ist (nur bei StoppKriterium: Anzahl der Iterationen)

[[Datei:AoCStatuspng.png]]

TSP-Ameisenalgorithmus: Handbuch - Versionsgeschichte

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

Bepf: /* Auswahl einer TSP-Karte (Traveling Salesman Problem Karte) */