Genetic TSP (beendet)
Bei diesem Projekt wird versucht, eine möglichst gute Lösung für ein Traveling Salesman Problem, das Problem des Handlungsreisenden, zu finden.
Das Traveling Salesman Problem ist wie folgt definiert: Für eine Anzahl von n Städten sind alle Entfernungen zwischen zwei der Städte bekannt. Gesucht ist eine Route durch alle Städte, die möglichst kurz ist. Problematisch ist dabei die explosionsartig anwachsende Zahl möglicher Routen. Für n Städte sind n! Routen möglich. Für 10 Städte ergeben sich damit bereits 362880 Touren und für 20 Städte schon 1,216 x 1017 Touren. Selbst mit schnellen Computern ist dieses Problem deshalb nur für sehr wenige Städte in vernünftiger Zeit berechenbar.
Interessanterweise lassen sich in deutlich kürzerer Zeit Routen finden, die nur um einen gewissen Faktor länger als die optimale (d.h. kürzeste) Route sind. Hier wird dazu ein genetischer Algorithmus genutzt. Bei diesem werden verschiedene Individuen (mögliche Routen) zufällig erzeugt. Je kürzer die Route, desto "fitter" ist das Individuum. Die fittesten Individuen paaren sich für die nächste Runde dieses evolutionären Vorgangs, d.h. die kürzesten Routen werden miteinander kombiniert. Da dieser Prozess nicht zwangsläufig zu guten Ergebnissen führt, gibt es auch noch Mutationen, d.h. manche Routen werden zufällig ein wenig geändert.
Die zu findende Route geht durch 15112 deutsche Städte. Aktueller Rekordhalter für die Berechnung der kürzesten bekannten Tour durch diese Städte sind die Princeton University & Rice University.
siehe auch:
Inhalt
Projektübersicht
 Genetic TSP
| |
|---|---|
| Name | Genetic TSP |
| Kategorie | Mathematik |
| Ziel | Finden einer optimalen Route durch alle deutschen Städte |
| Kommerziell | nein |
| Homepage | offline, hier archive.org Link |
| Dieses Projekt wird in Frankreich durchgeführt. |
Projektstatus
Clientprogramm
Betriebssysteme
| Windows | ||
| Linux | ||
| DOS |
| |
| BSD | ||
| Solaris | ||
| Java (betriebssystemunabhängig) |
Client-Eigenschaften
| Funktioniert auch über Proxy | 
|
| Normal ausführbares Programm |
|
| Als Bildschirmschoner benutzbar | 
|
| Kommandozeilenversion verfügbar |
|
| Personal Proxy für Work units erhältlich |
|
| Work units auch per Mail austauschbar |
|
| Quellcode verfügbar |
|
| Auch offline nutzbar |
|
| Checkpoints |
|
Besonderheiten des Clients
Bei diesem Client handelt es sich um ein Java-Applet, welches das Java-Plugin 1.3 voraussetzt. Seit Version 1.25 ist keine ständige Online-Verbindung mehr notwendig. Es reicht, das Browser-Fenster geöffnet zu lassen. Beim nächsten Connect werden die Daten automatisch zum Server geschickt.
Veröffentlichte Versionen
- 30.11.1999: 1.50
Screenshots
Hauptbildschirm
Projektstatus kurz nach dem start, Bei diesem Bild handelt es sich um eine Kopie des Status von der Webseite (keine Ausgabe des Clients).
