Die Neuronen in einem echten Gehirn sind mit zahlreichen anderen Neuronen ihrer Umgebung verbunden, sind also relativ stark miteinander vernetzt. Bei der Verwendung künstlicher neuronaler Netze hat sich dagegen gezeigt, dass eine zu starke und "ungeordnete" Vernetzung der künstlichen Neuronen zur Lösung vieler Probleme nicht geeignet ist (über das "Warum" kann man nun diskutieren - ich würde ja darauf tippen, dass es unter anderem daran liegt, dass künstliche neuronale Netze über viel weniger Neuronen als echte Gehirne verfügen und dass die Abläufe eines echten Gehirns nur in Teilen nachgebildet werden). Daher ist es üblich, KNNs in einer eher strukturierten Form aufzubauen (wenngleich es auch Projekte gibt, die versuchen, sich dem Aufbau eines echten Gehirns etwas mehr anzunähern - mit viel mehr Neuronen dann natürlich).

Die übliche Form eines künstlichen neuronalen Netzes ist die Schichtenarchitektur; die künstlichen Neuronen werden dabei, wie es der Name sagt, in verschiedenen Schichten (engl. Layer) hintereinander angeordnet. Eine wichtige Schicht ist dabei die letzte, die sogenannte Ausgabeschicht (engl. output layer): die Ausgabesignale der Neuronen dieser Schicht werden "nach außen geleitet", sie bilden gewissermaßen die Ausgabe des KNN (im echten Gehirn wären sie mit den Neuronen vergleichbar, welche Impulse auf vom Gehirn wegführende Nerven leiten). Die restlichen Schichten des KNN sind im Allgemeinen verborgen und werden daher als verdeckte Schichten (engl. hidden layer) bezeichnet. Die folgende Abbildung zeigt ein einfaches zweischichtiges Netz mit einer verdeckten Schicht und der Ausgabeschicht; zudem verfügt es über 3 mögliche Eingaben, die an die Neuronen der verdeckten Schicht angelegt werden:

Sehr gebräuchliche Netztypen sind die einschichtigen und die zweischichtigen Netze. Das widerspricht vielleicht etwas der Erwartung, dass neuronale Netze doch eigentlich etwas komplexes sind und daher möglichst viele Schichten haben sollten; in der Praxis hat sich aber für viele Aufgaben gezeigt, dass derart "einfach" aufgebaute Netze vollkommen genügen, um die gestellten Aufgaben zu lösen.

Sind die Neuronen einer Schicht alle nur mit denjenigen der darauffolgenden Schicht verbunden, spricht man von einem Feedforward-Netz. Ein derartiges Netz ist relativ einfach zu programmieren, hat jedoch einen "Nachteil" (Nachteil in Anführungszeichen, da er in der Praxis nicht immer von Bedeutung ist): Signale werden in derartigen Netzen immer "vorwärts" (daher der Name) von einer Schicht in die nächste gegeben; einmal "errechnete" Informationen werden also weitergegeben und sind dann verloren.

In der Praxis ist das nicht immer von Bedeutung, da genügend Probleme auch ohne die Speicherung von Informationen gelöst werden können. Ab und zu ist es aber doch nötig, dem Netz eine Art von Gedächtnis zu geben. Das Vorgehen hierfür ist ähnlich zu dem, welches ich bereits im letzten Artikel bei der Speicherung von Bits mit Hilfe von Neuronen erläutert habe: es werden zusätzlich zu den vorwärtsgerichteten auch rückwärtsgerichtete Kanten, also Kanten zurück auf ein Neuron selber, auf ein Neuron der gleichen Schicht oder sogar auf Neuronen vorheriger Schichten, eingeführt. Derartige Netze werden folgerichtig als rekurrente Netze bezeichnet und stellen eine Möglichkeit dar, Informationen zu speichern (sie haben also eine Art Gedächtnis), aber auch, zeitlich ausgedehnte Eingaben zu verarbeiten und darin Muster zu erkennen. Obiges Netz erweitert um alle drei Arten von rückwärtsgerichteten Kanten könnte also so aussehen:

Besitzt jedes Neuron eine Verbindung zu jedem anderen Neuron, so spricht man übrigens von einem vollständig vernetzten oder verbundenem KNN.

Welche Art von Netz (mit wie vielen Schichten) und Vernetzung (Feedforward, rekurrent oder vollständig vernetzt) letztendlich für die Lösung eines Problems verwendet werden kann, hängt in der Regel vom Problem selber ab. Mittlerweile gibt es für viele Problemarten best practise-Erfahrungen (ich suche immer noch nach einer vernünftigen deutschen Übersetzung dafür - Vorschläge?), die angewendet werden können. Leider trifft das natürlich nicht auf sämtliche Probleme zu - die Suche nach dem richtigen Netz ist also bereits ein kleines Problem für sich und kann etwa durch ein trial-and-error-Verfahren oder aber auch durch evolutionäre Algorithmen (oder andere Optimierungsalgorithmen) gelöst werden.

Neben der passenden Netzstruktur muss übrigens auch dafür gesorgt werden, dass die möglichen Eingaben auf eine Art und Weise codiert werden, dass sie möglichst günstig in das Netz gefüttert werden können. Oftmals ist diese Aufgabe nicht trivial, da die Codierung der Daten erheblichen Einfluss auf die Effektivität des Netzes hat. Leider können automatisierte Algorithmen dies kaum übernehmen, so dass es in der Regel dem Entwickler eines Netzes überlassen bleibt, eine geeignete Codierung zu finden. Um es noch schwieriger zu machen, muss natürlich auch die Ausgabe des Netzes entsprechend interpretiert werden. Hier gibt es zwei Möglichkeiten: entweder wird versucht, die Ausgaben so zu interpretieren, dass sie einen Sinn ergeben (nichts anderes tun wir im täglichen Leben mit den teils haarsträubenden verbalen Auswürfen diverser Personen des öffentlichen Interesses [die Bissigkeit musste jetzt einmal sein - bitte nicht zu ernst nehmen]), oder das Netz wird dazu gebracht, seine Ausgaben so zu formulieren, wie es der Programmierer erwartet.

Die Findung der richtigen Netzstruktur und die korrekte Codierung der Eingaben reichen allerdings noch nicht aus, um ein KNN auch erfolgreich zur Problemlösung zu verwenden; mindestens ebenso wichtig ist es natürlich, das Netz entsprechend zu konfigurieren, sprich, die Gewichte der Verbindungen zwischen den Neuronen sowie die Schwellwerte und die Aktivierungsfunktionen der einzelnen Neuronen korrekt einzustellen. Hier durch raten, probieren oder "errechnen" auf Anhieb die richtige Konfiguration zu finden, ist sehr schwierig und wird umso schwerer, je größer das Netz ist - es wird also auch hierfür ein Algorithmus benötigt, welcher die richtigen Einstellungen bestimmt. Evolutionäre Algorithmen können auch hier helfen, öfter jedoch wird sich wieder einmal am echten Gehirn orientiert und ein anderes Verfahren verwendet: das Lernen. Ziel dabei ist es, dem KNN durch verschiedene Methoden ein bestimmtes Verhalten anzuerziehen, ganz so, wie Lebewesen im Laufe ihrer Entwicklung neue Dinge lernen können; es soll also dazu gebracht werden, die Ausgaben zu generieren, die erwartet werden. Doch dazu beim nächsten mal ein wenig mehr (und als kleine Vorwarnung: es könnte etwas mathematischer werden).

Über den Sinn, einen Computer im Computer nachzubauen, kann man sich nun natürlich streiten - beeindruckend ist es allemal. Und Spaß hat es sicherlich auch gemacht.

Zuerst einmal (und mehr oder weniger unabhängig von dem, was noch folgt) wollen wir aber zeigen, dass ein künstliches neuronales Netz ebenso mächtig ist wie ein beliebiger moderner Computer, das heißt, die gleichen Dinge berechnen kann. Dazu ist es nötig zu wissen, wie Computer grundsätzlich überhaupt arbeiten, das heißt, wie sie einen Strom von Informationen verarbeiten können. Alte Hasen können jetzt einfach weiterlesen, allen anderen empfehle ich meine Artikelserie zum Thema "Wie Rechner rechnen".

Die Basis der Informationsverarbeitung im Computer stellen die logischen Operationen dar, allen voran die Basisverknüpfungen UND, ODER und NICHT. Mit Ihrer Hilfe lässt sich jede beliebige Verknüpfung von binären Zahlen darstellen; ein System, welches diese Operationen beherrscht und über einen Speicher verfügt, ist -  was die Rechenfähigkeit angeht - ebenso mächtig wie ein handelsüblicher Computer. Ein KNN könnte nun genau dafür benutzt werden; in der Praxis hat das zwar keinen großen Nutzen (immerhin haben wir ja normale Computer), ist aber dennoch interessant, weswegen ich es auch im Folgenden vorstellen möchte. Also immer im Hinterkopf behalten: für die tatsächliche Anwendung künstlicher neuronaler Netze spielt dieser Artikel nur eine untergeordnete Rolle; zum Verständnis der Funktionsweise ist er aber geeignet.

Noch eine Anmerkung, bevor es losgeht: wenn ich im weiteren Verlauf von "Neuronen" rede, so sind damit in der Regel "künstliche Neuronen" gemeint.

Als erstes wollen wir die drei oben genannten Basisverknüpfungen UND, ODER und NICHT mit Hilfe künstlicher Neuronen darstellen. Zur Erinnerung hier noch einmal die Verknüpfungstabelle (in der Reihenfolge NICHT, UND, ODER):

Aus dem letzten Teil wissen wir, dass jedes künstliche Neuron über eine Menge von gewichteten Eingabekanälen, einem Schwellwert, einer Aktivierungsfunktion und natürlich dem Ausgabekanal besteht. Zur Realisierung der NICHT-Funktion wird daher ein Neuron mit einer Eingabe und für die UND- und ODER-Funktion jeweils ein Neuron mit 2 Eingaben benötigt. Für alle drei Neuronen soll gelten, dass sie als Aktivierungsfunktion eine einfache Sprungfunktion verwenden, die beim Überschreiten eines bestimmten Schwellwertes den Wert 1, ansonsten den Wert 0 erzeugt.

Die Neuronen für die UND- und ODER-Funktion lassen sich somit auch ganz einfach beschreiben; die Eingabegewichte werden dazu für alle Eingaben auf den Wert 1 gesetzt und als Schwellwert für das UND-Neuron der Wert 2 und für das ODER-Neuron der Wert 1 gewählt. Wenn wir kurz nachrechnen, erschließt sich dieses Vorgehen auch sofort:

Zur Berechnung des Ausgabewertes eines künstlichen Neurons werden alle Eingaben mit ihrem Gewicht multipliziert, aufaddiert und als Argument für die Aktivierungsfunktion verwendet; erreicht oder überschreitet der Wert des Arguments den Schwellwert, so wird bei einer Sprungfunktion der höhere Wert (hier: 1), ansonsten der niedrigere (hier: 0) erzeugt (und ja, eine Sprungfunktion kann auch umgekehrt funktionieren). 

Für unser ODER-Neuron bedeutet das, dass der Schwellwert 1 erreicht wird, sobald mindestens eine der beiden Eingaben den Wert 1 aufweist (da das Gewicht ebenfalls 1 ist, hat es keine weitere Auswirkung). Das Neuron feuert also, wenn wenigstens eine der Eingaben 1 ist, womit es genau der ODER-Funktion entspricht. Analog dazu feuert das UND-Neuron erst, wenn an beiden Eingabekanälen der Wert 1 anlegt, da nur so der Schwellwert von 2 erreicht wird.

Das NICHT-Neuron wird nun nach dem gleichen Gedankengang umgesetzt; allerdings benötigen wir hier als Gewicht für die einzige Eingabe den Wert -1 und nutzen als Schwellwert 0. Die Überlegung dahinter ist einfach: erhält das Neuron eine 1 als Eingabewert, so wird diese mit dem Gewicht von -1 multipliziert; das Ergebnis (ebenfalls -1) ist natürlich kleiner als 0, wodurch das Neuron nicht feuert. Bei einer Eingabe von 0 allerdings wird der Wert von 0 in die Aktivierungsfunktion gegeben, wodurch gerade der Schwellwert erreicht wird und das Neuron feuert.

Die drei Neuronen lassen sich übrigens grafisch folgendermaßen darstellen (Reihenfolge: NICHT, ODER, UND):

Durch Verknüpfung mehrerer Neuronen können nun alle möglichen logischen Schaltungen nachgebaut werden. Eine sehr einfache (uns schon bekannte) ist die Schaltung zur Addition zweier einzelner Bits, die ja bekanntlich mit Hilfe eines UND- und eines XOR-Gatters realisiert werden kann. Die logische Schaltung und die Schalttabelle für diese einfache Schaltung sahen so aus:

Wie zu sehen, benötigen wir für die Schaltung ein XOR-Gatter (⨁). Die XOR-Funktion lässt sich aber ganz einfach mit Hilfe von NICHT (¬), UND (∧) und ODER (∨) ausdrücken: 

X ⨁ Y = ( X ∧ ¬Y ) ∨ ( ¬X ∧ Y )

Als künstliches neuronales Netz sieht die gesamte Schaltung also folgendermaßen aus (das XOR bläht sie ein wenig auf; zur Übersichtlichkeit wurden die Gewichte weggelassen und negative Gewichte mit einem kleinen Kreis markiert):

Jetzt fehlt zur Simulation eines kompletten Computers eigentlich nur noch eine Möglichkeit, Informationen auch dauerhaft speichern zu können. Auch das lässt sich mit künstlichen Neuronen überaus elegant lösen, funktioniert allerdings anders als in einem echten Gehirn. In letzterem werden die Informationen hauptsächlich durch die Vernetzung zwischen den Neuronen gespeichert; in unserem künstlichen neuronalen Netz wollen wir die Informationen in den Neuronen hinterlegen. Dazu wird sich einer einfachen Technik bedient, nämlich der Weiterleitung der Ausgabe eines Neurons auf seine eigene Eingabe. Betrachten wir das folgende einfache künstliche Neuron (alle Gewichte sind wieder 1 beim Pfeil und -1 beim kleinen Kreis):

Neben den beiden offenkundigen Eingängen S (Set) und R (Reset) hat das Neuron noch einen dritten (namenlosen) Eingang, wobei der Ausgabewert des Neurons direkt auf diesen Eingang geleitet wird. Solange an den beiden Eingängen S und R jeweils kein Wert anliegt, erhält sich der Ausgabewert des Neurons selber (bei einer 0 als Ausgabe wird der Schwellwert nicht erreicht und die Ausgabe bleibt 0, bei einer 1 als Ausgabe wird der Schwellwert gerade erreicht und die Ausgabe bleibt 1) - das Neuron speichert also ein einzelnes Bit. Durch ein kurzes Signal am S-Eingang kann eine Information in das Neuron geschrieben werden (da hierdurch der Schwellwert erreicht wird, das Neuron feuert und sich die Information in Folge selbst erhält), durch ein Signal am R-Eingang wird die gespeicherte Information zurückgesetzt (durch das negative Gewicht ergibt sich in Summe aller Eingänge ein Wert von kleiner oder gleich 0, was unterhalb des Schwellwertes liegt - das Neuron feuert damit nicht mehr). Werden auf beide Eingänge S und R gleichzeitig ein Signal gegeben, ändert sich übrigens nichts am gespeicherten Wert.

 Das künstliche Neuron fungiert somit als einfacher Speicher, der eine Information von einem Bit dauerhaft speichern kann; durch eine geeignete Aneinanderreihung mehrerer derartiger Neuronen kann unser neuronales Netz nun also auch Informationen speichern. Zusammen mit den Neuronen für die logischen Operationen könnte nun also ein beliebiger Computer nachgebildet werden. Einen großen Sinn hat das natürlich nicht, da es ja Computer schon gibt und es nicht allzu viel bringt, sie durch ein künstliches Netz nachzubauen; es verdeutlicht aber doch relativ gut, wie derartige Netze künstliche Neuronen im Prinzip funktionieren. Bei der konkreten Anwendung wird allerdings ein wenig anders vorgegangen, aber dazu gibt es im nächsten Artikel ein paar mehr Informationen.

