AuK/Näherungsverfahren 2 WS13-14

Wiki-Quelltext dieser Seite.

;Autoren
:[mailto://s3dobitt@stud.hszg.de Dominik Bitterlich]<br/>
:[mailto://s3alhaes@stud.hszg.de Alexander Häse]


==DNA-Computing==

===Motivation===

NP-Probleme lassen sich mit konventionellen Rechnern nur mit einem exponentiellen Aufwand lösen, da diese verschiedenste Rechenschritte hintereinander, das heißt seriell,  verarbeiten. Ein anderer Ansatz für diese Art von Problemen stellt das DNA-Computing dar. Hierbei werden in einem Reagenzglas Informationen in DNA-Molekülen codiert. Das Reagenzglas wird somit zu einem Computer mit zahlreichen parallelen Prozessoren. 
Obwohl die Schaltzeit von Neuronen (Nervenzellen) im Bereich von einer Millisekunde derjenigen von Mikroprozessoren unterlegen ist, kann in der Natur zum Beispiel ein potentielles Beutetier einen Angreifer blitzartig erkennen und entsprechend reagieren. Dies ist eine Fähigkeit, welche das Vermögen von Mikroprozessoren übersteigt und die erst durch Parallelarbeit ermöglicht wird.

===Biologische Grundlagen===

Die gesamte Erbinformation lebender Zellen und Organismen ist in der DNA enthalten. Sie steuert in jeder einzelnen Zelle eines Lebewesens die biologischen Vorgänge wie zum Beispiel den Stoffwechsel und die Zellteilung. 
Alle Zellen eines Lebewesens enthalten die gleichen Erbinformationen in ihren Zellkernen. Die DNA speichert enorme Mengen an Information und wird über Generationen hinweg weitergegeben. Dadurch wird der Bestand einer Art gesichert. Der chemische Aufbau und die molekulare Struktur der DNA sind in allen Lebewesen identisch, gleichgültig ob es sich um Mensch, Pflanze, Pilz oder Bakterium handelt.

====Aufbau====
DNA kommt in allen Lebewesen vor, trägt deren Erbinformation und stellt somit den Bauplan für sämtliche Proteine eines Organismus dar. Die DNA kodiert Aminosäuresequenzen der Proteine.
DNA besteht aus zwei Strängen welche umeinander gewunden sind, die sogenannte Doppelhelix. Jeder Strang besteht aus Desoxyribonucleotiden, welche über Phosphodidesterbindungen miteinander verbunden sind. Desoxyribonucleotid enthält eine organische Base, den Zucker Desoxyribose und Phosphatsäurerest. Durch die lineare Anordnung der Nucleotide entsteht ein Zucker – Phosphat Rückgrat, bekannt als Backbone, von welchem die organischen Basen, A – Adenin , T – Thymin , G – Guanin und  C – Cytosin, abstehen. Durch den parallelen Verlauf stehen sich immer zwei Basenpaare gegenüber, dazwischen befinden sich Wasserstoffbrückenbindungen. Mögliche Paare sind A und T, T und A, G und C, C und G, welche als komplementären Basen bezeichnet werden. Bildlich kann man sich die Doppelhelix als Strickleiter vorstellen, welche zu einer Spirale verdreht ist. Die Holme entsprechen den Zucker – Phosphat Backbones, die Sprossen entsprechen den gepaarten Basen.

[[Bild:S3alhaes_DNA.png | thumb | center |500px | Abb.1: Aufbau DNA]]

===Allgemein===

DNA Computing weist in den Grundzügen Ähnlichkeiten zu Parallel Computing auf. Anhand verschiedener  DNA-Moleküle ist dieses Verfahren in der Lage eine Vielzahl an Möglichkeiten gleichzeitig zu bearbeiten. Bei bestimmten Spezialproblemen, wie z.B. dem NP-vollständigen-Problem, ist es theoretisch möglich, diese schneller und auf kleineren Raum zu lösen als mit konventionellen Prozessoren.
 
In einem Experiment wurde gezeigt, dass das Problem des Handelsreisenden mittels DNA-Computing lösbar ist. In diesem Fall wurde für jede vorkommende Stadt ein Typ DNA-Fragment erzeugt. Diese DNA-Fragmente waren in der Lage eine Bindung zu anderen DNA-Fragmenten gleichen Typs einzugehen. Mittels Reagenzglas entstanden binnen Sekunden aus den kleineren DNA-Fragmenten größere, welche dann die jeweiligen Reiserouten repräsentierten. Durch chemische Reaktionen wurden im Nachhinein DNA-Fragmente, die längere Reiserouten repräsentierten, eliminiert. Somit war man mit der Methode in der Lage das Problem zu lösen, da das entstandene DNA-Fragment die Lösung enthielt. Mit den damaligen Mitteln war man aber noch nicht in der Lage, die Lösung auszuwerten und somit wird dieses Experiment eher als Machbarkeitsnachweis gezählt.
====Vorteile====
*	Hohe Speicherdichte der DNA: $1bit/nm^3$. Bei einem 1 Liter Lösung mit 6g DNA existiert eine Speicherkapazität von $3\cdot10^{19}$ Terabyte
*	DNA ist in großer Anzahl im Reaktionsgefäß vorhanden und kann mittels PCR (Polymerase-Kettenreaktion) vervielfältigt werden. (Hohe Speicherredundanz)
*	Operationen wirken fast alle gleichzeitig auf alle Stränge. (Massive Parallelität)
*	Jedes denkbare Problem kann theoretisch bearbeitet werden.
*	Höhere Haltbarkeit der Daten als bei digitalen Speichermedien.
====Nachteile====
*	Langwierige Aufarbeitung der Rechenergebnisse notwendig.
*	Die Menge der benötigten DNA wächst exponentiell mit dem Aufwand eines Problems. Im Falle des Handelsreisenden bräuchte man bei einer Anzahl von 200 Städten eine Menge an DNA, welche vergleichbar mit der Masse der Erdkugel ist.

==Evolutionäre Algorithmen==

===Motivation===

Als Evolution bezeichnet man allgemein die stammesgeschichtliche Entwicklung von niederen zu höheren Lebensformen. Damit ist die Evolution einer der grundlegendsten Prozesse in der Natur. Mit Hilfe dieser können Arten bzw. Populationen sich u. a. an veränderte Bedingungen anpassen. Dies geschieht durch Faktoren wie der Mutation, der Selektion und der Rekombination. Sie dienen dazu, die Anpassung an die jeweiligen Bedingungen zu optimieren und somit die Chancen zu erhöhen, die Existenz der Population sicherzustellen.
Die evolutionären Algorithmen nehmen sich die genannten drei Hauptfaktoren als Vorbild und versuchen damit Lösungen von deterministisch schwer oder nicht lösbaren Problemen, wie z.B. den NP-vollständigen Problemen, zu finden.

===Einführung===

Anders als bei dem DNA-Computing, welches sich auf das einzelne Individuum bezieht, werden bei den evolutionären Algorithmen ganze Populationen und deren genetisch bedingte Entwicklung betrachtet. Dadurch spielen die Grundlagen der Populationsgenetik in dem Gebiet der evolutionären Algorithmen eine wichtige Rolle. Im Folgenden werden die drei in der Motivation genannten Hauptfaktoren aufgeschlüsselt und erklärt.

====Mutation====
Die Mutation als stochastischer Einflussfaktor ist in der Lage, neue Varianten zu finden und somit festzustellen, ob diese für die jeweiligen Bedingungen eine verbesserte Anpassung darstellen oder ungeeignet sind.  Am Genpool einer Population sorgen sie i. d. R. nur für geringfügige Veränderungen, für die Evolution sind sie aber ein wichtiger Bestandteil, da sich viele verschiedene Mutationen zu einer signifikanten Gesamtänderung summieren können.

[[Bild:S3alhaes_Mutation.jpg | thumb | center |200px | Abb.2: Mutation]]

====Rekombination====
Die Rekombination beschreibt den Prozess, aus dem vorhandenen Erbgut zweier Individuen Erbgut für ein Nachkommen zu erzeugen, welches sich aus dem alten Erbgut zusammensetzt. Durch diesen Prozess ist es möglich, Kombinationen zu finden, welche dem Optimum näher kommen als die vorhandenen.

[[Bild:S3alhaes_Crossover.jpg | thumb | center |200px | Abb.3: Rekombination]]

====Selektion====
Die Selektion beschreibt den Prozess, bei dem sich nur die vorteilhaftesten Eigenschaften einer Population durchsetzen. In der Natur selbst wird damit kein höheres Ziel angestrebt, sondern lediglich eine optimale momentane Anpassung angestrebt. Bei evolutionären Algorithmen kann anhand der sogenannten Fitnessfunktion kann genau abstrahiert werden, welche Eigenschaften positiv bzw. negativ zu bewerten sind.

Die Fitnessfunktion ist die Zielfunktion eines evolutionären Algorithmus. Genauso wie bei den evolutionären Algorithmen im Allgemeinen liegt auch hier ein biologisches Vorbild zugrunde, die sogenannte biologische Fitness. Sie gibt den Grad der Anpassung eines Organismus an seine Umgebung an. Bei den evolutionären Algorithmen besagt die Fitness eines Lösungsansatzes, wie gut er das Optimierungsproblem löst.
Da es zumeist ausreichend ist, bestimmte Ansätze zu vergleichen, um den besseren zu selektieren, muss die Fitnessfunktion nicht zwangsläufig einen absoluten Wert berechnen können. Eine relative Angabe der Fitness genügt in manchen Fällen (z.B. Turnierselektion – „Kandidat a ist besser als b“).
In dem Fall, dass eine Lösung zu n  Problemen gleichzeitig gesucht wird und diese Probleme  nicht zusammengefasst werden können, wird die Fitnessfunktion nicht als Einzelwert, sondern als n-Tupel angegeben. 

===Allgemein===

In den folgenden Teilabschnitten werden kurz die verschiedenen Ausprägungen der evolutionären Algorithmen vorgestellt. Dabei wird das Hauptaugenmerk auf die Beschreibung genetischer Algorithmen gelegt, um ein grundlegendes Verständnis für deren Methodik zu vermitteln. Anschließend werden die Methodiken der verbleibenden drei Ausprägungen, der Evolutionsstrategien, der evolutionären und der genetischen Programmierung, skizziert. Zu beachten ist hier, dass diese strikte Trennung der vier klassischen Ausprägungen in aktuellen Anwendungen zumeist nicht mehr zu finden ist und stattdessen eine große Zahl von Mischformen existiert.

====Genetische Algorithmen====

Genetische Algorithmen (GA) gehören allgemein in das Gebiet der evolutionären Algorithmen und haben die Evolutionstheorie nach Darwin zum Vorbild. Die Grundidee ist dabei, dass sich eine gefundene Lösung eines Problems mit der Zeit entwickelt und verbessert, es sind also naturanaloge Optimierungsprozeduren. Diese Anwendung eines aus der Biologie stammenden Konzeptes geht zurück auf den amerikanischen Mathematiker und Informatiker John Henry Holland. Dieser hat 1975 den Grundstein für unsere heutige Idee der GA gelegt und somit den Ablauf eines GA schematisch wie in Abb.2 dargestellt.

[[Bild:S3alhaes_Evo.png | thumb | center |500px | Abb.4: Prozesskette genetischer Algorithmen]]

Den Anfang eines GA bildet eine Reihe zufälliger erster Lösungen (oder „Individuen“), die bereits das Problem lösen. Kern des ersten Hauptschrittes ist damit die Erzeugung von Zufallszahlen und die Bestimmung von Realisierungen, welche für das gegebene Problem Lösungen darstellen. Danach erfolgt im zweiten Hauptschritt eine Bewertung der Fitness jedes Individuums der Population mittels einer Fitnessfunktion f(x). Im dritten Hauptschritt wird eine neue Population geschaffen, indem die folgenden vier Prozesse solange wiederholt werden, bis die neue Population vollständig ist. Zuerst findet die Selektion statt, d. h. anhand der Fitnessfunktion werden jene Individuen gefunden, durch deren Kombination die besten Nachfolger entstehen. Dabei gilt je besser die Fitness ist, desto größer ist die Chance bei der Selektion ausgewählt zu werden. Anschließend wird die Kombination der Individuen durch die sogenannte Rekombination optimiert. Würde keine Rekombination stattfinden, wären alle Nachfolger jeweils nur eine exakte Kopie ihrer Eltern. Auf die Rekombination folgt die Mutation, um den Genpool der Individuen aufzufrischen. Dabei werden neue, zufällige Kombinationsvarianten zugelassen. Die so entstandenen Nachfolger werden wiederum bewertet. Bei Akzeptanz werden sie in die neue Population aufgenommen und sonst beginnen die vier Prozesse erneut, bis sich auf iterativem Wege eine akzeptable Lösung ergibt. Im vierten Hauptschritt erfolgt ein erneuter Durchlauf des Algorithmus, indem die erstgenutzte Population durch die neue ersetzt wird. Auf diesem Weg kann abschließend getestet werden, ob die beste Lösung in der aktuellen Population gefunden wurde. Bei ausreichender Lösung wird der GA an dieser Stelle beendet, andernfalls startet der Algorithmus erneut beim zweiten Hauptschritt. 

Durch den zufälligen Charakter der Mutation ist diese Prozesskette, wie auch der Ausgangspunkt des Algorithmus, nicht-deterministisch und damit ist zu Anfang des GA nicht bestimmbar, wie viele Generationen von Individuen zur Erzeugung einer akzeptablen Lösung benötigt werden.

====Evolutionsstrategien====

Genetische Algorithmen bilden nicht den einzigen Ansatz für die Digitalisierung einer evolutionären Entwicklung. 1973 stellten die deutschen Informatiker Ingo Rechenberg und Hans-Paul Schwefel von der TU Berlin mit „Evolutionsstrategie“ das entscheidende Schriftstück zu Evolutionsstrategien (ES) vor. In der Grundidee, die Natur als Vorbild zur Lösung eines Optimierungsproblems zu nehmen, gleichen sich ES und GA. Grundlegende Unterschiede werden jedoch in der Wichtigkeit und Verwendung von Mutation und Selektion deutlich. Im Gegensatz zu den GA, wo die Mutation nur von geringer Bedeutung als zerstreuender Effekt ist, spielen in ES Mutation und Selektion eine zentrale Rolle. Während die Mutation bei beiden Ansätzen unabhängig von der Anzahl der Eltern aus einem Individuum ein neues erzeugt, wird sie bei GA klassisch durch das zufällige Invertieren einzelner Bits erzeugt und bei ES durch normalverteilte Veränderungen der Bits. Hinzu kommt der Einsatz selbstadaptiver Steuerungselemente der Parameter bei ES. Gemeint damit ist, dass jedes Individuum zusätzlich eine Information für die Mutationsstärke besitzt.

====Evolutionäre Programmierung====

Die Theorie der evolutionären Programmierung (EP) findet ihren Ursprung in dem 1966 von Lawrence Jerome Fogel, Alvin J. Owens und Michael John Walsh veröffentlichten Buch „Artificial Intelligence Through Simulated Evolution“. Im Unterschied zu klassischen GA und ES spielte dabei jedoch nicht die Optimierung der Lösung eines Problems die entscheidende Rolle, sondern die Entwicklung eines künstlich-intelligenten Automaten, der zur selbstständigen Lösung von Problemen in der Lage sein sollte. Der grundlegende konzeptuelle Unterschied zwischen GA/ES und EP besteht im Wesentlichen darin, dass bei erstgenannten die einzelnen Lösungen als Individuen interpretiert werden, wohingegen bei EP die Lösungen als Populationen interpretiert werden. Entsprechend wird bei EP auf genetische Operationen wie die Rekombination gänzlich verzichtet. Einzig die Mutation wird in der EP angewendet, wobei diese nicht auf einzelnen Bits ausgeführt wird wie bei GA und ES, sondern eine geringfügige Veränderung der Gesamtlösung, also der Population, darstellt.

====Genetische Programmierung====

Die genetische Programmierung (GP) basiert im Gegensatz zu allen drei zuvor genannten Klassen evolutionärer Algorithmen nicht darauf, die Lösung eines Optimierungsproblems zu finden, sondern auf der Idee Computerprogramme zu entwickeln, die selbst ein Problem lösen können. In ihrer modernen Form geht die GP auf den Informatiker John R. Koza und dessen Buch mit dem Titel „Genetic Programming: On the Programming of Computers by Means of Natural Selection“ (1992) zurück.

====Beispiel====

[http://alphard.ethz.ch/gerber/approx/default.html  Symbolische Regression]

==Neuronale Netze==

===Motivation===
Es gibt Arten von Problemen, welche nicht oder nur sehr schwer anhand von Algorithmen gelöst werden können. Dazu gehören unter anderem Frühwarnsysteme oder auch Zeitreihenanalysen. Die dazugehörigen Daten sind von sehr vielen unterschiedlichen Faktoren abhängig und lassen sich deswegen nicht ohne weiteres in einen Algorithmus implementieren. Das Problem besteht darin, dass ein Computer komplexe mathematische Operationen ausführen kann, allerdings nicht lernfähig ist. Ein Ansatz für die Lösung dieses Problems stellen die aus der Gehirnforschung bekannten Neuronalen Netze dar. Anhand dieser wird die Anwendung von mathematischen Modellen, den sogenannten künstlichen neuronalen Netzen, möglich,  welche „lernfähig“ sind und somit einen Lösungsansatz für die beschriebenen Probleme darstellen. 

===Biologische Grundlagen===
Anhand von neuronalen Netzen wird versucht die Struktur und Informationsarchitektur eines Nervensystems von Menschen abzubilden. Sie bestehen aus Neuronen, Gliazellen und einer Umgebung. Die Gliazelle ermöglicht die gegenseitige elektrische Isolation der Nervenzellen. Viel wichtiger für die Funktionsweise eines neuronalen Netzes sind die Neuronen bzw. Nervenzellen. Diese dienen zur Aufnahme, zur Verarbeitung und zur Weiterleitung von Reizen.

====Aufbau Neuronen====

Neuronen bestehen aus Dendriten, Zellkörper, Zellkern, Axon, Myelinscheide, Schwann-Zelle, Ranvierschnürring und Axonterminalen. Zur Erregung eines Neurons läuft das elektrische Signal durch das Axon. Das Axon ist zuständig für die Übertragung eines Aktionspotenziales. Mit Hilfe der Axonterminale kann das Signal chemisch an andere Neuronen bzw. Empfängerzellen weitergeleitet werden. Die Axonterminale selber sind mit den Dendriten anderer Zellen verbunden. Diese sind feine Verästelungen und dienen dazu Signale anderer Zellen zu empfangen und gegebenenfalls weiterzuleiten.

[[Bild:S3alhaes_Neuron.jpg | thumb | center |500px | Abb.5: Detailansicht Neuron]]

====Übertragung von elektrischen Reizen====

Zwischen der Umgebung und dem Axon besteht ein bestimmter Spannungsunterschied, dieser Zustand wird als Ruhepotential bezeichnet. Der Wert des Spannungsunterschiedes ist unterschiedlich, da z.B. die Gliahülle stark ausgebildet sein kann. Durch einen Reiz ändert sich die Spannung. Falls das Ruhepotential überschritten wird gibt das Axon die Differenz von Ruhepotential und Erregung als Aktionspotential an die Axonterminale weiter. Durch die Dendrite anderer Zellen wird das Aktionspotential aufgenommen und wiederum mit dem bestehenden Ruhepotential des Neurons abgeglichen.
 
===Künstliche neuronale Netze===
Ein künstliches neuronales Netz (KNN) ist ein mathematisches Modell, welchem der Aufbau und die Eigenschaften eines neuronalen Netzes zu Grunde liegen. Man verknüpft einzelne, simple Recheneinheiten (Perzeptron = analog zu Neuron) und gewichtet die Stärke der Bindung zwischen jeweils zwei Perzeptronen. Wird ein Gewicht positiv gewertet bedeutet dies einen erregenden Einfluss zwischen zwei Perzeptronen. Ist das Gewicht negativ gewertet, existiert ein hemmender Einfluss. Kein Einfluss existiert bei einem Gewicht von null. Zum Anfang eines jeweiligen KNN lassen sich nicht die gewünschten Ausgaben bestimmter Ein-Ausgabe-Paare herstellen. Dies geschieht erst durch die Wiederholung bestimmter Trainingsmuster. Die Trainingsmuster beinhalten bestimmte Lernregeln und modifizieren die Gewichte der einzelnen Perzeptronenpärchen. Das Wissen eines KNN wird somit in den Gewichten der Neuronen gespeichert.

[[Bild:S3alhaes_KNN.jpg | thumb | center |350px | Abb.6: Vereinfachte Darstellung KNN]]

====Die Basiseinheit Perzeptron====
Ein künstliches Neuron eines KNN ist equivalent zu einem Neuron im biologischen Sinne. Beide verknüpfen viele Eingangssignale über eine bestimmte Funktion mit einem Ausgangssignal. Die einfachste klassische Realisierung eines KNN stellt einsogenanntes Perzeptron dar, auch bekannt als das klassische „Ur-Neuronenmodell“, welches 1958 von Frank Rosenblatt ursprünglich zur Simulation der Netzhaut des menschlichen Auges entwickelt wurde. Ein Perzeptron enthält die Summe aller gewichteten Eingangssignale und eines fixen Eingangssignals $x_0 = 1$, das mit dem Gewicht $\omega_0$ gewichtet wird, und bildet diese Summe $s$ über eine Transfer- oder Aktivierungsfunktion $\sigma$ auf das Ausgangssignal $y$ ab. 

\[Y=\sigma(s)=\sigma(\omega^T \cdot x)=\sigma \left(\omega_0 + \sum_{i=1}^N \omega_i \cdot x_i  \right)\]

Insbesondere bezeichnet man das feste Eingangssignal $\omega_0$  auch als Offset oder Bias. Mathematisch ausgedrückt kann die Summe $s$ auch als das Skalarprodukt der Eingangssignale $x=[1,x_1,\dots,x_N]^T$ mit dem Vektor der Gewichte $\omega= [\omega_0, \omega_1,\dots, \omega_N]^T$ bezeichnet werden.
Symbolisch kann ein Perzeptron damit wie in folgender Abbildung dargestellt werden:

[[Bild:S3alhaes_Perzeptron.jpg| thumb | center |350px | Abb.7: Perzeptron]]

Die Auswahl der Transferfunktion orientiert sich in der Regel an der Art der Anwendung des KNN. Häufig verwendete Transferfunktionen sind unter anderem lineare Funktionen und Signum- oder Stufenfunktionen. Dabei gibt es keine konkreten Empfehlungen, wann welche Funktion angemessen ist. Allgemein kann gesagt werden, dass es in Analogie zum Gehirn vernünftig ist eine Transferfunktion auszuwählen, die in ihrem Wertebereich beschränkt ist. Auch ein biologisches Neuron kann nur ein endlich starkes Ausgangssignal erzeugen. Eine weitere allgemeine Empfehlung zur Wahl der Transferfunktion ist die Differenzierbarkeit. Grund hierfür ist, dass verschiedene Lernregeln, die eine Methode zur Bestimmung der Gewichte  $\omega$ mit Hilfe von Trainingsdaten unter Vorgabe grober Randbedingungen angeben, eine differenzierbare Transferfunktion voraussetzen.
Zusammenfassend ist zu sagen, dass ein Perzeptron durch die Eingangssignale $x$ und deren Gewichte $\omega$ sowie die Transferfunktion $\sigma$ vollständig beschrieben ist. Es spielt dabei keine Rolle, ob die Eingangssignale von einer Schnittstelle außerhalb des KNN stammen oder von vorgeschalteten Perzeptronen.

====Aufbau von KNN====
Der grundsätzliche Aufbau eines klassischen KNN besteht aus der Vernetzung vieler einzelner Perzeptronen, die in parallel geordneten Schichten, den sogenannten Layers, zusammengefasst werden. Dabei wird eine Klassifizierung von KNN anhand der Art der Vernetzung zwischen den Layers und innerhalb der Layer vorgenommen. Diese Einteilung wird auch als Topologie der KNN bezeichnet. 
Beispiele für verschiedene Topologien sind unter anderem vorwärtsgerichtete (Feedforward) Netze und rückgekoppelte (Feedback) Netze. Bei Feedforward Netzen sind von jedem Perzeptron eines Layers nur Vernetzungen in Perzeptronen  der nächsten Layer in Richtung des Ausgangssignals $y$ erlaubt. Eine weitere Unterteilung repräsentieren hier bspw. die Feedforward Netze mit Shortcut Connection. Darin sind zudem Vernetzungen zwischen Perzeptronen erlaubt, die einen Layer überspringen. Diese Topologie ist grundlegend und wird für die weiteren Formen der Vernetzung als Basis angenommen. In Erweiterung zu Feedforward Netzen erlauben Feedback Netze zudem, dass sich ein Perzeptron über beliebige Vernetzungen selbst beeinflussen kann. Dabei gibt es auch für Feedback Netze verschiedenste Varianten, wie bspw. die direkte Rückkopplung, bei der einzelne Perzeptronen zu sich selbst verbunden sind, aber nicht zu Perzeptronen aus vorangegangenen Layers.

[[Bild:S3alhaes_Feedforward_KNN.jpg | thumb | center |350px | Abb.8: Einschichtiges feedforward KNN]]

Allgemein besteht jedes KNN aus einer Eingabeschicht, einer oder mehreren versteckten Verarbeitungsschichten, den sogenannten Hidden-Layers, und einer Ausgabeschicht. Eine namentliche Charakterisierung verschiedener KNN erfolgt zumeist durch die Bezeichnung „n-schichtig“, wobei n die Anzahl der Hidden-Layers plus der Ausgabeschicht ist. Mit zunehmender Zahl von Layers eines KNN steigt zudem die Komplexität und damit auch die Anwendbarkeit auf komplizierte Probleme. Wenn mit einem 1-schichtigen Netz lediglich lineare Klassifikationsprobleme gelöst werden können, können dagegen mit einem 2-schichtigen Netz bereits beliebige Polynome approximiert werden.

===Beispiel===
Eines der grundlegendsten Beispiele zur Anwendung von KNN stellt die Realisierung der booleschen AND-Operation dar. Diese kann mittels eines 1-schichtigen KNN und eines einzigen Perzeptrons dargestellt werden. Gegeben sind zwei binäre Variablen $x_1$ und $x_2$. Die AND-Operation verknüpft die beiden Operanden gemäß folgender Tabelle.
{| class="wikitable"
|-
! Fall !! $x_1$ !! $x_2$ !! $x_1$ AND $x_2$ !! Gewünschte Ausgabe
|-
| 1 || 0 || 0 || 0 AND 0 || 0
|-
| 2 || 0 || 1 || 0 AND 1 || 0
|-
| 3 || 1 || 0 || 1 AND 0 || 0
|-
| 4 || 1 || 1 || 1 AND 1 || 1
|}

Anschaulich vorstellen kann man sich das Beispiel durch die graphische Darstellung. Deutlich wird dabei, dass es sich um ein Klassifikationsproblem handelt, wobei sich die Eingangs- und Ausgangssignale als Koordinaten in einem zweidimensionalen Koordinatensystem darstellen lassen. Es ist möglich, die Punkte $(x_1, x_2) = (0,0), (0,1), (1,0) $ von dem Punkt $(x_1, x_2) = (1,1)$ durch eine Gerade $g$ der folgenden Art zu trennen.
\[g: \omega_0 + \omega_1 x_1 + \omega_2 x_2 = 0\]

Durch manuelles Einstellen der Gewichte lässt sich herausfinden, dass die Gerade $g$ eine gewünschte Klassifikation vornimmt, wenn als Gewichte $\omega_0=-1.5, \omega_1=1, \omega_2=1$ vergeben werden. Damit lässt sich das Perzeptron durch folgende Transferfunktion vollständig beschreiben:
\[Y= \sigma( -1.5 + x_1 + x_2 )\]

[[Bild:S3alhaes_Klasseneinteilung_KNN.jpg| thumb | center |500px | Abb.9: Graphische Darstellung der booleschen AND-Operation (links) und Implementierung von $g$ in einem KNN (rechts)]]

Die sogenannte Aktivierung wird $y=0$ für alle unterhalb der Geraden liegenden Punkte $((x_1, x_2) = (0,0), (0,1), (1,0))$ und $y=1$ für alle oberhalb liegenden Punkte $((x_1, x_2) = (1,1))$.

===Vorteile===

* Mathematische Funktionen von beliebiger Art sind implementierbar. 
* Es bieten sich vielfältige Anwendungsmöglichkeiten auch über das mathematische Kernproblem hinaus. Ein Beispiel ist das in [Quelle] beschriebene Problem der Gesichtsausdruckserkennung.
Quelle: Christine L. Lisetti, David E. Rummelhart. Facial Expression Recognition Using a Neural Network. In Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference, 328-332, 1998
* Robust auch bei verrauschten Eingangsdaten.

===Nachteile===

* Es erfolgt eine implizite Repräsentation von Wissen, verteilt in den Gewichten zwischen den Schichten. Damit eine Art Black-Box.
* KNN’s weisen eine sehr hohe mathematische Komplexität und mangelnde Erklärbarkeit ihrer Wirkungsweise und ihres Verhaltens auf.

==Übungsaufgaben==

===DNA-Computing===

'''1.'''
Setzen Sie sich mit der Visualisierung des DNA-Stranges auseinander und versuchen Sie das System der DNA und der einzelnen vier Basen zu verstehen.

[http://www.csd.uwo.ca/~morey/dnatalk/java/dna.html DNA Applet]

===Evolutionäre Algorithmen===

'''2.'''
Untersuchen Sie die auf der folgenden Seite im unteren Bereich befindlichen Applet's zum Thema Evolutionäre Algorithmen. Varieren Sie die verschiedenen Parameter. Versuchen Sie optimale Lösungen zu finden. 

[http://www.nero.uni-bonn.de/course/courseframe.html  Evolutionäre Algorithmen Applet's ]

'''3.'''
xyz

===Neuronale Netze===


===Lösungen===

'''xyz'''
<popup name="Lösung">

</popup><br><br>

==Literatur==
Christian Wagenknecht ''Algorithmen und Komplexität.'' Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2

==Weblinks==
<sup>[1]</sup> [http://de.wikipedia.org/wiki/Desoxyribonukleins%C3%A4ure Wikipedia DNA]<br>
<sup>[2]</sup> [http://de.wikipedia.org/wiki/Neuronales_Netz Wikipedia Neuronales Netz]<br>
<sup>[3]</sup> [http://de.wikiversity.org/wiki/Kurs:Genetische_Algorithmen Wikiversity Genetische Algorithmen]<br>
<sup>[4]</sup> [http://www.uni-saarland.de/fak7/hartmann/files/docs/pdf/teaching/lectures/talks/WS0607/DNA-Computer.pdf Uni Saarland DNA Computing]<br>