Genetic TSP (beendet)

Aus Rechenkraft
(Weitergeleitet von Genetic TSP)
Zur Navigation springen Zur Suche springen

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:


Projektübersicht

InfoIcon.png 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


 
France01.gif    Dieses Projekt wird in Frankreich durchgeführt.


Projektstatus

InfoIcon.png Projektstatus
Status   beendet
Beginn 30.09.2001
Ende 01.12.2003

Clientprogramm

Betriebssysteme

Icon windows 16.png   Windows Checkbox 1.gif  
Icon linux 16.png   Linux Checkbox 1.gif  
Icon dos 16.png   DOS Checkbox 0.gif  


Icon freebsd 16.png   BSD Checkbox 0.gif  
Icon solaris 16.png   Solaris Checkbox 0.gif  
Icon java 16.png   Java (betriebssystemunabhängig)  Checkbox 1.gif  

Client-Eigenschaften

Funktioniert auch über Proxy Checkbox 1.gif
Normal ausführbares Programm Checkbox 1.gif
Als Bildschirmschoner benutzbar Checkbox 0.gif
Kommandozeilenversion verfügbar Checkbox 0.gif
Personal Proxy für Work units erhältlich   Checkbox 0.gif
Work units auch per Mail austauschbar Checkbox 0.gif
Quellcode verfügbar Checkbox 0.gif
Auch offline nutzbar Checkbox 0.gif
Checkpoints Checkbox 1.gif

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