Künstliche Intelligenzen (abgekürzt KI) sind ja ein beliebtes Thema in Science-Fiction-Literatur und -Filmen, wobei es meist (aus mir unerfindlichen Gründen) früher oder später dazu kommt, dass die KI Allmachtsphantasien entwickelt oder auf andere Art und Weise "den Verstand verliert". Die KI in derartigen Werken wird meist als sehr weit fortgeschritten und dem Menschen mindestens ebenbürtig, wenn nicht sogar überlegen, dargestellt; was dabei aber meist zu kurz kommt, ist eine Beschreibung der technologischen Grundlage dieser künstlichen Intelligenz. Ein geeigneter Kandidat für derartig unberechenbare Intelligenzen sind nun eben die künstlichen neuronalen Netze, da sie dem menschlichen Gehirn nachempfunden sind und ähnlich funktionieren. Aber von vorn.

Unser Gehirn besteht zum überwiegenden zu einem großen Teil aus Nervenzellen oder Neuronen, schätzungsweise einige 100 Milliarden an der Zahl. Eine Nervenzelle besteht hauptsächlich aus drei wichtigen Bestandteilen: dem Zellkörper, den Dendriten und dem Axon (siehe Bild). Der Zellkörper ist der zentrale Bestandteil der Zelle und enthält alle wichtigen Bestandteile, die zum Überleben und Funktionieren der Zelle wichtig sind. Die Dendriten sind gewissermaßen die "Eingänge" der Zelle - über sie werden Reize von anderen Nervenzellen an den Zellkern Zellkörper übertragen. Das Axon ist schließlich der "Ausgang" der Zelle, da die Zelle hierüber Reize an andere Neuronen übertragen kann (die Axonterminale in der Abbildung sind über Synapsen mit Dendriten weiterer Zellen verbunden).

Aufbau eines Neurons (Quelle: Wikipedia)

Ein Neuron funktioniert nun folgendermaßen: über die Dendriten werden von anderen Nervenzellen oder auch Sinneszellen eingehende Reize beziehungsweise Signale an den Zellkörper, konkret: an den Axonhügel (den Ansatz des Axons) weitergeleitet. Dadurch baut sich am Axonhügel ein sogenanntes Erregungspotential auf, also eine elektrische Spannung; (fast) gleichzeitig eingehenden Reize summieren sich hierbei auf. Übersteigt das aufsummierte Erregungspotential am Axonhügel eine bestimmte Schwelle (die folgerichtig als Schwellenpotential bezeichnet wird), wird ein Aktionspotential ausgelöst - man sagt, die Zelle feuert - und über das Axon an die verbundenen Dendriten und damit Nervenzellen verteilt (für die biologisch interessierten: die Reizübermittlung über das Axon und die Dendriten erfolgt elektrisch; zwischen diesen beiden Elementen werden die Reize über die Synapsen meist auf chemischem Weg übermittelt). Je kürzer ein Dendrit ist (also je näher sich seine Synapse am Zellkörper befindet), desto stärker ist auch das Signal, welches das Erregungspotential aufbaut. Noch einmal zusammengefasst: Reize werden über die Dendriten an den Zellkörper geleitet, wo sie sich aufsummieren; die Stärke der einzelnen Reize hängt von der Entfernung ihrer Ursprungssynapsen zum Zellkörper ab. Übersteigt die Summe der Reize einen gewissen Schwellwert, so wird über das Axon ein Signal (fester Stärke, das Aktionspotential) an die umliegenden Zellen weitergeleitet - die Zelle feuert. Das Zusammenspiel aller Neuronen im Körper, allen voran derer im Gehirn, stellt die Reiz- und Informationsverarbeitung dar, die allen Tieren zu eigen ist und von uns allgemein als "Denken" bezeichnet wird (wobei natürlich auch das gesamte vegetative Nervensystem, also die automatisch ablaufenden Vorgänge wie Steuerung des Blutkreislaufes, Verdauung usw. über diese Reizübertratung gesteuert werden).

In den 40er und 50er Jahren des letzten Jahrhunderts (direkt in den Anfängen der Informatik selber!) kamen nun einige clevere Leute auf die Idee, diesen ausgeklügelten Mechanismus der Reizverarbeitung mit Hilfe der gerade aufkommenden Computertechnologie nachzubilden - das war die Geburtsstunde der künstlichen neuronalen Netze (kurz KNN). Im Prinzip ist ein KNN die Nachbildung eines Gehirns mit dem Ziel, die enormen Verarbeitungsfähigkeiten von Gehirnen im Computer nachzubilden. Mittlerweile gibt es die unterschiedlichsten Varianten derartiger künstlicher Netze; im Folgenden und den weiteren Artikeln werde ich das Prinzip im Allgemeinen sowie einige typische Vertreter näher beschreiben.

So wie die Neuronen die zentralen Bestandteile des Nervensystems sind, stellen künstliche Neuronen die Grundbausteine eines KNN dar. Im Prinzip sind Neuronen und künstliche Neuronen ähnlich aufgebaut; beide besitzen viele Eingänge für Reize (die Dendriten beim Neuron), einen Körper, welcher die Reizverarbeitung vornimmt (der Zellkörper) sowie einen Ausgang, über welchen das Ergebnis der Reizverarbeitung an andere (künstliche) Neuronen verteilt wird (das Axon im Neuron). Bildlich kann ein künstliches Neuron folgendermaßen dargestellt werden:

Ein künstliches Neuron (Quelle: Wikipedia)

Die Eingaben x₁ bis x_n entsprechen dabei den Dendriten im Neuron. Wir erinnern uns: die Länge eines Dendrits (die Entfernung seiner Synapse zum Axonhügel) bestimmt den Einfluss des Reizes, der über diesen Dendriten kommt, auf das gesamte Erregungspotential. Dies wird in einem künstlichen Neuron über die Gewichtung w abgebildet; je höher der Wert der Gewichtung, desto größeren Einfluss hat die Eingabe des zugehörigen Eingangs. Die Übertragungsfunktion in der Abbildung stellt gewissermaßen das Äquivalent zum Erregungspotential dar, da hier die ankommenden Signale entsprechend ihrer Gewichte aufsummiert werden. Der Schwellwert entspricht dementsprechend dem Schwellenpotential im biologischen Neuron und die Aktivierung beziehungsweise die Ausgabe stellt das Axon dar.

Eine Besonderheit stellt dagegen die Aktivierungsfunktion dar. Ein natürliches Neuron arbeitet nach dem Alles-oder-nichts-Prinzip, das heißt, dass bei Überschreitung des Schwellenpotentials ein festes, immer gleiches Aktionspotential erzeugt wird. Künstliche Neuronen können nach diesem Prinzip arbeiten, aber ebenso nach anderen; die Aktivierungsfunktion definiert hierbei, welche Ausgabe bei welcher Eingabe in Abhängigkeit des Schwellwertes generiert wird.

Eine häufig verwendete Aktivierungsfunktion ist eine Sprungfunktion, und zwar die sogenannte Schwellenwertfunktion. Diese bildet das Verhalten realer Neuronen nach, da eine konstante Ausgabe erzeugt wird, sobald die Eingabesignale den Schwellwert übersteigen. Weitere mögliche Aktivierungsfunktionen sind lineare und stückweise lineare Funktionen, deren Ausgabe lineare von der Eingabe abhängt (das heißt, bei doppelt so großem Eingabewert ist die Ausgabe auch doppelt so groß) und die ebenfalls relativ häufig verwendeten Sigmoidfunktionen mit einer ungleichmäßigen Abhängigkeit zwischen Eingabe und Ausgabe. Untenstehende Abbildungen zeigen drei mögliche Aktivierungsfunktionen anhand eines Funktionsgraphen; auf der x-Achse findet sich hierbei der aufsummierte und gewichtete Eingabewert, auf der y-Achse kann der zu dieser Eingabe generierte Ausgabewert abgelesen werden. Am Beispiel der Sprungfunktion bedeutet das, dass die Funktion solange den Wert 0 generiert, wie die Eingabe kleiner oder gleich 0 ist (siehe dazu auch die Anmerkung unter den Bildern); sobald die Eingabe aber größer als 0 wird, generiert die Funktion einen konstanten Wert von 1.

Aktivierungsfunktion: Sprungfunktion

In den drei Abbildungen ist jetzt jeweils der Schwellwert noch nicht berücksichtigt worden; dies lässt sich ziemlich einfach erreichen, indem die Kurve einfach nach links (niedrigerer Schwellwert) oder rechts (höherer Schwellwert) verschoben wird. Alternativ (mathematisch äquivalent) kann der Schwellwert natürlich auch einfach von der aufsummierten Eingabe abgezogen werden - das führt zum gleichen Ergebnis.

Es fällt übrigens auf, dass die Eingaben auch negativ sein können. In künstlichen Neuronen wird das erreicht, indem das Gewicht einer Eingabe ebenfalls einen negativen Wert erhält. Auch dafür gibt es eine Entsprechung in echten Neuronen, da bestimmte Synapsen nämlich ein hemmendes statt ein aktivierendes Potential hervorrufen können.

So, damit haben wir eine parallele zwischen biologischen und künstlichen Neuronen hergestellt (letztere können übrigens rein virtuell im Computer, aber auch als echte mechanische Bauteile existieren). In der Theorie könnte man sich nun vorstellen, dass einfach ganz viele künstliche Neuronen hergenommen und - ähnlich einem Gehirn - zusammengeschaltet werden können und schon hat man sich ein eigenes Gehirn gebaut. Ganz so einfach funktioniert das natürlich aber nicht; wie nun aber künstliche neuronale Netze genau eingesetzt (und vor allem, wie sie erzeugt) werden, erzähle ich im nächsten Artikel.

Schadprogramme können in verschiedene Kategorien eingeteilt werden, je nachdem, wie sie sich selber verbreiten und was sie bewirken. Die folgenden drei, nach der Verbreitungsart kategorisierten Typen von Schadprogrammen sind die am häufigste anzutreffenden:

Viren

Viren sind die ursprünglichsten aller Schadprogramme. Ihr Name leitet sich aus ihrer Eigenschaft her, dass sie genau wie ihre biologischen Vorbilder "Wirtszellen", im Falle von Computern also meist Dateien, infizieren und für ihre Zwecke missbrauchen. Dabei schleusen sie ihren Programmcode in eine (in der Regel ausführbare) Datei ein, indem sie ihn zum Beispiel einfach an den Anfang der Datei kopieren. Wird die Datei nun gestartet, so wird auch irgendwann der Code des Virus ausgeführt. Der Virencode bewirkt in der Regel, dass sowohl neue Dateien im Dateisystem befallen als auch oft genug mehr oder weniger schädliche Aktionen durchgeführt werden, indem etwa weitere Dateien auf der Festplatte willkürlich zerstört werden. Ein Computervirus benötigt also ganz wie ein echter Virus immer einen Wirt, welchen er infizieren und für seine weitere Vermehrung benutzen kann. Die Verbreitung eines Computervirus von einem System auf ein anderes kann allerdings nur erfolgen, wenn eine infizierte manuell (das heißt, durch den Anwender) auf ein anderes System kopiert wird. Aus diesem Grund finden sich Viren auch vermehrt in Tauschbörsen und Seiten mit illegalen Programmdownloads, da hier viele Programme - oft ohne weitere Prüfung - über das Netzwerk verteilt werden und somit die Verbreitung der Viren unterstützen (und unter anderem deswegen sollte man auch tunlichst die Finger von derartigen Angeboten lassen).

Würmer

Viren sind passive Schadprogramme, welche eine Interaktion des Nutzers erfordern, um sich zu verbreiten. Demgegenüber stehen die Würmer, die sich aktiv, also ohne das Eingreifen des Anwenders verbreiten. Die Verbreitung läuft hier typischerweise über das Netzwerk; ein auf einem Rechner gestarteter Wurm kann etwa das lokale Mailprogramm ansteuern und sich selber per Mail an sämtliche Kontakte im Adressbuch des Programms schicken. Führen die Empfänger der Mail den Wurm bei sich auf dem Rechner aus (was nicht einmal so unwahrscheinlich ist, da die Mail ja in der Regel von einem vertrauenswürdigen Kontakt kam), so geht das Spiel von vorne los. Würmer können dabei einfache Programme sein, oder auch Dokumente mit automatisch ausgeführtem Code. Auch ist es denkbar, dass eine von einem Wurm verschickte E-Mail lediglich einen Link auf eine Website enthält; wird vom Empfänger der Mail auf diesen Link geklickt, so wird automatisch das Wurm-Programm auf dem Rechner installiert. Der Hauptschaden durch Würmer entsteht dadurch, dass sie die verfügbaren Ressourcen eines Rechners (insbesondere natürlich die verfügbare Internetverbindung) durch ihre weitere Verbreitung stark belasten und somit auch Abstürze des Systems hervorrufen können.

Trojaner

Ein Trojaner - oder eigentlich "Trojanisches Pferd", angelehnt an das trojanische Pferd der griechischen Mythologie - ist (analog zum mythologische Vorbild) ein Programm, welches eine bestimmte, nützliche Funktionalität vortäuscht, aber eigentlich eine ganz andere und meist schädliche Funktion hat. Wird der Trojaner durch den Anwender gestartet, so wird neben dem eigentlichen Programm noch der Schadcode ausgeführt, durch welchen etwa der Rechner ausspioniert oder Viren verbreitet werden können. Trojaner verbreiten sich, ähnlich wie Viren, zwischen Computern nur durch Nutzerinteraktion, wenn die Schadprogramme etwa aus dem Internet heruntergeladen werden. Alternativ kann ein Trojaner aber natürlich auch auf dem Rechner, auf dem er ausgeführt wird, einen Wurm installieren, welcher dann schließlich den Trojaner per Mail automatisiert weiter verbreitet - man hat dann einen Hybriden aus Trojaner und Wurm.

Es ist im Malware-Geschäft durchaus üblich, dass Hybriden aus mehreren Schadprogrammen im Umlauf sind, wenn etwa wie bereits erwähnt ein Trojaner Würmer oder Viren verbreitet oder ein Virus einen Wurm auf einem Rechner installiert. Derartige Verbindungen sind aber immer in ihrer ganzen Schädlichkeit geplant und von vornherein so konzipiert.

