Information Technology Reference
In-Depth Information
Die Funktion
E
1
müssen wir nun, dem oben allgemein beschriebenen Plan fol-
gend, so umformen, dass sie die Form einer Energiefunktion eines Hopfield-Netzes
über Neuronen
(
i
,
j
)
erhält, wobei die Matrixelemente
m
ij
die Rolle der Aktivierun-
gen der Neuronen übernehmen. Dazu müssen wir vor allem eine zweite Summation
über die Stationen (Index
i
)einführen.Wirerreichendies,indemwirfürdieStatio-
nen, auf denen die Städte
j
1
und
j
2
besucht werden, zwei Indizes
i
1
und
i
2
verwenden
und durch einen zusätzlichen Faktor sicherstellen, dass nur solche Summanden ge-
bildet werden, in denen diese beiden Indizes in der gewünschten Beziehung (
i
2
folgt
auf
i
1
)zueinanderstehen.Wirerhaltendann
E
1
=
(
i
1
,
j
1
){1,...,
n
}
2
(
i
2
,
j
2
){1,...,
n
}
2
d
j
1
j
2
·
(
i
1
mod
n
)+1,
i
2
·
m
i
1
j
1
·
m
i
2
j
2
,
wobei
ab
das sogenannte
Kronecker-Symbol
ist, das definiert ist durch
1,
falls
a
=
b
,
ab
=
0,
sonst.
Es fehlt nun nur noch der Faktor
2
vor den Summen, damit sich die Form einer
Energiefunktion ergibt. Diesen Faktor können wir z. B. einfach dadurch erhalten,
dass wir den Faktor
2indieSummenhineinziehen.Angemesseneristjedoch,nur
einen Faktor
1indieSummehineinzuziehenunddenFaktor2durchSymmetrisie-
rung des Faktors mit dem Kronecker-Symbol zu erzielen. Denn es ist ja gleichgültig,
ob
i
2
auf
i
1
folgt oder umgekehrt: In beiden Fällen wird die gleiche Beziehung zwi-
schen den Städten beschrieben. Wenn wir beide Reihenfolgen zulassen, wird auto-
matisch jede Entfernung auf der Rundreise doppelt berücksichtigt. Damit haben wir
schließlich
E
1
=
1
2
(
i
1
,
j
1
){
1,...,
n
}
2
(
i
2
,
j
2
){
1,...,
n
}
2
d
j
1
j
2
· (
(
i
1
mod
n
)+1,
i
2
+
i
1
,(
i
2
mod
n
)+1
) ·
m
i
1
j
1
·
m
i
2
j
2
.
Diese Funktion hat die Form einer Energiefunktion eines Hopfield-Netzes. Dennoch
können wir sie nicht direkt benutzen, denn sie wird offenbar gerade dann minimiert,
wenn alle
m
ij
=
0 sind, unabhängig von den Entfernungen zwischen den Städten. In
der Tat müssen wir bei der Minimierung der obigen Funktion zwei Nebenbedingun-
gen einhalten, nämlich:
•
Jede Stadt wird auf genau einer Station der Reise besucht, also
j
{
1, . . . ,
n
}
:
n
i
=1
m
ij
=
1,
d. h., jede Spalte der Matrix enthält genau eine 1.
• Auf jeder Station der Reise wird genau eine Stadt besucht, also
n
j
=1
m
ij
=
1,
i
{
1, . . . ,
n
}
:
d. h., jede Zeile der Matrix enthält genau eine 1.
