Im Kohonen-Netz wird das Prinzip selbstorganisierender Karten verwirklicht. Als Karte versteht man dabei eine Abbildung, die benachbarten Punkten im Definitionsbereich benachbarte Punkte im Wertebereich zuordnet. (Topologie-erhaltend).
Man kann das TSP mit Hilfe eines Kohonen-Netzes auf folgende Art lösen:
Man versteht die Anordnung der Städte im TSP als eine Anordnung von Punkten in der Ebene, die es zu erreichen gilt. Dazu wird ein Kreis mit einer gewissen Anzahl m (m >= Anzahl der Städte) von Kreispunkten in diese Ebene gelegt. (Bild 1) |
|
Bild 1 | |
Man wählt jetzt zufällig einen Punkt der Ebene aus. Jeder Kreispunkt wird in die Richtung dieses Punktes verschoben. Wie groß die Verschiebung ist, ist abhängig von der Entfernung der Punkte zueinander und eines Lernkoeffizienten. Die Kreispunkte, die näher an dem Punkt der Ebene liegen, werden stärker verschoben. (Bild 2) |
|
Bild 2 | |
Nach einer genügend großen Anzahl von Schritten, hat sich der 'Kreis' der optimalen Tour angenähert. (Bild 3) |
|
Bild 3 |
Eine sehr interessante Arbeit dazu haben FRITZKE und WILKE
von der Universität Erlangen-Nürnberg verfaßt. Sie versuchen die
Zeit- und Speicherplatzkomplexität des Algorithmus durch einige
Verbesserungen linear zu machen.
A Neural Network For The Traveling Salesman Problem With Linear Time And Space
Complexity
|
|
---|
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996