Untersuchungen haben nun aber gezeigt, dass Malware-Hybriden auch auf "natürlichem" Weg, also ohne explizite Planung, entstehen können. Das kann dann passieren, wenn ein Virus, welcher ja Dateien auf der Festplatte befällt, einen Wurm auf ebendieser Festplatte infiziert, welcher ja wiederum eine Datei ist (für derartige Verbindungen wurde übrigens der Name "Frankenmalware" geprägt). Das eigentlich Gefährliche ist nun: verbreitet sich der infizierte Wurm übers Netz, so nimmt er den Virus mit sich und trägt zu dessen Verbreitung bei. Wir erinnern uns: die meisten Viren sind nicht in der Lage, Rechnergrenzen zu übertreten, sondern verlassen sich auf die Verteilung durch den Benutzer. Dadurch aber, dass sich Würmer automatisiert verbreiten und Viren quasi im Gepäck mitführen, ergeben sich für die Viren vollkommen neue Verbreitungswege.

Zusätzlich kann es nun auch noch passieren, dass die beiden so im Verbund agierenden Schadprogramme über Funktionalitäten verfügen, welche dem jeweils anderen Programm helfen; wenn etwa der Wurm den Virenscanner eines Rechners blockiert, kann sich der mitgeführte Virus umso leichter ausbreiten.

Und um es noch schlimmer zu machen, wurde ein weiteres Szenario diskutiert. Viele Virenscanner sind in der Lage, Viren aus infizierten Dateien zu entfernen. Dabei geschieht es aber mitunter, dass die Struktur der ursprünglichen Datei bei der Desinfektion leicht verändert wird; nicht so stark, dass sich die Funktionalität ändert, aber immerhin genügend, dass sich die der Datei (gewissermaßen deren Erkennungsmerkmal für den Virenscanner) ändert. Hat nun ein Virus einen Wurm infiziert, wird diese infizierte Datei vom Virenscanner entdeckt und findet dieser zusätzlich noch zuerst den Virus in der Datei und entfernt ihn, so kann es passieren, dass sich die Signatur des Wurms ändert - mit dem Ergebnis, dass er nicht mehr von Virenscannern entdeckt werden kann (denn deren Suche basiert wie gesagt häufig auf dem Signaturvergleich von Dateien). Fast könnte man sagen, dass der Wurm einer evolutionstechnischen Mutation unterliegt, welche seine Überlebenschancen erhöht.

Auch wenn das Thema "Malware" ein eigentlich unerfreuliches ist, so sind derartige Beobachtungen dennoch interessant, da sie gewisse Parallelen zur Biologie besitzen und einen Ausblick darauf geben, was uns im Bereich der Computer noch so alles in Zukunft erwarten kann.

In jedem Fall aber, und diese Gelegenheit für eine Moralpredigt möchte ich mir nicht entgehen lassen, erinnern sie uns daran, was beim Umgang mit dem Internet immer wieder wichtig ist: Finger weg von dubiosen Seiten im Netz, keine illegalen Downloads und auf Links in Mails nur klicken, wenn man genau weiß, wohin der Link führt - man weiß nie, was man sonst bekommt. Und für einen Computer ist eine Vireninfektion nicht angenehmer als für einen Menschen - die alljährliche Erkältung dürfte dafür Argument genug sein.

Übrigens, die restlichen Videos im Kanal des Video-Autors sind auch sehr zu empfehlen.

Das generelle Problem evolutionärer Algorithmen (im weiteren auch einfach als EA bezeichnet) ist, dass sie nicht wirklich zielgerichtet arbeiten; nicht zielgerichtet heißt, dass der "Wert" der optimalen Lösung meist nicht bekannt ist und daher auch nicht gezielt danach gesucht werden kann. Es kann lediglich gesagt werden, welche von 2 möglichen Lösungen für ein Problem die bessere ist. Die eigentliche Problemlösung besteht also aus der Suche nach einer möglichst optimalen Lösung (daher der Name Optimierungsproblem) und nicht aus der Suche nach der optimalen Lösung (weil sie eben meist nicht bekannt ist).

Das ganze lässt sich auch grafisch sehr gut veranschaulichen. Ein Optimierungsproblem besitzt eine (endliche oder unendliche, das spielt keine Rolle) Menge an Lösungen (Individuen), wobei jede Lösung einen bestimmten Fitness-Wert hat. Zudem besitzt der Phänotyp - das Erscheinungsbild - der Lösungen eine bestimmt Anzahl von Parametern (im Katzenbeispiel waren es etwa 2: die x- und die y-Koordinate auf dem Bett). Bei nicht allzu vielen Parametern (im Grunde nur bei 1 oder 2) kann man zur Verdeutlichung der Problematik ein Diagramm anlegen, welches für jede Parameterwahl die Fitness anzeigt

Nehmen wir zum Einstieg das Katzenbeispiel; in diesem Fall besitzt der Phänotyp 2 Parameter (die x- und die y-Koordinate), stellt also ein zweidimensionales Problem dar. Zur Darstellung im Diagramm bietet sich hier zum Beispiel die Nutzung von Graustufen an; weiße Bereiche stellen "gute", im Katzenbeispiel also zentrumsnahe Positionen dar, schwarze Bereiche eher "schlechte Positionen, also solche, die weiter Weg vom Zentrum sind. Für das Katzenbeispiel ergibt sich hier ein relativ homogenes Bild mit einem weißen Zentrum und gleichmäßig dunkler werdenden Bereichen:

Eine Anmerkung noch, bevor es weitergeht: wenn wir nicht nur auf 3 Dimensionen beschränkt wären, ließen sich auch Probleme mit mehr Parametern darstellen; so beschränken wir im Folgenden aber auf Grund physikalischer Gesetzmäßigkeiten auf 1 und 2 Dimensionen - alles gesagt ist aber natürlich ebenso auf komplexere Probleme anwendbar!

Jetzt ist das Katzenbeispiel relativ simpel, da der Kurvenverlauf für die Fitnesswerte relativ eindeutig ist: von jedem Punkt des Koordinatensystems aus werden die Werte zur Mitte hin besser und erreichen genau in der Mitte ihr Optimum. Reale, durch evolutionäre Algorithmen lösbare und gelöste Probleme haben diesen Luxus nicht. Ein (beliebiges) anderes Problem mit 2 Parametern könnte etwa das folgende Fitnessdiagramm aufweisen (welches natürlich so meist überhaupt nicht bekannt ist - wir tun nur einmal so, als würden wir es kennen):

Im Bild erkennen wir, dass neben dem "besten" Optimum links oben noch ein "weniger gutes" Optimum rechts unten existiert (für die Sprachpedanten unter den Lesern: ich weiß, dass es kein "bestes" oder "weniger gutes" Optimum geben kann - die Begriffe sind hier eher umgangssprachlich gemeint; man möge mir verzeihen). Das Optimum oben links wollen wir im Folgenden als globales Optimum bezeichnen, da es global (also im ganzen Diagramm) das beste ist; das Optimum rechts unten ist dementsprechend ein lokales Optimum, da es lokal (unmittelbar in seiner Umgebung) den besten Wert darstellt (das globale Optimum ist somit auch gleichzeitig ein lokales). Gängige Probleme der Realität haben nicht nur 2 lokale Optima, sondern viel viel mehr, und leider weiß man in der Regel nicht, wo denn diese lokalen Optima liegen.

Dieses Problembild nun verdeutlicht sehr gut, welche Probleme bei der Verwendung evolutionärer Algorithmen auftreten können. Wir erinnern uns: es wurde bereits erwähnt, dass bei einem EA mehrere Parameter (die nichts mit den Problemparametern wie der Position der Katze zu tun haben) eingestellt werden können; insbesondere seien hier die Parameter für die Rekombinationsrate, die Mutationsrate und den Selektionsdruck genannt.

Die Rekombinationsrate bestimmt, wie viele für die nächste Generation ausgewählte Individuen miteinander rekombiniert werden sollen, bevor sie in die nächste Generation eingehen. Ein Wert von etwa 0.33 bedeutet, dass jeweils ein Drittel der ursprünglichen Individuen rekombiniert werden sollen und weitere zwei Drittel direkt in die nächste Generation übernommen werden.

Die Mutationsrate kann entweder dafür stehen, wie viele der Individuen der neuen Generation mutiert werden (bei einem Wert von 0.33 würden wieder im Schnitt ein Drittel der Individuen mutiert werden), oder aber auch, wie stark die Mutation ausfällt (ein Wert von 0.33 heißt, dass 33% des Genotyps zu mutieren sind, was ziemlich viel ist) - letztere Bedeutung kann sich aber durchaus auch in einem eigenen Parameter niederschlagen. 

Über den Selektionsdruck schließlich wird bestimmt, welche Individuen in die nächste Generation übernommen werden sollen. Ein hoher Selektionsdruck lässt nur die allerbesten Individuen für die Rekombination und Mutation zu, ein etwas geringerer Druck erlaubt auch "schlechtere" Individuen. Dies ist übrigens durchaus mit dem Selektionsdruck in der Biologie zu vergleichen; ein Pflanzenfresser in einer Region mit vielen Fleischfressern unterliegt in Bezug auf den Faktor "Prädator" einem starken Selektionsdruck - durch die Evolution werden insbesondere die Individuen "bevorzugt" (indem sie sich am meisten fortpflanzen können), welche am besten das Gefressenwerden vermeiden können. Sind in der Gegend aber wenige bis keine Prädatoren vorhanden, so ist der Selektionsdruck in Bezug auf diesen Faktor dementsprechend gering. In der natürlichen Welt existieren natürlich weitaus mehr Faktoren, die für die Selektion verantwortlich sind; bei den evolutionären Algorithmen gibt es (meist) nur einen einzigen Faktor, und das ist der Fitnesswert eines Individuums.

Was haben nun aber diese drei Parameter mit den lokalen Optima zu tun? Nun, nehmen wir zum Beispiel eine geringe Rekombinations- und Mutationsrate und einen hohen Selektionsdruck an. In so einem Fall unterscheiden sich aufeinanderfolgende Generationen nur geringfügig voneinander, wobei die Individuen in einer Folgegeneration im Schnitt ein klein wenig besser geworden sind. "Besser" heißt, dass sie sich etwas zum Optimum hin bewegt haben - aber welchem? Bei mehreren lokalen Optima wandern sie für gewöhnlich zum nächstgelegenen Optimum hin. Das impliziert aber auch, dass sie, haben sie einmal ein lokales Optimum erreicht, nicht zu einem anderen wandern werden - man sagt, der EA konvergiert in einem oder mehreren lokalen Optima. Wenn wir nun weiter berücksichtigen, dass die Individuen der ersten Generation zufällig erzeugt werden, lässt sich daraus schließen, dass das Gesamtergebnis des EA stark von dieser Ausgangssituation abhängt - wurden Individuen nahe des globalen Optimums erzeugt (welches man ja eigentlich erhalten möchte), wird dieses auch als Ergebnis der Berechnungen gefunden werden können. Befand sich initial allerdings kein Individuum in der Nähe des globalen Optimums, so wird irgendein lokales Optimum als bester gefundener Wert ermittelt; manchmal kann das ausreichend sein, oft genug ist es das jedoch nicht.

Auf der anderen Seite könnte man natürlich aber auch eine hohe Rekombinations- und Mutationsrate wählen. Aber auch das ist ist nicht optimal; je höher diese Werte nämlich sind, desto größere Sprünge machen die Individuen in aufeinanderfolgenden Generationen, da ja potentiell stärkere Veränderungen in ihrem Genotyp und damit dem Phänotyp auftreten. Ist zudem der Selektionsdruck gering, führt das dazu, dass der EA überhaupt nicht konvergiert, sondern sich die Individuen zufällig im Lösungsraum verteilen. Bei einem stärkeren Selektionsdruck werden sie sich dagegen zwar alle in der Nähe von lokalen Optima aufhalten und eventuell sogar den Sprung von einem lokalen Optimum zum nächsten schaffen können; jedoch konvergiert der Algorithmus auch hier nicht, da die einzelnen Individuen aufeinanderfolgender Generationen durch die starken Änderungen in ihrem Genotyp immer um die lokalen Optima kreisen, ohne jemals eins wirklich zu erreichen. Auch damit ist keinem geholfen.

Fassen wir also noch einmal zusammen: eine geringe Rekombinations- und Mutationsrate, verbunden mit hohem Selektionsdruck führt zu einem Konvergieren des Algorithmus in verschiedenen lokalen Optima, welche mehr oder weniger ausschließlich von der Ausgangskonfiguration abhängen. Eine hohe Rekombinations- und Mutationsrate bei hohem Selektrionsdruck führt dazu, dass die Individuen zwar nicht unbedingt bei wenigen lokalen Optima "hängenbleiben", sondern auch zwischen mehreren springen können, diese jedoch selten direkt erreichen - der Algorithmus konvergiert nicht. Ein zu geringer Selektionsdruck führt im Allgemeinen dazu, dass der EA nicht konvergiert, da immer wieder schlechte Individuen in die nächste Generation übernommen werden und somit keine zielgerichtete Optimierung stattfinden kann.

Die Schwierigkeit bei der Verwendung von evolutionären Algorithmen liegt also darin, die Parameter für Rekombinationsrate, Mutationsrate und Selektionsdruck so zu wählen, dass sie zum möglichst besten Ergebnis führen. Wie aber lässt sich das erreichen?

Für einen Teil der per EA lösbaren Optimierungsprobleme besteht die Lösung einfach darin, dass mit verschiedenen Parameterkonfigurationen experimentiert wird, bis eine gefunden wird, die zu brauchbaren Ergebnissen führt, das heißt, wo das Verhältnis von Konvergenz zu lokalen Optima und Springen zwischen den Optima ideal ist. Insbesondere Probleme, für welche einmal eine derartige Konfiguration gefunden und dann für verschiedene Probleminstanzen wiederverwendet werden kann, ist dieser Ansatz brauchbar.

Nicht alle Optimierungsprobleme lassen sich allerdings auf diese Art lösen. Der alternative Ansatz besteht in der Verwendung einer adaptiven Parameterwahl. Hierbei wird zuerst eine hohe Mutations- und Rekombinationsrate sowie ein geringer Selektionsdruck gewählt. Im Laufe der Generationen werden diese Parameter allerdings angepasst: die Mutations- und Rekombinationsraten sinken langsam und der Selektionsdruck steigt. Zu Beginn können sich die Individuen also relativ frei im Lösungsraum bewegen, mit fortschreitender Laufzeit des Algorithmus werden sie dagegen immer mehr zur Konvergenz auf ein lokales Optimum hin gezwungen (in diesem Punkt ähneln die evolutionären Algorithmen übrigens dem simulierten Abkühlen, mit dem Unterschied, das bei den EA mehrere Individuen betrachtet werden).

Wir haben nun also kennengelernt, wie die Parameter eines evolutionären Algorithmus gewählt werden können, um eine möglichst optimale Lösung finden zu können. Damit schließt die Reihe zu den evolutionären Algorithmen - das nächste mal geht es aber mit einem ähnlich spannenden Thema weiter.

Das erste ist ein Medley aus verschiedenen Stücken der Zelda-Reihe, gespielt von Lindsey Stirling; musikalisch orientiert sich das Medley (wie es für Medleys eben üblich ist) nahe am Original und kombiniert die ohnehin schon gute Musik zu einer ganz neuen Ohrenweide:

Das zweite Video ist eine wunderbare Opern-Umsetzung von Super Mario Bros. Musikalisch hat es (bis auf das 8-Bit-Gepiepse) nichts mit dem Spiel zu tun, sondern lässt den Helden von damals noch einmal klangvoll aufleben:

