Inhaltsverzeichnis

1.  Einführung  3

2.  Grundlagen künstlicher Neuronale Netze  3

2.1.  Mathematische Darstellung  5

2.2.  Netze mit Rückkopplung  8

   8

2.2.1.  Hopfield-Netze  

3.  Optimierung mit Neuronalen Netzen  12

3.1.  Allgemein  12

3.2.  Vorgehensweise  13

3.3.  Optimierungsaufgaben  18

3.3.1.  Das Traveling-Salesman-Problem  18

3.3.2.  Maschinenbelegungsplanung  19

4.  Zusammenfassung  20

Literaturverzeichnis   21

2

1. Einführung

Künstliche Neuronale Netze (im Folgenden auch KNN genannt) sind biologisch motivierte Modelle, die sich an Grundprinzipien der Arbeitsweise des Gehirns und des zentralen Nervensystems anlehnen. Während Probleme, die durch einen Algorithmus in kurzer Zeit exakt zu lösen sind, von einem Computer deutlich schneller gelöst werden können als von einem Menschen, so ist das menschliche Gehirn beispielsweise beim Erkennen von Gesichtern überlegen und liefert auch beim Ausfall einiger für die Problemlösung notwendiger Nervenzellen noch korrekte Ergebnisse. Die Idee ist daher, die Arbeitsweise des Gehirns auf den Computer zu übertragen. Mit ihrem Formalmodell des Neurons waren Warren McCulloch und Walter Pitts die Ersten, die sich mit dem Thema neuronale Netze beschäftigten. Seit ca. 1986 haben die Arbeiten mit und zu neuronalen Netzen stark zugenommen. Mittlerweile kann man das Themengebiet in zwei große Bereiche unterteilen: • Künstliche neuronale Netze, die modelliert werden, um die Funktionsweise des menschlichen Gehirns besser zu verstehen und

• künstliche neuronale Netze, die dazu dienen, konkrete Anwendungsprobleme zu lösen, aus Bereichen der Statistik, der Wirtschaftswissenschaften, der Technik und vielen andere Gebieten 1

Durch ihre besonderen Eigenschaften wie Lernfähigkeit, Fehlertoleranz, parallele In-formationsverarbeitung, Robustheit gegen verrauschte Daten und die Fähigkeit, Muster zu erkennen, stellen KNN bereits in vielen Bereichen eine ernst zu nehmende Alternative zu herkömmlichen Algorithmen dar.

2. Grundlagen künstlicher Neuronale Netze

Es handelt sich bei KNN um ein Netzwerk von einfach aufgebauten und komplex mit-einander verknüpften Verarbeitungseinheiten, den Neuronen. Sie besitzen die Fähigkeit, auf Eingabereize zu reagieren, zu lernen und sich der Umgebung entsprechend anzupassen. Unter Neuronen kann man sich auch primitive Funktionen vorstellen, die eine Ein-

¹ vgl.[REYBECK]

3

gabe in eine Ausgabe transformieren. Neuronale Netze sind also im Prinzip nichts anderes als Netze von Funktionen.

Die Neuronen, oft auch als Units, Einheiten oder Knoten bezeichnet, werden in der Regel in sogenannten Schichten angeordnet. Man unterscheidet hierbei zwischen Eingabeschicht, verborgener Schicht und Ausgabeschicht. Je nachdem welcher Schicht die Neuronen zugeordnet sind, spricht man von Input-Units, die von der Außenwelt Signale (Reize, Muster) empfangen können, den Hidden-Units, die sich zwischen Input- und Output-Units befinden und eine interne Repräsentation der Außenwelt beinhalten und den Output-Units, die die Ausgabe des KNN erzeugen und letztendlich die Signale an die Außenwelt weitergeben.

Durch gerichtete Verbindungen zwischen den Neuronen können sie sich nach vorgegebenen Regeln untereinander aktivieren, wodurch die Informationsverarbeitung stattfindet. Auf diese Weise ist es den KNN möglich mittels einfacher arithmetischer Funktionen sehr komplexe Eingabe-Ausgabe-Zusammenhänge abzubilden. Die Stärke der Verbindungen zwischen zwei Neuronen wird durch ein Gewicht angegeben. Der Einfluss einer Unit auf eine andere ist umso größer je größer der Absolutbetrag ist. Dabei bewirkt ein positives Gewicht, dass ein Neuron einen exzitatorischen, erregenden Einfluss,

4

ein negatives Gewicht einen inhibitorischen, also hemmenden Einfluss und ein Gewicht von Null keinen Einfluss auf ein anderes Neuron hat. 2

