Optimieren mit neuronalen Netzen

Inhaltsverzeichnis

1. Einführung

2. Grundlagen künstlicher Neuronale Netze
2.1. Mathematische Darstellung
2.2. Netze mit Rückkopplung
2.2.1. Hopfield-Netze

3. Optimierung mit Neuronalen Netzen
3.1. Allgemein
3.2. Vorgehensweise
3.3. Optimierungsaufgaben
3.3.1. Das Traveling-Salesman-Problem
3.3.2. Maschinenbelegungsplanung

4. Zusammenfassung

Literaturverzeichnis

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 Informationsverarbeitung, 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 miteinander 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 Eingabe 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.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Ein dreischichtiges feedforward-Netz

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, 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.^[3] 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 Abbildung in dieser Leseprobe nicht enthalten, berechnet sich aus Abbildung in dieser Leseprobe nicht enthalten, wobei Abbildung in dieser Leseprobe nicht enthaltenden Eingangswerten am Neuron Abbildung in dieser Leseprobe nicht enthaltenentspricht und Abbildung in dieser Leseprobe nicht enthaltenden Eingangsgewichten (Gewicht zwischen Neuron j und Neuron i). Diese Formel ist auch unter dem Namen Ausbreitungsregel oder Propagierungsfunktion bekannt.

Das Ergebnis dieser Funktion wird an die so genannte Aktivierungsfunktion Abbildung in dieser Leseprobe nicht enthalten=Abbildung in dieser Leseprobe nicht enthaltenweitergeleitet. Mit ihr wird aus dem Nettoinput Abbildung in dieser Leseprobe nicht enthalten, dem alten Aktivierungszustand Abbildung in dieser Leseprobe nicht enthaltenund dem Schwellenwert Θ eines Neurons dessen aktuelle Aktivierung Abbildung in dieser Leseprobe nicht enthaltenberechnet. Im Allgemeinen feuert ein Neuron, d.h. es gibt einen Ausgangswert 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 Abbildung in dieser Leseprobe nicht enthalten nachgeschaltet werden. 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 Aktivierungszustand 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.^[4]

Die Gewichte Abbildung in dieser Leseprobe nicht enthaltenlassen sich mit der Gewichtsmatrix W =(Abbildung in dieser Leseprobe nicht enthalten) mit i =1(1)m, j =1(1)n darstellen. Desweiteren führt man für die Eingänge den Vektor eT =(e1,…,en) und für die Ausgänge den Vektor oT =(o1,…,om) sowie den Schwellenwertvektor ΘT =(Θ1,…,Θm) ein.

Der Lernvorgang, also die Art und Weise, wie man die Gewichte verändert, erfolgt gemäß Abbildung in dieser Leseprobe nicht enthalten, wobei sich Abbildung in dieser Leseprobe nicht enthaltenje nach Lernregel unterschiedlich berechnet.

[...]

^[1] vgl. [REYBECK]

^[2] vgl. [PAT], S. 14 f.

^[3] vgl. [KINNE], S. 23

^[4] vgl. [PAT], S. 44