Und hier noch ein Bonus-Video für alle, die mit Computerspielen vielleicht nicht so viel anfangen können, dafür aber eingefleischte Star-Wars-Fans sind; die Piano Guys machen auch immer sehr schöne Videos:

Da bleibt nur noch der Abschlusskommentar des letzten Videos zu wiederholen:

You will start cello lessons - now.

In der Tat - fast hätte man Lust dazu.

Rekapitulieren wir noch einmal das Problem. Um die Eigenschaften eines Individuums zu mutieren, muss natürlich jede einzelne Eigenschaft bekannt und zudem vorgegeben sein, wie und vor allem in welchem Rahmen sie geändert werden darf. Auch für die Rekombination - die Verschmelzung der Eigenschaften zweier Individuen zu einem Kind - müssen natürlich sämtliche Eigenschaften der Individuen bekannt sein. Prinzipiell ist das natürlich kein Problem, führt jedoch dazu, dass ein einmal geschriebenes Programm nur zur Lösung exakt des Problems geeignet ist, für welches es entworfen wurde. Hinzu kommt, dass die Rekombination einzelner Eigenschaften zu einer insgesamt geringeren Variabilität zwischen den einzelnen Generationen von Individuen führt. Denken wir etwa an das Beispiel aus dem letzten Artikel: ein Individuum bestand bestand dort aus jeweils 2 Eigenschaften - der vertikalen und der horizontalen Position -, deren Rekombination nur zu ganz bestimmten Kindern führen konnte, wobei pro Elternpaar jeweils nur 2 verschiedene Kinder überhaupt möglich waren. Mit steigender Anzahl von Eigenschaften würde übrigens auch der Programmieraufwand immer weiter ansteigen, da die Funktionen zum Mutieren und Rekombinieren immer mehr Eigenschaften beachten müssten. Ein Ansatz, der sowohl allgemeingültig (und damit problemunabhängig) ist und auch problemlos auf "größere" Individuen angewandt werden kann, wäre also von Vorteil.

Die Idee ist relativ einfach: anstatt ein Individuum durch seine konkreten Eigenschaften - seinen Phänotyp - zu beschreiben, werden diese Eigenschaften in Form einer Bitkette codiert. Im Kontext unseres Beispiels aus dem letzten Artikel (wer sich nicht erinnert, möge noch einmal nachlesen) würde das bedeuten, dass die beiden Positionen (die vertikale und die horizontale) einfach durch Bitketten repräsentiert und aneinandergereiht werden. Nehmen wir an, ein Individuum hat die Position (12,7) und die möglichen Positionen befinden sich im Intervall (0,0) bis (15,15); es reichen also 4 Bit aus, um eine Komponente der Position zu beschreiben (wir erinnern uns). Dual codiert erhalten wir damit die Position (1100,0111); in einer einzigen Bitkette zusammengefasst können wir also durch die Kette 11000111 das Individuum beschreiben, welches an Position (12,7) liegt. Diese codierte Bitkette wollen wir - analog zur Genetik - als Genom bezeichnen.

Auf die gleiche Art und Weise kann nun jedes beliebige Individuum codiert werden. Es ist dabei übrigens nicht notwendig, dass die Eigenschaften eines Individuums zwingend aus einzelnen Zahlen bestehen, die dual codiert und dann aneinandergereiht werden. Die Codierung in eine Bitkette kann beliebig aussehen; es muss lediglich möglich sein, aus dieser Bitkette - dem Genotyp - das eigentliche Individuum - den Phänotyp - wiederherstellen zu können. Für diese Wiederherstellung wird eine Funktion g definiert, welche eine Bitkette auf das zugehörige Individuum abbildet. Für obiges Beispiel würde das etwa bedeuten, dass

g(11000111) = (12,7)

ist. Wie die Abbildung genau funktioniert, liegt dabei allein im Ermessen des Programmierers und kann praktisch beliebig umgesetzt werden. Zudem muss natürlich festgelegt werden, ob die Bitkette eine feste Länge haben soll (wie in unserem Beispiel mit 8 Bit) oder ob sie variabel sein kann; das hängt aber wie immer vom konkreten Problem ab. Übrigens muss man sich natürlich nicht auf Bitketten beschränken - jedes beliebige Wertesystem kann die Grundlage für die Informationskette bilden. Häufig verwendete Systeme sind eben das duale System, das Dezimalsystem mit nur natürlichen oder ganzen Zahlen oder auch das Dezimalsystem mit reellen Zahlen.

Wo liegt nun aber der eigentliche Vorteil darin, ein Individuum als Wertkette zu codieren und nicht den Phänotyp direkt für Mutation und Rekombination zu benutzen? Genau wie in der Natur alle Lebewesen auf der DNA basieren und Mutation sowie Rekombination den gleichen Prinzipien folgen - sei es ein Fisch, ein Insekt, eine Pflanze, ein Mensch oder ein anderes Tier -, können die gleichen Techniken bei der Mutation und Rekombination von Wertketten in einem evolutionären Algorithmus angewendet werden, unabhängig davon, wie das codierte Individuum aussieht. Man sagt, dass die Mutation und Rekombination auf dem Genotyp der Individuen stattfinden.

Die möglichen Mutationen hängen nun nicht mehr von den Eigenschaften des Individuums ab, sondern nur noch von den Operationen, die auf Wertketten - dem Genom - stattfinden können. Die einfachste Operation ist hier sicherlich auf Bitketten möglich: die Invertierung einer einzelnen, zufällig gewählten Position im Genom - aus einer 0 wird eine 1 oder umgekehrt - bewirkt die kleinstmögliche Änderung an einem derart codierten Individuum. Etwas umfangreichere Mutationen können mehrere Stellen im Genom oder ganze Abschnitte invertieren, bis hin zur gesamten Bitkette (wobei über die Sinnhaftigkeit einer solchen Makro-Mutation natürlich gestritten werden kann). Besteht das Genom nicht aus binären, sondern etwa aus natürlichen, ganzen oder reellen Zahlen, so können die einzelnen Positionen zwar nicht invertiert, so doch aber auf verschiedene andere Arten modifiziert werden. Denkbar ist hier alles, was man einer Zahl so antun kann; man kann Werte hinzuaddieren oder abziehen, man kann sie mit einem Faktor multiplizieren oder man kann dividieren, man kann sie auf einen Höchst- oder Mindestwert setzen und so weiter. Unabhängig von der dem Genom zugrundeliegenden Zahlenbasis kann man auch Abschnitte des Genoms austauschen oder - bei variabler Genomlänge - Abschnitte löschen oder zufällige neue Abschnitte hinzufügen. Ein kleines Beispiel hierzu; nehmen wir dazu unser obiges Beispielindividuum 11000111, welches die Position (12,7) codiert. Wenden wir verschiedene Mutationen darauf an, so können sich etwa die folgenden Individuen ergeben:

Invertierung einer einzelnen Bitposition (4):
11000111 -> 11010111 = (13,7)

Invertierung von zwei Bitpositionen (4 und 7):
11000111 -> 11010101 = (13,5)

Vertauschung zweier Genomabschnitte ([2,3] mit [5,6]):
11000111 -> 10111011 = (11,11)

Auch bei der Rekombination kann die einheitliche Darstellung des Genoms ausgenutzt werden. Ein typischer Rekombinationsvorgang eines evolutionären Algorithmus sieht so aus, dass die Genome zweier (oder mehrerer) Elternindividuen hergenommen, geteilt und zu (meist zwei) neuen Individuen zusammengesetzt werden. Die Teilung kann nach verschiedenen Verfahren erfolgen. Häufige Verwendung findet hier der 1-Punkt-Crossover, bei welchem die beiden Genome der Eltern an der gleichen Stelle geteilt und die beiden Teile jeweils untereinander vertauscht werden. Analog kann natürlich auch ein 2-Punkt-Crossover mit 2 Teilungspunkten oder ein beliebiger n-Punkt-Crossover verwendet werden. Darf die Länge des Genoms variieren, können die Teilungspunkte für den Crossover auch an unterschiedlichen Stellen innerhalb der Genome der Eltern liegen, so dass die Genomlänge der Kinder von der der Eltern abweicht. Da die Teilungspunkte in den Genomen natürlich nicht zwingend an den Stellen liegen müssen, welche bestimmte Eigenschaften des Individuums codieren (sofern überhaupt eine direkte Abbildung von Genomabschnitten auf Eigenschaften vorhanden ist), können bereits bei der Rekombination neue Eigenschaften entstehen, wodurch die Variabilität der Individuen in der Nachfolgegeneration erhöht wird (ein oft begrüßenswerter Umstand bei der Anwendung evolutionärer Algorithmen; warum, sehen wir im nächsten Artikel). Zur Demonstration noch 3 kleine Bilder (übernommen aus der Wikipedia); die beiden Farben repräsentieren jeweils die Genom(abschnitt)e der beiden Elternteile:

1-Punkt-Crossover:

2-Punkt-Crossover:

1-Punkt-Crossover mit variabler Genomlänge:

Mit dem hier beschriebenen Verfahren ist es also möglich, einen einmal programmierten evolutionären Algorithmus auf jedes beliebige Problem anwenden zu können. Anstatt immer den gesamten Algorithmus neu programmieren zu müssen, reicht es zur Problemlösung also, 3 problemabhängige Informationen vorzugeben: die Art des Genoms der Individuen (die Basis der Wertkette, ob es fester oder variabler Länge sein kann und ob Restriktionen etwa in Bezug auf die größtmögliche Zahl in einem Genom mit Dezimalzahlen bestehen); die Abbildungsfunktion g, welche den Genotyp eines Individuums auf seinen Phänotyp abbildet; und natürich die Fitnessfunktion f, die den Phänotyp (alternativ natürlich auch direkt den Genotyp) eines Individuums bewertet. Mit Hilfe dieser 3 Angaben kann ein einmal programmierter Algorithmus prinzipiell auf jedes beliebige, [update]durch evolutionäre Algorithmen zu lösende[/update] Problem angewendet werden. Eine, wie ich finde, überaus elegante Lösung, welche das Vorbild der Natur aufgreift und zur Lösung von Problemen einsetzt.

Rekapitulation

Rekapitulieren wir zuerst noch einmal die Arbeitsweise eines evolutionären Algorithmus. Ausgehend von einer Anfangsgeneration g₀ werden sukzessive neue Generationen erstellt, indem aus der aktuellen Generation jeweils einige Individuen (die Lösungskandidaten) selektiert, also ausgewählt werden; Vertreter dieser Auswahl werden rekombiniert, also miteinander gekreuzt und das entstehende neue Individuum noch einmal mutiert, also verändert. Durch Wiederholung der Rekombination und Mutation entsteht eine neue Generation, welche die Ausgangsbasis für die nächste Iteration im Algorithmus darstellt. Das ganze wird so lange wiederholt, bis eine hinreichend gute Lösung gefunden wurde. Der Pseudocode hierfür sieht so aus:

(1)  Evolutionary Algorithm: g₀ ∈ Tⁿ → T:
(2)    t ∈ T
(3)    g ∈ Tⁿ, g ← g₀
(4)    do:
(5)       g', g'' ∈ Tⁿ
(6)       g' ← select individuals from g
(7)       g'' ← recombine individuals in g'
(8)       mutate individuals in g''
(9)       t ← select best individual in g''
(10)   while t not good enough
(11)   return t

Schauen wir uns doch die Schritte einmal in der Reihenfolge der Ausführung im Detail an. Anzumerken ist vorher, dass es für jeden Schritt die verschiedensten Strategien gibt, deren Anwendbarkeit meist eng mit der in den jeweils anderen Schritten gewählten Strategie zusammenhängt; bei manchen Strategien kann es sogar passieren, dass Selektion und Rekombination zu einem Schritt verschmelzen. Ich werde im Folgenden das allgemeine Vorgehen bei den einzelnen Schritten beschreiben und einige der möglichen Strategien vorstellen.

Das ganze möchte ich parallel an einem kleinen Beispiel demonstrieren. Bevor ich hier aber mit einem mathematischen Problem anfange und damit zusätzliche Verwirrung stifte, nehme ich lieber ein praktisches (und nicht ganz ernst gemeintes) Problem aus der realen Welt (welches zudem zumindest jedem Katzenbesitzer bekannt sein dürfte). Betrachten wir das folgende Bild (via icanhascheezburger.com):

Das Optimierungsproblem hier dürfte klar sein: wir sind eine Katze und möchten und so positionieren, dass wir den maximalen Platz auf dem Bett einnehmen, also genau in der Mitte liegen. Tun wir zudem so, als wüssten wir nicht genau, wo die Mitte ist und würden sie durch einen evolutionären Algorithmus bestimmen wollen. Das Optimierungsproblem ist also, eine Position genau in der Mitte zu finden; die Lösungskandidaten sind die verschiedenen möglichen Positionen auf dem Bett.

Selektion

Die Selektion ist der Schritt, in welchem aus der aktuellen Generation Individuen für die Rekombination ausgewählt werden. Grundsätzlich lassen sich hier zwei Vorgehensweisen unterscheiden, deren Wahl die genaue Funktionsweise der Rekombination beeinflusst. Zum einen kann zuerst die zu rekombinierende Menge an Individuen komplett ausgewählt werden; die Rekombination erfolgt dann in der Regel, indem jeweils zwei Individuen aus der selektierten Menge zufällig ausgewählt und miteinander gekreuzt werden. Zum anderen können Selektion und Rekombination auch gleichzeitig erfolgen, indem wiederholt zuerst zwei Individuen ausgewählt und diese direkt miteinander rekombiniert werden - die Zeilen (6) und (7) im Pseudocode würden also zu einer verschmelzen und es würde keine Zwischenmenge g' entstehen.

In jedem Fall wird aber ein Kriterium gebraucht, nach welchem die Individuen ausgewählt werden sollen. Das einfachste wäre natürlich eine zufällige Selektion; dies würde aber vollkommen den Selektionsdruck (dieser entsteht nämlich durch die Strenge der Selektion) nehmen und damit zu einer ungerichteten Evolution führen - dem Ziel würde man damit nicht näher kommen. Ein anderes Selektionsverfahren ist also notwendig!

Im Allgemeinen kann man sagen, dass eher Individuen ausgewählt werden sollen, welche "besser", also näher an der gewünschten Lösung dran sind. Um ein Individuum nach seiner Güte zu beurteilen, wird dazu die sogenannte Fitnessfunktion (meist mit f  bezeichnet) benutzt. Der Wortbestandteil "Funktion" entspricht hier ganz der mathematischen Bedeutung: die Fitnessfunktion ist eine mathematische Funktion, welche ein Individuum als Argument verlangt, dieses intern bewertet und seine Güte als einen Zahlenwert zurückgibt. Dieser Zahlenwert kann je nach Problem in einem begrenzten oder einem offenen Intervall liegen; ob die kleineren Werte "besser" sind oder die größeren, hängt auch vom Problem ab. Unabhängig davon aber können mit Hilfe der Fitnessfunktion sämtliche Individuen in der Generation bewertet und ihrer Güte nach sortiert werden - und das wird in der Regel auch zuerst gemacht.