Um mit KNN Funktionen darstellen zu können, bedarf es einer Vorschrift zur Berechnung der Gewichte. Für die meisten Anwendungen existiert jedoch eine solche direkte Berechnungsvorschrift nicht. Aus diesem Grund versucht man andere Methoden zur Ermittlung der Gewichte zu finden. Dieser Vorgang des Bestimmens der Gewichte, so dass ein Netz die in der gewählten Topologie vorgegebene Funktion darstellen kann, bezeichnet man als Lernen. ³ Lernregeln geben dabei die Art und Weise an, wie das neuronale Netz diese Veränderungen vornimmt. Man unterscheidet grundsätzlich zwischen: • supervised learning: Der korrekte Output wird vorgeben und daran werden die Gewichte optimiert.

• unsupervised learning: Es wird kein Output vorgegeben.

Lernregeln stellen einen Algorithmus dar, der darüber Auskunft gibt, welche Gewichte des neuronalen Netzes wie stark erhöht oder reduziert werden sollen. Solche Regeln sind z.B. die Hebb-Regel, Delta-Regel, Backpropagation oder das Competitive Learning.

In der Ausbreitungsphase oder Recall-Phase werden hingegen keine Gewichte mehr verändert. Stattdessen wird hier auf Grundlage der bereits modifizierten Gewichte aus der Lernphase untersucht, ob das Netz etwas gelernt hat. Dazu präsentiert man den Input-Units Reize und prüft, welchen Output das neuronale Netz berechnet.

2.1. Mathematische Darstellung

Ein Neuron besitzt mehrere unabhängige Eingänge. Für jeden dieser Eingänge gibt es externe Eingabesignale oder Reize mit einer entsprechenden Gewichtung. Die Eingabewerte können reell, binär oder bipolar sein.

Der Nettoinput, also die kumulativen Eingabereize eines Neurons i , berechnet sich aus n ∑ , wobei j e den Eingangswerten am Neuron i entspricht und ij w den Ein- = e w net

j ij i

1 = j

gangsgewichten (Gewicht zwischen Neuron j und Neuron i). Diese Formel ist auch unter dem Namen Ausbreitungsregel oder Propagierungsfunktion bekannt.

² vgl. [PAT], S. 14 f.

³ vgl. [KINNE], S. 23

5

Das Ergebnis dieser Funktion wird an die so genannte Aktivierungsfunktion a = ) , ( weitergeleitet. Mit ihr wird aus dem Nettoinput net , dem alten Θ i a net f

neu alt i

Aktivierungszustand alt a und dem Schwellenwert Θ eines Neurons dessen aktuelle Ak-

tivierung neu berechnet. Im Allgemeinen feuert ein Neuron, d.h. es gibt einen Aus- a

gangswert ab, wenn der Nettoinput größer als ein Schwellenwert Θ ist. Häufig werden lineare Funktionen, binäre Schwellenwertfunktionen und sigmoide Funktionen als Aktivierungsfunktionen verwendet, wie in Abbildung 2 dargestellt. Der Aktivierungsfunktion kann eine Ausgabefunktion ) ( neu nachgeschaltet wer- o = a f

den. Sie definiert, welches Ausgabesignal an benachbarte Einheiten weitergegeben werden soll. Aktivierungsfunktion und Ausgabefunktion werden häufig zur Transferfunktion zusammengefasst. In der Regel wird der Ausgangszustand dem inneren Aktivie-rungszustand gleichgesetzt, in einigen Fällen aber ermöglicht die Ausgabefunktion einen Wettbewerb der nachfolgenden Neuronen einer Schicht. So z.B. konkurrieren sie bei der „winner-takes-all“-Ausgabefunktion um die Eingabereize, wobei aber nur bei einem der Elemente, dessen Transferfunktion den höchsten Wert liefert, die Gewichtungen verstärkt werden. Bei allen anderen Elementen dieser Schicht bleiben die Gewichtungen unverändert. ⁴ Die Gewichte ij w lassen sich mit der Gewichtsmatrix W=( ij w ) mit i=1(1)m, j=1(1)n

darstellen. Desweiteren führt man für die Eingänge den Vektor e T =(e 1 ,…,e n ) und für die Ausgänge den Vektor o T =(o 1 ,…,o m ) sowie den Schwellenwertvektor Θ T =(Θ 1 ,…,Θ m ) ein.

Der Lernvorgang, also die Art und Weise, wie man die Gewichte verändert, erfolgt ge- alt neu mäß , wobei sich ∆ je nach Lernregel unterschiedlich berechnet. ∆ + = w w

ij ij ij ij

⁴ vgl. [PAT], S. 44

6