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