Für die Selektion gibt es nun die verschiedensten Möglichkeiten. So können zum Beispiel streng die besten X Individuen für die weitere Rekombination ausgewählt werden, es können unter den besten X zufällig Individuen ausgewählt werden (auch mehrfach und damit auch mehr als X - ein Individuum kann sich ja wie ein Lebewesen auch mehrfach paaren) und es ist auch denkbar, unter allen Individuen beliebig zu wählen, wobei die Wahlwahrscheinlichkeit X eines Individuums umso höher ist, je höher seine Güte ist. Weitere Auswahlverfahren sind natürlich möglich; in jedem Fall wird man aber eine Menge von Individuen für die Rekombination erhalten, deren durchschnittliche Güte besser als der Durchschnitt ist - der Evolution wird damit eine Richtung gegeben. Je strenger übrigens der Parameter X gewählt wird, desto stärker ist der Selektionsdruck; im extremsten Fall wird nur noch das beste Individuum zur Rekombination ausgewählt (warum das keine gute Idee ist, sehen wir aber ein andermal). Schreiben wir die Selektion einmal im Pseudocode auf (f ist unsere Fitnessfunktion):

(1)  select individuals: g ∈ Tⁿ → Tⁿ:
(2)    for all t ∈ g:
(3)      t.fitness ← f(t)
(4)    g' ∈ Tⁿ, g' ← {}
(5)    while not enough elements in g':
(6)       t ∈ T
(7)       t ← select element from g according to strategy
(7)       g' ←  g' ∪ {t}
(8)   return g'

Angewendet auf unser Katzenproblem haben wir als Fitnessfunktion natürlich diejenige Funktion, welche die Entfernung von einer Position zur Bettmitte bestimmt; niedrigere Zahlen sind also besser, die 0 wäre das Optimum. Wir nehmen an, dass die Funktion das auf magische Art und Weise bestimmt, da wir ja - wie abgesprochen - nicht wissen, wo die Mitte ist (bei der Lösung realer Probleme weiß man in der Regel auch nicht, wie die beste Lösung aussieht, kann aber die Güte der Individuen trotzdem meist auf die ein oder andere Art berechnen oder wenigstens schätzen). Hier ein kleines Beispielbild mit einigen möglichen (zufällig generierten) Lösungskandidaten, ihrer Güte (geschätzte Entfernung zur Mitte) und (schwarz markiert) denjenigen Individuen, die für die Rekombination nach einer nicht näher benannten Strategie ausgewählt wurden (der schwarze Punkt in der Mitte ist, nun, die Mitte):

Rekombination

Wurde durch Selektion eine Menge von geeigneten Individuen ausgewählt, können wir nun daran gehen, diese miteinander zu (re-)kombinieren, sie miteinander zu kreuzen. Dazu wählt man jeweils zwei Individuen zufällig aus der selektierten Menge aus (oder selektiert, wie bereits erwähnt, erst an dieser Stelle 2 Individuen aus der Gesamtmenge) und vermischt ihre Eigenschaften miteinander, ganz so, wie es bei der natürlichen Fortpflanzung geschieht (das ist jetzt natürlich etwas vereinfachend dargestellt, aber als Analogie geeignet). Jedes Individuum hat in der Regel eine feste Menge an Eigenschaften, genau wie ein Lebewesen (zum Beispiel Haar- oder Fellfarbe, Körpergröße, Blütenblattfarbe und ähnliches) und genau wie in der realen Welt erbt ein erzeugtes Individuum eine Mischung der Eigenschaften seiner Eltern (an etwaig mitlesende Biologen: dominante und rezessive Vererbung spielen bei evolutionären Algorithmen keine Rolle, da jedes Individuum eher einer Keimzelle entspricht und damit haploid ist). Die Vermischung kann auch auf unterschiedliche Arten erfolgen, etwa, indem jede der möglichen Eigenschaften zufällig von einem der beiden Rekombinationspartner gewählt wird oder indem die erste Hälfte der Eigenschaften vom ersten und die zweite Hälfte vom zweiten Partner übernommen wird. Weitere Strategien sind denkbar und ich werde im nächsten Artikel noch eine Möglichkeit vorstellen, wie jede denkbare Rekombinationsstrategie unabhängig von den Eigenschaften ausgeführt werden kann. Hier soll es erst einmal genügen, wenn wir sagen, dass die Eigenschaften je zweier Individuen zu einem neuen Individuum kombiniert werden, welches dann eine Mischung aus Eigenschaften seiner beiden Eltern besitzt. Im Pseudocode sieht das so aus: 

(1)  recombine individuals: g ∈ Tⁿ → Tⁿ:
(2)    g' ∈ Tⁿ, g' ← {}
(3)    while not enough elements in g':
(4)       t, t₁, t₂ ∈ T
(5)       (t₁, t₂) ← select randomly from g
(6)       t ← recombine t₁ and t₂ randomly
(7)       g' ←  g' ∪ {t}
(8)   return g'

Insgesamt müssen natürlich genügend neue Individuen entstehen, damit die nächste Generation genauso mächtig ist wie die vorherige. Ist sie kleiner, würden irgendwann keine Individuen mehr übrig sein; ist sie größer, würde die Populationsgröße immer weiter zunehmen mit dem Ergebnis, dass irgendwann der Speicher des Computers voll wäre. Übrigens müssen nicht immer genau zwei Individuen miteinander rekombiniert werden; es können natürlich auch mehr sein - zwei hat sich aber als relativ günstige Zahl erwiesen.

Wenden wir nun den Rekombinationsalgorithmus auf unsere selektierten Positionen des Katzenproblems an. Eine Position hat dabei in der Regel lediglich zwei Eigenschaften, nämlich die vertikale und die horizontale Position auf dem Bett. Die Rekombination zweier Eltern soll also immer so geschehen, dass vom ersten Elter die vertikale und vom zweiten Elter die horizontale Position genommen und zu einem neuen Individuum vermischt werden. Wir erhalten damit aus den alten Individuen (grau, diese werden nach diesem Schritt verworfen) die neuen (schwarz), wobei einige der Rekombinationen zweier Eltern mit ihrem Ergebnis durch Pfeile gekennzeichnet sind. Eine Güte wurde für die neuen Kinder jetzt noch nicht eingetragen, da sie noch nicht berechnet wurde (wir sehen aber schon, dass einige der neu generierten Individuen besser sind als ihre Eltern); wie man sieht, stehen die im vorherigen Schritt nicht selektierten Individuen gar nicht mehr zur Diskussion:

Mutation

Damit bleibt noch ein letzter Schritt zu klären: die Mutation. Sie sorgt dafür, dass in den vorhandenen Pool an Eigenschaften (den Genpool) etwas Bewegung kommt und neue Eigenschaften entstehen. Ohne die Mutation würde sich der evolutionäre Algorithmus nämlich im Kreis drehen, da immer nur Individuen mit den gleichen Eigenschaften entstehen würden.

Die Mutation an sich ist relativ simpel: jedes der bei der Rekombination entstandenen Individuen wird hergenommen und eine, einige oder alle seiner Eigenschaften zufällig verändert. Die Stärke der Mutation ist dabei oft ein einstellbarer Parameter, da je nach Problem stärkere oder schwächere Mutationen von Vorteil sein können. Auch hier existiert wie bei der Rekombination ein Verfahren, welches unabhängig von den tatsächlichen Eigenschaften der Individuen (also für alle denkbaren Individuen aller möglichen Probleme) eine Mutation durchführen kann und welches ich im nächsten Artikel vorstellen werde. Der Pseudocode für die Mutation sieht denkbar einfach aus: 

(1)  mutate individuals: g ∈ Tⁿ → Tⁿ:
(4)    for all t ∈ g:
(3)      t ← mutate t randomly
(4)    return g

Bei unserem Katzenproblem sind die mutierbaren Eigenschaften natürlich wieder die vertikale und die horizontale Position auf dem Bett. Jedes der bei der Rekombination entstandenen Individuen wird nun mutiert, also ein klein wenig auf dem Bett in eine zufällige Richtung verschoben (da wir ja, wie abgesprochen, gar nicht wissen, wo die Mitte ist, können wir auch nicht einfach pauschal "zur Mitte hin" schieben). Bildlich ausgedrückt sieht das so aus (zugegeben, es wirkt etwas chaotisch, aber die Intention sollte erkennbar sein); grau sind die "alten" (rekombinierten) Individuen, der Pfeil zeigt die Schieberichtung an und die schwarzen Kreise markieren die Individuen, welche die nächste Generation bilden werden.

Abschluss

Der Algorithmus würde nun von vorne beginnen und aus den neu erstellten Individuen wiederum eine geeignete Auswahl treffen, diese rekombinieren und mutieren - so lange, bis ein genügend gutes Individuum gefunden wurde. "Genügend gut" liegt hier natürlich immer im Auge des Problemlösers. Ist die Güte der besten Lösung bekannt (im Katzenbeispiel etwa die Entfernung zur Mitte), kann so lange gerechnet werden, bis ein Individuum mit genau dieser Güte oder einer um nicht mehr als X% abweichenden Güte gefunden wurde. Ist die beste Güte dagegen nicht bekannt (was bei vielen Optimierungsproblemen der Fall ist), kann eine bestimmte Anzahl von zu berechnenden Generationen vorgegeben werden, in der Hoffnung, dass nach dieser Zeit bereits ein relativ guter Lösungskandidat gefunden wurde. Alternativ kann das Abbruchkriterium auch sein, dass sich über eine bestimmte Anzahl von Generationen hinweg der durchschnittliche Gütewert einer Generation nicht mehr wesentlich ändert; das kann nämlich auch passieren, dann ist man in einem sogenannten lokalen Optimum gelandet (was das ist, besprechen wir auch ein andermal).

Evolutionäre Algorithmen haben die Eigenschaft, dass für ansonsten schwierig zu berechnende Probleme auf relativ einfache Art und Weise eine gute Lösung gesucht werden kann. Ihr größter Vorteil ist hierbei vor allem die Geschwindigkeit der Berechnung; die traditionelle Suche nach einer guten Lösung eines schwierigen Problems verschlingt meist so viel Zeit, dass sie nicht praktikabel ist. Ein evolutionärer Algorithmus bietet hier einen Ausweg, der zwar nicht zwangsläufig die beste Lösung findet, aber zumindest eine hinreichend gute, und das in annehmbarer Zeit. Betrachten wir zum Beispiel das Katzenproblem; innerhalb einer einzigen Generation wurden aus diesen zufällig generierten Lösungskandidaten

durch Selektion, Rekombination und Mutation diese Kandidaten erzeugt:

Die Kandidaten sind dabei eindeutig mehr Richtung Mitte gewandert. Noch einige Generationen mehr und es kann bereits eine sehr gute Lösung für das Positionierungsproblem verfügbar sein!

Natürlich haben auch die evolutionären Algorithmen Probleme. Insbesondere die Behandlung von lokalen Optima ist hier wichtig (was man genau darunter versteht und wie man sie vermeidet, besprechen wir demnächst). Zudem ist das aktuell beschriebene Vorgehen zwar anwendbar, jedoch sehr problemspezifisch; durch die gezielte Auswahl und Mutation von Eigenschaften ist ein einmal programmierter Algorithmus nur für genau das Problem zu benutzen, für welches er programmiert wurde. Wie man das eleganter lösen kann, möchte ich im nächsten Artikel aufzeigen.

Bei der Erforschung der Evolution hat man das Problem, dass sie relativ langsam abläuft und daher nur in kleinem Ausmaß und über längere Zeiträume betrachtet werden kann. Einfacher ist es da natürlich, die Auswirkungen der Evolution zu untersuchen, so wie es zum Beispiel Charles Darwin unter anderem bei den berühmten Darwinfinken (Bild links) tat und was am Ende auch zur Entwicklung seiner Theorie über die Entwicklung der Arten beigetragen hat. Parallel dazu kann natürlich auch das Erbgut erforscht werden, da es die biologische Grundlage für die Evolution bildet. Beide Themenbereiche - Evolution und Genetik - sind überaus interessante Forschungsgebiete, auf denen große Personen wie Charles Darwin, Ernst Haeckel und Gregor Mendel tätig waren. Nun mag sich allerdings der ein oder andere fragen (und tut es auch), wo denn der Sinn derartiger Forschungen liegt, insbesondere in Bezug auf die Evolution. Unabhängig von der allgemeinen Bedenklichkeit dieser Frage (die kann dann nämlich in ihrer Naivität auf sehr viele Bereiche angewendet werden) haben Erkenntnisse auf beiden Forschungsgebieten auch Auswirkungen auf komplett andere Tätigkeitsfelder gehabt; insbesondere sei hier die Informatik zu nennen: aufbauend auf den (allgemeinen) Theorien der Evolution und Genetik wurde hier nämlich eine spezielle Gruppe von Verfahren zur Problemlösung entwickelt, nämlich die evolutionären Algorithmen, und über die möchte ich heute etwas schreiben.

Biologische Grundlagen

Bevor es zu den evolutionären Algorithmen geht, muss allerdings noch einmal ein kurzer Ausflug in die Biologie erfolgen, und zwar zu den Grundlagen von Evolution und Genetik (nur, damit die Begrifflichkeiten einigermaßen geklärt sind). Wichtig ist hier unter anderem der Begriff des Individuums. Im Folgenden wollen wir (unabhängig von existierenden Definitionen) unter einem Individuum einen unabhängig von seiner Umgebung existierenden Repräsentanten einer Art mit einem eigenen Erbgut verstehen (wobei sich die "Unabhängigkeit" natürlich nicht auf Nahrungsabhängigkeiten, Symbiosen und dergleichen bezieht). Ein Individuum in der Biologie ist also alles, worauf wir mit dem Finger zeigen und sagen können: Das dort!

Die Eigenschaften eines Individuums werden durch sein Erbgut, das Genom bestimmt, welches sich aus den einzelnen Genen zusammensetzt (rechts zum Beispiel ein menschliches Genom, [via Wikipedia]). Das gesamte Genom eines Individuums beschreibt seinen Genotyp (wichtiger Begriff für später, bitte merken), das Erbbild. Die Gesamtheit aller Eigenschaften eines Individuums (also Aussehen, Verhalten usw.) wird dagegen als Phänotyp bezeichnet (auch wichtig, auch merken). Man kann also sagen, dass der Genotyp eines Individuums seinen Phänotyp bestimmt.

Der Genotyp ist über die Lebensdauer eines Individuums mehr oder weniger fest und kann sich nur durch externe Einflüsse verändern. Zudem gibt ein Lebewesen sein Genbild an seine Nachkommen weiter; da aber die Nachkommen in der Regel doch von ihrem Erzeuger abweichen (vom Klonen einmal abgesehen), muss während der Fortpflanzung eine Veränderung des Genotyps stattfinden. Die beiden hieran hauptsächlich beteiligten Mechanismen sind die Mutation und - bei mehrgeschlechtlicher Fortpflanzung - die Rekombination. Ohne jetzt allzu sehr auf Details einzugehen: Mutation bezeichnet die Veränderung des Erbgutes einer Zelle, die entweder spontan oder durch äußere Einfluss stattfindet. Treten diese Mutationen in den Keimzellen auf, werden sie an die Nachkommen weitergegeben. Die Rekombination tritt (unter anderem) auf, wenn während der Befruchtung bei der Fortpflanzung die Ei- und die Samenzelle und damit ihr Erbgut verschmelzen und somit einen neuen Genotyp ausbilden.

