Die Kohonen-Karte

Beim Travelling-Salesman-Problem kommt eine eindimensionale Version der von Teuvo Kohonen 1982 entwickelten selbstorganisierenden Merkmalskarte zum Einsatz. Die mathematische Formulierung ist wie folgt:

Gegeben sei ein Datenraum R (hier: [0,1] x [0,1]), in dem sich N Datenpunkte xi befinden, ferner eine Kette (1dim) oder ein Gitter (2dim) aus P Knoten i, i = 1...N. Auf diesem Gitter ist eine Abstandsfunktion (i,j) → dij definiert (z.B. euklidische - oder Manhatten-Distanz.) Ferner gebe es zu jedem Knoten i einen "Referenzvektor" wi aus R, der nach folgenden Algorithmus bewegt wird:

  1. Initalisiere eine Zählvariable t ← 0 und wähle eine maximale Iterationszahl tmax .
  2. Wähle einen zufälligen Datenpunkt x &isin {x1...xN}
  3. Bestimme den nächstgelegenen Referenzvektor wI, d.h. I = argmini ( | x - wi| )
  4. Verschiebe jeden Datenpunkt gemäß &Delta wi = &epsilon(t) hiI (x - wi) mit hij= exp[- dij / σ(t)2 ], wobei gelten möge:
    • ε(t) = εi (εi / &epsilonf)t /tmax
    • σ(t) = σi (σi / &sigmaf)t /tmax
    Es wird also der nächstliegende Referenzvektor in Richtung von x verschoben, die im Gitter (nicht im Eingaberaum!) benachbarten Referenzvektoren ebenfalls, aber schwächer.
  5. erhöhe t &larr t+1 und wiederhole ab 2.
Am Ende ist das Gitter i.a. geordnet, d.h. im Gitter benachbarte Knoten haben in R benachbarte Referenzvektoren. Hier besteht die Datenmenge aus N Städten, die (geschlossene) Kette aus P Knoten. Dargestellt sind jeweils die Knoten der Kette anhand ihrer Referenzvektoren im Eingaberaum.