Information Technology Reference
In-Depth Information
8.4 Lösen von Optimierungsproblemen
Hopfield-Netze lassen sich unter Ausnutzung ihrer Energiefunktion auch zum Lö-
sen von Optimierungsproblemen einsetzen. Die prinzipielle Idee ist die folgende:
Durch die Berechnungen eines Hopfield-Netzes wird ein (lokales) Minimum sei-
ner Energiefunktion erreicht. Wenn es nun gelingt, die zu optimierende Funktion so
umzuschreiben, dass sie als die (zu minimierende) Energiefunktion eines Hopfield-
Netzes interpretiert werden kann, können wir ein Hopfield-Netz konstruieren, in-
dem wir aus den Summanden dieser Energiefunktion die Gewichte und Schwellen-
werte des Netzes ablesen. Dieses Hopfield-Netz wird in einen zufälligen Anfangszu-
stand versetzt, und die Berechnungen werden wie üblich ausgeführt. Wir erreichen
dann einen stabilen Zustand, der einem Minimum der Energiefunktion, und damit
auch einem Optimum der zu optimierenden Funktion entspricht. Allerdings ist zu
beachten, dass u.U. nur ein lokales Optimum erreicht wird.
Das gerade beschriebene Prinzip ist offenbar sehr einfach. Die einzige Schwie-
rigkeit, die sich noch stellt, besteht darin, dass beim Lösen von Optimierungspro-
blemen oft Nebenbedingungen eingehalten werden müssen, etwa die Argumente
der zu optimierenden Funktion bestimmte Wertebereiche nicht verlassen dürfen. In
einem solchen Fall reicht es nicht, einfach nur die zu optimierende Funktion in ei-
ne Energiefunktion eines Hopfield-Netzes umzuformen, sondern wir müssen außer-
dem Vorkehrungen treffen, dass die Nebenbedingungen eingehalten werden, damit
die mit Hilfe des Hopfield-Netzes gefundene Lösung auch gültig ist.
Um die Nebenbedingungen einzuarbeiten, gehen wir im Prinzip genauso vor
wie zur Optimierung der Zielfunktion. Wir stellen für jede Nebenbedingung eine
Funktion auf, die durch Einhalten der Nebenbedingung optimiert wird, und formen
diese Funktion in eine Energiefunktion eines Hopfield-Netzes um. Schließlich kom-
binieren wir die Energiefunktion, die die Zielfunktion beschreibt, mit allen Energie-
funktionen, die sich aus Nebenbedingungen ergeben. Dazu nutzen wir das folgende
Lemma:
Lemma 8.1
Gegeben seien zwei Hopfield-Netze über der gleichen Menge U von Neuronen
mit den Gewichten w
(
i
)
uv
,denSchwellenwerten
(
i
u
und den Energiefunktionen
E
i
=
1
v
U
{
u
}
w
(
i
)
uv
act
u
act
v
+
u
U
(
i
)
2
u
U
act
u
u
für i
=
1, 2
.(DerIndexigibtan,aufwelchesderbeidenNetzesichdieGrößenbeziehen.)
Weiter seien a
,
b
IR
.DannistE
=
aE
1
+
bE
2
die Energiefunktion des Hopfield-Netzes
über den Neuronen in U, das die Gewichte w
uv
=
aw
(1)
uv
+
bw
(2)
und die Schwellenwer-
uv
te
u
=
a
(1
u
+
b
(2)
besitzt.
u
Dieses Lemma erlaubt es uns, die durch das Hopfield-Netz zu minimierende Ener-
giefunktion als Linearkombination mehrerer Energiefunktionen zusammenzusetzen.
Sein Beweis ist trivial (er besteht im einfachen Ausrechnen von
E
=
aE
1
+
bE
2
), wes-
wegen wir ihn hier nicht im Detail ausführen.
Als Beispiel für die beschriebene Vorgehensweise betrachten wir, wie man das
bekannte Problem des Handlungsreisenden (traveling salesman problem, TSP) mit
Hilfe eines Hopfield-Netzes (näherungsweise) lösen kann. Dieses Problem besteht