Durch Vorgänge auf der Ebene der Gene wird also der Genotyp eines Individuums bestimmt. Dies hat, wie bereits geschrieben, Auswirkungen auf seinen Phänotyp, also seine nach außen hin sichtbaren Merkmale - und an dieser Stelle greifen die Mechanismen der Evolution. Der Phänotyp eines Individuums bestimmt, wie gut es in einer Umgebung zurecht kommt - man spricht von der Anpassung eines Individuums an seine Umgebung. Je besser es angepasst ist, das heißt, je stärker sein Phänotyp auf ein Überleben in seiner Umgebung ausgerichtet ist, desto größer ist auch die Wahrscheinlichkeit, dass es länger überlebt und seine Gene an Nachkommen (vor allem an mehr Nachkommen) weitergibt. Dieser Mechanismus wird als natürliche Selektion bezeichnet und ist einer der Grundpfeiler der Evolutionstheorie.

Evolution zur Problemlösung in der Informatik

Jetzt stellt sich natürlich die Frage, wie die Mechanismen von Mutation, Rekombination und Selektion genutzt werden können, um Probleme in der Informatik zu lösen. Zuerst einmal: ein Problem kann jede Fragestellung sein, die sich mit Hilfe computergestützter Methoden beantworten lässt. Bekannte Problemstellungen sind etwa die Suche nach einer möglichst kurzen Route durch verschiedene Orte (bekannt als Rundreiseproblem), die optimale Auswahl von Objekten aus einer Menge nach bestimmten Kriterien (das Rucksackproblem) oder die platzsparendste Anordnung von Objekten auf einem Trägermaterial (was zum Beispiel besonders wichtig bei der Entwicklung von Prozessoren ist). Insbesondere die sogenannten Optimierungsprobleme sind von Interesse; damit sind Probleme gemeint, die nicht nur eine eindeutige Lösung besitzen, sondern deren verschiedene Lösungen nach ihrer Güte eingeteilt werden können. So gibt es etwa bei der Suche nach einer Rundreise vielleicht eine optimale Route, aber die anderen möglichen Routen sind ebenfalls Lösungen des Problems - nur eben nicht so gute.

Der Trick ist nun, eine möglichst gute Lösung eines Problems zu suchen, indem verschiedene Lösungskandidaten zufällig generiert und diese dann in einer künstlichen Umgebung unter der Einwirkung der Mechanismen von Evolution und Genetik zu modifizieren, um sich so einer optimalen Lösung anzunähern. Und genau das ist es, was die evolutionären Algorithmen machen. Im Groben sieht das Vorgehen dabei wie im Folgenden beschrieben aus:

Zu Beginn wird (manuell oder automatisch) eine Menge von zufälligen Lösungskandidaten - jeder Lösungskandidat ist ein einzelnes Individuum - erstellt, welche die Ausgangsbasis der Suche bilden. Diese Individuen haben nun die Möglichkeit, sich unter einem gewissen Selektionsdruck so lange "fortzupflanzen", bis ein hinreichend guter Lösungskandidat entstanden ist (oft genug reicht das nämlich schon zur Lösung eines Optimierungsproblems). Für gewöhnlich wird dabei noch ein Alterungskonzept zugrunde gelegt, durch welches alte Individuen "sterben" und durch ihre Nachkommen ersetzt werden; die Individuen werden dabei meist in aufeinanderfolgende Generationen (oder - biologisch ungenau - in Populationen) eingeteilt. 

Die Vermehrung der Individuen geschieht, indem etwa die Eigenschaften zweier nach bestimmten Kriterien ausgesuchter (selektierter) Individuen miteinander (re-)kombiniert und der so entstehende Nachfahre noch einmal zufällig mutiert wird. Dies wird für verschiedene Individuen einer Generation mehrmals ausgeführt, wodurch die Nachfolgegeneration entsteht, welche ihre Vorgänger für den nächsten Iterationsschritt im Algorithmus ersetzt. Der Prozess wird insgesamt so lange wiederholt, bis oben genanntes Abbruchkriterium - ein hinreichend guter Lösungskandidat - erreicht wurde. Wenn wir das ganze in Pseudocode notieren, erhalten wir folgenden Algorithmus (g₀ ist die Ausgangsgeneration,  T ist der Typ eines Lösungskandidaten):

(1)  Evolutionary Algorithm: g₀ ∈ Tⁿ → T:
(2)    t ∈ T
(3)    g ∈ Tⁿ, g ← g₀
(4)    do:
(5)       g', g'' ∈ Tⁿ
(6)       g' ← select individuals from g
(7)       g'' ← recombine individuals in g'
(8)       mutate individuals in g''
(9)       t ← select best individual in g''
(10)   while t not good enough
(11)   return t

Durch diesen Algorithmus kann auf ziemlich elegante Weise eine gute Lösung für ein ansonsten recht schwierig zu lösendes Problem gefunden werden. Jetzt muss natürlich aber auch noch geklärt werden, wie denn nun die Mutation, Rekombination und Selektion der Individuen genau stattfindet, was das ganze mit den anfänglich erwähnten Begriffen von Genotyp und Phänotyp zu tun hat und - so ehrlich wollen wir sein - wo die Probleme des Verfahrens liegen. Aber das hebe ich mir für das nächste mal auf.

Genetik

Mit den grundlegenden Prinzipien der (in erster Linie durch Charles Darwin allgemein bekannt gewordenen) Evolution kennen sich ja sicherlich die meisten der Leser hier aus. Die "Grundeinheit" der Evolution ist ja das Gen oder genauer eigentlich, die DNA, jene Doppelhelix aus Nukleinsäuren, die unsere Erbgutinformationen repräsentiert. Mittelbar mit der DNA verbunden sind so wichtige Begriffe wie Mutation, Selektion und Fitness. Das Grundkonzept der Evolution - soweit man hier im wissenschaftlichen Sinne überhaupt von einem Konzept reden kann - ist, dass die Lebewesen mit der besten Angepasstheit an ihre Umwelt auch die größte Chance haben, zu überleben und sich zu reproduzieren. Weniger gut angepasste Arten müssen sich entweder anpassen und damit neue Arten hervorbringen (was natürlich kein aktiver Vorgang ist) oder werden über kurz oder lang aussterben; da sich aber die Umwelt ständig ändert, sind auch die meisten Lebewesen dem Druck der Veränderung ausgesetzt. Umweltänderungen können zum einen auf Grund langsamer klimatischer und geografischer Änderungen stattfinden, aber auch durch "spontane" Änderungen (gern auch "Katastrophen" genannt), wie etwa große Vulkanausbrüche oder Meteoriteneinschläge (manch einer mag auch die Menschheit an sich zu diesen Katastrophen rechnen, da sie innerhalb sehr kurzer Zeit gewaltige Änderungen auf unserem Planeten hervorgerufen hat). Ein weiterer wichtiger Umwelteinfluss ist aber auch die Entwicklung der anderen Arten in der Umgebung; findet bei einem Beutetier/Prädator eine Änderung statt, so muss sich auch der Jäger/Gejagte anpassen, um auf die geänderten Umweltbedingungen zu reagieren (auch das ist natürlich kein aktiver Vorgang - kein Lebewesen kann sich dazu entscheiden, sich zu ändern, sondern es geschieht rein passiv über Mutation und Selektion!).

Für den folgenden Text gilt: ich bin kein Evolutionsforscher, hoffe jedoch, mit meinen Aussagen in Bezug auf die Evolution nicht allzu sehr daneben zu liegen.

Memetik

Eine modernere, 1976 von Richard Dawkins beschriebene Theorie ist die Mem-Theorie. Dabei werden Meme als grundlegende Gedankeneinheiten bzw. Informationseinheiten definiert und beschreiben im Grunde bestimmte kulturelle Konzepte und Informationen. Die Theorie geht davon aus, dass sich diese Meme durch Kommunikation verbreiten und dabei - ähnlich den Genen der Evolution - veränderlich und einem Selektionsdruck unterworfen sind. Der wichtige Punkt hierbei ist meiner Meinung nach übrigens die Kommunikation, ein im Gegensatz zur Mutation bewusst ausgeführter Vorgang, der zur Verbreitung von Informationen führt. Man mag von der Mem-Theorie und ihrem Nutzen halten, was man mag; im Folgenden möchte ich mich dennoch des Begriffs des Mems bedienen und ihn auf die Welt der Informatik anwenden.

Anwendung der Theorien auf Computerprogramme

Betrachtet man die Entwicklung von Computerprogrammen über die letzten Jahr(zehnt)e hinweg, so lassen sich einige (vorsichtige) Analogien zur Genetik und Memetik finden. Bezogen auf die Genetik gibt es da natürlich die "triviale" Sichtweise, dass Computerprogramme ständigen Mutationen unterliegen, wobei ihr zugrundeliegender Programmcode gewissermaßen das Erbgut, also die DNA darstellt, welche (durch Programmierer) verändert wird. Inwieweit hier allerdings noch eine Analogie zur Genetik vorliegt, ist zumindest diskussionswürdig, da sich Programmcode nicht zufällig ändert, sondern zielgerichtet modifiziert wird (etwas, das genau gegensätzlich zur Mutation von Genen stattfindet). Auf der anderen Seite hat man aber auch den Effekt der Rekombination (der zweigeschlechtlichen Fortpflanzung in der Tier- und Pflanzenwelt), wenn nämlich mehrere Programme miteinander verschmelzen (etwa bei der Ausnutzung von Programmbibliotheken).

Interessanter als die Betrachtung der Analogien auf Ebene der Gene sind meiner Meinung nach aber die Gemeinsamkeiten zwischen der Selektion der Evolution und den Mechanismen des "Überlebens" von Computerprogrammen. Genauso wie jedes Lebewesen mit seiner Umwelt interagiert und dort einem Selektionsdruck unterworfen ist, reagieren Computerprogramme auf veränderte Einflüsse in der IT-Umgebung. Und genauso, wie sich Lebewesen auf langsame und plötzliche Änderungen ihrer Umwelt sowie bei ihren Beutetieren, Jägern und Nahrungskonkurrenten einstellen müssen, reagieren Computerprogramme auf die gleichen Änderungen. Lebewesen benötigen zudem irgendeine Form von Nahrung und eine Gelegenheit zur Fortpflanzung, um zu überstehen; für Programme gilt das gleiche, wobei hier "Nahrung" und "Fortpflanzungsgelegenheit" in einer Einheit kombiniert werden, nämlich in uns, dem Nutzer, da ein Programm dadurch überlebt, dass es genutzt wird.

Änderungen in der Umwelt

Was nun die Änderungen der Umwelt betrifft: die "Umwelt" eines Computerprogramms besteht zum einen natürlich aus der Hardware, auf der das Programm läuft (die Geografie und das Klima), dem Betriebssystem (welches ich auch fast zum Klima und zur Geografie rechnen möchte) und den anderen Programmen, die entweder auf dem gleichen System laufen (wobei es hier meist ein mehr oder weniger friedliches Miteinander gibt) oder generell existieren und eine ähnliche Aufgabe erfüllen wie das Programm selber; hier entsteht vor allem der Konkurrenzdruck, der zur Selektion der Programme führt.

Im Verlauf der Jahrzehnte gab es im Bereich der Hardware zahlreiche, meist kontinuierliche Veränderungen, an welche sich die Programme mit der Zeit angepasst haben. Die offensichtlichste Änderung war natürlich die Zunahme der zur Verfügung stehenden Ressourcen - Rechengeschwindigkeit und verfügbare Speichermenge - an welche sich die Programme durch bessere Ressourcenausnutzung angepasst haben (mit dem kuriosen Effekt, dass Programme heutzutage trotz schnellerer Computer noch immer nicht schneller laufen - aber das ist ein anderes Thema). Aber auch nicht so deutlich hervortretende Faktoren können zu den langsamen Umweltveränderungen gezählt werden. So hat sich insbesondere in den letzten Jahren die Anzahl der parallel arbeitenden Kerne in den Prozessoren erhöht, was dazu geführt hat, dass Computerprogramme immer mehr parallelisiert wurden, das heißt mehrere interne Aufgaben gleichzeitig berechnen können. Auch die verfügbaren Auflösungen der Monitore und damit der verfügbare Platz zur Darstellung von Informationen vergrößerte sich, woran sich die Programme natürlich auch angepasst haben.

Neben den langsamen Veränderungen gab es von Zeit zu Zeit natürlich auch immer wieder plötzlich auftretende Neuerungen. Da wäre vor allem auch die Entwicklung von Grafikoberflächen für Betriebssysteme zu nennen - durch ihre Einführung Mitte der 1980er Jahre haben sich teilweise vollkommen neue Bedienkonzepte ergeben, welche relativ schnell ausgenutzt wurden. Selbst die Entwicklung der Personal Computer in den 70ern fand in einem relativ kurzen Zeitraum statt und hat zur Entstehung ganz neuer Programme geführt - schließlich gab es davor praktisch nur "Großrechenanlagen", die nicht für den Heimgebrauch geeignet waren. Die Entwicklung des World Wide Web schließlich war die letzte große Neuerung, welche die heutige Zeit vollkommen beherrscht und teilweise vollkommen neue Programmkonzepte hervorgebracht hat (seitdem herrscht ein wenig Flaute im Bereich der Entwicklung grundlegend neuer Technologien; ob sich zum Beispiel das Cloud Computing als großer Wurf herausstellt, wird erst die Zeit zeigen können).

Ein wichtiger Faktor in der "Evolution der Programme" ist natürlich aber immer der Konkurrenzdruck anderer Programme gewesen. Zur Lösung eines Problems existieren für gewöhnlich mehrere Programme, welche um "Nahrung" - also Nutzer - miteinander konkurrieren und versuchen, durch immer neue Fähigkeiten ihre Konkurrenten auszustechen. Je mehr Konkurrenten existieren und je "stärker" (also je bedrohlicher für die eigene Existenz) diese sind, desto schneller entwickelt sich ein Programm auch weiter. Umgekehrt führt das dazu, dass sich ein Programm, welches in seinem Aufgabengebiet dominant ist und kaum Konkurrenz hat, relativ langsam weiterentwickelt - ein prominentes Beispiel hierfür folgt gleich noch.

Ähnlich der Evolution kann man die Entwicklung von Programmen aber auch unter dem Gesichtspunkt der Memetik betrachten. Ein Programm würde hier einem Mem, also einer Gedanken- oder Informationseinheit entsprechen, welches durch Kommunikation - in der Regel durch Empfehlung an andere Nutzer - und häufige Benutzung weiter verbreitet wird. Auch hierzu folgen gleich noch einige prominente Beispiele.

Überhaupt: bisher waren das ja alles theoretische Betrachtungen. Die beste Theorie nützt aber nichts, wenn sie nicht mit der realen Welt verglichen wird. Wenden wir uns also einigen Beispielen zu, an welchen ich demonstrieren möchte, wie die Gedanken der Genetik und Memetik auf die Informatikwelt angewendet werden können.

Beispiel: Betriebssysteme

An Betriebssystemen fällt die Evolution von Programmen immer besonders auf, da sie den Gesamteindruck eines Systems bestimmen und ständig präsent sind. Beherrscht wird der Markt hier eindeutig von den verschiedenen Windows-Versionen mit ungefähr 80% Marktanteil, gefolgt von Mac OS, wiederum gefolgt von Unix-basierten Systemen - der Markt ist also relativ überschaubar.

Die starke Präsenz von Windows verhindert wirkungsvoll das Wachstum anderer Betriebssysteme in relevantem Ausmaß, da es zum einen das standardmäßig installierte Betriebssystem auf vielen neu ausgelieferten Rechnern ist und - bedingt dadurch - viele Leute lediglich dieses System kennen und natürlich bei ihm bleiben. Windows ist also nicht nur der Spitzenprädator in seinem Gebiet in dem Sinne, dass es praktisch keine natürlichen Feinde hat, sondern es drängt die Konkurrenz auch erfolgreich an den Rand. Der Effekt des relativ geringen Selektionsdrucks ist allerdings auch, dass es hin und wieder zu "Fehlentwicklungen" kommen kann - man nehme nur Windows Vista, welches zwar auch eine relativ weite Verbreitung erlangt hatte, im Allgemeinen jedoch als mehr oder weniger großer Fehlschlag angesehen wird - es wird mittlerweile auch ziemlich schnell von Windows 7 (sozusagen der Weiterentwicklung der Art) verdrängt, da letzteres weitaus besser an die Umwelt "angepasst" ist in dem Sinne, dass es seine Aufgabe besser erfüllt. Insgesamt entwickelt sich Windows aber relativ langsam fort, da die Umwelt hier recht stabil ist und häufige Neuerungen im Moment nicht erforderlich sind.

Demgegenüber stehen etwa die Unix-artigen Betriebssysteme wie zum Beispiel Linux; global gesehen haben sie eine recht geringe Verbreitung, in bestimmten Bereichen (sozusagen ökologischen Nischen) sind sie aber klar dominant und sichern dadurch ihr Überleben - insbesondere das Server-Umfeld wäre hier zu nennen. Unix ist durch die Präsenz von Windows einem recht hohen Selektionsdruck ausgesetzt, was zu häufigeren Neuerungen führt (häufiger als Windows zumindest). 

Insgesamt gesehen sind Betriebssysteme jedoch relativ stabil. Im Hardware-Bereich gibt es selten plötzliche Neuerungen, so dass sich die Betriebssysteme an die langsam ablaufenden Prozesse der Hardware-Verbesserung angepasst haben und sich auch selbst nur langsam verändern (wir reden hier von einem informationstechnischen "langsam" - das heißt, im Verlaufe einiger Jahre).

Beispiel: Internetbrowser

Ganz anders auf dem Gebiet der Internetbrowser; hier herrscht insbesondere seit einigen Jahren ein immens starker Konkurrenzdruck, welcher die Browserentwicklung stark beschleunigt und dazu geführt hat, dass zwischen verschiedenen Programmversionen teilweise nur wenige Wochen liegen. Da die Konkurrenz ständig neue Entwicklungen bringt, findet hier ein echtes "Wettrüsten" statt: kaum hat ein Browser eine neue Eigenschaft, ziehen die anderen Hersteller hinterher und präsentieren für ihre Browser eine eigene Implementierung oder gar Verbesserung dieser Eigenschaft.

Aber das war nicht immer so. Lange Zeit war der Internet Explorer, zusammen mit dem dominanten Windows ausgeliefert, der beherrschende Browser in der Computerwelt. Durch die fehlende Konkurrenz wurde er auch kaum weiterentwickelt; im Gegensatz zu den Betriebssystemen, wo eine langsame Entwicklung noch halbwegs ertragbar ist, war dieses Verhalten im Bereich des Internets allerdings fatal. Das World Wide Web verändert sich sehr schnell, wobei der Internet Explorer diesen Veränderungen nicht gerecht wurde; zahlreiche Sicherheitslücken waren die Folge. Durch seine große Verbreitung konnte sich das Programm zwar noch eine Zeit lang behaupten, wurde aber nach und nach durch andere Programme verdrängt (das würde ich übrigens Evolution in Aktion nennen) - insbesondere auch durch den Firefox.

Der Fall Firefox ist nun ein wenig kurios. Zu Anfang konnte er sich gut verbreiten, da er im Gegensatz zu vielen anderen Browsern sowohl kostenlos als auch werbefrei war und viele der Probleme des Internet Explorers vermied. Mittlerweile hat der Browser den höchsten Marktanteil bei den Browsern überhaupt - und das, obwohl mittlerweile alle verfügbaren Browser als ungefähr gleichwertig betrachtet werden können und der Firefox keineswegs "besser" ist als andere. Im Gegensatz zu Windows, welches auf vielen Geräten ohnehin vorinstalliert ist (ebenso wie der Internet Explorer übrigens) muss der Firefox manuell heruntergeladen werden - seine nach wie vor weite Verbreitung muss also irgendwie erklärt werden. An dieser Stelle möchte ich auf die Mem-Theorie von Dawkins verweisen. Eine Besonderheit des Firefox-Browsers ist, dass er bereits von vielen Nutzern verwendet und daher auch sehr oft weiterempfohlen wird. Das Mem "Firefox" ist demzufolge sehr präsent und hält sich dadurch so weit oben an der Spitze, dass es durch ständige Kommunikation erneuert wird. Für den durchschnittlichen Nutzer wäre es relativ egal, ob er nun Firefox, Opera, Internet Explorer oder Chrome benutzt - da ihm aber im Durchschnitt vermutlich am häufigsten Firefox empfohlen wird, greift er zu diesem Browser und wird selber auch weiter für dessen Verbreitung sorgen. 

Beispiel: Programmiersprachen

Auch im Bereich der Programmiersprachen (die ich jetzt auch einfach mal als "Programme" bezeichne) herrscht ein sehr starker Konkurrenzdruck, da es auch hier eine Unzahl von verschiedenen Arten gibt, die um die Nutzergunst werben und die - ebenso wie Programme, aber auch wie Lebewesen - einer ständigen Modifikation und Anpassung an die Umwelt unterliegen. Insbesondere kann es auch passieren, dass ehemals sehr erfolgreiche Sprachen an den Rand der Bedeutungslosigkeit gedrängt und durch andere Sprachen ersetzt werden, je nach dem, welche Sprache gerade am besten an die aktuellsten Gegebenheiten angepasst ist (ein echtes Aussterben ist allerdings nicht so oft zu beobachten - bei einigen Sprachen kann man hier durchaus von "leider" sprechen). Nehmen wir etwa den Sprung von Assembler zu den Hochsprachen. Vor der Entwicklung der strukturierten Programmierung war Assembler die hauptsächlich (praktisch einzige) zur Verfügung stehende Programmiersprache; mit dem Aufkommen der ersten strukturierten Programmiersprachen wie Basic und Pascal aber wurde Assembler ziemlich schnell verdrängt und fristet heute ein Nischendasein im Bereich des High Performance Computing und der extrem systemnahen Entwicklung (man mag jetzt einwenden, dass das nicht unbedingt eine "Nische" ist - relativ gesehen ist Assembler aber nicht sonderlich weit verbreitet). Gleiches geschieht Sprachen, die mit der aktuellen Entwicklung der Technik und insbesondere den Anforderungen an moderne Programmiersprachen nicht Schritt halten können (also weniger gut an die Umwelt angepasst sind) und so ebenfalls an Bedeutung verlieren; prominentes Beispiel hierfür ist die Programmiersprache C++, welche lange Zeit ohne Neuerungen auskommen und dafür mit sinkender Verbreitung bezahlen musste.

Andersherum gilt aber auch der memetische Ansatz für Programmiersprachen. Sprachen mit einer sehr weiten Verbreitung können sich - ähnlich wie der Firefox - allein dadurch länger behaupten, dass sie ständig weiterempfohlen (auch und vor allem in der akademischen Lehre!) und benutzt werden. Dabei ist der Verwendungsgrad teilweise völlig unabhängig davon, wie "gut" die Sprache zur Lösung bestimmter Probleme geeignet ist; allein dadurch, dass sie eine weite Verbreitung hat, wird sie auf alle möglichen Probleme angewendet, auch auf solche, für die es eigentlich bessere Ansätze gäbe. Der Grund hierfür dürfte unter anderem auch sein, dass viele Leute zuerst mit einer bestimmten Sprache in Kontakt kommen und dann zeitlebens an ihr hängen bleiben (ganz analog zu Webbrowsern, Betriebssystemen und so weiter) - gewissermaßen stellen derartige Sprachen ein selbsterhaltendes Mem dar.

Fazit

Ich hoffe, meine Gedanken zur Evolution und Verbreitung einigermaßen verständlich zu (digitalem) Papier gebracht zu haben. Wir haben gesehen, auf welche Art und Weise Programme am Leben erhalten und verbreitet werden und wie aus dem Umfeld der Informatik Parallelen zur Genetik und Memetik gezogen werden können. 

Welche Erkenntnisse aus derartigen Betrachtungen gezogen werden können, ist nun natürlich zu diskutieren - ähnliches gilt aber auch für die Evolutionstheorie und die Memetik (letztere wird übrigens auch genau dafür kritisiert, dass sie keinen echten "Mehrwert" in Bezug auf die Erkenntnis bringt). Ich persönlich denke aber, dass Gedanken und Untersuchungen zur Verbreitung von Programmen durchaus von Vorteil sein können. Auf der einen Seite natürlich für die Softwareentwickler, die nach Wegen suchen, ihre eigenen Programme zu verbreiten oder in guter Verbreitung zu halten; auf der anderen Seite aber auch für die Nutzer von Programmen, die durch derartige Betrachtungen ihr eigenes Nutzungsverhalten hinterfragen können und sich somit vielleicht wenigstens ab und zu die Frage stellen, aus welchem Grund sie an einem bestimmten Programm festhalten und ob nicht doch vielleicht ab und zu ein Programmwechsel etwas frischen Wind in das (Computer-)Leben bringen würde.

Die Historie hat gezeigt: in dynamischen Systemen führt Stillstand nur selten zum Erfolg; nur, wer sich verändert und anpasst, kann mit dem Wandel Schritt halten. Habt also Mut zur Veränderung und schaut ab und zu über den Tellerrand hinaus - irgendwann wird es sicherlich auf die ein oder andere Weise belohnt werden.

Vorab noch eine kleine Anmerkung für all die Webgurus da draußen: das hier soll keine Anleitung dafür sein, wie man CSS bei der Erstellung von Websites möglichst effektiv und "gut" benutzt - es ist lediglich eine Einführung in das Thema an sich für alle Interessierten, die einfach einmal wissen möchten, wie denn ein Browser überhaupt weiß, was er darstellen soll. So, jetzt geht es aber los.

Noch einmal kurz zur Erinnerung: Mit Hilfe von HTML-Tags kann der Text in einem HTML-Dokument strukturiert werden; der folgende Codeausschnitt markiert etwa einen Absatz:

<p>Dies ist ein Absatz.</p>

Möchte man den Text im Absatz nun formatieren, also sein Erscheinungsbild ändern, so kann das durchaus auch mit Mitteln von HTML allein erreicht werden. Um den Text etwa fett, kursiv und in roter Schrift anzuzeigen, könnte man etwa folgendes schreiben:

<p><b><i><font color="#FF0000">
Dies ist ein Absatz.
</font></i></b></p>

Das würde dann zu folgendem Ergebnis führen, wobei das <b> den Fettdruck (für bold), das <i> den Kursivdruck (für italic) und das <font color="#FF0000"> den Druck in roter Farbe markiert:

        Dies ist ein Absatz.

Jetzt werden alle Leser sicherlich zustimmen, wenn ich sage, dass eine derartige Notation eher umständlich ist und insbesondere bei verschiedenen gleichzeitig anzuwendenden Formatierungen zu einer starken Schachtelung des Codes führt und damit dessen Lesbarkeit nicht gerade zuträglich ist. Zum Glück gibt es aber CSS, welches eine bedeutend einfachere Formatierung erlaubt.

Die Grundidee hinter CSS ist, dass mit Hilfe einer speziellen deklarativen, also beschreibenden Programmiersprache die Formatierungsanweisungen für einen Textbestandteil effizient aufzuschreiben und durch den Browser dann anwenden zu lassen. Die Zuordnung von einem derartigen CSS-Fragment zu einem Textbestandteil kann dabei entweder lokal erfolgen, das heißt, dass ein bestimmtes Textelement - zum Beispiel ein Absatz - direkt mit CSS-Code versehen wird; oder aber - und hier liegt der eigentliche Charme von CSS - die Zuordnung erfolgt global, so dass alle Textbestandteile, die einem bestimmten Muster folgen, mit einer vorgegebenen Formatierung versehen werden. Wie das funktioniert, schauen wir uns jetzt im Detail an.

Fangen wir mit der lokalen Zuordnung an. Wie bereits im letzten Artikel gesehen, können HTML-Tags mit Eigenschaften versehen werden, etwa wenn das Ziel eines Hyperlinks angegeben werden soll (wer sich nicht mehr erinnert, schaue bitte noch einmal im Artikel nach). Eine dieser Eigenschaften, die an alle HTML-Tags angehängt werden kann, ist die  style-Eigenschaft. Ihr kann als Wert eine Zeichenkette übergeben werden, welche nach CSS-Vorgaben aufgebaut ist und den gewünschten Stil, also die Formatierung beschreibt. Obiges HTML-Monster kann also mit Hilfe der style-Eigenschaft folgendermaßen umformuliert werden (die Interpretation der einzelnen Bestandteile überlasse ich dem Leser; es sollte nicht allzu schwierig sein):

<p style="font-weight:bold; font-style:italic; color:red;">
Dies ist ein Absatz.
</p>

Zugegeben, das sieht jetzt nicht wirklich besser aus als die HTML-Variante; insbesondere die erste Zeile erscheint doch sehr umständlich. Dennoch hat diese Notation zwei Vorteile. Zum einen können innerhalb der style-Eigenschaft viele verschiedene Angaben gemacht werden, für die man ohne CSS jeweils ein eigenes Tag benötigen würde (womit die Anzahl der Tags auf Grund der vielen verschiedenen Formationsmöglichkeiten ziemlich schnell ziemlich groß werden würde). Zum anderen ist die Verschachtelungstiefe der CSS-Variante bedeutend geringer als die der HTML-Variante; in der HTML-Variante sind insgesamt 5 Elemente (inklusive des eigentlichen Textes) ineinander verschachtelt, die CSS-Variante kommt mit 2 Elementen aus. Dadurch sinkt die Komplexität des Dokumentes und damit natürlich auch die Möglichkeit, Fehler zu machen.

Der eigentliche Vorteil von CSS kommt aber dann zum Tragen, wenn in einem Text mehrere Elemente auf die gleiche Art formatiert werden sollen. Ohne CSS oder mit CSS in der ausschließlich lokalen Variante müssten die Formatierungsanweisungen an jedes gewünschte Textelement neu angefügt werden - eine umständliche Aufgabe. Soll zu einem späteren Zeitpunkt die Formatierung geändert werden, hat man noch mehr Arbeit, da der HTML-Code an vielen Stellen modifiziert werden muss. Um diese Probleme zu umgehen, können CSS-Formatierungsanweisungen auch global, also an einer zentralen Stelle notiert werden; dies kann entweder im HTML-Dokument selbst erfolgen oder aber in einem eigenen Dokument, welches über eine spezielle Anweisung mit dem zu formatierenden HTML-Dokument verknüpft wird.

Die Einbettung in das HTML-Dokument selber kann im Kopf des Dokumentes mit Hilfe des style-Tags (in Analogie zur style-Eigenschaft) erfolgen, in welchem der CSS-Code notiert wird. Der CSS-Code besteht dabei aus einer Folge von Namen für Textbausteinen (also zum Beispiel das p für Absätze oder h1 für Überschriften auf oberster Ebene) mit einer zugeordneten Formatierung. Die Beispiel-Formatierung von oben könnte also folgendermaßen notiert werden (diesmal das komplette HTML-Dokument):

<html>
  <head>
    <style type="text/css">
      p {
        font-weight : bold; 
        font-style : italic;
        color:red;
      }
    </style>
  </head>
  <body>
    <p>Dies ist ein Absatz.</p>
    <p>
      Dieser Absatz hat die gleiche Formatierung.
    </p>
  </body>
</html>

Das resultierende Dokument würde dann so aussehen:

        Dies ist ein Absatz.

        Dieser Absatz hat die gleiche Formatierung.

Man kann also mit einer einzigen Formatierungs-Anweisung problemlos mehrere Textbausteine formatieren - praktisch! Jetzt möchte man allerdings natürlich nicht, dass immer alle Textbausteine einer Art auf eine bestimmte Art formatiert werden; immerhin gibt es nur einen Baustein für Absätze (für pingelige: gut, zwei mit dem div-Element) und man möchte unter Umständen eben nicht alle Absätze gleich formatieren. Zu diesem Zweck erlaubt CSS auch die Definition von Klassen, mit deren Hilfe die Formatierung von Textelementen eingeschränkt werden kann, da nur diejenigen Elemente formatiert werden, die einer bestimmten Klasse entsprechen. Klingt kompliziert? Hier ein Beispiel:

<html>
  <head>
    <style type="text/css">
      p.mark {
        font-weight : bold; 
        font-style : italic;
        color:red;
      }
    </style>
  </head>
  <body>
    <p class="mark">Dies ist ein Absatz.</p>
    <p>
      Dieser Absatz ist nicht formatiert.
    </p>
  </body>
</html>

Die Klasse hier heißt mark und die Notation p,mark bedeutet, dass nur Absätze der Klasse mark (markiert durch <p class="mark">) formatiert werden. Das Ergebnis sieht entsprechend so aus:

        Dies ist ein Absatz.

        Dieser Absatz ist nicht formatiert.

Da eine Website naturgemäß aus mehreren Webpages besteht (die Website bezeichnet den gesamten Internetauftritt, zum Beispiel Scienceblogs im Allgemeinen, und Webpage oder Internetseite/Webseite bezeichnet ein einzelnes Dokument, etwa diesen Artikel hier - das wird gern verwechselt), die alle der gleichen Formatierung folgen sollen, ist es gemeinhin sinnvoll, die CSS-Definitionen in eine externe Datei auszulagern und in allen Webpages einer Website einzubinden. Statt also im Kopf einer Webpage die CSS-Formatierungsanweisungen zu notieren, schreibt man sie in eine externe Datei - zum Beispiel format.css und bindet diese dann über folgenden Code ein:

<html>
  <head>
    <link
        rel="stylesheet" 
        type="text/css" 
        href="format.css" /> 
  </head>
  <body>
    <p class="mark">Dies ist ein Absatz.</p>
    <p>
      Dieser Absatz ist nicht formatiert.
    </p>
  </body>
</html>

Jede Änderung an der CSS-Datei hat jetzt zur Folge, dass automatisch alle Webpages, welche die CSS-Datei benutzen, neu formatiert werden - eine praktische Möglichkeit, um einerseits alle Webpages einer Website in einem einheitlichen Design zu halten und andererseits Änderungen am Design schnell und vor allem sicher in alle Webpages zu propagieren. Durch einen Austausch der CSS-Datei ist es zudem möglich, temporär ein anderes Design für eine Website einzuführen - wenn etwa zur Weihnachtszeit alles hübsch festlich dargestellt werden soll; danach kann die originale CSS-Datei wieder verwendet und somit das originale Design ohne Umstände wiederhergestellt werden. CSS ist de facto auch der Standard bei der Formatierung von Websites - kaum ein Webentwickler wird daran vorbeikommen (für die Kenner: abgesehen von den Entwicklern von Flash-Sites natürlich).

Damit haben wir die Grundlagen der Webentwicklung geklärt. Wer sich jetzt bemüßigt fühlen sollte, eigene Erfahrungen in diesem Bereich zu sammeln: die Website selfhtml.org ist ein guter Einstiegspunkt dafür, da sie einen guten Überblick über die möglichen HTML-Tags und CSS-Elemente bietet. 

Update

Leser Andreas P. hat mich auf eine schöne Site im Internet aufmerksam gemacht, welche einen großen Vorteil von CSS, nämlich den schnellen Austausch des Designs einer Website, besonders hervorhebt. Interessierte klicken bitte hier.

_{^*Ich hoffe, hier wenigstens dem ein oder anderen Leser noch etwas Neues erzählen zu können. Sollte dies tatsächlich der Fall sein, so mögen sich doch bitte einmal einige der so neu Informierten in den Kommentaren melden, damit ich einmal einen kleinen Überblick darüber bekomme, wie denn so die Wissensverteilung unter den Lesern ist.}

HTML ist ein Akronym für Hyptertext Markup Language und bezeichnet eine sogenannte Auszeichnungssprache. Auszeichnungssprachen fanden ursprünglich im Umfeld der Typografie Anwendung und wurden benutzt, um besondere textliche Hervorhebungen wie Fett- oder Kursivdruck im Originaltext für den späteren Druck zu markieren. Später entstanden insbesondere im IT-Umfeld verschiedene Methoden, um den Inhalt von Dokumenten zu beschreiben, welche heutzutage im Allgemeinen unter dem Begriff Auszeichnungssprache zusammengefasst werden. Insbesondere HTML ist unter diesen Sprachen sehr weit verbreitet, da es genutzt wird, um einen Großteil der Websites im Internet zu beschreiben. Eine Auszeichnungssprache an sich ist erst einmal eine vollkommen passive Sache. Sie dient wie gesagt dazu, ein bestimmtes Format näher zu beschreiben; das müssen auch nicht zwangsläufig Texte sein, da praktisch jede Information mit einer Auszeichnungssprache notiert werden kann. Nutzbar wird die so gespeicherte Information aber erst, wenn sie durch ein wie auch immer geartetes Programm ausgewertet wird - im Falle von HTML wäre das etwa der Webbrowser, der ein HTML-Dokument aus dem Internet herunterlädt und dann in der durch den Autoren des Dokumentes gewünschten Form darstellt (das funktioniert allerdings nicht immer ganz so, wie es soll, insbesondere dann, wenn ein Auszeichnungsformat durch verschiedene Programme unterschiedlich interpretiert wird, wie es etwa bei Webbrowsern der Fall ist). Die Kombination aus Sprache und interpretierendem Programm ermöglicht also die vollständige Nutzung der Daten. Wie ein Programm zur Auswertung einer Auszeichnungssprache funktioniert, werden wir ein andermal betrachten (nämlich dann, wenn es um die Funktionsweise von Parsern geht) - hier möchte ich dagegen die eingangs erwähnte Sprache HTML näher vorstellen und beschreiben, wie man damit eine Website aufbauen kann.

Die folgenden Ausführungen können Interessierte übrigens direkt nachahmen; dazu reicht es, in einem beliebigen einfachen Texteditor (Notepad, Wordpad oder ähnliches - Microsoft Word ist hier nicht unbedingt geeignet) eine neue Datei anzulegen und diese unter einem beliebigen Namen mit der Dateiendung .html abzuspeichern. Öffnet man diese Datei im Anschluss per Doppelklick, sollte sich der entsprechend dargestellte Inhalt im Standardbrowser zeigen (ich habe ja die Hoffnung, dass wenigstens der ein oder andere das hier geschriebene direkt mit ausprobiert).

Die Auszeichnungssprache HTML folgt einem bestimmten Schema. Hierbei wird der darzustellende Text direkt in eine Datei geschrieben; zusätzlich kann er aber auch noch durch sogenannte Tags, also Markierungen um bestimmte Formatierungsinformationen (fett, kursiv usw.) angereichert oder (ebenfalls durch Tags) strukturiert werden. Aber fangen wir von vorne an.

Das einfachste aller HTML-Dokumente besteht direkt aus dem Text, den es repräsentieren soll; der Browser wird dann auch nichts weiter tun, als das Dokument auf die denkbar einfachste aller Möglichkeiten darzustellen, ähnlich einem ganz einfachen Texteditor (nur natürlich ohne die Bearbeitungsfunktionalität). Der folgende Beispieltext (gern auch als HTML-Code bezeichnet) in ein HTML-Dokument geschrieben wäre demzufolge die einfachste Art von Webpage überhaupt:

Ich lese gern Scienceblogs.de

Nun trifft man derartige Seiten im Internet natürlich höchst selten an; für gewöhnlich wird der Text einer Website auf die ein oder andere Art strukturiert und formatiert (also in der optischen Darstellung modifiziert) sein. Beides geschieht mit Hilfe sogenannter Tags, genauer: mit Hilfe von Tag-Paaren, bestehend aus Start-Tag und End-Tag. Ein Start-Tag besteht dabei immer aus einem von gewinkelten Klammern eingeschlossenen Bezeichner (und einer Menge von Eigenschaften, dazu aber mehr), also zum Beispiel <b>; das dazugehörige End-Tag sieht genauso aus, nur mit einem zusätzlichen Slash hinter der öffnenden Klammer, also etwa </b>. Die möglichen Bezeichner in den Klammern sind mit ihrer Bedeutung durch den HTML-Standard, einer formalen Spezifikation unter Federführung des W3C, mehr oder weniger vorgegeben, wobei jedoch leider viele Browser eigene Elemente eingeführt haben. Zwischen dem Start- und End-Tag werden die zu strukturierenden oder formatierenden Textbestandteile geschrieben, wobei diese wiederum Tags enthalten können und so weiter. Das beispielhaft genannte Tag-Paar mit einem b sorgt etwa dafür, dass der eingeschlossene Text fett hervorgehoben wird; nehmen wir also unser Beispiel von oben und schreiben

Ich lese <b>gern</b> Scienceblogs.de

so erhalten wir (probiert es aus) als Darstellung im Browser:

  Ich lese gern Scienceblogs.de

Die Tags zur Text-Formatierung haben übrigens oft deskriptiven Charakter, das heißt anstatt eine genaue Formatierung vorzugeben, wird notiert, was ein Text darstellen soll. Bestes Beispiel hierfür sind etwa Überschriften; anstatt ein Textelement als Fett und in einer größeren Schriftgröße zu markieren, wird es lediglich als Überschrift getaggt, etwa so (h1 ist das Tag für Hauptüberschriften):

<h1>Ich lese gern Scienceblogs.de</h1>

Der Browser erledigt dann den Rest und stellt den Text entsprechend formatiert dar:

Ich lese gern Scienceblogs.de

Neben der reinen Formatierung des Textes ist es üblich, diesen auch zusätzlich noch zu strukturieren. Ein HTML-Dokument wird dabei traditionell in einen Kopfteil mit allgemeinen Informationen über das Dokument und einen Körper mit dem eigentlichen Inhalt unterteilt. Der Inhalt kann wiederum in Überschriften, Absätze, Listen, Tabellen und ähnliche Elemente unterteilt werden, für die es jeweils eigene Tags gibt. Eine einfache vollständig strukturierte HTML-Datei könnte etwa so aussehen (das umschließende html-Tag markiert den Inhalt als HTML):

<html>
  <head>
    <title>Einführung in HTML</title>
  </head>
  <body>
    <h1>Darum mag ich Scienceblogs:</h1>
    <p>
      Ich lese <b>gern</b> Scienceblogs.de, da es
      <ul>
        <li><i>informativ</i></li>
        <li><i>spannend und</i></li>
        <li><i>gut geschrieben</i></li>
      </ul> ist.
    </p>
  </body>
</html>

Eine kurze Erklärung der Elemente: mit head und body werden der Kopfteil und der Körper des HTML-Dokumentes markiert; mit Hilfe des title-Tags wird der im Browser angezeigte Titel der Webpage notiert; das p-Tag beschreibt einen Absatz im Dokument. Mit dem Tag ul wird schließlich eine (ungeordnete) Liste und mit li ein einzelnes Element in der Liste beschrieben (welches mit Hilfe des i-Tags außerdem kursiv dargestellt wird). Der Teil des HTML-Körpers würde demzufolge etwa so aussehen:

Darum mag ich Scienceblogs:

Ich lese gern Scienceblogs.de, da es

• informativ
• spannend und
• gut geschrieben

Wer mehr über die einzelnen HTML-Elemente erfahren möchte, ist auf de.selfhtml.org gut aufgehoben. Zudem bieten viele Browser die Möglichkeit, den HTML-Text einer Webpage direkt anzuzeigen (normalerweise sieht man ja nur die fertig formatierte Struktur). Wer sich dafür interessiert, findet meist im Kontext-Menü (Rechtsklick in einer Webpage) oder allgemeinen Menü (in jedem Browser woanders, meist aber oben links) des Browsers eine entsprechende Option. Die hier vorgestellten Möglichkeiten zur Textformatierung und -strukturierung können übrigens nicht nur durch die Ersteller einer Website genutzt werden; auch die Anwender einer Website können sich manchmal der Tags bedienen, etwa wenn sie Kommentare unter Artikel schreiben möchten (ob das funktioniert, hängt in der Regel vom eingesetzten System ab - auf Scieneblogs funktioniert es).

Wäre man nur auf die Tags zur Strukturierung einer Website angewiesen, würde man ziemlich viele von ihnen benötigen, um alle möglichen Formatierungen auszudrücken. Aus diesem Grund ist es möglich, bestimmte Tags mit Eigenschaften zu versehen, die weiteren Einfluss auf die (inhaltliche und optische) Darstellung nehmen. Die Eigenschaft eines Tags wird im Start-Tag hinter der Tag-Bezeichnung in der Form eigenschaft=wert notiert, wobei die verfügbaren Eigenschaften wiederum vom Tag abhängen. Ein relativ häufig benutztes Tag hierfür dürfte der Anker zur Markierung von Hyperlinks sein. Das Tag a (für anchor) besitzt die mögliche Eigenschaft href, durch welche das Ziel eines Verweises (also etwa ein Link) angegeben werden kann. Auf unser Eingangs-Beispiel bezogen, könnte man also folgendes schreiben:

Ich lese gern <a href="http://scienceblogs.de/">SB.de</a>

Damit hätte man einen einfachen Hyperlink auf eine Adresse im Internet definiert, der auf der Webpage wie folgend aussehen würde:

  Ich lese gern SB.de

Mit den hier vorgestellten Tags ist es möglich, einfache Websites zu gestalten. Größere optische Änderungen an der Standard-Darstellung können sich jedoch mit dieser Methode leider ziemlich aufwändig gestalten, da jedes Tag separat mit Formatierungs-Eigenschaften versehen werden müsste. Um die Gestaltung von Websites weiter zu vereinfachen, wurden daher die Cascading Style Sheets (kurz CSS) eingeführt, mit denen die Formatierung weitaus besser gestaltet werden kann; darüber werde ich aber im nächsten Artikel etwas erzählen.