Andere Links:

Algoritmos Genticos y Computacin Evolutiva
Eine spanische Übersetzung dieses Artikels.

Einführung
Oben

Kreationisten werfen gelegentlich vor, die Evolution sei als wissenschaftliche Theorie nutzlos, weil sie keine praktischen Vorteile bringe und keinen Bezug zum täglichen Leben habe. Doch allein die Beweise der Biologie zeigen, dass diese Behauptung falsch ist. Es gibt zahlreiche natürliche Phänomene, für die uns die Evolution eine fundierte theoretische Grundlage bietet. Um nur eines zu nennen: Die beobachtete Entwicklung von Resistenzen – gegen Insektizide bei Schädlingen in der Landwirtschaft, gegen Antibiotika bei Bakterien, gegen Chemotherapie bei Krebszellen und gegen Antiretrovirale bei Viren wie HIV – ist eine direkte Folge der Gesetze von Mutation und natürlicher Selektion. Das Verständnis dieser Prinzipien hat uns geholfen, Strategien zur Bekämpfung dieser schädlichen Organismen zu entwickeln. Das evolutionäre Postulat der gemeinsamen Abstammung hat die Entwicklung neuer Medikamente und medizinischer Verfahren unterstützt, indem es Forschern eine gute Vorstellung davon gab, welche Organismen sie untersuchen sollten, um Ergebnisse zu erhalten, die am ehesten für den Menschen relevant sind. Schließlich wurde das Prinzip der selektiven Zucht von Menschen mit großem Erfolg genutzt, um maßgeschneiderte Organismen zu schaffen, die in der Natur nichts Vergleichbares bieten, und dies zu ihrem eigenen Vorteil. Das kanonische Beispiel ist natürlich die Vielzahl domestizierter Hunde (aus Wölfen wurden in nur wenigen tausend Jahren Rassen so unterschiedlich wie Bulldoggen, Chihuahuas und Dackel gezüchtet), aber weniger bekannte Beispiele sind kultivierter Mais (sehr unterschiedlich von seinen wilden Verwandten, von denen keines die vertrauten „Ähren" von menschlich angebautem Mais hat), Goldfische (wie Hunde haben wir Varietäten gezüchtet, die sich dramatisch vom Wildtyp unterscheiden) und Milchkühe (mit enormen Eutern, die weit größer sind als für die Nahrung der Nachkommen erforderlich wären).

Kritiker könnten vorwerfen, dass Kreationisten diese Dinge ohne Rückgriff auf die Evolution erklären können. Zum Beispiel erklären Kreationisten oft die Entwicklung von Resistenz gegen Antibiotika bei Bakterien oder die durch künstliche Selektion bewirkten Veränderungen bei domestizierten Tieren damit, dass Gott beschloss, Organismen in festen Gruppen zu erschaffen, die als „Arten" oder baramin bezeichnet werden. Obwohl natürliche Mikroevolution oder menschlich geleitete künstliche Selektion innerhalb der ursprünglich erschaffenen „Hund-Art", „Kuh-Art" oder „Bakterien-Art" (!) verschiedene Varietäten hervorrufen können, kann keine Zeitspanne oder genetische Veränderung eine „Art" in eine andere verwandeln. Allerdings wird genau erklärt, wie die Kreationisten bestimmen, was eine „Art" ist, oder welcher Mechanismus verhindert, dass Lebewesen über ihre Grenzen hinaus evolvieren, invariabel nie.

Aber in den letzten Jahrzehnten hat der weitere Fortschritt der modernen Technologie etwas Neues hervorgebracht. Die Evolution bringt nun praktische Vorteile in einem ganz anderen Bereich, und dieses Mal können die Kreationisten nicht mehr behaupten, dass ihre Erklärung die Fakten ebenso gut erklärt. Dieser Bereich ist die Informatik, und die Vorteile ergeben sich aus einer Programmierstrategie, die genetische Algorithmen genannt wird. Dieser Aufsatz wird erklären, was genetische Algorithmen sind, und zeigen, wie sie für die Evolution/Kreationismus-Debatte relevant sind.

Was ist ein genetischer Algorithmus?
Zurück nach oben

Kurz gesagt ist ein genetischer Algorithmus (oder GA als Abkürzung) eine Programmiertechnik, die die biologische Evolution als Problemlösungsstrategie nachahmt. Gegeben ein spezifisches Problem zu lösen, ist die Eingabe für den GA eine Menge potenzieller Lösungen für dieses Problem, in einer bestimmten Weise kodiert, und ein Maß, das als Fitness-Funktion bezeichnet wird und es ermöglicht, jeden Kandidaten quantitativ zu bewerten. Diese Kandidaten können bereits bekannte Lösungen sein, die funktionieren, wobei das Ziel des GA darin besteht, sie zu verbessern, aber häufiger werden sie zufällig generiert.

Das GA bewertet dann jeden Kandidaten gemäß der Fitnessfunktion. In einem Pool zufällig generierter Kandidaten werden natürlich die meisten gar nicht funktionieren, und diese werden gelöscht. Allerdings können rein zufällig einige Hoffnung machen – sie können Aktivität zeigen, auch wenn nur schwache und unvollkommene Aktivität, zur Lösung des Problems.

Diese vielversprechenden Kandidaten werden beibehalten und zur Reproduktion zugelassen. Es werden mehrere Kopien davon erstellt, doch die Kopien sind nicht perfekt; während des Kopiervorgangs werden zufällige Änderungen eingeführt. Diese digitalen Nachkommen gehen dann in die nächste Generation über und bilden einen neuen Pool von Lösungsvorschlägen, und sie unterziehen sich einer zweiten Runde der Fitnessbewertung. Diejenigen Lösungsvorschläge, die durch Änderungen an ihrem Code verschlechtert wurden oder sich nicht verbessert haben, werden erneut gelöscht; doch wiederum rein zufällig können die in die Population eingeführten zufälligen Variationen einige Individuen verbessert haben, wodurch sie zu besseren, vollständigeren oder effizienteren Lösungen für das vorliegende Problem geworden sind. Auch diese gewinnenden Individuen werden ausgewählt und mit zufälligen Änderungen in die nächste Generation kopiert, und der Prozess wiederholt sich. Die Erwartung ist, dass die durchschnittliche Fitness der Population in jeder Runde zunimmt, und somit durch Wiederholung dieses Prozesses für hunderte oder tausende Runden sehr gute Lösungen für das Problem entdeckt werden können.

Wie auch immer es für manche erschreckend und kontraintuitiv erscheinen mag, haben genetische Algorithmen sich als eine enorm leistungsfähige und erfolgreiche Problemlösungsstrategie erwiesen und die Kraft evolutionärer Prinzipien dramatisch demonstriert. Genetische Algorithmen wurden in einer Vielzahl von Bereichen eingesetzt, um Lösungen für Probleme zu entwickeln, die so schwierig oder sogar schwieriger sind als die, denen menschliche Designer gegenüberstehen. Darüber hinaus sind die von ihnen gefundenen Lösungen oft effizienter, eleganter oder komplexer als etwas Vergleichbares, das ein menschlicher Ingenieur produzieren würde. In einigen Fällen haben genetische Algorithmen Lösungen gefunden, die die Programmierer, die die Algorithmen ursprünglich geschrieben haben, völlig verwirren!

Darstellungsverfahren

Bevor ein genetischer Algorithmus auf ein beliebiges Problem angewendet werden kann, ist eine Methode erforderlich, um potenzielle Lösungen für dieses Problem in einer Form zu kodieren, die ein Computer verarbeiten kann. Ein gängiger Ansatz besteht darin, Lösungen als Binärstrings zu kodieren: Folgen von 1ern und 0ern, wobei die Ziffer an jeder Position den Wert eines bestimmten Aspekts der Lösung darstellt. Ein weiterer, ähnlicher Ansatz besteht darin, Lösungen als Arrays von ganzen Zahlen oder Dezimalzahlen zu kodieren, wobei jede Position erneut einen bestimmten Aspekt der Lösung repräsentiert. Dieser Ansatz ermöglicht eine höhere Präzision und Komplexität als die vergleichsweise eingeschränkte Methode, nur Binärzahlen zu verwenden, und ist oft „intuitiv näher am Problemspace" (Fleming und Purshouse 2002, S. 1228).

Diese Technik wurde beispielsweise in der Arbeit von Steffen Schulze-Kremer verwendet, der einen genetischen Algorithmus entwickelte, um die dreidimensionale Struktur eines Proteins basierend auf der Aminosäuresequenz vorherzusagen, die in es eingeht (Mitchell 1996, S. 62). Der GA von Schulze-Kremer verwendete reellwertige Zahlen, um die sogenannten „Torsionswinkel" zwischen den Peptidbindungen darzustellen, die die Aminosäuren verbinden. (Ein Protein besteht aus einer Sequenz von Grundbausteinen, den Aminosäuren, die wie Glieder einer Kette miteinander verbunden sind. Sobald alle Aminosäuren verknüpft sind, faltet sich das Protein zu einer komplexen dreidimensionalen Form zusammen, basierend darauf, welche Aminosäuren sich gegenseitig anziehen und welche sich gegenseitig abstoßen. Die Form eines Proteins bestimmt seine Funktion.) Genetische Algorithmen zum Training von neuronalen Netzen verwenden diese Kodierungsmethode häufig ebenfalls.

Ein dritter Ansatz besteht darin, Individuen in einem GA als Buchstabenketten darzustellen, wobei jeder Buchstabe wiederum für einen spezifischen Aspekt der Lösung steht. Ein Beispiel für diese Technik ist der Ansatz von Hiroaki Kitano zur „grammatikalischen Kodierung", bei dem ein GA mit der Aufgabe betraut wurde, eine einfache Menge von Regeln namens kontextfreie Grammatik zu entwickeln, die ihrerseits verwendet wurde, um neuronale Netze für eine Vielzahl von Problemen zu generieren (Mitchell 1996, S. 74).

Der Vorteil aller drei dieser Methoden besteht darin, dass sie es einfach machen, Operatoren zu definieren, die die zufälligen Änderungen bei den ausgewählten Kandidaten bewirken: eine 0 in eine 1 umwandeln oder umgekehrt, einen Wert um eine zufällig gewählte Menge erhöhen oder verringern, oder einen Buchstaben durch einen anderen ersetzen. (Siehe den Abschnitt Methoden der Änderung für weitere Details zu den genetischen Operatoren.) Eine weitere Strategie, die hauptsächlich von John Koza der Stanford University entwickelt wurde und genetische Programmierung genannt wird, stellt Programme als verzweigte Datenstrukturen, sogenannte Bäume, dar (Koza et al. 2003, S. 35). In diesem Ansatz können zufällige Änderungen dadurch bewirkt werden, dass der Operator geändert oder der Wert an einem gegebenen Knoten im Baum verändert wird, oder indem ein Teilbaum durch einen anderen ersetzt wird.

Genetic Programming Trees

Abbildung 1: Drei einfache Programm-Bäume der Art, die normalerweise in der genetischen Programmierung verwendet werden. Der mathematische Ausdruck, den jeder darstellt, ist darunter angegeben.

Es ist wichtig zu beachten, dass evolutionäre Algorithmen keine Kandidatenlösungen als Datenstrings fester Länge darstellen müssen. Manche tun dies, andere jedoch nicht; beispielsweise kann Kitanos oben besprochene grammatikalische Kodierung effizient skaliert werden, um große und komplexe neuronale Netze zu erzeugen, und Kozas genetische Programmierbäume können so groß wachsen, wie es zur Lösung des jeweiligen Problems erforderlich ist.

Selektionsmethoden

Es gibt viele verschiedene Techniken, die ein genetisches Algorithmus verwenden kann, um Individuen auszuwählen, die in die nächste Generation kopiert werden sollen, aber unten sind einige der häufigsten Methoden aufgeführt. Einige dieser Methoden sind sich gegenseitig ausschließend, andere können jedoch und werden oft in Kombination verwendet.

Elitistische Selektion: Die am besten angepassten Mitglieder jeder Generation werden garantiert ausgewählt. (Die meisten GAs verwenden keinen reinen Elitismus, sondern stattdessen eine modifizierte Form, bei der das einzelne beste oder einige der besten Individuen jeder Generation in die nächste Generation kopiert werden, falls nichts Besseres auftaucht.)

Selektion proportional zur Fitness: Individuen mit höherer Fitness werden eher, aber nicht mit Sicherheit, ausgewählt.

Roulette-Rad-Auswahl: Eine Form der fitness-proportionalen Auswahl, bei der die Wahrscheinlichkeit, dass ein Individuum ausgewählt wird, proportional zum Grad ist, in dem seine Fitness größer oder kleiner als die Fitness seiner Konkurrenten ist. (Konzeptionell kann dies als ein Roulette-Spiel dargestellt werden – jedes Individuum erhält einen Abschnitt des Rades, aber fittere Individuen erhalten größere Abschnitte als weniger fittere. Das Rad wird dann gedreht, und jedes Mal, auf welchem Abschnitt es landet, wird dasjenige Individuum ausgewählt, das diesen Abschnitt „besitzt".)

Skalierung der Selektion: Wenn die durchschnittliche Fitness der Population steigt, nimmt auch die Stärke des selektiven Drucks zu, und die Fitnessfunktion wird diskriminierender. Diese Methode kann hilfreich sein, um später die beste Selektion vorzunehmen, wenn alle Individuen eine relativ hohe Fitness aufweisen und nur geringe Unterschiede in der Fitness ein Individuum von einem anderen unterscheiden.

Turnierauswahl: Untergruppen von Individuen werden aus der größeren Population ausgewählt, und Mitglieder jeder Untergruppe treten gegeneinander an. Nur ein Individuum aus jeder Untergruppe wird zur Fortpflanzung ausgewählt.

Rangselektion: Jeder Individuum in der Population wird basierend auf der Fitness eine numerische Rangzahl zugewiesen, und die Selektion erfolgt auf Grundlage dieser Rangordnung statt auf absoluten Unterschieden in der Fitness. Der Vorteil dieser Methode besteht darin, dass sie verhindern kann, dass sehr fitte Individuen zu früh die Dominanz erlangen, was die weniger fiten Individuen zum Opfer fällt. Dies würde die genetische Vielfalt der Population verringern und möglicherweise Versuche behindern, eine akzeptable Lösung zu finden.

Generationselektion: Die Nachkommen der Individuen, die aus jeder Generation ausgewählt werden, bilden die gesamte nächste Generation. Keine Individuen werden zwischen den Generationen beibehalten.

Steady-state selection: Die Nachkommen der Individuen, die aus jeder Generation ausgewählt wurden, kehren in den bereits bestehenden Genpool zurück und ersetzen einige der weniger fiten Mitglieder der vorherigen Generation. Einige Individuen werden zwischen den Generationen beibehalten.

Hierarchische Selektion: Individuen durchlaufen in jeder Generation mehrere Runden der Selektion. Niedrigere Evaluierungen sind schneller und weniger diskriminierend, während diejenigen, die höhere Stufen erreichen, strenger evaluiert werden. Der Vorteil dieser Methode besteht darin, dass sie die gesamte Rechenzeit reduziert, indem schnellere, weniger selektive Evaluierungen verwendet werden, um die Mehrheit der Individuen aussortieren zu können, die wenig oder keine Aussicht auf Erfolg zeigen, und nur diejenigen, die diesen ersten Test bestehen, einer strengeren und rechenintensiveren Fitnessbewertung unterzogen werden.

Veränderungsmethoden

Sobald die Selektion geeignete Individuen ausgewählt hat, müssen diese zufällig verändert werden, um die Fitness für die nächste Generation zu verbessern. Es gibt zwei grundlegende Strategien, dies zu erreichen. Die erste und einfachste wird Mutation genannt. Genau wie Mutation bei Lebewesen ein Gen in ein anderes verwandelt, führt Mutation in einem genetischen Algorithmus zu kleinen Änderungen an einzelnen Stellen im Code eines Individuums.

Die zweite Methode wird Crossover genannt und umfasst die Auswahl von zwei Individuen, um Segmente ihres Codes auszutauschen, wodurch künstliche „Nachkommen" entstehen, die Kombinationen ihrer Eltern sind. Dieser Prozess soll den analogen Prozess der Rekombination simulieren, der während der sexuellen Reproduktion bei Chromosomen auftritt. Übliche Formen des Crossovers sind Single-Point Crossover, bei dem ein Austauschpunkt an einer zufälligen Stelle in den Genomen der beiden Individuen festgelegt wird und ein Individuum seinen gesamten Code vor diesem Punkt beisteuert, während das andere seinen gesamten Code nach diesem Punkt liefert, um einen Nachkommen zu erzeugen, und Uniform Crossover, bei dem der Wert an einer beliebigen Stelle im Genom des Nachkommen entweder der Wert des Genoms eines Elternteils an dieser Stelle oder der Wert des Genoms des anderen Elternteils an dieser Stelle ist, gewählt mit einer Wahrscheinlichkeit von 50/50.

Crossover
Mutation

Abbildung 2: Crossing-over und Mutation. Die obigen Diagramme veranschaulichen die Wirkung dieser genetischen Operatoren auf Individuen in einer Population von 8-Bit-Zeichenketten. Das obere Diagramm zeigt zwei Individuen, die einem Single-Point-Crossing-over unterzogen werden; der Austauschpunkt ist zwischen der fünften und sechsten Position im Genom festgelegt, wodurch ein neues Individuum entsteht, das ein Hybrid seiner Eltern ist. Das zweite Diagramm zeigt ein Individuum, das an Position 4 einer Mutation unterzogen wird, wodurch die 0 an dieser Position im Genom in eine 1 umgewandelt wird.

Andere Problemlösungstechniken

Mit dem Aufkommen der künstlichen Lebensberechnung und der Entwicklung heuristischer Methoden haben sich andere computergestützte Problemlösungstechniken entwickelt, die in mancher Hinsicht genetischen Algorithmen ähneln. Dieser Abschnitt erläutert einige dieser Techniken, inwiefern sie genetischen Algorithmen ähneln und inwiefern sie sich von ihnen unterscheiden.

  • Neuronale Netze
    Ein neuronales Netz, kurz auch neuronales Netz genannt, ist ein Problemlösungsverfahren, das auf einem Computermodell basiert, das beschreibt, wie Neuronen im Gehirn miteinander verbunden sind. Ein neuronales Netz besteht aus Schichten von Verarbeitungseinheiten, die als Knoten bezeichnet werden und durch gerichtete Verbindungen miteinander verbunden sind: eine Eingabeschicht, eine Ausgabeschicht und null oder mehrere dazwischenliegende verborgene Schichten. Ein anfängliches Muster von Eingaben wird der Eingabeschicht des neuronalen Netzes präsentiert, und die angeregten Knoten leiten dann ein Signal an die Knoten der nächsten Schicht weiter, mit denen sie verbunden sind. Wenn die Summe aller Eingaben, die in einen dieser virtuellen Neuronen eintreten, höher ist als die sogenannte Aktivierungsschwelle dieses Neurons, aktiviert sich dieses Neuron selbst und leitet sein eigenes Signal an Neuronen in der nächsten Schicht weiter. Das Aktivierungsmuster breitet sich daher vorwärts aus, bis es die Ausgabeschicht erreicht und dort als Lösung für die präsentierte Eingabe zurückgegeben wird. Genau wie im Nervensystem biologischer Organismen lernen neuronale Netze und optimieren ihre Leistung im Laufe der Zeit durch wiederholte Runden des Anpassens ihrer Schwellenwerte, bis die tatsächliche Ausgabe für eine gegebene Eingabe mit der gewünschten Ausgabe übereinstimmt. Dieser Prozess kann von einem menschlichen Experimentator überwacht werden oder kann automatisch mit einem Lernalgorithmus ablaufen (Mitchell 1996, S. 52). Genetische Algorithmen wurden sowohl zum Aufbau als auch zum Training neuronaler Netze eingesetzt.

Ein einfaches neuronales Netzwerk
Abbildung 3: Ein einfaches feedforward-neuronales Netzwerk mit einer Eingabeschicht, die aus vier Neuronen besteht, einer versteckten Schicht, die aus drei Neuronen besteht, und einer Ausgabeschicht, die aus vier Neuronen besteht. Die Zahl auf jedem Neuron repräsentiert dessen Aktivierungsschwelle: Es feuert nur, wenn es mindestens so viele Eingaben erhält. Das Diagramm zeigt das neuronale Netzwerk, das mit einer Eingabesequenz präsentiert wird, und zeigt, wie die Aktivierung vorwärts durch das Netzwerk ausbreitet, um eine Ausgabe zu erzeugen.

  • Hill-climbing
    Ähnlich wie genetische Algorithmen, jedoch systematischer und weniger zufällig, beginnt ein Hill-climbing-Algorithmus mit einer ersten Lösung für das vorliegende Problem, die in der Regel zufällig gewählt wird. Anschließend wird die Zeichenkette mutiert, und wenn die Mutation zu einer höheren Fitness für die neue Lösung im Vergleich zur vorherigen führt, wird die neue Lösung beibehalten; andernfalls wird die aktuelle Lösung erhalten. Der Algorithmus wird dann wiederholt, bis keine Mutation gefunden werden kann, die die Fitness der aktuellen Lösung erhöht, und diese Lösung wird als Ergebnis zurückgegeben (Koza et al. 2003, S. 59). (Um zu verstehen, woher der Name dieser Technik stammt, stellen Sie sich vor, der Raum aller möglichen Lösungen für ein gegebenes Problem wird als dreidimensionale Konturlandschaft dargestellt. Ein bestimmter Satz von Koordinaten auf dieser Landschaft repräsentiert eine bestimmte Lösung. Lösungen, die besser sind, liegen höher in der Höhe und bilden Hügel und Gipfel; diejenigen, die schlechter sind, liegen niedriger in der Höhe und bilden Täler. Ein „Hill-climber" ist dann ein Algorithmus, der an einem gegebenen Punkt auf der Landschaft beginnt und unablässig bergauf wandert.) Hill-climbing ist das, was als greedy algorithm bekannt ist, was bedeutet, dass er zu jedem Schritt die beste verfügbare Wahl trifft, in der Hoffnung, dass auf diese Weise das insgesamt beste Ergebnis erzielt werden kann. Im Gegensatz dazu sind Methoden wie genetische Algorithmen und simulated annealing, die weiter unten besprochen werden, nicht greedy; diese Methoden treffen manchmal suboptimale Entscheidungen in der Hoffnung, dass sie später zu besseren Lösungen führen.

  • Simulated annealing
    Eine weitere Optimierungstechnik, die den evolutionären Algorithmen ähnelt, ist das simulated annealing. Die Idee entlehnt ihren Namen vom industriellen Prozess des annealing, bei dem ein Material über einen kritischen Punkt erhitzt wird, um es zu erweichen, und dann allmählich abgekühlt wird, um Defekte in seiner kristallinen Struktur zu beseitigen und eine stabilere und regelmäßige Gitteranordnung von Atomen zu erzeugen (Haupt und Haupt 1998, S. 16). Beim simulated annealing gibt es, wie bei genetischen Algorithmen, eine Fitnessfunktion, die eine Fitnesslandschaft definiert; jedoch gibt es, im Gegensatz zu einer Population von Kandidaten wie bei GAs, nur einen einzigen Kandidaten für eine Lösung. Das simulated annealing fügt zudem das Konzept der „Temperatur" hinzu, einer globalen numerischen Größe, die sich im Laufe der Zeit allmählich verringert. In jedem Schritt des Algorithmus mutiert die Lösung (was gleichbedeutend mit einem Wechsel zu einem benachbarten Punkt der Fitnesslandschaft ist). Anschließend wird die Fitness der neuen Lösung mit der Fitness der vorherigen Lösung verglichen; wenn sie höher ist, wird die neue Lösung beibehalten. Andernfalls trifft der Algorithmus eine Entscheidung, ob sie beibehalten oder verworfen werden soll, basierend auf der Temperatur. Wenn die Temperatur hoch ist, wie zu Beginn, können sogar Änderungen, die signifikante Verringerungen der Fitness verursachen, beibehalten und als Grundlage für die nächste Runde des Algorithmus verwendet werden, aber je niedriger die Temperatur wird, desto mehr neigt der Algorithmus dazu, nur Fitness-erhöhende Änderungen zu akzeptieren. Schließlich erreicht die Temperatur Null und das System „friert ein"; diejenige Konfiguration, in der es sich zu diesem Zeitpunkt befindet, wird zur Lösung. Das simulated annealing wird häufig für Ingenieuranwendungen wie die Bestimmung der physikalischen Anordnung von Komponenten auf einem Computerchip verwendet (Kirkpatrick, Gelatt und Vecchi 1983).

Kurze Geschichte der GAs
Oben

Die frühesten Beispiele für das, was heute als genetische Algorithmen bezeichnet werden, tauchten Ende der 1950er und Anfang der 1960er Jahre auf, programmiert von Evolutionsbiologen auf Computern, die explizit darauf abzielten, Aspekte der natürlichen Evolution zu modellieren. Es kam keinem von ihnen in den Sinn, dass diese Strategie möglicherweise allgemeiner auf künstliche Probleme anwendbar wäre, doch diese Erkenntnis ließ nicht lange auf sich warten: „Evolutionäre Berechnung war in den formative Tagen des elektronischen Computers definitiv in der Luft" (Mitchell 1996, S. 2). Bis 1962 hatten Forscher wie G.E.P. Box, G.J. Friedman, W.W. Bledsoe und H.J. Bremermann unabhängig voneinander evolutionäre inspirierte Algorithmen für die Funktionsoptimierung und das maschinelle Lernen entwickelt, doch ihre Arbeit erzielte wenig Nachfolge. Ein erfolgreicherer Fortschritt in diesem Bereich erfolgte 1965, als Ingo Rechenberg, damals an der Technischen Universität Berlin, eine Technik einführte, die er Evolution Strategy nannte, obwohl sie eher an Hill-Climber als an genetische Algorithmen erinnerte. Bei dieser Technik gab es keine Population oder Kreuzung; ein Elternteil wurde mutiert, um einen Nachkommen zu erzeugen, und das Bessere der beiden wurde beibehalten und wurde zum Elternteil für die nächste Runde der Mutation (Haupt und Haupt 1998, S. 146). Spätere Versionen führten die Idee einer Population ein. Evolution Strategies werden heute immer noch von Ingenieuren und Wissenschaftlern eingesetzt, insbesondere in Deutschland.

Die nächste wichtige Entwicklung auf diesem Gebiet erfolgte 1966, als L.J. Fogel, A.J. Owens und M.J. Walsh in Amerika eine Technik einführten, die sie evolutionäre Programmierung nannten. In dieser Methode wurden Kandidatenlösungen für Probleme als einfache endliche Automaten dargestellt; ähnlich wie bei Rechberg's Evolution Strategy arbeitete ihr Algorithmus durch zufällige Mutation eines dieser simulierten Automaten und Beibehaltung des besseren der beiden (Mitchell 1996, S.2; Goldberg 1989, S.105). Ähnlich wie bei Evolution Strategies ist auch eine breitere Formulierung der evolutionären Programmierungstechnik heute noch ein Bereich laufender Forschung. Was jedoch in beiden Methoden noch fehlte, war die Anerkennung der Bedeutung von Crossover.

Schon 1962 legte die Arbeit von John Holland über adaptive Systeme das Fundament für spätere Entwicklungen; vor allem war Holland auch der Erste, der Crossing-Over und andere Rekombinationsoperatoren explizit vorschlug. Die wegweisende Arbeit auf dem Gebiet der genetischen Algorithmen erfolgte jedoch erst 1975 mit der Veröffentlichung des Buches Anpassung in natürlichen und künstlichen Systemen. Aufbauend auf früheren Forschungsarbeiten und Publikationen sowohl von Holland selbst als auch von Kollegen an der University of Michigan war dieses Buch das erste, das das Konzept adaptiver digitaler Systeme unter Verwendung von Mutation, Selektion und Crossing-Over, die Prozesse der biologischen Evolution simulierend, als Problemlösungsstrategie systematisch und rigoros darstellte. Das Buch versuchte zudem, genetische Algorithmen auf eine feste theoretische Grundlage zu stellen, indem es den Begriff der Schemata einführte (Mitchell 1996, S. 3; Haupt und Haupt 1998, S. 147). Im selben Jahr etablierte die wichtige Dissertation von Kenneth De Jong das Potenzial von GAs, indem er zeigte, dass sie bei einer Vielzahl von Testfunktionen gut abschneiden, einschließlich verrauschter, unstetiger und multimodaler Suchlandschaften (Goldberg 1989, S. 107).

Diese grundlegenden Werke weckten ein breiteres Interesse an evolutionärer Informatik. Anfang bis Mitte der 1980er Jahre wurden genetische Algorithmen auf ein breites Spektrum von Themen angewendet, von abstrakten mathematischen Problemen wie Bin-Packing und Graphenfärbung bis hin zu konkreten ingenieurwissenschaftlichen Fragen wie der Steuerung von Rohrleitungsströmungen, Mustererkennung und Klassifizierung sowie der strukturellen Optimierung (Goldberg 1989, S. 128).

Ursprünglich waren diese Anwendungen vor allem theoretischer Natur. Allerdings haben sich genetische Algorithmen mit der weiteren Verbreitung der Forschung in den kommerziellen Sektor verlagert, wobei ihr Aufstieg durch das exponentielle Wachstum der Rechenleistung und die Entwicklung des Internets gefördert wurde. Heute ist die evolutionäre Berechnung ein blühendes Feld, und genetische Algorithmen lösen „Probleme alltäglichen Interesses" (Haupt und Haupt 1998, S. 147) in Forschungsbereichen so unterschiedlicher Natur wie die Vorhersage von Aktienmärkten und die Portfolio-Planung, Luft- und Raumfahrttechnik, Mikrochip-Design, Biochemie und Molekularbiologie sowie die Planung von Flugplänen und Montagelinien. Die Kraft der Evolution hat praktisch jedes Feld berührt, das man nennen kann, und formt die Welt um uns herum auf unzählige unsichtbare Weise, während neue Anwendungen weiterhin entdeckt werden, solange die Forschung fortgesetzt wird. Und im Kern aller dieser Entwicklungen liegt nichts anderes als Charles Darwins einfaches, kraftvolles Einsicht: Dass die zufällige Chance der Variation, gekoppelt mit dem Gesetz der Selektion, eine Problemlösungstechnik unvorstellbarer Kraft und nahezu unbegrenzter Anwendung ist.

Was sind die Stärken von GAs?
Oben
  • Der erste und wichtigste Punkt ist, dass genetische Algorithmen intrinsisch parallel sind. Die meisten anderen Algorithmen sind seriell und können den Lösungsraum eines Problems nur zu einem Zeitpunkt in einer Richtung erkunden. Wenn sich herausstellt, dass die von ihnen gefundene Lösung suboptimal ist, bleibt nichts anderes übrig, als alle bisher durchgeführten Arbeiten aufzugeben und von vorne zu beginnen. Da genetische Algorithmen jedoch mehrere Nachkommen haben, können sie den Lösungsraum gleichzeitig in mehreren Richtungen erkunden. Wenn sich ein Pfad als Sackgasse herausstellt, können sie diesen leicht eliminieren und die Arbeit auf vielversprechendere Wege fortsetzen, wodurch sie bei jedem Durchlauf eine größere Chance haben, die optimale Lösung zu finden.

    Der Vorteil der Parallelität geht jedoch darüber hinaus. Betrachten Sie Folgendes: Alle 8-stelligen Binärstrings (Strings aus 0ern und 1ern) bilden einen Suchraum, der als ******** dargestellt werden kann (wobei das * für "entweder 0 oder 1" steht). Der String 01101010 ist ein Mitglied dieses Raums. Er ist jedoch auch ein Mitglied des Raums 0*******, des Raums 01******, des Raums 0******0, des Raums 0*1*1*1*, des Raums 01*01**0 und so weiter. Indem die Fitness dieses einen bestimmten Strings bewertet wird, würde ein genetischer Algorithmus jeden dieser vielen Räume, zu denen er gehört, abtasten. Über viele solcher Bewertungen hinweg würde er einen zunehmend genaueren Wert für die mittlere Fitness jedes dieser Räume aufbauen, von denen jeder viele Mitglieder hat. Daher bewertet ein GA, der explizit eine kleine Anzahl von Individuen bewertet, implizit eine viel größere Gruppe von Individuen – genau wie ein Meinungsforscher, der Fragen an ein bestimmtes Mitglied einer ethnischen, religiösen oder sozialen Gruppe stellt, hofft, etwas über die Meinungen aller Mitglieder dieser Gruppe zu erfahren, und daher die nationale Meinung zuverlässig vorhersagen kann, während er nur einen kleinen Prozentsatz der Bevölkerung befragt. Auf die gleiche Weise kann der GA "hineinfinden" in den Raum mit den Individuen der höchsten Fitness und das beste Individuum aus dieser Gruppe finden. Im Kontext evolutionärer Algorithmen wird dies als Schema-Theorem bezeichnet und ist der "zentrale Vorteil" eines GAs gegenüber anderen Problemlösungsmethoden (Holland 1992, S. 68; Mitchell 1996, S. 28-29; Goldberg 1989, S. 20).

  • Wegen des Parallelismus, der es ermöglicht, viele Schemata implizit gleichzeitig zu bewerten, sind genetische Algorithmen besonders gut geeignet, um Probleme zu lösen, bei denen der Raum aller potenziellen Lösungen wirklich riesig ist – zu groß, um ihn in einer vernünftigen Zeitspanne erschöpfend durchsuchen zu können. Die meisten Probleme, die in diese Kategorie fallen, werden als „nichtlinear" bezeichnet. Bei einem linearen Problem ist die Fitness jedes Komponenten unabhängig, sodass jede Verbesserung eines einzelnen Teils zu einer Verbesserung des Systems als Ganzes führt. needless to say, sind wenige reale Probleme so. Nichtlinearität ist die Norm, wobei die Änderung einer Komponente Auswirkungen auf das gesamte System haben kann und mehrere Änderungen, die einzeln nachteilig sind, zu viel größeren Verbesserungen der Fitness führen können, wenn sie kombiniert werden. Nichtlinearität führt zu einer kombinatorischen Explosion: Der Raum von 1.000-stelligen Binärstrings kann durch die Bewertung von nur 2.000 Möglichkeiten erschöpfend durchsucht werden, wenn das Problem linear ist, wohingegen bei einem nichtlinearen Problem eine erschöpfende Suche die Bewertung von 21000 Möglichkeiten erfordert – eine Zahl, die in voller Schreibweise über 300 Stellen benötigen würde.

    Glücklicherweise erlaubt der implizite Parallelismus eines GA, auch diese enorme Anzahl von Möglichkeiten zu überwinden und erfolgreich optimale oder sehr gute Ergebnisse in kurzer Zeit zu finden, nachdem nur kleine Bereiche der riesigen Fitnesslandschaft direkt abgetastet wurden (Forrest 1993, S. 877). Zum Beispiel hat ein genetischer Algorithmus, der gemeinsam von Ingenieuren von General Electric und dem Rensselaer Polytechnic Institute entwickelt wurde, ein Hochleistungs-Turbinendesign für Flugzeugtriebwerke erstellt, das dreimal besser ist als eine von Menschen entworfene Konfiguration und 50 % besser als eine Konfiguration, die von einem Expertensystem entwickelt wurde, indem es einen Lösungsraum erfolgreich durchnavigiert hat, der mehr als 10387 Möglichkeiten enthält. Herkömmliche Methoden zur Konstruktion solcher Turbinen sind ein zentraler Bestandteil von Ingenieurprojekten, die bis zu fünf Jahre dauern und über 2 Milliarden Dollar kosten; der genetische Algorithmus entdeckte diese Lösung nach zwei Tagen auf einem typischen Ingenieurs-Desktop-Workstation (Holland 1992, S. 72).

  • Ein weiterer bemerkenswerter Vorteil genetischer Algorithmen besteht darin, dass sie bei Problemen gut funktionieren, bei denen die Fitnesslandschaft komplex ist – also bei Problemen, bei denen die Fitnessfunktion unstetig, verrauscht, sich über die Zeit ändert oder viele lokale Optima aufweist. Die meisten praktischen Probleme besitzen einen riesigen Lösungsraum, der nicht erschöpfend durchsucht werden kann; die Herausforderung besteht dann darin, die lokalen Optima zu vermeiden – Lösungen, die besser sind als alle anderen, die ihnen ähnlich sind, aber nicht so gut wie andere Lösungen an anderer Stelle im Lösungsraum. Viele Suchalgorithmen können in lokalen Optima stecken bleiben: Wenn sie den Gipfel eines Hügels auf der Fitnesslandschaft erreichen, stellen sie fest, dass es in der Nähe keine besseren Lösungen gibt, und schließen daraus, dass sie das beste Ergebnis erreicht haben, obwohl es an anderer Stelle auf der Karte höhere Gipfel gibt.

    Evolutionäre Algorithmen haben sich andererseits als effektiv erwiesen, um lokale Optima zu verlassen und das globale Optimum auch in einer sehr zerklüfteten und komplexen Fitnesslandschaft zu finden. (Es sei angemerkt, dass es in der Realität in der Regel keine Möglichkeit gibt, festzustellen, ob eine gegebene Lösung eines Problems das eine globale Optimum ist oder nur ein sehr hohes lokales Optimum. Dennoch kann ein GA, auch wenn er nicht immer eine nachweislich perfekte Lösung für ein Problem liefert, fast immer mindestens eine sehr gute Lösung liefern.) Alle vier Hauptkomponenten eines GAs – Parallelität, Selektion, Mutation und Kreuzung – arbeiten zusammen, um dies zu erreichen. Zu Beginn erzeugt der GA eine diverse Anfangspopulation und wirft ein „Netz" über die Fitnesslandschaft. (Koza (2003, S. 506) vergleicht dies mit einer Armee von Fallschirmspringern, die auf die Landschaft des Suchraums eines Problems herabfallen, wobei jeder Befehle erhält, den höchsten Gipfel zu finden.) Kleine Mutationen ermöglichen es jedem Individuum, seine unmittelbare Umgebung zu erkunden, während die Selektion den Fortschritt fokussiert und die Nachkommen des Algorithmus bergauf zu vielversprechenderen Teilen des Lösungsraums führt (Holland 1992, S. 68).

    Kreuzung ist jedoch das Schlüsselelement, das genetische Algorithmen von anderen Methoden wie Steigungssuchern und simuliertem Ausglühen unterscheidet. Ohne Kreuzung ist jede einzelne Lösung auf sich allein gestellt und erkundet den Suchraum in ihrer unmittelbaren Umgebung ohne Bezug darauf, was andere Individuen möglicherweise entdeckt haben. Mit Kreuzung hingegen findet ein Informationsaustausch zwischen erfolgreichen Kandidaten statt – Individuen können von dem profitieren, was andere gelernt haben, und Schemata können gemischt und kombiniert werden, mit dem Potenzial, einen Nachkommen hervorzubringen, der die Stärken beider Eltern aufweist und die Schwächen keines von ihnen. Dieser Punkt wird in Koza et al. 1999, S. 486, illustriert, wo die Autoren ein Problem der Synthese eines Tiefpassfilters unter Verwendung genetischer Programmierung diskutieren. In einer Generation wurden zwei Elternschaltungen ausgewählt, um einer Kreuzung zu unterzogen; einer der Eltern hatte eine gute Topologie (Komponenten wie Induktoren und Kondensatoren an den richtigen Stellen), aber eine schlechte Dimensionierung (Werte für Induktivität und Kapazität seiner Komponenten, die weit zu niedrig waren). Der andere Elternteil hatte eine schlechte Topologie, aber eine gute Dimensionierung. Das Ergebnis der Paarung beider durch Kreuzung war ein Nachkomme mit der guten Topologie eines Elternteils und der guten Dimensionierung des anderen, was zu einer erheblichen Verbesserung der Fitness gegenüber beiden Eltern führte.

    Das Problem, das globale Optimum in einem Raum mit vielen lokalen Optima zu finden, wird auch als Dilemma der Exploration versus Exploitation bezeichnet, „ein klassisches Problem für alle Systeme, die sich anpassen und lernen können" (Holland 1992, S. 69). Sobald ein Algorithmus (oder ein menschlicher Designer) eine Problemlösungsstrategie gefunden hat, die zufriedenstellend zu funktionieren scheint, sollte er sich darauf konzentrieren, diese Strategie bestmöglich zu nutzen, oder sollte er nach anderen suchen? Das Aufgeben einer bewährten Strategie, um nach neuen zu suchen, führt fast garantiert zu Verlusten und einer Verschlechterung der Leistung, zumindest kurzfristig. Aber wenn man sich einer bestimmten Strategie verschreibt und alle anderen ausschließt, läuft man das Risiko, bessere Strategien nicht zu entdecken, die zwar existieren, aber noch nicht gefunden wurden. Auch hier haben sich genetische Algorithmen als sehr gut erwiesen, dieses Gleichgewicht zu finden und gute Lösungen mit einem angemessenen Zeit- und Rechenaufwand zu entdecken.

  • Ein weiterer Bereich, in dem genetische Algorithmen hervorragend abschneiden, ist ihre Fähigkeit, viele Parameter gleichzeitig zu manipulieren (Forrest 1993, S. 874). Viele reale Probleme können nicht in Bezug auf einen einzelnen Wert formuliert werden, der minimiert oder maximiert werden soll, sondern müssen in Bezug auf mehrere Ziele ausgedrückt werden, die in der Regel Kompromisse beinhalten: man kann nur eines auf Kosten des anderen verbessern. Genetische Algorithmen sind sehr gut darin, solche Probleme zu lösen: insbesondere ermöglicht ihre Nutzung von Parallelität, mehrere gleich gute Lösungen für dasselbe Problem zu erzeugen, wobei möglicherweise eine Kandidatenlösung einen Parameter optimiert und eine andere Kandidatenlösung einen anderen (Haupt und Haupt 1998, S. 17), und ein menschlicher Überwacher kann dann einen dieser Kandidaten auswählen, um ihn zu verwenden. Wenn eine bestimmte Lösung eines mehrzieligen Problems einen Parameter in einem solchen Maße optimiert, dass dieser Parameter nicht weiter verbessert werden kann, ohne dass dies zu einer entsprechenden Verringerung der Qualität eines anderen Parameters führt, wird diese Lösung als Pareto-optimal oder nicht dominiert bezeichnet (Coello 2000, S. 112).

  • Schließlich ist eine der Eigenschaften genetischer Algorithmen, die auf den ersten Blick als Nachteil erscheinen könnte, tatsächlich einer ihrer Stärken: nämlich, dass GAs nichts über die Probleme wissen, für die sie eingesetzt werden. Anstatt wie menschliche Designer bekannte domänenspezifische Informationen zu nutzen, um jeden Schritt zu leiten und Änderungen mit einem spezifischen Blick auf die Verbesserung vorzunehmen, sind GAs „blinde Uhrmacher" (Dawkins 1996); sie führen zufällige Änderungen an ihren Kandidatenlösungen vor und nutzen dann die Fitnessfunktion, um zu bestimmen, ob diese Änderungen eine Verbesserung bewirken.

    Die Tugend dieser Technik besteht darin, dass sie genetischen Algorithmen ermöglicht, sozusagen mit einem offenen Geist zu beginnen. Da ihre Entscheidungen auf Zufälligkeit basieren, sind theoretisch alle möglichen Suchpfade für einen GA offen; im Gegensatz dazu muss jede Problemlösungsstrategie, die auf Vorwissen basiert, zwangsläufig damit beginnen, viele Pfade a priori auszuschließen und somit möglicherweise neuartige Lösungen zu übersehen, die dort existieren könnten (Koza et al. 1999, S. 547). Da GAs keine Vorurteile auf der Grundlage etablierter Überzeugungen darüber haben, „wie Dinge gemacht werden sollten" oder was „auf keinen Fall funktionieren könnte", haben sie dieses Problem nicht. Ebenso wird jede Technik, die auf Vorwissen basiert, versagen, wenn solches Wissen nicht verfügbar ist, aber GAs werden durch Ignoranz nicht beeinträchtigt (Goldberg 1989, S. 23). Durch ihre Komponenten Parallelität, Kreuzung und Mutation können sie sich weit über die Fitnesslandschaft erstrecken, Regionen erkunden, die von intelligent produzierten Algorithmen möglicherweise übersehen wurden, und potenziell Lösungen von erschreckender und unerwarteter Kreativität entdecken, die menschlichen Designern niemals in den Sinn gekommen wären. Ein anschauliches Beispiel hierfür ist die Wiederauffindung durch genetische Programmierung des Konzepts der negativen Rückkopplung – ein Prinzip, das für viele wichtige elektronische Bauteile heute entscheidend ist, das aber, als es erstmals entdeckt wurde, neun Jahre lang kein Patent erhielt, weil das Konzept so widersprüchlich zu etablierten Überzeugungen war (Koza et al. 2003, S. 413). Evolutionäre Algorithmen sind natürlich weder bewusst noch besorgt darüber, ob eine Lösung gegen etablierte Überzeugungen verstößt – nur darum, ob sie funktioniert.

Was sind die Grenzen von GA?
Oben

Obwohl genetische Algorithmen sich als eine effiziente und leistungsfähige Problemlösungsstrategie erwiesen haben, sind sie kein Allheilmittel. GAs haben zwar gewisse Einschränkungen; es wird jedoch gezeigt werden, dass all diese überwunden werden können und keine davon die Gültigkeit der biologischen Evolution betreffen.

  • Die erste und wichtigste Überlegung bei der Erstellung eines genetischen Algorithmus ist die Definition einer Repräsentation für das Problem. Die Sprache, die zur Spezifikation von Kandidatenlösungen verwendet wird, muss robust sein; d. h., sie muss in der Lage sein, zufällige Änderungen zu tolerieren, sodass keine fatalen Fehler oder Unsinn konsistent entstehen.

    Es gibt zwei Hauptwege, dies zu erreichen. Der erste, der von den meisten genetischen Algorithmen verwendet wird, besteht darin, Individuen als Listen von Zahlen zu definieren – binärwertig, ganzzahlwertig oder reellwertig –, wobei jede Zahl einen Aspekt einer Kandidatenlösung repräsentiert. Wenn die Individuen binäre Strings sind, können 0 oder 1 für das Fehlen oder Vorhandensein eines bestimmten Merkmals stehen. Wenn sie Listen von Zahlen sind, können diese Zahlen viele verschiedene Dinge repräsentieren: die Gewichte der Verbindungen in einem neuronalen Netzwerk, die Reihenfolge der besuchten Städte in einer bestimmten Tour, die räumliche Platzierung elektronischer Komponenten, die Werte, die in einen Regler eingespeist werden, die Torsionswinkel von Peptidbindungen in einem Protein und so weiter. Mutation beinhaltet dann das Ändern dieser Zahlen, das Umdrehen von Bits oder das Hinzufügen oder Subtrahieren zufälliger Werte. In diesem Fall ändert sich der eigentliche Programmcode nicht; der Code verwaltet die Simulation und verfolgt die Individuen, bewertet ihre Fitness und stellt möglicherweise sicher, dass nur Werte entstehen, die für das gegebene Problem realistisch und möglich sind.

    Bei einer anderen Methode, dem genetischen Programmieren, ändert sich der eigentliche Programmcode doch. Wie im Abschnitt Methoden der Repräsentation diskutiert, stellt GP Individuen als ausführbare Code-Bäume dar, die durch das Ändern oder Austauschen von Unterbäumen mutiert werden können. Beide Methoden erzeugen Repräsentationen, die gegen Mutation robust sind und viele verschiedene Arten von Problemen darstellen können, und wie im Abschnitt Einige spezifische Beispiele diskutiert, haben beide beträchtlichen Erfolg erzielt.

    Das Problem der Repräsentation von Kandidatenlösungen auf eine robuste Weise stellt sich in der Natur nicht, weil die von der Evolution verwendete Repräsentationsmethode, nämlich der genetische Code, von sich aus robust ist: mit nur wenigen Ausnahmen, wie einer Reihe von Stop-Codons, gibt es keine Sequenz von DNA-Basen, die nicht in ein Protein übersetzt werden kann. Daher wird praktisch jede Änderung an den Genen eines Individuums immer noch ein verständliches Ergebnis produzieren, und Mutationen in der Evolution haben daher eine höhere Chance, eine Verbesserung zu erzeugen. Dies steht im Gegensatz zu menschengeschaffenen Sprachen wie Englisch, bei denen die Anzahl der sinnvollen Wörter im Vergleich zur Gesamtzahl der Möglichkeiten, Buchstaben des Alphabets zu kombinieren, gering ist, und daher zufällige Änderungen an einem englischen Satz wahrscheinlich Unsinn produzieren.

  • Das Problem, wie die Fitnessfunktion zu formulieren ist, muss sorgfältig bedacht werden, damit eine höhere Fitness erreichbar ist und tatsächlich einer besseren Lösung für das gegebene Problem entspricht. Wenn die Fitnessfunktion schlecht gewählt oder unpräzise definiert wird, kann der genetische Algorithmus möglicherweise keine Lösung für das Problem finden oder sich stattdessen für das falsche Problem entscheiden. (Diese letztere Situation wird manchmal als die Tendenz eines GA, zu „betrügen", beschrieben, obwohl in Wirklichkeit lediglich geschieht, dass der GA das tut, was ihm befohlen wurde, nicht das, was seine Schöpfer beabsichtigt haben.) Ein Beispiel hierfür findet sich in Graham-Rowe 2002, in dem Forscher einen evolutionären Algorithmus in Verbindung mit einem reprogrammierbaren Hardware-Array einsetzten und die Fitnessfunktion so einrichteten, dass sie die sich entwickelnde Schaltung belohnte, wenn sie ein oszillierendes Signal ausgab. Am Ende des Experiments wurde tatsächlich ein oszillierendes Signal erzeugt – aber statt dass die Schaltung selbst als Oszillator fungierte, wie die Forscher es beabsichtigt hatten, stellten sie fest, dass sie zu einem Funkempfänger geworden war, der ein oszillierendes Signal von einer nahegelegenen elektronischen Ausrüstung aufnahm und weiterleitete!

    Dies ist jedoch kein Problem in der Natur. Im Labor der biologischen Evolution gibt es nur eine Fitnessfunktion, die für alle Lebewesen gleich ist – der Drang zu überleben und sich fortzupflanzen, unabhängig davon, welche Anpassungen dies ermöglichen. Diejenigen Organismen, die sich im Vergleich zu ihren Konkurrenten üppiger fortpflanzen, sind fitter; diejenigen, die sich nicht fortpflanzen, sind unpassend.

  • Neben der Wahl einer guten Fitnessfunktion müssen auch die anderen Parameter eines GA – die Populationsgröße, die Mutations- und Crossover-Rate sowie die Art und Stärke der Selektion – sorgfältig gewählt werden. Ist die Populationsgröße zu klein, kann der genetische Algorithmus möglicherweise nicht genügend Teile des Lösungsraums erforschen, um konsistent gute Lösungen zu finden. Ist die Rate des genetischen Wandels zu hoch oder wird das Selektionsschema schlecht gewählt, können vorteilhafte Schemata gestört werden, und die Population kann in eine Katastrophe des Fehlers geraten, wobei sie sich so schnell ändert, dass die Selektion niemals Konvergenz herbeiführen kann.

    Lebewesen stehen tatsächlich ebenfalls vor ähnlichen Schwierigkeiten, und die Evolution hat diese bewältigt. Es ist wahr, dass eine Population aussterben kann, wenn ihre Größe zu gering wird, die Mutationsraten zu hoch sind oder der Selektionsdruck zu stark ist (eine solche Situation könnte durch drastische Umweltveränderungen verursacht werden). Die Lösung ist die „Evolution der Evolvierbarkeit" – Anpassungen, die die Fähigkeit einer Spezies zur Anpassung verändern. Beispielsweise haben die meisten Lebewesen ausgeklügelte molekulare Maschinen entwickelt, die Fehler während des DNA-Replikationsprozesses überprüfen und korrigieren, wodurch ihre Mutationsrate auf akzeptabel niedrige Niveaus gesenkt wird; umgekehrt treten einige Bakterienspezies bei schwerem Umweltstress in einen Zustand der Hypermutation ein, bei dem die Rate von DNA-Replikationsfehlern stark ansteigt und die Wahrscheinlichkeit erhöht wird, dass eine ausgleichende Mutation entdeckt wird. Natürlich können nicht alle Katastrophen vermieden werden, aber die enorme Vielfalt und die hochkomplexen Anpassungen der Lebewesen heute zeigen, dass die Evolution im Allgemeinen eine erfolgreiche Strategie ist. Ebenso zeigen die vielfältigen Anwendungen und die beeindruckenden Ergebnisse, die durch genetische Algorithmen erzielt werden, dass es sich um ein leistungsfähiges und lohnendes Forschungsgebiet handelt.

  • Eine Art von Problem, mit der genetische Algorithmen Schwierigkeiten haben, sind Probleme mit „täuschenden" Fitnessfunktionen (Mitchell 1996, S. 125), bei denen die Positionen verbesserter Punkte irreführende Informationen darüber liefern, wo das globale Optimum wahrscheinlich zu finden ist. Zum Beispiel stellen Sie sich ein Problem vor, bei dem der Suchraum aus allen achtstelligen Binärstrings besteht und die Fitness eines Individuums direkt proportional zur Anzahl der 1er darin ist – d. h., 00000001 wäre weniger fit als 00000011, welches wiederum weniger fit als 00000111 wäre, und so weiter – mit zwei Ausnahmen: Der String 11111111 erwies sich als sehr geringe Fitness, und der String 00000000 erwies sich als sehr hohe Fitness. Bei einem solchen Problem wäre ein GA (sowie die meisten anderen Algorithmen) nicht wahrscheinlicher, das globale Optimum zu finden, als eine zufällige Suche.

    Die Lösung dieses Problems ist sowohl für genetische Algorithmen als auch für die biologische Evolution dieselbe: Die Evolution ist kein Prozess, der jedes Mal das einzige globale Optimum finden muss. Sie kann fast ebenso gut abschneiden, indem sie das Gipfel eines hohen lokalen Optimums erreicht, und für die meisten Situationen wird dies ausreichen, auch wenn das globale Optimum von diesem Punkt aus nicht leicht zu erreichen ist. Die Evolution ist sehr wohl ein „Satisficer" – ein Algorithmus, der eine „ausreichend gute" Lösung liefert, auch wenn es nicht unbedingt die beste mögliche Lösung ist, gegeben eine vernünftige Menge an investierter Zeit und Mühe in die Suche. Die FAQ Evidence for Jury-Rigged Design in Nature gibt Beispiele für dieses sehr Ergebnis in der Natur. (Es ist auch erwähnenswert, dass wenige, wenn überhaupt, reale Probleme so vollständig täuschend sind wie der etwas konstruierte obige Beispiel. Normalerweise gibt die Position lokaler Verbesserungen zumindest einige Informationen über die Position des globalen Optimums.)

  • Ein bekanntes Problem, das bei einem GA auftreten kann, ist die frühe Konvergenz. Wenn sich früh im Verlauf der Ausführung ein Individuum entwickelt, das fitter ist als die meisten seiner Konkurrenten, kann es sich so stark vermehren, dass es die Vielfalt der Population zu früh verringert. Dies führt dazu, dass der Algorithmus auf das lokale Optimum konvergiert, das dieses Individuum repräsentiert, anstatt die Fitnesslandschaft gründlich genug zu durchsuchen, um das globale Optimum zu finden (Forrest 1993, S. 876; Mitchell 1996, S. 167). Dies ist ein besonders häufiges Problem in kleinen Populationen, in denen sogar zufällige Schwankungen der Reproduktionsrate dazu führen können, dass ein Genotyp gegenüber anderen dominiert.

    Die von GA-Forschern am häufigsten eingesetzten Methoden zur Bewältigung dieses Problems umfassen alle die Kontrolle der Stärke der Selektion, um übermäßig fitten Individuen keinen zu großen Vorteil zu verschaffen. Rank-, Skalierungs- und Turnierselktion, die bereits diskutiert wurden, sind drei Hauptmethoden, um dies zu erreichen; einige Skalierungsmethoden der Selektion umfassen die Sigma-Skalierung, bei der die Reproduktion auf einem statistischen Vergleich mit der durchschnittlichen Fitness der Population basiert, und die Boltzmann-Selktion, bei der die Stärke der Selektion im Verlauf einer Ausführung ähnlich der „Temperatur"-Variable beim simulierten Ausglühen zunimmt (Mitchell 1996, S. 168).

    Die frühe Konvergenz tritt in der Natur tatsächlich auf (wo Biologen sie genetische Drift nennen). Dies sollte nicht überraschend sein; wie oben diskutiert, ist die Evolution als Problemlösungsstrategie nicht verpflichtet, die einzige beste Lösung zu finden, sondern lediglich eine, die gut genug ist. Allerdings ist die frühe Konvergenz in der Natur weniger häufig, da die meisten vorteilhaften Mutationen bei Lebewesen nur kleine, inkrementelle Verbesserungen der Fitness bewirken; Mutationen, die einen so großen Fitnessgewinn bewirken, dass ihre Träger einen dramatischen reproduktiven Vorteil haben, sind selten.

  • Schließlich raten mehrere Forscher (Holland 1992, S. 72; Forrest 1993, S. 875; Haupt und Haupt 1998, S. 18) davon ab, genetische Algorithmen auf analytisch lösbare Probleme anzuwenden. Es ist nicht so, dass genetische Algorithmen keine guten Lösungen für solche Probleme finden können; es ist lediglich so, dass traditionelle analytische Methoden viel weniger Zeit und Rechenleistung benötigen als genetische Algorithmen und, im Gegensatz zu diesen, in der Regel mathematisch garantiert sind, die eine exakte Lösung zu liefern. Natürlich ist, da es keine mathematisch perfekte Lösung für jedes Problem der biologischen Anpassung gibt, dieses Problem in der Natur nicht relevant.

Einige spezifische Beispiele für GAs
Oben

Da die Kraft der Evolution zunehmend weite Anerkennung findet, wurden genetische Algorithmen eingesetzt, um eine breite Vielfalt von Problemen in einer extrem diversen Reihe von Feldern anzugehen, was ihre Kraft und ihr Potenzial deutlich zeigt. In diesem Abschnitt werden einige der bemerkenswertesten Anwendungen diskutiert, zu denen sie herangezogen wurden.

  • Akustik
    Sato et al. 2002 verwendeten genetische Algorithmen, um einen Konzertsaal mit optimalen akustischen Eigenschaften zu entwerfen, wobei die Klangqualität für das Publikum, den Dirigenten und die Musiker auf der Bühne maximiert wurde. Diese Aufgabe beinhaltet die gleichzeitige Optimierung mehrerer Variablen. Beginnend mit einem schuhkartonförmigen Saal erzeugten die GA der Autoren zwei nicht dominierte Lösungen, die beide als „blattförmig" beschrieben wurden (S. 526). Die Autoren stellen fest, dass diese Lösungen Proportionen aufweisen, die denen des Wiener Grosser Musikvereinsaal ähneln, der weithin als einer der besten – wenn nicht der beste – Konzertsaal der Welt in Bezug auf akustische Eigenschaften anerkannt ist.

    Porto, Fogel und Fogel 1995 verwendeten evolutionäre Programmierung, um neuronale Netze zu trainieren, um zwischen Sonarreflexionen verschiedener Objekttypen zu unterscheiden: künstliche Metallsphären, Seamounts, Fische und Pflanzen sowie zufälligen Hintergrundrauschen. Nach 500 Generationen hatte das beste evolvierte neuronale Netz eine Wahrscheinlichkeit der korrekten Klassifizierung zwischen 94% und 98% und eine Wahrscheinlichkeit der Fehlklassifizierung zwischen 7,4% und 1,5%, was „vernünftige Wahrscheinlichkeiten für Detektion und Fehlalarm" (S. 21) darstellt. Das evolvierte Netz entsprach der Leistung eines weiteren Netzes, das durch simuliertes Ausglühen entwickelt wurde, und übertraf konsequent Netze, die durch Rückwärtspropagation trainiert wurden, die „wiederholt bei suboptimalen Gewichtssets steckten, die keine zufriedenstellenden Ergebnisse lieferten" (S. 21). Im Gegensatz dazu zeigten beide stochastischen Methoden, dass sie in der Lage sind, diese lokalen Optima zu überwinden und kleinere, effektivere und robusteren Netze zu erzeugen; die Autoren schlagen jedoch vor, dass der evolutionäre Algorithmus, im Gegensatz zum simulierten Ausglühen, auf einer Population operiert und somit globale Informationen über den Suchraum nutzt, was potenziell zu einer besseren Leistung auf lange Sicht führen kann.

    Tang et al. 1996 untersuchen die Anwendungen genetischer Algorithmen im Bereich der Akustik und Signalverarbeitung. Ein Bereich besonderem Interesses ist die Verwendung von GAs zur Entwicklung von aktiven Geräuschunterdrückungssystemen (Active Noise Control, ANC), die unerwünschte Geräusche auslöschen, indem sie Schallwellen erzeugen, die destruktiv mit dem unerwünschten Rauschen interferieren. Dies ist ein mehrzieliges Problem, das die präzise Platzierung und Steuerung mehrerer Lautsprecher erfordert; GAs wurden sowohl zur Entwicklung der Regler als auch zur Ermittlung der optimalen Platzierung der Lautsprecher für solche Systeme eingesetzt, was in experimentellen Tests zu einer „effektiven Dämpfung von Geräuschen" (S. 33) führte.

  • Aerospace-Engineering
    Obayashi et al. 2000 used a multiple-objective genetic algorithm to design the wing shape for a supersonic aircraft. Three major considerations govern the wing's configuration - minimizing aerodynamic drag at supersonic cruising speeds, minimizing drag at subsonic speeds, and minimizing aerodynamic load (the bending force on the wing). These objectives are mutually exclusive, and optimizing them all simultaneously requires tradeoffs to be made.

    The chromosome in this problem is a string of 66 real-valued numbers, each of which corresponds to a specific aspect of the wing: its shape, its thickness, its twist, and so on. Evolution with elitist rank selection was simulated for 70 generations, with a population size of 64 individuals. At the termination of this process, there were several Pareto-optimal individuals, each one representing a single non-dominated solution to the problem. The paper notes that these best-of-run individuals have "physically reasonable" characteristics, indicating the validity of the optimization technique (p.186). To further evaluate the quality of the solutions, six of the best were compared to a supersonic wing design produced by the SST Design Team of Japan's National Aerospace Laboratory. All six were competitive, having drag and load values approximately equal to or less than the human-designed wing; one of the evolved solutions in particular outperformed the NAL's design in all three objectives. The authors note that the GA's solutions are similar to a design called the "arrow wing" which was first suggested in the late 1950s, but ultimately abandoned in favor of the more conventional delta-wing design.

    In a follow-up paper (Sasaki et al. 2001), the authors repeat their experiment while adding a vierte objective, namely minimizing the twisting moment of the wing (a known potential problem for arrow-wing SST designs). Additional control points for thickness are also added to the array of design variables. After 75 generations of evolution, two of the best Pareto-optimal solutions were again compared to the Japanese National Aerospace Laboratory's wing design for the NEXST-1 experimental supersonic airplane. It was found that both of these designs (as well as one optimal design from the previous simulation, discussed above) were physically reasonable and superior to the NAL's design in all four objectives.

    Williams, Crossley und Lang 2001 applied genetic algorithms to the task of spacing satellite orbits to minimize coverage blackouts. As telecommunications technology continues to improve, humans are increasingly dependent on Earth-orbiting satellites to perform many vital functions, and one of the problems engineers face is designing their orbital trajectories. Satellites in high Earth orbit, around 22,000 miles up, can see large sections of the planet at once and be in constant contact with ground stations, but these are far more expensive to launch and more vulnerable to cosmic radiation. It is more economical to put satellites in low orbits, as low as a few hundred miles in some cases, but because of the curvature of the Earth it is inevitable that these satellites will at times lose line-of-sight access to surface receivers and thus be useless. Even constellations of several satellites experience unavoidable blackouts and losses of coverage for this reason. The challenge is to arrange the satellites' orbits to minimize this downtime. This is a multi-objective problem, involving the minimization of both the average blackout time for all locations and the maximum blackout time for any one location; in practice, these goals turn out to be mutually exclusive.

    When the GA was applied to this problem, the evolved results for three, four and five-satellite constellations were unusual, highly asymmetric orbit configurations, with the satellites spaced by alternating large and small gaps rather than equal-sized gaps as conventional techniques would produce. However, this solution significantly reduced both average and maximum revisit times, in some cases by up to 90 minutes. In a news article about the results, Dr. William Crossley noted that "engineers with years of aerospace experience were surprised by the higher performance offered by the unconventional design".

    Keane und Brown 1996 verwendeten eine GA, um ein neues Design für einen tragenden Truss oder Balken zu entwickeln, der im Orbit zusammengebaut werden und für Satelliten, Raumstationen und andere Luft- und Raumfahrtbauprojekte verwendet werden konnte. Das Ergebnis, eine verdrehte, organisch aussehende Struktur, die mit einem menschlichen Beinbein verglichen wurde, verwendet nicht mehr Material als das Standard-Truss-Design, ist jedoch leichtgewichtig, stark und deutlich besser darin, schädliche Vibrationen zu dämpfen, wie durch reale Tests des Endprodukts bestätigt wurde. Und doch: „Keine Intelligenz hat die Designs erstellt. Sie haben sich einfach entwickelt" (Petit 1998). Die Autoren des Papiers bemerken ferner, dass ihre GA nur für 10 Generationen lief, aufgrund des rechenintensiven Charakters der Simulation, und die Population war noch nicht stagniert. Die Fortsetzung des Laufs für weitere Generationen hätte zweifellos weitere Leistungsverbesserungen hervorgebracht. Ein genetisch optimierter Truss
    Abbildung 4: Ein genetisch optimierter dreidimensionaler Truss mit verbesserter Frequenzantwort. (Angelehnt an [1].)


    Finally, as reported in Gibbs 1996, Lockheed Martin has used a genetic algorithm to evolve a series of maneuvers to shift a spacecraft from one orientation to another within 2% of the theoretical minimum time for such maneuvers. The evolved solution was 10% faster than a solution hand-crafted by an expert for the same problem.

  • Astronomie und Astrophysik
    Charbonneau 1995 schlägt die Nützlichkeit von GA für Probleme in der Astrophysik vor, indem sie sie auf drei Beispielprobleme anwendet: Anpassung der Rotationskurve einer Galaxie basierend auf den beobachteten Rotationsgeschwindigkeiten ihrer Komponenten, Bestimmung des Pulsationsperioden eines veränderlichen Sterns basierend auf Zeitreihendaten und Ermittlung der kritischen Parameter in einem magnetohydrodynamischen Modell des Sonnenwinds. Alle drei dieser Probleme sind schwierige mehrdimensionale nichtlineare Probleme.

    Charbonneaus genetischer Algorithmus, PIKAIA, verwendet generationenbasierte, fitness-proportionale Rangselektion gekoppelt mit Elitismus, wodurch sichergestellt wird, dass das einzelne beste Individuum unverändert einmal in die nächste Generation kopiert wird. PIKAIA hat eine Crossover-Rate von 0,65 und eine variable Mutationsrate, die zunächst auf 0,003 eingestellt ist und später allmählich ansteigt, wenn sich die Population der Konvergenz nähert, um die Variabilität im Genpool aufrechtzuerhalten.

    Im Problem der galaktischen Rotationskurve erzeugte die GA zwei Kurven, die beide sehr gute Anpassungen an die Daten waren (ein häufiges Ergebnis bei diesem Typ von Problem, bei dem wenig Kontrast zwischen benachbarten Gipfeln besteht); weitere Beobachtungen können dann unterscheiden, welche bevorzugt werden soll. Im Zeitreihenproblem war die GA beeindruckend erfolgreich bei der autonomen Generierung einer hochwertigen Anpassung an die Daten, aber schwierigere Probleme wurden nicht so gut angepasst (obwohl, wie Charbonneau hervorhebt, diese Probleme mit konventionellen Techniken ebenso schwer zu lösen sind). Der Artikel schlägt vor, dass eine hybride GA, die sowohl künstliche Evolution als auch standardanalytische Techniken einsetzt, möglicherweise bessere Ergebnisse liefern würde. Schließlich wurde bei der Ermittlung der sechs kritischen Parameter des Sonnenwinds von der GA der Wert von drei davon mit einer Genauigkeit von weniger als 0,1% und die verbleibenden drei mit Genauigkeiten von weniger als 1 bis 10% erfolgreich bestimmt. (Obwohl eine niedrigere experimentelle Fehlerquote für diese drei immer vorzuziehen wäre, weist Charbonneau darauf hin, dass es keine anderen robusten, effizienten Methoden gibt, um ein sechsdimensionales nichtlineares Problem dieser Art experimentell zu lösen; ein konjugierter Gradienten-Verfahren funktioniert „solange eine sehr gute Startnäherung bereitgestellt werden kann" (S. 323). Im Gegensatz dazu erfordern GAs kein derart fein abgestimmtes domänenspezifisches Wissen.)

    Basierend auf den bisher erzielten Ergebnissen schlägt Charbonneau vor, dass GAs in anderen schwierigen Problemen der Astrophysik verwendet werden können und sollten, insbesondere inverse Probleme wie Doppler-Bildgebung und helioseismische Inversionen. Zum Schluss argumentiert Charbonneau, dass GAs ein „starker und vielversprechender Kandidat" (S. 324) in diesem Feld sind, der erwartet werden kann, traditionelle Optimierungstechniken zu ergänzen, anstatt sie zu ersetzen, und schließt mit dem Fazit, „die Kernaussage, falls es eine geben soll, ist, dass genetische Algorithmen funktionieren, und oft erschreckend gut" (S. 325).

  • Chemie
    Hochleistungslaser mit ultrakurzen Impulsen können komplexe Moleküle in einfachere Moleküle aufspalten, ein Prozess mit wichtigen Anwendungen in der organischen Chemie und der Mikroelektronik. Die spezifischen Endprodukte einer solchen Reaktion können durch Modulation der Phase des Laserimpulses gesteuert werden. Für große Moleküle ist es jedoch zu schwierig, die gewünschte Impulsform analytisch zu berechnen: Die Berechnungen sind zu komplex, und die relevanten Eigenschaften (die Potentialenergieflächen der Moleküle) sind nicht präzise genug bekannt.

    Assion et al. 1998 lösten dieses Problem, indem sie einen evolutionären Algorithmus zur Gestaltung der Impulsform verwendeten. Anstatt komplexes, problembezogenes Wissen über die quantenmechanischen Eigenschaften der Eingabemoleküle einzugeben, um den Impuls nach Spezifikationen zu gestalten, feuert der EA einen Impuls ab, misst die Anteile der resultierenden Produktmoleküle, mutiert die Strahleigenschaften zufällig in der Hoffnung, diese Anteile dem gewünschten Ausgang näherzubringen, und der Prozess wiederholt sich. (Anstatt die Eigenschaften des Laserstrahls direkt zu verfeinern, stellen die Autoren des GA Individuen als eine Menge von 128 Zahlen dar, wobei jede eine Spannungswert ist, der den Brechungsindex eines Pixels im Laserlichtmodulator steuert. Auch hier ist kein problembezogenes Wissen über die Eigenschaften entweder des Lasers oder der Reaktionsprodukte erforderlich.) Die Autoren stellen fest, dass ihr Algorithmus, wenn er auf zwei Beispielsubstanzen angewendet wird, „automatisch die beste Konfiguration findet... egal wie kompliziert die molekulare Reaktion auch sein mag" (S. 920), was „automatisierte kohärente Kontrolle von Produkten demonstriert, die chemisch voneinander und vom Ausgangsmolekül verschieden sind" (S. 921).

    In den frühen bis mittleren 1990er Jahren revolutionierte die weit verbreitete Einführung einer neuartigen Technik zur Arzneimitteldesign namens Kombinatorische Chemie die Pharmaindustrie. Bei dieser Methode werden anstatt der mühsamen, präzisen Synthese einer einzelnen Verbindung nach der anderen bewusst eine Vielzahl von Reaktanten gemischt, um eine noch größere Vielfalt von Produkten zu erzeugen – Hunderte, Tausende oder Millionen verschiedener Verbindungen pro Charge –, die dann schnell auf biochemische Aktivität hin gescreent werden können. Beim Entwerfen von Reaktantenbibliotheken für diese Technik gibt es zwei Hauptansätze: reaktantenbasiertes Design, das optimierte Gruppen von Reaktanten auswählt, ohne zu berücksichtigen, welche Produkte entstehen, und produktbasiertes Design, das Reaktanten auswählt, die am ehesten Produkte mit den gewünschten Eigenschaften erzeugen. Produktbasiertes Design ist schwieriger und komplexer, hat sich jedoch als Ergebnis besserer und vielfältigerer kombinatorischer Bibliotheken und einer höheren Wahrscheinlichkeit für ein brauchbares Ergebnis erwiesen.

    In einer von der Forschungs- und Entwicklungsabteilung von GlaxoSmithKline finanzierten Arbeit diskutiert Gillet 2002 die Verwendung eines mehrzieligen genetischen Algorithmus für das produktbasierte Design kombinatorischer Bibliotheken. Bei der Auswahl der Verbindungen, die in eine bestimmte Bibliothek eingehen, müssen Eigenschaften wie molekulare Vielfalt und Gewicht, Kosten der Materialien, Toxizität, Absorption, Verteilung und Metabolismus berücksichtigt werden. Wenn das Ziel darin besteht, Moleküle zu finden, die einem bestehenden Molekül mit bekannter Funktion ähneln (eine gängige Methode des neuen Arzneimitteldesigns), kann auch die strukturelle Ähnlichkeit berücksichtigt werden. Diese Arbeit präsentiert einen mehrzieligen Ansatz, bei dem eine Menge von Pareto-optimalen Ergebnissen entwickelt werden kann, die jedes dieser Ziele maximieren oder minimieren. Der Autor schließt, dass der GA in der Lage war, die Kriterien der molekularen Vielfalt und der maximalen synthetischen Effizienz gleichzeitig zu erfüllen, und Moleküle finden konnte, die drug-like waren sowie „sehr ähnlich zu gegebenen Zielmolekülen nach der Erforschung eines sehr kleinen Bruchteils des gesamten Suchraums" (S. 378).

    In einer verwandten Arbeit diskutieren Glen und Payne 1995 die Verwendung genetischer Algorithmen, um neue Moleküle von Grund auf neu automatisch zu entwerfen, um einem gegebenen Satz von Spezifikationen zu entsprechen. Gegeben eine Anfangspopulation, entweder zufällig generiert oder unter Verwendung des einfachen Moleküls Ethan als Saatgut, fügt der GA zufällig Atome und Molekülfragmente hinzu, entfernt und verändert sie mit dem Ziel, Moleküle zu generieren, die den gegebenen Einschränkungen entsprechen. Der GA kann gleichzeitig eine große Anzahl von Zielen optimieren, einschließlich Molekulargewicht, Molekularvolumen, Anzahl der Bindungen, Anzahl der chiralen Zentren, Anzahl der Atome, Anzahl der rotierbaren Bindungen, Polarisierbarkeit, Dipolmoment und mehr, um Kandidatenmoleküle mit den gewünschten Eigenschaften zu produzieren. Basierend auf experimentellen Tests, einschließlich eines schwierigen Optimierungsproblems, das die Generierung von Molekülen mit Eigenschaften ähnlich denen von Ribose (ein Zuckerstoff, der häufig in antiviralen Medikamenten nachgeahmt wird) umfasste, schließen die Autoren, dass der GA ein „exzellenter Ideengenerator" (S. 199) ist, der „schnelle und leistungsstarke Optimierungseigenschaften" bietet und „eine vielfältige Menge möglicher Strukturen" generieren kann (S. 182). Sie stellen weiter fest: „Besonders hervorzuheben ist die leistungsstarke Optimierungsfähigkeit des genetischen Algorithmus, selbst bei relativ kleinen Populationsgrößen" (S. 200). Als Zeichen dafür, dass diese Ergebnisse nicht nur theoretisch sind, berichtet Lemley 2001, dass die Unilever-Konzern genetische Algorithmen verwendet hat, um neue antimikrobielle Verbindungen für Reiniger zu entwerfen, die sie patentiert haben.

  • Elektrotechnik
    Ein feldprogrammierbares Gatterarray, kurz FPGA, ist eine spezielle Art von Leiterplatte mit einem Array von Logikzellen, die jeweils als jede Art von Logikgatter fungieren können und durch flexible Verbindungen miteinander verknüpft sind, die Zellen verbinden können. Beide Funktionen werden durch Software gesteuert, sodass die Platine lediglich durch das Laden eines speziellen Programms auf der Stelle verändert werden kann, um die Funktionen einer Vielzahl von Hardwaregeräten auszuführen.

    Dr. Adrian Thompson hat dieses Gerät ausgenutzt, in Kombination mit den Prinzipien der Evolution, um einen Prototypen für einen Spracherkennungskreis zu erzeugen, der zwischen gesprochene Befehle unterscheiden und darauf reagieren kann, indem er lediglich 37 Logikgatter verwendet – eine Aufgabe, die für jeden menschlichen Ingenieur als unmöglich betrachtet worden wäre. Er erzeugte zufällige Bit- Strings aus 0en und 1en und verwendete sie als Konfigurationen für das FPGA, wählte die am besten angepassten Individuen aus jeder Generation, reproduzierte und mutierte sie zufällig, tauschte Abschnitte ihres Codes aus und übertrug sie auf eine andere Runde der Selektion. Sein Ziel war es, ein Gerät zu entwickeln, das zunächst zwischen Tönen unterschiedlicher Frequenzen (1 und 10 Kilohertz) unterscheiden und dann zwischen den gesprochenen Wörtern "go" und "stop" unterscheiden konnte.

    Dieses Ziel wurde innerhalb von 3000 Generationen erreicht, aber der Erfolg war sogar größer als erwartet. Das entwickelte System verwendet weit weniger Zellen als etwas, das ein menschlicher Ingenieur hätte entwerfen können, und es benötigt nicht einmal den kritischsten Bestandteil von menschlich gebauten Systemen – einen Taktgeber. Wie funktioniert es? Thompson hat keine Ahnung, obwohl er das Eingangssignal durch eine komplexe Anordnung von Rückkopplungsschleifen im entwickelten Kreislauf verfolgt hat. Tatsächlich sind von den 37 Logikgattern, die das Endprodukt verwendet, fünf von ihnen überhaupt nicht mit dem Rest des Kreises auf irgendeine Weise verbunden – doch wenn ihre Stromversorgung entfernt wird, hört der Kreislauf auf zu funktionieren. Es scheint, dass die Evolution einige subtile elektromagnetische Effekte dieser Zellen ausgenutzt hat, um ihre Lösung zu finden, doch die exakte Funktionsweise der komplexen und komplizierten entwickelten Struktur bleibt ein Rätsel (Davidson 1997).

    Altshuler und Linden 1997 verwendeten ein genetisches Algorithmus, um Drahtantennen mit vorher festgelegten Eigenschaften zu entwickeln. Die Autoren stellen fest, dass das Design solcher Antennen ein ungenauer Prozess ist, der mit den gewünschten Eigenschaften beginnt und dann die Form der Antenne durch "Rätsel.... Intuition, Erfahrung, Näherungsformeln oder empirische Studien" (p.50) bestimmt. Diese Technik ist zeitaufwendig, liefert oft keine optimalen Ergebnisse und funktioniert tendenziell nur gut für relativ einfache, symmetrische Designs. Im Gegensatz dazu wird bei der genetischen Algorithmus-Ansatz der Ingenieur die elektromagnetischen Eigenschaften der Antenne festlegt, und der GA synthetisiert automatisch eine passende Konfiguration.

    A Crooked-Wire Genetic Antenna
    Abbildung 5: Eine gewundene Drahtgenetische Antenne
    (nach Altshuler und Linden 1997, Abbildung 1).    		 Altshuler und Linden verwendeten ihren GA, um eine kreisförmig polarisierte Sieben-Segment-Antenne mit halbkugelförmiger Abdeckung zu entwerfen; das Ergebnis ist links dargestellt. Jedes Individuum im GA bestand aus einem binären Chromosom, das die dreidimensionalen Koordinaten jedes Endes jedes Drahts angab. Die Fitness wurde bewertet, indem jeder Kandidat gemäß einem elektromagnetischen Verkabelungscode simuliert wurde, und das beste Individuum der Lauf wurde dann gebaut und getestet. Die Autoren beschreiben die Form dieser Antenne, die traditionellen Antennen nicht ähnelt und keine offensichtliche Symmetrie aufweist, als "ungewöhnlich seltsam" und "gegenintuitiv" (p.52), doch sie hatte ein nahezu gleichmäßiges Strahlungsmuster mit hoher Bandbreite sowohl in der Simulation als auch im experimentellen Test, was der vorherigen Spezifikation hervorragend entsprach. Die Autoren schließen, dass eine auf genetischen Algorithmen basierende Methode für das Antennenentwurf "bemerkenswerte Versprechungen" zeigt. "...dieses neue Designverfahren ist fähig, genetische Antennen zu finden, die schwierige Antennenprobleme effektiv lösen können, und es wird besonders nützlich in Situationen sein, in denen bestehende Designs nicht ausreichen" (p.52).
  • Finanzmärkte
    Mahfoud und Mani 1996 verwendeten ein genetisches Algorithmus, um die zukünftige Performance von 1600 börsennotierten Aktien vorherzusagen. Konkret wurde das GA mit der Aufgabe betraut, die relative Rendite jeder Aktie zu prognostizieren, definiert als die Rendite dieser Aktie minus die durchschnittliche Rendite aller 1600 Aktien über den fraglichen Zeitraum, 12 Wochen (ein Kalenderquartal) in die Zukunft. Als Eingabe wurde dem GA historische Daten über jede Aktie in Form einer Liste von 15 Attributen wie dem Kurs-Gewinn-Verhältnis und der Wachstumsrate, gemessen zu verschiedenen vergangenen Zeitpunkten, zur Verfügung gestellt; das GA wurde gebeten, eine Reihe von if/then-Regeln zu entwickeln, um jede Aktie zu klassifizieren und als Ausgabe sowohl eine Empfehlung bezüglich des Handelns mit dieser Aktie (kaufen, verkaufen oder keine Vorhersage) als auch eine numerische Prognose der relativen Rendite bereitzustellen. Die Ergebnisse des GA wurden mit denen eines etablierten, auf neuronalen Netzen basierenden Systems verglichen, das die Autoren bereits seit drei Jahren zuvor zur Vorhersage von Aktienkursen und zum Management von Portfolios verwendet hatten. Natürlich ist der Aktienmarkt ein extrem lautes und nichtlineares System, und kein Vorhersagemechanismus kann zu 100% der Zeit korrekt sein; die Herausforderung besteht darin, einen Prädiktor zu finden, der häufiger als nicht korrekt ist.

    In dem Experiment erstellten das GA und das neuronale Netz jeweils am Ende jeder Woche Prognosen für jede der 1600 Aktien über zwölf aufeinanderfolgende Wochen. Zwölf Wochen nach jeder Vorhersage wurde die tatsächliche Performance mit der vorhergesagten relativen Rendite verglichen. Insgesamt übertraf das GA das neuronale Netz signifikant: In einem Durchlauf des Experiments sagte das GA die Richtung einer Aktie zu 47,6% der Zeit korrekt voraus, machte keine Vorhersage zu 45,8% der Zeit und machte eine falsche Vorhersage nur zu 6,6% der Zeit, was einer Gesamtprädiktionsgenauigkeit von 87,8% entspricht. Obwohl das neuronale Netz öfter definitive Vorhersagen traf, war es auch öfter in seinen Vorhersagen falsch (tatsächlich spekulieren die Autoren, dass die größere Fähigkeit des GA, keine Vorhersage zu treffen, wenn die Daten unsicher waren, ein Faktor für seinen Erfolg war; das neuronale Netz erzeugt immer eine Vorhersage, es sei denn, es wird vom Programmierer explizit eingeschränkt). Im 1600-Aktien-Experiment erzeugte das GA eine relative Rendite von +5,47%, gegenüber +4,40% für das neuronale Netz – ein statistisch signifikanter Unterschied. Tatsächlich übertraf das GA auch signifikant drei wichtige Aktienmarktindizes – den S&P 500, den S&P 400 und den Russell 2000 – über diesen Zeitraum; Zufall wurde als Ursache dieses Ergebnisses auf dem 95%-Konfidenzniveau ausgeschlossen. Die Autoren schreiben diesen überzeugenden Erfolg der Fähigkeit des genetischen Algorithmus zu, nichtlineare Beziehungen zu lernen, die für menschliche Beobachter nicht sofort offensichtlich sind, sowie der Tatsache, dass es dem menschlichen Experten eine „a priori-Voreingenommenheit gegen kontraintuitive oder konträre Regeln" (S. 562) fehlt.

    Ähnlicher Erfolg wurde von Andreou, Georgopoulos und Likothanassis 2002 erzielt, die hybride genetische Algorithmen verwendeten, um neuronale Netze zu entwickeln, die Wechselkurse von Fremdwährungen bis zu einem Monat im Voraus vorhersagten. Im Gegensatz zum letzten Beispiel, wo GAs und neuronale Netze im Wettbewerb standen, arbeiteten hier die beiden in Koncert, wobei das GA die Architektur (Anzahl der Eingabeeinheiten, Anzahl der versteckten Einheiten und die Anordnung der Verbindungen zwischen ihnen) des Netzes entwickelte, das dann von einem Filteralgorithmus trainiert wurde.

    Als historische Informationen wurde dem Algorithmus 1300 vorherige rohe tägliche Werte von fünf Währungen – dem US-Dollar, der deutschen Mark, dem französischen Franc, dem britischen Pfund und der griechischen Drachme – zur Verfügung gestellt und gebeten, ihre zukünftigen Werte 1, 2, 5 und 20 Tage im Voraus vorherzusagen. Die Performance des hybriden GA zeigte in allen getesteten Fällen ein „bemerkenswertes Maß an Genauigkeit" (S. 200) und übertraf mehrere andere Methoden, einschließlich neuronaler Netze allein. Korrelationen für den Ein-Tage-Fall lagen zwischen 92 und 99%, und obwohl die Genauigkeit über zunehmend größere Zeitverzögerungen abnahm, blieb das GA „sehr erfolgreich" (S. 206) und übertraf eindeutig die anderen Methoden. Die Autoren schließen, dass „bemerkenswerter Prädiktionserfolg sowohl in einem Schritt im Voraus als auch in einem mehrstufigen Prädiktionshorizont erzielt wurde" (S. 208) – tatsächlich stellen sie fest, dass ihre Ergebnisse bei weitem besser sind als jede verwandte Prädiktionsstrategie, die auf dieser Datenreihe oder anderen Währungen versucht wurde.

    Die Verwendung von GAs auf den Finanzmärkten hat begonnen, sich in reale Brokerhäuser auszubreiten. Naik 1996 berichtet, dass LBS Capital Management, ein amerikanisches Unternehmen mit Sitz in Florida, genetische Algorithmen verwendet, um Aktien für einen von ihm verwalteten Pensionsfonds auszuwählen. Coale 1997 und Begley und Beals 1995 berichten, dass First Quadrant, ein Investmentunternehmen in Kalifornien, das über 2,2 Milliarden Dollar verwaltet, GAs verwendet, um Investitionsentscheidungen für alle ihre Finanzdienstleistungen zu treffen. Ihr entwickeltes Modell erwirtschaftet im Durchschnitt 255 Dollar für jeden investierten 100 Dollar über sechs Jahre, gegenüber 205 Dollar für andere Arten von Modellierungssystemen.

  • Spiele
    One of the most novel and compelling demonstrations of the power of genetic algorithms was presented by Chellapilla und Fogel 2001, who used a GA to evolve neural networks that could play the game of checkers. The authors state that one of the major difficulties in these sorts of strategy-related problems is the Kreditverteilungsproblem - in other words, how does one write a fitness function? It has been widely believed that the mere criterion of win, lose or draw does not provide sufficient information for an evolutionary algorithm to figure out what constitutes good play.

    In this paper, Chellapilla and Fogel overturn that assumption. Given only the spatial positions of pieces on the checkerboard and the total number of pieces possessed by each side, they were able to evolve a checkers program that plays at a level competitive with human experts, without any intelligent input as to what constitutes good play - indeed, the individuals in the evolutionary algorithm were not even told what the criteria for a win were, nor were they told the result of any one game.

    In Chellapilla and Fogel's representation, the game state was represented by a numeric list of 32 elements, with each position in the list corresponding to an available position on the board. The value at each position was either 0 for an unoccupied square, -1 if that square was occupied by an enemy checker, +1 if that square was occupied by one of the program's checkers, and -K or +K for a square occupied by an enemy or friendly king. (The value of K was not pre-specified, but again was determined by evolution over the course of the algorithm.) Accompanying this was a neural network with multiple processing layers and one input layer with a node for each of the possible 4x4, 5x5, 6x6, 7x7 and 8x8 squares on the board. The output of the neural net for any given arrangement of pieces was a value from -1 to +1 indicating how good it felt that position was for it. For each move, the neural network was presented with a game tree listing all possible moves up to four turns into the future, and a move decision was made based on which branch of the tree produced the best results for it.

    The evolutionary algorithm began with a population of 15 neural networks with randomly generated weights and biases assigned to each node and link; each individual then reproduced once, generating an offspring with variations in the values of the network. These 30 individuals then competed for survival by playing against each other, with each individual competing against 5 randomly chosen opponents per turn. 1 point was awarded for each win and 2 points were deducted for each loss. The 15 best performers, based on total score, were selected to produce offspring for the next generation, and the process repeated. Evolution was continued for 840 generations (approximately six months of computer time).

    Klasse Rating
    Senior Master 2400+
    Master 2200-2399
    Expert 2000-2199
    Klasse A 1800-1999
    Klasse B 1600-1799
    Klasse C 1400-1599
    Klasse J < 200
    		Das einzelne beste Individuum, das aus dieser Selektion hervorging, wurde als Teilnehmer auf der Gaming-Website www.zone.com registriert. Über einen Zeitraum von zwei Monaten spielte es gegen 165 menschliche Gegner, die ein Spektrum hoher Fähigkeitsstufen von Klasse C bis Master umfassten, gemäß dem Ranking-System des United States Chess Federation (dargestellt links, einige Ränge zur Klarheit weggelassen). Von diesen Spielen gewann das neuronale Netz 94, verlor 39 und remisierte 32; basierend auf den Rankings der Gegner in diesen Spielen war das evolvierte neuronale Netz einem Spieler mit einem mittleren Rating von 2045,85 gleichzusetzen, was es auf das Expertenniveau platzierte – ein höheres Ranking als 99,61 % von über 80.000 Spielern, die auf der Website registriert waren. Eines der bedeutendsten Siege des neuronalen Netzes war, als es einen Spieler besiegte, der an 98. Stelle aller registrierten Spieler rangierte, dessen Rating nur 27 Punkte unter dem Master-Niveau lag.


    Tests conducted with a simple piece-differential program (which bases moves solely on the difference between the number of checkers remaining to each side) with an eight-move look-ahead showed the neural net to be significantly superior, with a rating over 400 points higher. "A program that relies only on the piece count and an eight-ply search will defeat a lot of people, but it is not an expert. The best evolved neural network is" (p.425). Even when it was searching positions two further moves ahead than the neural net, the piece-differential program lost decisively in eight out of ten games. This conclusively demonstrates that the evolved neural net is not merely counting pieces, but is somehow processing spatial characteristics of the board to decide its moves. The authors point out that opponents on zone.com often commented that the neural net's moves were "strange", but its overall level of play was described as "very tough" or with similar complimentary terms.

    To further test the evolved neural network (which the authors named "Anaconda" since it often won by restricting its opponents' mobility), it was played against a commercial checkers program, Hoyle's Classic Games, distributed by Sierra Online (Chellapilla und Fogel 2000). This program comes with a variety of built-in characters, each of whom plays at a different skill level. Anaconda was tested against three characters ("Beatrice", "Natasha" and "Leopold") designated as expert-level players, playing one game as red and one game as white against each of them with a six-ply look-ahead. Though the authors doubted that this depth of look-ahead would give Anaconda the ability to play at the expert skill level it had previously shown, it won six straight victories out of all six games played. Based on this outcome, the authors expressed skepticism over whether the Hoyle software played at the skill level advertised, though it should be noted that they reached this conclusion based nur on the ease with which Anaconda defeated it!

    The ultimate test of Anaconda was given in Chellapilla und Fogel 2002, where the evolved neural net was matched against the best checkers player in the world: Chinook, a program designed principally by Dr. Jonathan Schaeffer of the University of Alberta. Rated at 2814 in 1996 (with its closest human competitors rated in the 2600s), Chinook incorporates a book of opening moves provided by human grandmasters, a sophisticated set of middle-game algorithms, and a complete database of all possible moves with ten pieces on the board or less, so it never makes a mistake in the endgame. An enormous amount of human intelligence and expertise went into the design of this program.

    Chellapilla and Fogel pitted Anaconda against Chinook in a 10-game tournament, with Chinook playing at a 5-ply skill level, making it roughly approximate to master level. Chinook won this contest, four wins to two with four draws. (Interestingly, the authors note, in two of the games that ended as draws, Anaconda held the lead with four kings to Chinook's three. Furthermore, one of Chinook's wins came from a 10-ply series of movies drawn from its endgame database, which Anaconda with an 8-ply look-ahead could not have anticipated. If Anaconda had had access to an endgame database of the same quality as Chinook's, the outcome of the tournament might well have been a victory for Anaconda, four wins to three.) These results "provide good support for the expert-level rating that Anaconda earned on www.zone.com" (p.76), with an overall rating of 2030-2055, comparable to the 2045 rating it earned by playing against humans. While Anaconda is not an invulnerable player, it is able to play competitively at the expert level and hold its own against a variety of extremely skilled human checkers players. When one considers the very simple fitness criterion under which these results were obtained, the emergence of Anaconda provides dramatic corroboration of the power of evolution.

  • Geophysik
    Sambridge und Gallagher 1993 verwendeten ein genetisches Algorithmus, um Erdbebenhypozentren basierend auf seismologischen Daten zu lokalisieren. (Das Hypozentrum ist der Punkt unter der Erdoberfläche, an dem ein Erdbeben beginnt. Das Epizentrum ist der Punkt auf der Oberfläche direkt über dem Hypozentrum.) Dies ist eine außerordentlich komplexe Aufgabe, da die Eigenschaften seismischer Wellen von den Eigenschaften der Gesteinsschichten abhängen, durch die sie sich ausbreiten. Die traditionelle Methode zur Lokalisierung des Hypozentrums stützt sich auf das, was als seismisches Inversionsalgorithmus bekannt ist, der mit einer ersten Schätzung des Standorts beginnt, die Ableitungen der Wellenausbreitungszeit in Bezug auf die Quellposition berechnet und eine Matrixoperation durchführt, um einen aktualisierten Standort bereitzustellen. Dieser Prozess wird wiederholt, bis eine akzeptable Lösung erreicht ist. (Dieser Beitrag des Monats aus November 2003 bietet weitere Informationen.) Allerdings erfordert diese Methode Ableitungsdaten und ist anfällig dafür, in lokalen Optima stecken zu bleiben.

    Ein Lokalisierungsalgorithmus, der nicht von Ableitungsdaten oder Geschwindigkeitsmodellen abhängt, kann diese Mängel vermeiden, indem er nur das Vorwärtsproblem berechnet - die Differenz zwischen beobachteten und vorhergesagten Wellenanflugzeiten für verschiedene Hypozentrumslagen. Allerdings wäre eine erschöpfende Suche auf Basis dieser Methode weit zu rechenintensiv. Dies ist natürlich genau die Art von Optimierungsproblem, bei der genetische Algorithmen hervorragend abschneiden. Wie alle GAs ist der von der zitierten Arbeit vorgeschlagene Algorithmus parallel aufgebaut - anstatt einzeln ein Hypozentrum schrittweise zu stören und der Lösung näher zu bringen, beginnt er mit einer Wolke potenzieller Hypozentren, die sich im Laufe der Zeit verkleinert, um auf eine einzelne Lösung zu konvergieren. Die Autoren stellen fest, dass ihr Ansatz "nahezu optimale Lösungen schnell lokalisieren kann, ohne eine erschöpfende Suche im Parameterraum" (S. 1467), ein "hochorganisiertes Verhalten mit effizienter Suche" aufweist und "ein Kompromiss zwischen der Effizienz ableitungsbasierter Methoden und der Robustheit einer vollständig nichtlinearen erschöpfenden Suche" darstellt (S. 1469). Die Autoren schließen, dass ihr genetischer Algorithmus "effizient für wahrhaft globale Optimierung" ist (S. 1488) und "ein leistungsstarkes neues Werkzeug zur Durchführung robuster Hypozentrumslokalisierung" (S. 1489).

  • Materialtechnik
    Giro, Cyrillo und Galvão 2002 verwendeten genetische Algorithmen, um elektrisch leitfähige, auf Kohlenstoff basierende Polymere, sogenannte Polyaniline, zu entwerfen. Diese Polymere, eine kürzlich erfundene Klasse von synthetischen Materialien, haben „großes technologisches Anwendungspotenzial" und könnten Fenster zu „neuen grundlegenden physikalischen Phänomenen" öffnen (S. 170). Aufgrund ihrer hohen Reaktivität können Kohlenstoffatome jedoch eine nahezu unendliche Anzahl von Strukturen bilden, was eine systematische Suche nach neuen Molekülen mit interessanten Eigenschaften fast unmöglich macht. In dieser Arbeit wenden die Autoren einen auf genetischen Algorithmen (GA) basierenden Ansatz auf die Aufgabe an, neue Moleküle mit vorab festgelegten Eigenschaften zu entwerfen, beginnend mit einer zufällig generierten Population von Anfangskandidaten. Sie schließen daraus, dass ihre Methodik ein „sehr effektives Werkzeug" (S. 174) sein kann, um Experimentalisten bei der Suche nach neuen Verbindungen zu führen, und dass sie allgemein genug ist, um auf das Design neuartiger Materialien angewendet zu werden, die zu fast jeder Klasse von Molekülen gehören.

    Weismann, Hammel und Bäck 1998 wandten evolutionäre Algorithmen auf ein „nichttriviales" (S. 162) industrielles Problem an: das Design von mehrschichtigen optischen Beschichtungen, die für Filter verwendet werden, um Licht bestimmter Frequenzen zu reflektieren, zu übertragen oder zu absorbieren. Diese Beschichtungen werden beispielsweise bei der Herstellung von Sonnenbrillen oder Compact Discs eingesetzt. Ihre Herstellung ist eine präzise Aufgabe: Die Schichten müssen in einer bestimmten Reihenfolge und mit bestimmten Dicken aufgetragen werden, um das gewünschte Ergebnis zu erzielen, und unkontrollierbare Umgebungsvariationen im Herstellungsprozess wie Temperatur, Verschmutzung und Luftfeuchtigkeit können die Leistung des fertigen Produkts beeinträchtigen. Viele lokale Optima sind nicht robust gegenüber solchen Variationen, was bedeutet, dass die maximale Produktqualität mit höheren Raten unerwünschter Abweichungen erkauft werden muss. Das in dieser Arbeit betrachtete spezielle Problem hatte zudem mehrere Kriterien: Neben der Reflexion wurde auch die spektrale Zusammensetzung (Farbe) des reflektierten Lichts berücksichtigt.

    Der EA (evolutionärer Algorithmus) funktionierte durch Variation der Anzahl der Beschichtungsschichten und der Dicke jeder einzelnen Schicht und erzeugte Designs, die „wesentlich robuster gegenüber Parametervariationen" (S. 166) waren und eine höhere durchschnittliche Leistung aufwiesen als traditionelle Methoden. Die Autoren schließen daraus, dass „evolutionäre Algorithmen mit traditionellen Methoden des Designs mehrschichtiger optischer Beschichtungen konkurrieren oder diese sogar übertreffen können" (S. 167), ohne dass domänenspezifisches Wissen in die Suchfunktion integriert werden muss und ohne die Population mit guten Anfangsdesigns zu besamen.

    Eine weitere Anwendung von GAs im Bereich der Materialtechnik verdient Erwähnung: Robin et al. 2003 verwendeten GAs, um Belichtungsmuster für einen Elektronenstrahl der Elektronenlithografie zu entwerfen, der verwendet wird, um Strukturen im Submikrometerbereich auf integrierte Schaltkreise zu ätzen. Das Entwerfen dieser Muster ist eine hochkomplexe Aufgabe; es ist umständlich und verschwenderisch, sie experimentell zu bestimmen, aber die hohe Dimensionalität des Suchraums besiegt die meisten Suchalgorithmen. Bis zu 100 Parameter müssen gleichzeitig optimiert werden, um den Elektronenstrahl zu steuern und Streuung sowie Proximity-Effekte zu verhindern, die sonst die fein strukturierten Formen ruinieren würden, die geformt werden. Das Vorwärtsproblem – die Bestimmung der resultierenden Struktur als Funktion der Elektronendosis – ist einfach und lässt sich leicht simulieren, aber das inverse Problem, die Elektronendosis zu bestimmen, um eine gegebene Struktur zu erzeugen, was hier gelöst wird, ist weitaus schwieriger und es existiert keine deterministische Lösung.

    Genetische Algorithmen, die „bekanntlich in der Lage sind, gute Lösungen für sehr komplexe Probleme hoher Dimensionalität zu finden" (S. 75), ohne dass domänenspezifische Informationen über die Topologie des Suchlandschafts bereitgestellt werden müssen, wurden erfolgreich auf dieses Problem angewendet. Die Autoren des Papiers verwendeten einen stationären GA mit Roulette-Rad-Auswahl in einer Computersimulation, was „sehr gut optimierte" (S. 77) Belichtungsmuster ergab. Im Gegensatz dazu wurde eine Art von Hügelsteiger, bekannt als Simplex-Abwärtsalgorithmus, auf dasselbe Problem angewendet, ohne Erfolg; die SD-Methode geriet schnell in lokale Optima, aus denen sie nicht entkommen konnte, und lieferte Lösungen schlechter Qualität. Auch ein hybrider Ansatz der GA- und SD-Methoden konnte die Ergebnisse, die allein vom GA geliefert wurden, nicht verbessern.

  • Mathematik und Algorithmik
    Obwohl einige der vielversprechendsten Anwendungen und überzeugendsten Demonstrationen der Kraft von GAs (Genetischen Algorithmen) im Bereich des Ingenieurdesigns liegen, sind sie auch für "reine" mathematische Probleme relevant. Haupt und Haupt 1998 (S. 140) diskutieren die Verwendung von GAs zur Lösung höhergradiger nichtlinearer partieller Differentialgleichungen, typischerweise durch das Finden der Werte, für die die Gleichungen gleich null sind, und geben als Beispiel eine nahezu perfekte GA-Lösung für die Koeffizienten der fünften Ordnung der Super Korteweg-de Vries-Gleichung.

    Das Sortieren einer Liste von Elementen in die richtige Reihenfolge ist eine wichtige Aufgabe in der Informatik, und ein Sorting Network (Sortiernetzwerk) ist eine effiziente Methode, dies zu erreichen. Ein Sortiernetzwerk ist eine feste Liste von Vergleichen, die an einem Satz von Elementen einer gegebenen Größe durchgeführt werden; bei jedem Vergleich werden zwei Elemente verglichen und ausgetauscht, wenn sie nicht in der richtigen Reihenfolge stehen. Koza et al. 1999, S. 952, verwendeten genetische Programmierung, um minimale Sortiernetzwerke für 7-Elemente-Sätze (16 Vergleiche), 8-Elemente-Sätze (19 Vergleiche) und 9-Elemente-Sätze (25 Vergleiche) zu entwickeln. Mitchell 1996, S. 21, diskutiert die Verwendung von genetischen Algorithmen durch W. Daniel Hillis, um ein Sortiernetzwerk mit 61 Vergleichen für einen 16-Elemente-Satz zu finden, nur einen Schritt mehr als das kleinste bekannte. Dieses letztere Beispiel ist aus zwei Innovationen, die es verwendete, besonders interessant: diploide Chromosomen und vor allem die Wirt-Parasit-Koevolution. Sowohl die Sortiernetzwerke als auch die Testfälle entwickelten sich gegenseitig weiter; Sortiernetzwerke bekamen eine höhere Fitness basierend darauf, wie viele Testfälle sie korrekt sortierten, während Testfälle eine höhere Fitness bekamen, basierend darauf, wie viele Sortiernetzwerke sie dazu bringen konnten, falsch zu sortieren. Die GA mit Koevolution performte signifikant besser als die gleiche GA ohne sie.

    Ein letzter, bemerkenswerter Beleg für GAs im Bereich der Algorithmik findet sich in Koza et al. 1999, die genetische Programmierung verwendeten, um eine Regel für das Mehrheitsklassifizierungsproblem in eindimensionalen Zellularautomaten zu entdecken, die besser ist als alle bekannten von Menschen geschriebenen Regeln. Ein eindimensionaler Zellularautomat kann als ein endliches Band mit einer gegebenen Anzahl von Positionen (Zellen) darauf betrachtet werden, wobei jede Zelle entweder den Zustand 0 oder den Zustand 1 halten kann. Der Automat läuft für eine gegebene Anzahl von Zeitschritten; in jedem Schritt erhält jede Zelle einen neuen Wert basierend auf ihrem vorherigen Wert und dem Wert ihrer nächsten Nachbarn. (Das Game of Life ist ein zweidimensionaler Zellularautomat.) Das Mehrheitsklassifizierungsproblem besteht darin, eine Tabelle von Regeln zu finden, sodass, wenn mehr als die Hälfte der Zellen auf dem Band anfänglich 1 sind, alle Zellen den Wert 1 annehmen; sonst nehmen alle Zellen den Wert 0 an. Die Herausforderung liegt darin, dass jede einzelne Zelle nur Informationen über ihre nächsten Nachbarn zugreifen kann; daher müssen gute Regelsets auf irgendeine Weise einen Weg finden, Informationen über entfernte Regionen des Bands zu übertragen.

    Es ist bekannt, dass eine perfekte Lösung für dieses Problem nicht existiert - kein Regelset kann alle möglichen Anfangskonfigurationen genau klassifizieren - aber in den letzten zwanzig Jahren gab es eine lange Abfolge immer besserer Lösungen. Im Jahr 1978 entwickelten drei Forscher die sogenannte GKL-Regel, die 81,6% der möglichen Anfangszustände korrekt klassifiziert. Im Jahr 1993 wurde eine bessere Regel mit einer Genauigkeit von 81,8% entdeckt; im Jahr 1995 wurde eine weitere Regel mit einer Genauigkeit von 82,178% gefunden. Alle diese Regeln erforderten erhebliche Arbeit durch intelligente, kreative Menschen, um entwickelt zu werden. Im Gegensatz dazu hat die beste Regel, die von einer Laufzeit genetischer Programmierung entdeckt wurde, wie in Koza et al. 1999, S. 973 angegeben, eine Gesamtgenauigkeit von 82,326% - besser als jede der von Menschen geschaffenen Lösungen, die in den letzten zwei Jahrzehnten entwickelt wurden. Die Autoren bemerken, dass ihre neuen Regeln qualitativ unterschiedlich von zuvor veröffentlichten Regeln sind und feingranulare interne Darstellungen der Zustandsdichte sowie komplexe Sätze von Signalen zur Kommunikation von Informationen über große Distanzen verwenden.

  • Militär und Strafverfolgung
    Kewley und Embrechts 2002 verwendeten genetische Algorithmen, um taktische Pläne für militärische Schlachten zu entwickeln. Die Autoren bemerken, dass "[d]as Planen einer taktischen militärischen Schlacht eine komplexe, hochdimensionale Aufgabe ist, die erfahrene Fachkräfte oft in Schwierigkeiten bringt" (S. 163), nicht nur, weil solche Entscheidungen meist unter hohem Stress getroffen werden, sondern auch, weil selbst einfache Pläne eine große Anzahl widersprüchlicher Variablen und Ergebnisse berücksichtigen müssen: Minimierung der eigenen Verluste, Maximierung der Feindverluste, Kontrolle des gewünschten Geländes, Ressourcenschonung und so weiter. Menschliche Planer haben Schwierigkeiten, mit den Komplexitäten dieser Aufgabe umzugehen und müssen oft auf "schnelle und schmutzige" Ansätze zurückgreifen, wie zum Beispiel das Tun dessen, was das letzte Mal funktioniert hat.

    Um diese Schwierigkeiten zu überwinden, entwickelten die Autoren des zitierten Papiers einen genetischen Algorithmus, um die Erstellung von Schlachtplänen zu automatisieren, in Verbindung mit einem grafischen Schlachtsimulatorprogramm. Der Kommandeur gibt das bevorzugte Ergebnis ein, und der GA entwickelt automatisch einen Schlachtplan; im verwendeten Simulator wurden Faktoren wie die Topografie des Landes, die Vegetationsbedeckung, die Bewegungsgeschwindigkeit der Truppen und die Schussgenauigkeit berücksichtigt. In diesem Experiment wurde auch die Ko-Evolution verwendet, um die Qualität der Lösungen zu verbessern: Schlachtpläne für die feindlichen Kräfte entwickelten sich gleichzeitig mit den eigenen Plänen, was den GA zwang, alle Schwächen in seinem eigenen Plan zu korrigieren, die ein Gegner ausnutzen könnte. Um die Qualität der vom GA erzeugten Lösungen zu messen, wurden diese mit Schlachtplänen für denselben Szenario verglichen, die von einer Gruppe von "erfahrenen Militärfachleuten... die als sehr fähig zur Entwicklung taktischer Handlungsoptionen für die in diesem Experiment eingesetzten Kräfte gelten" (S. 166) erstellt wurden. Diese erfahrenen Experten erstellten sowohl ihren eigenen Plan als auch, wenn die Lösung des GA abgeschlossen war, die Möglichkeit, diese zu prüfen und nach eigenem Ermessen zu modifizieren. Schließlich wurden alle Plan-Sets mehrmals im Simulator ausgeführt, um ihre durchschnittliche Qualität zu bestimmen.

    Die Ergebnisse sprechen für sich selbst: Die evolvierte Lösung übertraf sowohl den eigenen Plan der Militärfachleute als auch den Plan, der durch deren Modifikationen der Lösung des GA erzeugt wurde. "...[D]ie Pläne, die von automatisierten Algorithmen erzeugt wurden, hatten eine signifikant höhere mittlere Leistungsfähigkeit als diejenigen, die von erfahrenen Militärfachleuten generiert wurden" (S. 161). Darüber hinaus bemerken die Autoren, dass der Plan des GA guten taktischen Sinn machte. (Er beinhaltete einen zweigleisigen Angriff auf die feindliche Position durch mechanisierte Infanterie-Plazons, unterstützt durch Angriffshelikopter und Bodenscouts, in Verbindung mit unbemannten Luftfahrzeugen, die Aufklärungsarbeiten durchführten, um Artilleriefeuer zu steuern.) Zusätzlich beinhaltete der evolvierte Plan einzelne eigene Einheiten, die doktrinäre Missionen ausführten – eine emergente Eigenschaft, die sich im Verlauf des Laufs entwickelte, anstatt vom Experimentator spezifiziert zu werden. In zunehmend vernetzten modernen Schlachtfeldern sollte das attraktive Potenzial eines evolutionären Algorithmus, der die Produktion hochwertiger taktischer Pläne automatisieren kann, offensichtlich sein.

    Eine interessante Anwendung von GAs in der Strafverfolgung wurde in Naik 1996 berichtet, die die Software "FacePrints" beschrieb, ein Projekt, um Zeugen bei der Identifizierung und Beschreibung von Straftätern zu helfen. Das klischeehafte Bild des Polizeiskizzenzeichners, der auf die Hinweise der Zeugen hin ein Bild des Gesichts des Verdächtigen zeichnet, ist eine schwierige und ineffiziente Methode: Die meisten Menschen sind nicht gut darin, einzelne Aspekte eines Gesichts zu beschreiben, wie zum Beispiel die Größe der Nase oder die Form des Kiefers, sind aber besser darin, ganze Gesichter zu erkennen. FacePrints nutzt dies aus, indem es einen genetischen Algorithmus verwendet, der Bilder von Gesichtern auf der Basis von Datenbanken mit Hunderten von individuellen Merkmalen entwickelt, die auf unzählige Arten kombiniert werden können. Das Programm zeigt Zeugen zufällig generierte Gesichter an, die diejenigen auswählen, die der Person am meisten ähneln, die sie gesehen haben; die ausgewählten Gesichter werden dann mutiert und gekreuzt, um neue Merkmal-Kombinationen zu erzeugen, und der Prozess wiederholt sich, bis ein genaues Porträt des Gesichts des Verdächtigen entsteht. In einem realen Raubfall waren die finalen Porträts, die von den drei Zeugen erstellt wurden, auffällig ähnlich, und das resultierende Bild wurde in der lokalen Zeitung abgedruckt.

  • Molekularbiologie
    Bei lebenden Organismen sind transmembranäre Proteine Proteine, die durch eine Zellmembran hindurchragen. Transmembranäre Proteine erfüllen oft wichtige Funktionen, wie das Erkennen des Vorhandenseins bestimmter Substanzen außerhalb der Zelle oder deren Transport in die Zelle. Das Verständnis des Verhaltens eines transmembranären Proteins erfordert die Identifizierung des Abschnitts dieses Proteins, der tatsächlich in der Membran eingebettet ist, was als transmembranäres Domäne bezeichnet wird. In den letzten zwei Jahrzehnten haben Molekularbiologen eine Reihe von zunehmend genaueren Algorithmen für diesen Zweck veröffentlicht.

    Alle von lebenden Organismen verwendeten Proteine bestehen aus denselben 20 Aminosäuren. Einige dieser Aminosäuren sind hydrophob, was bedeutet, dass sie von Wasser abgestoßen werden, und einige sind hydrophil, was bedeutet, dass sie von Wasser angezogen werden. Aminosäuresequenzen, die Teil einer transmembranären Domäne sind, sind eher hydrophob. Allerdings ist Hydrophobie kein präzise definiertes Merkmal, und es gibt keine allgemein akzeptierte Skala zur Messung derselben.

    Koza et al. 1999, Kapitel 16, verwendete genetische Programmierung, um einen Algorithmus zu entwerfen, der transmembranäre Domänen eines Proteins identifiziert. Der genetischen Programmierung wurde eine Reihe von Standardmathematischen Operatoren zur Verfügung gestellt, mit denen gearbeitet werden konnte, sowie eine Reihe von booleschen Aminosäure-erkennenden Funktionen, die +1 zurückgeben, wenn die Aminosäure an einer gegebenen Position die Aminosäure ist, die sie erkennen, und sonst -1. (Zum Beispiel nimmt die A?-Funktion als Argument eine Zahl entgegen, die einer Position innerhalb des Proteins entspricht, und gibt +1 zurück, wenn die Aminosäure an dieser Position Alanin ist, was durch den Buchstaben A bezeichnet wird; sonst gibt sie -1 zurück). Eine einzelne gemeinsam genutzte Speichervariable hielt eine laufende Summe der Gesamtschätzung, und wenn der Algorithmus abgeschlossen war, wurde der Proteinabschnitt als transmembranäre Domäne identifiziert, wenn sein Wert positiv war. Gaben nur diese Werkzeuge, würde es für einen menschlichen Gestalter die Schaffung neuer Informationen bedeuten, um eine effiziente Lösung für dieses Problem herzustellen?

    Die von der genetischen Programmierung erzeugten Lösungen wurden auf ihre Fitness bewertet, indem sie an 246 Proteinabschnitten getestet wurden, deren transmembranärer Status bekannt war. Das beste Individuum der Laufzeit wurde dann an 250 zusätzlichen, aus der Stichprobe stammenden, Testfällen evaluiert und mit der Leistung der vier besten bekannten von Menschen geschriebenen Algorithmen für denselben Zweck verglichen. Das Ergebnis: Die genetische Programmierung erzeugte einen Algorithmus zur Identifizierung von transmembranären Abschnitten mit einer Gesamtfehlerquote von 1,6% - deutlich niedriger als alle vier von Menschen geschriebenen Algorithmen, von denen der beste eine Fehlerquote von 2,5% hatte. Der genetisch entworfene Algorithmus, den die Autoren die 0-2-4-Regel nannten, funktioniert wie folgt:

    • Erhöhen Sie die laufende Summe um 4 für jedes Vorkommen von Glutaminsäure (eine elektrisch geladene und stark hydrophile) Aminosäure im Proteinabschnitt.
    • Erhöhen Sie die laufende Summe um 0 für jedes Vorkommen von Alanin, Phenylalanin, Isoleucin, Leucin, Methionin oder Valin (alle stark hydrophoben Aminosäuren) im Proteinabschnitt.
    • Erhöhen Sie die laufende Summe um 2 für jedes Vorkommen aller anderen Aminosäuren.
    • Wenn [(SUM - 3.1544)/0.9357] kleiner als die Länge des Proteinabschnitts ist, klassifizieren Sie diesen Abschnitt als transmembranäre Domäne; andernfalls klassifizieren Sie ihn als nicht-transmembranäre Domäne.

  • Mustererkennung und Datenmining
    Competition in the telecommunications industry today is fierce, and a new term - "churn" - has been coined to describe the rapid rate at which subscribers switch from one service provider to another. Churn costs telecom carriers a large amount of money each year, and reducing churn is an important factor in increasing profitability. If carriers can contact customers who are likely to switch and offer them special incentives to stay, churn rates can be reduced; but no carrier has the resources to contact more than a small percent of its customers. The problem is therefore how to identify customers who are more likely to churn. All carriers have extensive databases of customer information that can theoretically be used for this purpose; but what method works best for sifting through this vast amount of data to identify the subtle patterns and trends that signify a customer's likelihood of churning?

    Au, Chan und Yao 2003 applied genetic algorithms to this problem to generate a set of if-then rules that predict the churning probability of different groups of customers. In their GA, the first generation of rules, all of which had one condition, was generated using a probabilistic induction technique. Subsequent generations then refine these, combining simple, single-condition rules into more complex, multi-condition rules. The fitness measure used an objective "interestingness" measure of correlation which requires no subjective input. The evolutionary data-mining algorithm was tested on a real-world database of 100,000 subscribers provided by a Malaysian carrier, and its performance was compared against two alternative methods: a multilayer neural network and a widely used decision-tree-based algorithm, C4.5. The authors state that their EA was able to discover hidden regularities in the database and was "able to make accurate churn prediction under different churn rates" (p.542), outperforming C4.5 under all circumstances, outperforming the neural network under low monthly churn rates and matching the neural network under larger churn rates, and reaching conclusions more quickly in both cases. Some further advantages of the evolutionary approach are that it can operate efficiently even when some data fields are missing and that it can express its findings in easily understood rule sets, unlike the neural net.

    Among some of the more interesting rules discovered by the EA are as follows: subscribers are more likely to churn if they are personally subscribed to the service plan and have not been admitted to any bonus scheme (a potential solution is to admit all such subscribers to bonus schemes); subscribers are more likely to churn if they live in Kuala Lumpur, are between 36 and 44 in age, and pay their bills with cash (presumably because it is easier for subscribers who pay cash, rather than those whose accounts are automatically debited, to switch providers); and subscribers living in Penang who signed up through a certain dealer are more likely to churn (this dealer may be providing poor customer service and should be investigated).

    Rizki, Zmuda und Tamburino 2002 used evolutionary algorithms to evolve a complex pattern recognition system with a wide variety of potential uses. The authors note that the task of pattern recognition is increasingly being performed by machine learning algorithms, evolutionary algorithms in particular. Most such approaches begin with a pool of predefined features, from which an EA can select appropriate combinations for the task at hand; by contrast, this approach began from the ground up, first evolving individual feature detectors in the form of expression trees, then evolving cooperative combinations of those detectors to produce a complete pattern recognition system. The evolutionary process automatically selects the number of feature detectors, the complexity of the detectors, and the specific aspects of the data each detector responds to.

    To test their system, the authors gave it the task of classifying aircraft based on their radar reflections. The same kind of aircraft can return quite different signals depending on the angle and elevation at which it is viewed, and different kinds of aircraft can return very similar signals, so this is a non-trivial task. The evolved pattern recognition system correctly classified 97.2% of the targets, a higher net percentage than any of the three other techniques - a perceptron neural network, a nearest-neighbor classifier algorithm, and a radial basis algorithm - against which it was tested. (The radial basis network's accuracy was only 0.5% less than the evolved classifier, which is not a statistically significant difference, but the radial basis network required 256 feature detectors while the evolved recognition system used only 17.) As the authors state, "The recognition systems that evolve use fewer features than systems formed using conventional techniques, yet achieve comparable or superior recognition accuracy" (p.607). Various aspects of their system have also been applied to problems including optical character recognition, industrial inspection and medical image analysis.

    Hughes und Leyland 2000 also applied multiple-objective GAs to the task of classifying targets based on their radar reflections. High-resolution radar cross section data requires massive amounts of disk storage space, and it is very computationally intensive to produce an actual model of the source from the data. By contrast, the authors' GA-based approach proved very successful, producing a model as good as the traditional iterative approach while reducing the computational overhead and storage requirements to the point where it was feasible to generate good models on a desktop computer. By contrast, the traditional iterative approach requires ten times the resolution and 560,000 times as many accesses of image data to produce models of similar quality. The authors conclude that their results "clearly demonstrate" (p.160) the ability of the GA to process both two- and three-dimensional radar data of any level of resolution with far fewer calculations than traditional methods, while retaining acceptably high accuracy.

  • Robotik
    Das internationale RoboCup-Turnier ist ein Projekt zur Förderung von Fortschritten in der Robotik, der künstlichen Intelligenz und verwandten Bereichen, indem es ein Standardproblem bereitstellt, an dem neue Technologien erprobt werden können – speziell handelt es sich um ein jährliches Fußballturnier zwischen Teams autonomer Roboter. (Das erklärte Ziel ist es, bis 2050 ein Team humanoider Roboter zu entwickeln, das gegen die weltmeisterliche menschliche Fußballmannschaft gewinnen kann; zur gegenwärtigen Zeit sind die meisten teilnehmenden Roboterteams radgetrieben.) Die Programme, die die Mitglieder des Roboterteams steuern, müssen komplexes Verhalten zeigen, indem sie entscheiden, wann sie blockieren, wann sie schießen, wie sie sich bewegen, wann sie den Ball an Mitspieler passen, wie sie Abwehr und Angriff koordinieren und so weiter. In der Simulationsliga des Wettbewerbs 1997 stellten David Andre und Astro Teller ein Team namens Darwin United vor, dessen Steuerungsprogramme automatisch von Grund auf durch genetische Programmierung entwickelt wurden – eine Herausforderung für die konventionelle Weisheit, dass „dieses Problem für eine solche Technik einfach zu schwierig ist" (Andre und Teller 1999, S. 346).

    Um dieses schwierige Problem zu lösen, stellten Andre und Teller dem Algorithmus der genetischen Programmierung eine Reihe von primitiven Steuerfunktionen zur Verfügung, wie Drehen, Bewegen, Schießen und so weiter. (Diese Funktionen waren selbst während des Verlaufs der Evolution Veränderungen und Verfeinerungen unterworfen.) Ihre Fitnessfunktion, die geschrieben wurde, um gutes Spiel im Allgemeinen zu belohnen, anstatt spezifisch Tore zu erzielen, lieferte eine Liste von zunehmend wichtigen Zielen: dem Ball nahe zu kommen, den Ball zu schießen, den Ball auf der gegnerischen Seite des Feldes zu halten, in die richtige Richtung zu bewegen, Tore zu erzielen und das Spiel zu gewinnen. Es ist zu beachten, dass kein Code bereitgestellt wurde, um das Team spezifisch zu lehren, wie es diese komplexen Ziele zu erreichen hat. Die entwickelten Programme wurden dann mit einem hierarchischen Selektionsmodell bewertet: Zuerst wurden die Kandidatenteams auf einem leeren Feld getestet und verworfen, wenn sie innerhalb von 30 Sekunden kein Tor erzielten. Als Nächstes wurden sie gegen ein Team aus stationären „Schießpfosten" bewertet, die den Ball auf die gegenüberliegende Seite des Feldes schießen. Drittens spielte das Team ein Spiel gegen das siegreiche Team des RoboCup 1997. Schließlich wurden Teams, die gegen dieses Team mindestens ein Tor erzielten, gegeneinander ausgespielt, um festzustellen, welches das beste war.

    Von den 34 Teams in seiner Division kam Darwin United schließlich auf Platz 17, was genau in der Mitte des Feldes lag und die Hälfte der von Menschen geschriebenen Einträge übertraf. Während ein Turniersieg zweifellos beeindruckender gewesen wäre, ist dieses Ergebnis an sich wettbewerbsfähig und signifikant und erscheint noch mehr so im Lichte der Geschichte. Vor etwa 25 Jahren befanden sich Schachspiel-Computerprogramme in ihren Kindertagen; ein Computer war erst kürzlich zum ersten Mal sogar in einer regionalen Konkurrenz eingetreten, obwohl er nicht gewann (Sagan 1979, S. 286). Aber „[e]ine Maschine, die Schach im mittleren Bereich menschlicher Expertise spielt, ist eine sehr leistungsfähige Maschine" (ebenda), und es könnte gesagt werden, dass dasselbe für Roboterfußball gilt. Genau wie Schachspiel-Maschinen heute auf Weltmeister-Niveau konkurrieren, welche Arten von Systemen wird genetische Programmierung in 20 oder 30 Jahren produzieren?

  • Routing und Zuordnung
    Burke und Newall 1999 used genetic algorithms to schedule exams among university students. The timetable problem in general is known to be NP-complete, meaning that no method is known to find a guaranteed-optimal solution in a reasonable amount of time. In such a problem, there are both hard constraints - two exams may not be assigned to the same room at the same time - and soft constraints - students should not be assigned to multiple exams in succession, if possible, to minimize fatigue. Hard constraints must be satisfied, while soft constraints should be satisfied as far as possible. The authors dub their hybrid approach for solving this problem a "memetic algorithm": an evolutionary algorithm with rank-based, fitness-proportionate selection, combined with a local hill-climber to optimize solutions found by the EA. The EA was applied to data sets from four real universities (the smallest of which had an enrollment of 25,000 students), and its results were compared to results produced by a heuristic backtracking method, a well-established algorithm that is among the best known for this problem and that is used at several real universities. Compared to this method, the EA produced a result with a quite uniform 40% reduction in penalty.

    He und Mort 2000 applied genetic algorithms to the problem of finding optimal routing paths in telecommunications networks (such as phone networks and the Internet) which are used to relay data from senders to recipients. This is an NP-hard optimization problem, a type of problem for which GAs are "extremely well suited... and have found an enormous range of successful applications in such areas" (p.42). It is also a multiobjective problem, balancing conflicting objectives such as maximizing data throughput, minimizing transmission delay and data loss, finding low-cost paths, and distributing the load evenly among routers or switches in the network. Any successful real-world algorithm must also be able to re-route around primary paths that fail or become congested.

    In the authors' hybrid GA, a shortest-path-first algorithm, which minimizes the number of "hops" a given data packet must pass through, is used to generate the seed for the initial population. However, this solution does not take into account link congestion or failure, which are inevitable conditions in real networks, and so the GA takes over, swapping and exchanging sections of paths. When tested on a data set derived from a real Oracle network database, the GA was found to be able to efficiently route around broken or congested links, balancing traffic load and maximizing the total network throughput. The authors state that these results demonstrate the "effectiveness and scalability" of the GA and show that "optimal or near-optimal solutions can be achieved" (p.49).

    This technique has found real-world applications for similar purposes, as reported in Begley und Beals 1995. The telecommunications company U.S. West (now merged with Qwest) was faced with the task of laying a network of fiber-optic cable. Until recently, the problem of designing the network to minimize the total length of cable laid was solved by an experienced engineer; now the company uses a genetic algorithm to perform the task automatically. The results: "Design time for new networks has fallen from two months to two days and saves US West $1 million to $10 million each" (p.70).

    Jensen 2003 and Chryssolouris und Subramaniam 2001 applied genetic algorithms to the task of generating schedules for job shops. This is an NP-hard optimization problem with multiple criteria: factors such as cost, tardiness, and throughput must all be taken into account, and job schedules may have to be rearranged on the fly due to machine breakdowns, employee absences, delays in delivery of parts, and other complications, making robustness in a schedule an important consideration. Both papers concluded that GAs are significantly superior to commonly used dispatching rules, producing efficient schedules that can more easily handle delays and breakdowns. These results are not merely theoretical, but have been applied to real-world situations:

    As reported in Naik 1996, organizers of the 1992 Paralympic Games used a GA to schedule events. As reported in Petzinger 1995, John Deere & Co. has used GAs to generate schedules for a Moline, Illinois plant that manufactures planters and other heavy agricultural equipment. Like luxury cars, these can be built in a wide variety of configurations with many different parts and options, and the vast number of possible ways to build them made efficient scheduling a seemingly intractable problem. Productivity was hampered by scheduling bottlenecks, worker teams were bickering, and money was being lost. Finally, in 1993, Deere turned to Bill Fulkerson, a staff analyst and engineer who conceived of using a genetic algorithm to produce schedules for the plant. Overcoming initial skepticism, the GA quickly proved itself: monthly output has risen by 50 percent, overtime has nearly vanished, and other Deere plants are incorporating GAs into their own scheduling.

    As reported in Rao 1998, Volvo has used an evolutionary program called OptiFlex to schedule its million-square-foot factory in Dublin, Virginia, a task that requires handling hundreds of constraints and millions of possible permutations for each vehicle. Like all genetic algorithms, OptiFlex works by randomly combining different scheduling possibilities and variables, determines their fitness by ranking them according to costs, benefits and constraints, then causes the best solutions to swap genes and sends them back into the population for another trial. Until recently, this daunting task was handled by a human engineer who took up to four days to produce the schedule for each week; now, thanks to GAs, this task can be completed in one day with minimal human intervention.

    As reported in Lemley 2001, United Distillers and Vintners, a Scottish company that is the largest and most profitable spirits distributor in the world and accounts for over one-third of global grain whiskey production, uses a genetic algorithm to manage its inventory and supply. This is a daunting task, requiring the efficient storage and distribution of over 7 million barrels containing 60 distinct recipes among a vast system of warehouses and distilleries, depending on a multitude of factors such as age, malt number, wood type and market conditions. Previously, coordinating this complex flow of supply and demand required five full-time employees. Today, a few keystrokes on a computer instruct a genetic algorithm to generate a new schedule each week, and warehouse efficiency has nearly doubled.

    Beasley, Sonander und Havelock 2001 used a GA to schedule airport landings at London Heathrow, the United Kingdom's busiest airport. This is a multiobjective problem that involves, among other things, minimizing delays and maximizing number of flights while maintaining adequate separation distances between planes (air vortices that form in a plane's wake can be dangerous to another flying too closely behind). When compared to actual schedules from a busy period at the airport, the GA was able to reduce average wait time by 2-5%, equating to one to three extra flights taking off and landing per hour - a significant improvement. However, even greater improvements have been achieved: as reported in Wired 2002, major international airports and airlines such as Heathrow, Toronto, Sydney, Las Vegas, San Francisco, America West Airlines, AeroMexico, and Delta Airlines are using genetic algorithms to schedule takeoffs, landings, maintenance and other tasks, in the form of Ascent Technology's SmartAirport Operations Center software (see http://www.ascent.com/faq.html). Breeding and mutating solutions in the form of schedules that incorporate thousands of variables, "Ascent beats humans hands-down, raising productivity by up to 30 percent at every airport where it's been implemented."

  • Systemtechnik
    Benini und Toffolo 2002 applied a genetic algorithm to the multi-objective task of designing wind turbines used to generate electric power. This design "is a complex procedure characterized by several trade-off decisions... The decision-making process is very difficult and the design trends are not uniquely established" (p.357); as a result, there are a number of different turbine types in existence today and no agreement on which, if any, is optimal. Mutually exclusive objectives such as maximum annual energy production and minimal cost of energy must be taken into account. In this paper, a multi-objective evolutionary algorithm was used to find the best trade-offs between these goals, constructing turbine blades with the optimal configuration of characteristics such as tip speed, hub/tip ratio, and chord and twist distribution. In the end, the GA was able to find solutions competitive with commercial designs, as well as more clearly elucidate the margins by which annual energy production can be improved without producing overly expensive designs.

    Haas, Burnham und Mills 1997 used a multiobjective genetic algorithm to optimize the beam shape, orientation and intensity of X-ray emitters used in targeted radiotherapy to destroy cancerous tumors while sparing healthy tissue. (X-ray photons aimed at a tumor tend to be partially scattered by structures within the body, unintentionally damaging internal organs. The challenge is to minimize this effect while maximizing the radiation dose delivered to the tumor.) Using a rank-based fitness model, the researchers began with the solution produced by the conventional method, an iterative least-squares approach, and then used the GA to modify and improve it. By constructing a model of a human body and exposing it to the beam configuration evolved by the GA, they found good agreement between the predicted and actual distributions of radiation. The authors conclude that their results "show a sparing of [healthy organs] that could not be achieved using conventional techniques" (p.1745).

    Lee und Zak 2002 used a genetic algorithm to evolve a set of rules to control an automotive anti-lock braking system. While the ability of antilock brake systems to reduce stopping distance and improve maneuverability has saved many lives, the performance of an ABS is dependent on road surface conditions: for example, an ABS controller that is optimized for dry asphalt will not work as well on wet or icy roads, and vice versa. In this paper, the authors propose a GA to fine-tune an ABS controller that can identify the road surface properties (by monitoring wheel slip and acceleration) and respond accordingly, delivering the appropriate amount of braking force to maximize the wheels' traction. In testing, the genetically tuned ABS "exhibits excellent tracking properties" (p.206) and was "far superior" (p.209) to two other methods of braking maneuvers, quickly finding new optimal values for wheel slip when the type of terrain changes beneath a moving car and reducing total stopping distance. "The lesson we learned from our experiment... is that a GA can help to fine-tune even a well-designed controller. In our case, we already had a good solution to the problem; yet, with the help of a GA, we were able to improve the control strategy significantly. In summary, it seems that it is worthwhile to try to apply a GA, even to a well-designed controller, because there is a good chance that one can find a better set of the controller settings using GAs" (p.211).

    As cited in Schechter 2000, Dr. Peter Senecal of the University of Wisconsin used small-population genetic algorithms to improve the efficiency of diesel engines. These engines work by injecting fuel into a combustion chamber which is filled with extremely compressed and therefore extremely hot air, hot enough to cause the fuel to explode and drive a piston that produces the vehicle's motive force. This basic design has changed little since it was invented by Rudolf Diesel in 1893; although vast amounts of effort have been put into making improvements, this is a very difficult task to perform analytically because it requires precise knowledge of the turbulent behavior displayed by the fuel-air mixture and simultaneous variation of many interdependent parameters. Senecal's approach, however, eschewed the use of such problem-specific knowledge and instead worked by evolving parameters such as the pressure of the combustion chamber, the timing of the fuel injections and the amount of fuel in each injection. The result: the simulation produced an improved engine that consumed 15% less fuel than a normal diesel engine and produced one-third as much nitric oxide exhaust and half as much soot. Senecal's team then built a real diesel engine according to the specifications of the evolved solution and got the same results. Senecal is now moving on to evolving the geometry of the engine itself, hopefully producing even greater improvements.

    As cited in Begley und Beals 1995, Texas Instruments used a genetic algorithm to optimize the layout of components on a computer chip, placing structures so as to minimize the overall area and create the smallest chip possible. Using a connection strategy that no human had thought of, the GA came up with a design that took 18% less space.

    Finally, as cited in Ashley 1992, a proprietary software system known as Engineous that employs genetic algorithms is being used by companies in the aerospace, automotive, manufacturing, turbomachinery and electronics industries to design and improve engines, motors, turbines and other industrial devices. In the words of its creator, Dr. Siu Shing Tong, Engineous is "a master 'tweaker,' tirelessly trying out scores of 'what-if' scenarios until the best possible design emerges" (p.49). In one trial of the system, Engineous was able to produce a 0.92 percent increase in the efficiency of an experimental turbine in only one week, while ten weeks of work by a human designer produced only a 0.5 percent improvement.

    Granted, Engineous does not rely solely on genetic algorithms; it also employs numerical optimization techniques and expert systems which use logical if-then rules to mimic the decision-making process of a human engineer. However, these techniques are heavily dependent on domain-specific knowledge, lack general applicability, and are prone to becoming trapped on local optima. By contrast, the use of genetic algorithms allows Engineous to explore regions of the search space that other methods miss.

    Engineous has found widespread use in a variety of industries and problems. Most famously, it was used to improve the turbine power plant of the Boeing 777 airliner; as reported in Begley und Beals 1995, the genetically optimized design was almost 1% more fuel-efficient than previous engines, which in a field such as this is "a windfall". Engineous has also been used to optimize the configuration of industrial DC motors, hydroelectric generators and steam turbines, to plan out power grids, and to design superconducting generators and nuclear power plants for orbiting satellites. Rao 1998 also reports that NASA has used Engineous to optimize the design of a high-altitude airplane for sampling ozone depletion, which must be both light and efficient.

Kreationistische Argumente
Oben

Wie zu erwarten war, hat die reale Demonstration der Kraft der Evolution, die GAs repräsentieren, für Kreationisten überraschend und beunruhigend erwiesen, die stets behauptet haben, dass nur Intelligent Design, nicht aber zufällige Variation und Selektion, den Informationsgehalt und die Komplexität lebender Wesen hervorbringen konnte. Sie haben daher argumentiert, dass der Erfolg genetischer Algorithmen uns nichts über die biologische Evolution schließen lässt. Die Kritikpunkte zweier Anti-Evolutionisten, die zwei unterschiedliche Standpunkte vertreten, werden behandelt: der junge-Erde-Kreationist Dr. Don Batten von Answers in Genesis, der einen Artikel mit dem Titel "Genetische Algorithmen – zeigen sie, dass Evolution funktioniert?" verfasst hat, und der alte-Erde-Kreationist sowie Intelligent-Design-Befürworter Dr. William Dembski, dessen jüngstes Buch No Free Lunch (Dembski 2002) dieses Thema behandelt.

Don Batten

  • Einige Merkmale bei lebenden Dingen sind qualitativ, während GAs immer quantitativ sind
    Batten behauptet, dass GAs quantitativ sein müssen, sodass jede Verbesserung ausgewählt werden kann. Das ist wahr. Er geht dann weiter und sagt: „Viele biologische Merkmale sind qualitativ – es funktioniert entweder oder es funktioniert nicht, sodass es keinen schrittweisen Weg gibt, von keiner Funktion zur Funktion zu gelangen." Diese Behauptung wurde jedoch nicht bewiesen und wird auch nicht durch Belege unterstützt. Batten versucht nicht einmal, ein Beispiel für ein biologisches Merkmal zu geben, das entweder „funktioniert oder nicht funktioniert" und daher nicht schrittweise aufgebaut werden kann.

    Aber selbst wenn er ein solches Merkmal anbieten würde, wie könnte er überhaupt beweisen, dass es keinen schrittweisen Weg zu ihm gibt? Selbst wenn wir von einem solchen Weg nichts wissen, folgt daraus, dass es keinen gibt? Natürlich nicht. Batten behauptet effektiv, dass, wenn wir nicht verstehen, wie bestimmte Merkmale entstanden sind, es unmöglich ist, dass diese Merkmale entstanden sind – ein klassisches Beispiel für die elementare logische Fehlschluss der Argumentation aus Unwissenheit. Der Suchraum aller möglichen Varianten eines gegebenen biologischen Merkmals ist enorm, und in den meisten Fällen umfasst unser Wissen nur einen unendlich kleinen Bruchteil der Möglichkeiten. Es kann sehr wohl zahlreiche Wege zu einer Struktur geben, über die wir noch nichts wissen; es gibt keinen Grund, anzunehmen, dass unser gegenwärtiges Unwissen unsere zukünftigen Fortschritte einschränkt. Tatsächlich gibt uns die Geschichte Grund zur Zuversicht: Wissenschaftler haben enormen Fortschritt gemacht bei der Erklärung der Evolution von viele komplexen biologischen Strukturen und Systemen, sowohl makroskopisch als auch mikroskopisch (siehe beispielsweise diese Seiten zur Evolution von komplexen molekularen Systemen, „Uhr"-Genen, der Zungenschnabels oder dem Bombardierkäfer). Es ist gerechtfertigt, anzunehmen, dass diejenigen, die uns bisher entgangen sind, in Zukunft ebenfalls aufgeklärt werden.

    Tatsächlich geben uns GAs selbst einen hervorragenden Grund, daran zu glauben. Viele der Probleme, auf die sie angewendet wurden, sind komplexe Ingenieur- und Designfragen, bei denen die Lösung nicht im Voraus bekannt war und daher das Problem nicht „vorbereitet" werden konnte, um den Erfolg des Algorithmus zu unterstützen. Wenn die Kreationisten recht hätten, wäre es völlig vernünftig gewesen, zu erwarten, dass genetische Algorithmen bei der Anwendung auf diese Probleme immer wieder miserabel scheitern würden, stattdessen ist jedoch das Gegenteil eingetreten: GAs haben mächtige, hochwertige Lösungen für schwierige Probleme in einer vielfältigen Reihe von Bereichen entdeckt. Dies wirft ernsthaft in Frage, ob es überhaupt Probleme gibt, wie Batten sie beschreibt, deren Lösungen für einen evolutionären Prozess unzugänglich sind.

  • GAs selektieren für ein Merkmal nach dem anderen, während lebende Organismen mehrdimensional sind
    Batten stellt fest, dass in GAs „ein einzelnes Merkmal selektiert wird, während jedes lebende Wesen mehrdimensional ist", und behauptet, dass bei lebenden Wesen mit hunderten von Merkmalen „die Selektion auf alle Merkmale wirken muss, die das Überleben beeinflussen", während „[e]ine GA mit drei oder vier verschiedenen Zielen nicht funktionieren wird, oder ich wage zu sagen, schon gar nicht nur mit zwei."

    Dieses Argument offenbart Battens tiefgreifende Unkenntnis der einschlägigen Literatur. Selbst eine oberflächliche Durchsicht der Arbeiten zu evolutionären Algorithmen (oder ein Blick auf einen früheren Abschnitt dieses Essays) hätte gezeigt, dass Mehrobjectiv-Genetische Algorithmen ein bedeutendes und florierendes Forschungsgebiet innerhalb des breiteren Feldes der evolutionären Berechnung sind und ihn davon abgehalten hätten, eine so peinlich falsche Behauptung aufzustellen. Es gibt Zeitschriftenartikel, ganze Ausgaben prominenter Zeitschriften zur evolutionären Berechnung, ganze Konferenzen und ganze Bücher zum Thema Mehrobjectiv-GAs. Coello 2000 bietet eine sehr umfassende Übersicht mit fünf Seiten Referenzen zu Arbeiten zur Verwendung von Mehrobjectiv-Genetischen Algorithmen in einem breiten Spektrum von Feldern; siehe auch Fleming und Purshouse 2002; Hanne 2000; Zitzler und Thiele 1999; Fonseca und Fleming 1995; Srinivas und Deb 1994; Goldberg 1989, S. 197. Für einige Bücher und Arbeiten, die die Verwendung von Mehrobjectiv-GAs zur Lösung spezifischer Probleme diskutieren, siehe: Obayashi et al. 2000; Sasaki et al. 2001; Benini und Toffolo 2002; Haas, Burnham und Mills 1997; Chryssolouris und Subramaniam 2001; Hughes und Leyland 2000; He und Mort 2000; Kewley und Embrechts 2002; Beasley, Sonander und Havelock 2001; Sato et al. 2002; Tang et al. 1996; Williams, Crossley und Lang 2001; Koza et al. 1999; Koza et al. 2003. Für eine umfassende Sammlung von Zitaten zu Mehrobjectiv-GAs siehe http://www.lania.mx/~ccoello/EMOO/.

  • GAs erlauben keine Möglichkeit für Aussterben oder Katastrophe durch Fehler
    Batten behauptet, dass in GAs "etwas immer überlebt, um den Prozess fortzusetzen", während dies in der realen Welt nicht notwendigerweise zutrifft – kurz gesagt, GAs erlauben keine Möglichkeit für Aussterben.

    Dies ist jedoch nicht korrekt; Aussterben kann auftreten. Zum Beispiel verwenden einige GAs ein Selektionsmodell namens Thresholding, bei dem Individuen eine Fitness höher als ein vorbestimmter Schwellenwert haben müssen, um zu überleben und sich fortzupflanzen (Haupt und Haupt 1998, S. 37). Wenn in einem solchen GA kein Individuum diesen Standard erfüllt, kann die Population tatsächlich aussterben. Aber selbst in GAs, die kein Thresholding verwenden, können Zustände auftreten, die dem Aussterben ähneln. Wenn die Mutationsraten zu hoch sind oder die Selektionsdrücke zu stark, wird ein GA niemals eine machbare Lösung finden. Die Population kann hoffnungslos durcheinandergeraten, da schädliche Mutationen sich schneller ansammeln als die Selektion sie entfernen kann und dadurch fittere Kandidaten gestört werden (Fehlerkatastrophe), oder sie kann hilflos hin- und hergeraten, ohne einen Gewinn an Fitness zu erreichen, der groß genug wäre, um selektiert zu werden. Genau wie in der Natur muss ein Gleichgewicht herrschen, sonst wird eine Lösung niemals erreicht. Der einzige Vorteil, den ein Programmierer in dieser Hinsicht hat, besteht darin, dass er, wenn dies eintritt, das Programm mit anderen Werten neu laden kann – für die Populationsgröße, für die Mutationsrate, für den Selektionsdruck – und von vorne beginnen kann. Offensichtlich ist dies für lebende Organismen keine Option. Batten sagt: "Es gibt keine Regel in der Evolution, die besagt, dass einige Organismen in der sich entwickelnden Population lebensfähig bleiben werden, unabhängig davon, welche Mutationen auftreten", aber es gibt auch in genetischen Algorithmen keine solche Regel.

    Batten stellt auch fest, dass "die GAs, die ich künstlich untersucht habe, das Beste der vorherigen Generation künstlich bewahren und es vor Mutationen oder Rekombination schützen, falls in der nächsten Iteration nichts Besseres produziert wird". Diese Kritik wird im nächsten Punkt behandelt.

  • GAs ignorieren die Kosten der Substitution
    Battens nächster Vorwurf ist, dass GAs „Haldanes Dilemma" ignorieren, wonach ein Allel, das weniger zum Fitness eines Organismus beiträgt, entsprechend länger benötigt, um in einer Population fixiert zu werden. Offensichtlich bezieht er sich auf die elitäre Selektionstechnik, die automatisch den besten Kandidaten in jeder Generation auswählt, unabhängig davon, wie gering sein Vorteil gegenüber seinen Konkurrenten auch sein mag. Er hat recht damit, dass in der Natur sehr geringe Wettbewerbsvorteile deutlich länger benötigen, um sich auszubreiten. Genetische Algorithmen sind in dieser Hinsicht kein exaktes Modell der biologischen Evolution.

    Dies ist jedoch vom Thema ablenkend. Die elitäre Selektion ist eine Idealisierung der biologischen Evolution – ein Modell davon, was würde in der Natur geschehen, wenn der Zufall nicht von Zeit zu Zeit eingreifen würde. Wie Batten anerkennt, besagt Haldanes Dilemma nicht, dass eine leicht vorteilhafte Mutation niemals in einer Population fixiert wird; es besagt lediglich, dass dies länger dauert. Wenn jedoch die Rechenzeit knapp ist oder ein GA-Forscher eine Lösung schneller erhalten möchte, kann es wünschenswert sein, diesen Prozess durch die Implementierung von Elitismus zu überspringen. Ein wichtiger Punkt ist, dass Elitismus nicht beeinflusst, welche Mutationen entstehen, sondern lediglich sicherstellt, dass die besten davon, die entstehen, ausgewählt werden. Es wäre egal, wie stark die Selektion wäre, wenn informationssteigernde Mutationen nicht auftreten würden. Mit anderen Worten, Elitismus beschleunigt die Konvergenz, sobald eine gute Lösung entdeckt wurde – es führt nicht zu einem Ergebnis, das sonst nicht eingetreten wäre. Daher, wenn genetische Algorithmen mit Elitismus neue Informationen produzieren können, kann dies auch die Evolution in freier Wildbahn tun.

    Darüber hinaus verwenden nicht alle GAs die elitäre Selektion. Viele tun dies nicht, sondern stützen sich stattdessen nur auf die Roulette-Rad-Selektion und andere stochastische Sampling-Techniken, und dennoch waren diese nicht weniger erfolgreich. Zum Beispiel geben Koza et al. 2003, S. 8-9, Beispiele für 36 Fälle, in denen genetisches Programmieren menschenkonkurrierende Ergebnisse erzielt hat, einschließlich der automatischen Nachbildung von 21 zuvor patentierten Erfindungen (sechs davon wurden während oder nach 2000 patentiert), von denen 10 die Funktionalität des Patents auf eine neue Weise duplizieren, sowie zwei patentierbare neue Erfindungen und fünf neue Algorithmen, die für denselben Zweck besser abschneiden als jedes von Menschen geschriebene Algorithmus. Wie Dr. Koza in einer früheren Referenz auf dieselbe Arbeit (1999, S. 1070) feststellt: „Die elitäre Strategie wird nicht verwendet." Zu den anderen in diesem Essay zitierten Arbeiten, in denen Elitismus nicht verwendet wird, gehören: Robin et al. 2003; Rizki, Zmuda und Tamburino 2002; Chryssolouris und Subramaniam 2001; Burke und Newall 1999; Glen und Payne 1995; Au, Chan und Yao 2003; Jensen 2003; Kewley und Embrechts 2002; Williams, Crossley und Lang 2001; Mahfoud und Mani 1996. In jedem dieser Fälle, ohne irgendeinen Mechanismus, der sicherstellt, dass die besten Individuen in jeder Generation ausgewählt wurden, ohne diese Individuen von potenziell schädlichen zufälligen Änderungen auszunehmen, produzieren genetische Algorithmen immer noch leistungsstarke, effiziente, menschenkonkurrierende Ergebnisse. Diese Tatsache könnte für Kreationisten wie Batten überraschend sein, ist aber für Befürworter der Evolution völlig erwartbar.

  • GAs ignorieren generationsspezifische Zeitbeschränkungen
    Diese Kritik ist verwirrend. Batten behauptet, dass eine einzelne Generation in einem GA (Genetischen Algorithmus) Mikrosekunden dauern kann, während eine einzelne Generation bei jedem lebenden Organismus von Minuten bis zu Jahren dauern kann. Das ist zwar wahr, aber wie dies die Gültigkeit von GAs als Beleg für die Evolution betrifft, wird nicht erklärt. Wenn ein GA neue Informationen erzeugen kann, unabhängig davon, wie lange dies dauert, dann kann die Evolution in der Natur dies ebenfalls tun; dass GAs dies tatsächlich können, ist das einzige, was dieser Aufsatz beweisen will. Die einzige verbleibende Frage wäre dann, ob die biologische Evolution tatsächlich genügend Zeit hatte, um signifikante Veränderungen hervorzurufen, und die Antwort auf diese Frage wäre Sache von Biologen, Geologen und Physikern, nicht von Computerprogrammierern.

    Die Antwort, die diese Wissenschaftler gegeben haben, stimmt jedoch vollständig mit den evolutionären Zeitskalen überein. Zahlreiche unabhängige Beweislinien, einschließlich radiometrischer Isochronendatierung, der Abkühlungsraten von Weißen Zwergen, der Nichtexistenz von Isotopen mit kurzen Halbwertszeiten in der Natur, der Fluchtraten ferner Galaxien und der Analyse der kosmischen Hintergrundstrahlung, führen alle zu demselben Schluss: Eine Erde und ein Universum, die viele Milliarden Jahre alt sind, was bei allen vernünftigen Schätzungen mehr als genug Zeit ist, damit die Evolution die gesamte Vielfalt des Lebens hervorbringt, die wir heute sehen.

  • GAs verwenden unrealistisch hohe Mutations- und Reproduktionsraten
    Batten behauptet ohne jegliche unterstützende Belege oder Quellenangaben, dass GAs „häufig Hunderte oder Tausende von ‚Nachkommen' pro Generation produzieren", eine Rate, die selbst Bakterien, die am schnellsten reproduzierenden biologischen Organismen, nicht erreichen können.

    Diese Kritik verfehlt in mehrfacher Hinsicht das Ziel. Erstens, wenn das verwendete Maß (wie es sein sollte) die Anzahl der Nachkommen pro Generation ist, anstatt die Anzahl der Nachkommen pro Zeiteinheit, dann gibt es eindeutig biologische Organismen, die sich schneller fortpflanzen können als Bakterien und deren Raten ungefähr denen entsprechen, die Batten als unrealistisch bezeichnet. Zum Beispiel kann eine einzelne Fröschart Tausende von Eiern auf einmal legen, von denen jedes das Potenzial hat, sich zu einem Erwachsenen zu entwickeln. Gewiss, die meisten dieser Eier werden aufgrund von Ressourcenknappheit und Prädation überleben, aber dann werden die meisten „Nachkommen" in jeder Generation einer GA ebenfalls nicht überleben.

    Zweitens und noch wichtiger ist, dass ein genetischer Algorithmus, der zur Lösung eines Problems eingesetzt wird, nicht dazu gedacht ist, ein einzelnes Organismus darzustellen. Stattdessen ist ein genetischer Algorithmus eher analog zu einer gesamten Population von Organismen – schließlich sind es Populationen, nicht Individuen, die sich entwickeln. Es ist natürlich völlig plausibel, dass eine ganze Population kollektiv Hunderte oder Tausende von Nachkommen pro Generation hat. (Der Kreationist Walter ReMine macht denselben Fehler in Bezug auf Dr. Richard Dawkins' „Marder"-Programm. Siehe diesen Post des Monats für weitere Informationen.)

    Darüber hinaus sagt Batten, die Mutationsrate sei in GAs künstlich hoch, während lebende Organismen Fehlerkorrektur-Maschinerie besitzen, die darauf ausgelegt ist, die Mutationsrate auf etwa 1 zu 10 Milliarden Basenpaaren zu begrenzen (obwohl dies zu niedrig ist – die tatsächliche Zahl liegt näher bei 1 zu 1 Milliarde. Siehe Dawkins 1996, S. 124). Nun, das ist natürlich wahr. Wenn GAs mit dieser Rate mutierten, würden sie zu lange brauchen, um reale Probleme zu lösen. Offensichtlich sollte als relevant betrachtet werden die Mutationsrate relativ zur Größe des Genoms. Die Mutationsrate sollte hoch genug sein, um eine ausreichende Menge an Vielfalt in der Population zu fördern, ohne die Individuen zu überfluten. Ein durchschnittlicher Mensch wird zwischen einer und fünf Mutationen besitzen; dies ist für die Nachkommen einer GA keineswegs unrealistisch.

  • GAs haben künstlich kleine Genome
    Battens Argument, dass das Genom eines genetischen Algorithmus "künstlich klein ist und nur eine Sache tut", ist stark irreführend. Erstens ist es, wie wir gesehen haben, nicht wahr, dass ein GA nur eine Sache tut; es gibt viele Beispiele für genetische Algorithmen, die speziell designed sind, um viele Parameter gleichzeitig zu optimieren, oft weit mehr Parameter gleichzeitig als ein menschlicher Gestalter es jemals könnte.

    Und wie genau quantifiziert Batten "künstlich klein"? Viele evolutionäre Algorithmen, wie John Kozas genetische Programmierung, verwenden Variablenlängen-Codierungen, bei denen die Größe von Kandidatenlösungen willkürlich groß werden kann. Batten behauptet, dass selbst der einfachste lebende Organismus weit mehr Informationen in seinem Genom hat, als ein GA jemals produziert hat, aber während Organismen, die heute leben, möglicherweise relativ große Genome haben, liegt das daran, dass viel Komplexität im Laufe von Milliarden Jahren Evolution gewonnen wurde. Wie der Artikel Probability of Abiogenesis darauf hinweist, gibt es gute Gründe zu glauben, dass die frühesten lebenden Organismen sehr viel einfacher waren als jede derzeit existierende Art - selbstreplizierende Moleküle wahrscheinlich nicht länger als 30 oder 40 Untereinheiten, die leicht durch die 1800 Bits Information spezifiziert werden könnten, die Batten anscheinend zumindest einen GA zugebilligt hat. Genetische Algorithmen sind ebenfalls eine sehr neue Technik, deren volles Potenzial noch nicht ausgeschöpft wurde; digitale Computer selbst sind nur ein paar Jahrzehnte alt, und wie Koza (2003, S. 25) hervorhebt, haben evolutionäre Rechenverfahren in den letzten 15 Jahren zunehmend substantiellere und komplexere Ergebnisse erzeugt, im Einklang mit dem anhaltenden raschen Anstieg der Rechenleistung, der oft als "Moore's Law" bezeichnet wird. Genau wie das frühe Leben sehr einfach im Vergleich zu dem, was danach kam, werden heutige genetische Algorithmen, trotz der beeindruckenden Ergebnisse, die sie bereits erzielt haben, wahrscheinlich in der Zukunft weit größere Dinge hervorbringen.

  • GAs ignorieren die Möglichkeit einer Mutation im gesamten Genom
    Batten scheint nicht zu verstehen, wie genetische Algorithmen funktionieren, und er zeigt dies mit diesem Argument. Er behauptet, dass im echten Leben "Mutationen im gesamten Genom auftreten, nicht nur in einem Gen oder Abschnitt, der ein bestimmtes Merkmal spezifiziert". Das ist zwar wahr, aber wenn er sagt, dass dies für GAs nicht zutrifft, dann liegt er falsch. Genau wie bei lebenden Organismen erlauben GAs Mutationen und Rekombinationen überall in den Genomen ihrer Kandidatenlösungen; genau wie bei lebenden Organismen müssen GAs schädliche Veränderungen aussortieren, während sie gleichzeitig vorteilhafte auswählen.

    Batten geht weiter und behauptet, dass "das Programm selbst vor Mutationen geschützt ist; nur Zielsequenzen werden mutiert", und wenn das Programm selbst mutiert würde, würde es bald abstürzen. Diese Kritik ist jedoch irrelevant. Es gibt keinen Grund, warum das steuernde Programm eines GA mutiert werden sollte. Das Programm ist kein Teil des genetischen Algorithmus; das Programm überwacht den genetischen Algorithmus und mutiert die Kandidatenlösungen, die der Programmierer zu verbessern sucht. Das Programm, das den GA ausführt, ist nicht analog zur Fortpflanzungsmechanik eines Organismus, einen Vergleich, den Batten versuchen möchte. Stattdessen ist es analog zu den invarianten Naturgesetzen, die die Umgebungen regeln, in denen lebende Organismen leben und sich fortpflanzen, und diese werden weder erwartet zu ändern noch müssen sie davor "geschützt" werden.

  • GAs ignorieren Probleme der irreduziblen Komplexität
    Unter Verwendung des Arguments von "irreduzibler Komplexität" durch den alt-erdkreationistischen Michael Behe argumentiert Batten: "Viele biologische Merkmale erfordern das Vorhandensein vieler verschiedener Komponenten, die zusammen funktionieren, damit das Merkmal überhaupt existieren kann," während dies bei GAs nicht der Fall ist.

    Es ist jedoch trivial zu zeigen, dass eine solche Behauptung falsch ist, da genetische Algorithmen schon irreduzibel komplexe Systeme erzeugt haben. Zum Beispiel ist der Spracherkennungs-Schaltkreis, den Dr. Adrian Thompson entwickelt hat (Davidson 1997), aus 37 Kernlogikgattern zusammengesetzt. Fünf davon sind nicht einmal mit dem Rest des Schaltkreises verbunden, doch alle 37 sind erforderlich, damit der Schaltkreis funktioniert; wenn eines davon von seiner Stromversorgung getrennt wird, hört das gesamte System auf zu funktionieren. Dies entspricht Behes Definition eines irreduzibel komplexen Systems und zeigt, dass ein evolutionärer Prozess solche Dinge erzeugen kann.

    Es sei darauf hingewiesen, dass dies dasselbe Argument wie das erste ist, lediglich in anderer Sprache dargelegt, und somit ist die Widerlegung dieselbe. Irreduzible Komplexität ist kein Problem für die Evolution, sei diese in lebenden Wesen in freier Wildbahn oder in Silizium auf einem Prozessorschaltkreis eines Computers stattfindend.

  • GAs ignorieren Polygenie, Pleiotropie und andere genetische Komplexitäten
    Batten argumentiert, dass GAs Probleme der Polygenie (die Bestimmung eines Merkmals durch mehrere Gene), Pleiotropie (ein Gen, das mehrere Merkmale beeinflusst) sowie dominante und rezessive Gene ignorieren.

    Keine dieser Behauptungen ist jedoch wahr. GAs ignorieren Polygenie und Pleiotropie nicht: diese Eigenschaften dürfen lediglich natürlich entstehen, anstatt absichtlich kodiert zu werden. Es ist offensichtlich, dass in jedem komplexen, voneinander abhängigen System (d. h. einem nichtlinearen System) die Änderung oder Entfernung eines Teils einen Kaskadeneffekt von Veränderungen über das gesamte System hinweg auslöst; daher integrieren GAs Polygenie und Pleiotropie von Natur aus. „In der Literatur zu genetischen Algorithmen wird Parameterinteraktion als Epistasie bezeichnet (ein biologischer Begriff für Geninteraktion). Wenn es wenig bis keine Epistasie gibt, funktionieren Suchalgorithmen nach Minimum [d. h. Hügelsteiger --A.M.] am besten. Genetische Algorithmen glänzen, wenn die Epistasie mittel bis hoch ist..." (Haupt und Haupt 1998, S. 31, ursprünglicher Hervorhebung).

    Ebenso gibt es einige Implementierungen von genetischen Algorithmen, die diploide Chromosomen sowie dominante und rezessive Gene besitzen (Goldberg 1989, S. 150; Mitchell 1996, S. 22). Diejenigen, die dies nicht tun, ähneln lediglich haploiden Organismen, wie Bakterien, mehr als diploiden Organismen, wie Menschen. Da Bakterien (nach bestimmten Maßstäben) zu den erfolgreichsten Organismen auf diesem Planeten gehören, bleiben solche GAs ein gutes Modell für die Evolution.

  • GAs haben keine Mehrfach-Leserahmen
    Batten diskutiert die Existenz mehrerer Leserahmen in den Genomen einiger Lebewesen, bei denen die DNA-Sequenzen unterschiedliche funktionelle Proteine kodieren, wenn sie in unterschiedlichen Richtungen oder mit unterschiedlichen Startverschiebungen gelesen werden. Er behauptet, dass "die Erstellung eines GAs zur Generierung solcher informationsdichten Kodierung aussichtslos erscheint".

    Eine solche Herausforderung verlangt eine Antwort, und hier ist sie: Soule und Ball 2001. In dieser Arbeit stellen die Autoren einen genetischen Algorithmus mit mehreren Leserahmen und dichter Kodierung vor, der es ermöglicht, mehr Informationen zu speichern als die Gesamtlänge seines Genoms. Ähnlich wie die drei-Nukleotid-Codons, die Aminosäuren in den Genomen von Lebewesen spezifizieren, waren die Codons dieses GAs fünfstellige Binärstrings. Da die Codons fünf Stellen lang waren, gab es fünf verschiedene mögliche Leserahmen. Die Sequenz 11111 dient als "Start"-Codon und 00000 als "Stop"-Codon; da die Start- und Stop-Codons an beliebiger Stelle im Genom auftreten können, war die Länge jedes Individuums variabel. Regionen des Chromosoms, die nicht zwischen Start-Stop-Paaren lagen, wurden ignoriert.

    Der GA wurde an vier klassischen Funktionsmaximierungsproblemen getestet. "Zunächst nehmen die meisten Bits an keinem Gen teil, d. h., der Großteil eines Chromosoms ist nicht-kodierend. Auch dies liegt daran, dass bei den anfänglichen zufälligen Individuen relativ wenige Start-Stop-Codon-Paare vorhanden sind. Allerdings nimmt die Anzahl der Bits, die nicht teilnehmen, extrem schnell ab." Während des Laufs kann der GA die effektive Länge seines Genoms erhöhen, indem er neue Start-Codons in verschiedenen Leserahmen einführt. Bis zum Ende des Laufs "ist der Überlappungsgrad sehr hoch. Viele Bits nehmen an mehreren (und oft allen fünf) Genen teil." Bei allen Testproblemen begann der GA im Durchschnitt mit 5 spezifizierten Variablen; bis zum Ende des Laufs war diese Zahl auf einen Durchschnitt von rund 25 gestiegen.

    Bei den Testproblemen erzeugte der GA mit mehreren Leserahmen signifikant bessere Lösungen als ein standardmäßiger GA bei zwei von vier Problemen und bessere durchschnittliche Lösungen bei den verbleibenden zwei. Bei einem Problem komprimierte der GA erfolgreich 625 Bits an Gesamtinformationen in ein Chromosom von nur 250 Bits Länge, indem er alternative Leserahmen nutzte. Die Autoren bezeichnen dieses Verhalten als "äußerst sophisticated" und schließen daraus, dass "Diese Daten zeigen, dass ein GA Leserahmen erfolgreich nutzen kann, trotz der zusätzlichen Komplexität" und "Es ist klar, dass ein GA neue 'Gene' einführen kann, wie sie zur Lösung eines gegebenen Problems notwendig sind, selbst unter den Schwierigkeiten, die durch die Verwendung von Start- und Stop-Codons und überlappenden Genen entstehen".

  • GAs haben vorbestimmte Ziele
    Wie bei mehreren anderen zeigt diese Einwendung, dass Batten nicht vollständig versteht, was ein genetischer Algorithmus ist und wie er funktioniert. Er argumentiert, dass GAs im Gegensatz zur Evolution Ziele haben, die von vornherein vorbestimmt und spezifiziert sind, und bietet als Beispiel dafür Dr. Richard Dawkins' "Marder"-Programm an.

    Das Marder-Programm ist jedoch kein echter genetischer Algorithmus und ist nicht typisch für genetische Algorithmen, genau aus diesem Grund. Es war nicht beabsichtigt, die Problemlösungskraft der Evolution zu demonstrieren. Stattdessen lag sein einziger Zweck darin, den Unterschied zwischen einstufiger Selektion (das berüchtigte "Gewitter, das durch einen Schrottplatz weht und eine 747 erzeugt") und kumulativer, mehrstufiger Selektion zu zeigen. Es hatte zwar ein spezifisches Ziel, das von vornherein vorbestimmt war. Echte genetische Algorithmen jedoch nicht.

    In einem allgemein weit gefassten Sinne haben GAs ein Ziel: nämlich, eine akzeptable Lösung für ein gegebenes Problem zu finden. In diesem gleichen Sinne hat auch die Evolution ein Ziel: Organismen zu produzieren, die besser an ihre Umwelt angepasst sind und somit einen größeren Fortpflanzungserfolg erfahren. Aber genau wie die Evolution ein Prozess ohne spezifische Ziele ist, spezifizieren GAs nicht von vornherein wie ein gegebenes Problem gelöst werden soll. Die Fitness-Funktion wird lediglich eingerichtet, um zu bewerten, wie gut eine Kandidatenlösung funktioniert, ohne eine bestimmte Art und Weise vorzuschreiben, wie sie funktionieren soll, und ohne ein Urteil über die Art und Weise zu fällen, die sie erfunden hat. Die Lösung selbst entsteht dann durch einen Prozess der Mutation und Selektion.

    Battens nächster Satz zeigt deutlich, dass er nicht versteht, was ein genetischer Algorithmus ist. Er behauptet: "Vielleicht, wenn der Programmierer ein Programm entwickeln könnte, das alles zulässt und dann die Überlebensfähigkeit der 'Organismen' misst, nähme es sich der Sache, die die Evolution tun soll, vielleicht näher" - aber genau so funktionieren genetische Algorithmen. Sie erzeugen zufällig Kandidatenlösungen und mutieren diese zufällig über viele Generationen. Keine Konfiguration wird im Voraus spezifiziert; wie Batten es ausdrückt, ist alles erlaubt. Wie John Koza (2003, S. 37) schreibt, unheimlich Battens Worte wiederholend: "Ein wichtiges Merkmal... ist, dass die Selektion [im genetischen Programmieren] nicht gierig ist. Individuen, die als unterlegen bekannt sind, werden in einem gewissen Maße ausgewählt. Das beste Individuum in der Population ist nicht garantiert ausgewählt zu werden. Darüber hinaus wird das schlechteste Individuum in der Population nicht unbedingt ausgeschlossen. Alles kann passieren und nichts ist garantiert." (Ein früherer Abschnitt hat diesen Punkt bereits als eine Stärke eines GAs diskutiert.) Und doch entstehen durch die Anwendung eines selektiven Filters auf diese zufällig mutierenden Kandidaten effiziente, komplexe und leistungsstarke Lösungen für schwierige Probleme, Lösungen, die von keiner Intelligenz entworfen wurden und die oft Lösungen gleichziehen oder übertreffen können, die von Menschen entworfen wurden. Battens leichtfertige Behauptung, dass "Das ist natürlich unmöglich", wird eindeutig durch die Realität widerlegt.

  • GAs erzeugen tatsächlich keine neuen Informationen
    Battens letzter Einwand lautet: „Bei einem bestimmten GA muss man fragen, wie viel des vom Programm erzeugten ‚Informationsgehalts' tatsächlich im Programm spezifiziert ist, anstatt de novo erzeugt zu werden." Er wirft vor, dass GAs oft nichts weiter tun, als den besten Weg zu finden, auf dem bestimmte Module interagieren, wenn sowohl die Module selbst als auch die Art ihrer Interaktion bereits im Voraus spezifiziert sind.

    Es ist schwierig zu beurteilen, was man von diesem Argument halten soll. Jedes denkbare Problem – Terme in einer Kalkül-Gleichung, Moleküle in einer Zelle, Komponenten eines Motors, Aktien an einem Finanzmarkt – kann in Bezug auf Module ausgedrückt werden, die auf gegebene Weise interagieren. Wenn man nur unbestimmte Module hat, die auf unbestimmte Weise interagieren, gibt es kein Problem zu lösen. Bedeutet dies, dass die Lösung für kein Problem die Erzeugung neuer Informationen erfordert?

    In Bezug auf Battens Kritik, wonach der im Lösungsansatz enthaltene Informationsgehalt bereits im Problem vorbestimmt ist, ist der beste Weg, seine Bedenken zu zerstreuen, darauf hinzuweisen, dass es viele Beispiele gibt, bei denen GAs mit zufällig erzeugten Anfangspopulationen beginnen, die in keiner Weise darauf ausgelegt sind, dem GA zu helfen, das Problem zu lösen. Zu solchen Beispielen gehören: Graham-Rowe 2004; Davidson 1997; Assion et al. 1998; Giro, Cyrillo und Galvão 2002; Glen und Payne 1995; Chryssolouris und Subramaniam 2001; Williams, Crossley und Lang 2001; Robin et al. 2003; Andreou, Georgopoulos und Likothanassis 2002; Kewley und Embrechts 2002; Rizki, Zmuda und Tamburino 2002; und insbesondere Koza et al. 1999 und Koza et al. 2003, die die Verwendung von genetischer Programmierung zur Erzeugung von 36 menschenwettbewerbsfähigen Erfindungen in den Bereichen analoge Schaltungstechnik, Molekularbiologie, Algorithmik, Industrieregelungstechnik und anderen Feldern diskutieren, alle beginnend mit Populationen zufällig erzeugter Anfangskandidaten.

    Zugegeben, einige GAs beginnen mit intelligent erzeugten Lösungen, die sie dann zu verbessern suchen, doch dies ist irrelevant: In solchen Fällen geht es nicht nur darum, die ursprünglich eingegebene Lösung zurückzugeben, sondern sie durch die Erzeugung neuer Informationen zu verbessern. In jedem Fall kann es selbst dann, wenn die Ausgangslage so ist, wie Batten sie beschreibt, eine alles andere als triviale Aufgabe sein, den effizientesten Weg zu finden, auf dem eine Reihe von Modulen unter einem gegebenen Satz von Einschränkungen interagieren können, und dessen Lösung einen beträchtlichen Anteil an neuen Informationen beinhaltet: Die Planung in internationalen Flughäfen, beispielsweise, oder Fertigungsstraßen, oder die Verteilung von Fässern zwischen Lagern und Destillerien. Auch hier haben sich GAs als effektiv erwiesen, um Probleme zu lösen, deren Komplexität jeden Menschen übersteigen würde. Angesichts der vielfältigen Innovationen und unerwartet effektiven Lösungen, die aus GAs in vielen Bereichen hervorgehen, klingt Battens Behauptung, dass „Die Menge der neu erzeugten Informationen (durch einen GA) in der Regel sehr trivial ist", tatsächlich hohl.

William Dembski

Das jüngste Buch des alt-erdkreationistischen Dr. William Dembski, No Free Lunch: Warum spezifizierte Komplexität nicht ohne Intelligenz erworben werden kann, widmet sich weitgehend dem Thema evolutionärer Algorithmen und deren Beziehung zur biologischen Evolution. Insbesondere befasst sich Dembskis Buch mit einer schwer greifbaren Eigenschaft, die er „spezifizierte Komplexität" nennt, die er in lebenden Wesen in abundance vorfindet und die er weiter behauptet, dass evolutionäre Prozesse nicht in der Lage sind zu erzeugen, wodurch „Design" durch unbestimmte Mechanismen eines unidentifizierten „intelligenten Designers" die einzige Alternative bleibt. Um seinen Fall zu stützen, beruft sich Dembski auf eine Klasse mathematischer Sätze, die als No Free Lunch-Theoreme bekannt sind, die er als Beweis dafür anführt, dass evolutionäre Algorithmen im Durchschnitt nicht besser abschneiden als eine blinde Suche.

Richard Wein hat eine hervorragende und umfassende Widerlegung von Dembski verfasst, mit dem Titel Not a Free Lunch But a Box of Chocolates, und ihre Punkte werden hier nicht wiederholt. Ich werde stattdessen auf Kapitel 4 des Buches von Dembski eingehen, das sich im Detail mit genetischen Algorithmen befasst.

Dembski hat ein Hauptargument gegen GA, das im Laufe dieses Kapitels ausführlich entwickelt wird. Obwohl er nicht leugnet, dass sie beeindruckende Ergebnisse erzielen können – tatsächlich sagt er, dass es etwas „seltsam überzeugendes und fast magisches" (S. 221) an der Weise gibt, wie GA Lösungen finden, die nichts mit von Menschen entworfener Ähnlichkeit haben –, argumentiert er, dass ihr Erfolg auf die spezifizierte Komplexität zurückzuführen ist, die ihnen von ihren menschlichen Gestaltern „geschmuggelt" wird und sich anschließend in den von ihnen produzierten Lösungen manifestiert. „Mit anderen Worten, alle spezifizierte Komplexität, die wir aus einem evolutionären Algorithmus erhalten, muss zunächst in seine Konstruktion und in die Informationen eingeführt werden, die den Algorithmus leiten. Evolutionäre Algorithmen erzeugen oder schaffen also keine spezifizierte Komplexität, sondern nutzen lediglich bereits existierende spezifizierte Komplexität" (S. 207).

Das erste offensichtliche Problem in Dembskis Argumentation ist dieses. Obwohl sein Kapitel über evolutionäre Algorithmen etwa 50 Seiten umfasst, behandeln die ersten 30 dieser Seiten nichts anderes als Dr. Richard Dawkins' "Marder"-Algorithmus, der, wie bereits diskutiert, kein wahrer genetischer Algorithmus ist und nicht repräsentativ für genetische Algorithmen. Dembskis zwei weitere Beispiele – die gekrümmten Draht-Genetischen Antennen von Edward Altshuler und Derek Linden sowie die Schachspielende neuronalen Netze von Kumar Chellapilla und David Fogel – werden erst in den letzten 10 Seiten des Kapitels eingeführt und werden insgesamt drei Seiten lang diskutiert. Dies ist ein schwerwiegender Mangel, bedenkt man, dass das "Marder"-Programm nicht repräsentativ für die meisten Arbeiten im Bereich der evolutionären Berechnung ist; dennoch werden Dembskis Argumente in Bezug darauf analysiert.

Hinsichtlich des „Marder-Programms" stellt Dembski fest, dass „Dawkins und andere Darwinisten dieses Beispiel verwenden, um die Kraft evolutionärer Algorithmen zu veranschaulichen" (S. 182), und erneut, dass „Darwinisten ... von dem METHINKS IT IS LIKE A WEASEL-Beispiel sehr angetan sind und es als Veranschaulichung der Kraft evolutionärer Algorithmen betrachten, um spezifizierte Komplexität zu erzeugen" (S. 183). Dies ist ein Strohmann von Dembskis Schöpfung (nicht zuletzt, weil Dawkins' Buch lange vor der Erfindung dieses Begriffs durch Dembski geschrieben wurde!). Hier ist, was Dawkins wirklich über den Zweck seines Programms sagt:

"Was zählt ist der Unterschied zwischen der Zeit, die die kumulative Selektion benötigt, und der Zeit, die derselbe Computer, der mit gleicher Geschwindigkeit auf Hochtouren arbeitet, benötigen würde, um das Zielsatz zu erreichen, wenn er gezwungen wäre, das andere Verfahren der Ein-Schritt-Selektion zu verwenden: etwa eine Million-Million-Million-Million-Million Jahre." (Dawkins 1996, S. 49, Hervorhebung im Original)

Anders ausgedrückt, sollte das Programm der Marder dazu dienen, den Unterschied zwischen zwei verschiedenen Arten von Selektion zu verdeutlichen: Einstufige Selektion, bei der ein komplexes Ergebnis durch reines Zufallsglück in einem einzigen Sprung entsteht, und kumulative Selektion, bei der ein komplexes Ergebnis Stück für Stück über einen Filterprozess aufgebaut wird, der Verbesserungen bevorzugt bewahrt. Es war nie beabsichtigt, eine Simulation der Evolution als Ganzes zu sein.

Einstufige Selektion ist der absurd unwahrscheinliche Prozess, der in der kreationistischen Literatur häufig angegriffen wird, indem er mit einem Wirbelsturm verglichen wird, der durch einen Schrottplatz bläst und ein 747-Flugzeug erzeugt, oder mit einer Explosion in einer Druckerei, die ein Wörterbuch erzeugt. Kumulative Selektion ist das, was die Evolution tatsächlich nutzt. Um mit einstufiger Selektion ein funktionelles Ergebnis von nennenswerter Komplexität zu erzielen, müsste man im Durchschnitt viele Male so lange warten wie das aktuelle Alter des Universums. Mit kumulativer Selektion kann jedoch dasselbe Ergebnis in einem vergleichsweise sehr kurzen Zeitraum erreicht werden. Die Demonstration dieses Unterschieds war der Punkt von Dawkins' Programm „Marder", und das war der einzige Punkt dieses Programms. In einem Anmerkung zu diesem Kapitel schreibt Dembski: „Es ist bemerkenswert, wie Dawkins' Beispiel ohne jegliche Andeutung der grundlegenden Schwierigkeiten, die damit verbunden sind, recycelt wird" (S. 230), doch es sind nur Missverständnisse in den Köpfen von Kreationisten wie Dembski und Batten, die das Marder-Programm dafür kritisieren, dass es etwas demonstriert, das es nie demonstrieren sollte, die zu diesen „Schwierigkeiten" führen.

Im Gegensatz zu jedem in diesem Aufsatz besprochenen Beispiel evolutionärer Algorithmen hat das Fuchsprogramm tatsächlich ein einziges, vorab festgelegtes Ziel, und die Qualität der von ihm generierten Lösungen wird durch einen expliziten Vergleich mit diesem vorab festgelegten Ziel bewertet. Daher hat Dembski recht, wenn er sagt, dass das Fuchsprogramm keine neuen Informationen erzeugt. Allerdings macht er dann einen gigantischen und völlig unbegründeten Sprung, wenn er diesen Schluss auf alle evolutionären Algorithmen überträgt: „Als die einzige Möglichkeit, die Dawkins' evolutionärer Algorithmus erreichen kann, hat die Zielsequenz tatsächlich eine minimale Komplexität.... Evolutionäre Algorithmen sind daher unfähig, wahre Komplexität zu erzeugen" (S. 182). Selbst Dembski scheint dies zu erkennen, wenn er schreibt: „...die meisten evolutionären Algorithmen in der Literatur sind so programmiert, dass sie einen Raum möglicher Lösungen für ein Problem durchsuchen, bis sie eine Antwort finden – nicht, wie Dawkins es hier tut, indem sie die Antwort im Voraus explizit in sie programmieren" (S. 182). Aber dann, nachdem er einen völlig guten Grund dafür gegeben hat, warum das Fuchsprogramm nicht repräsentativ für GAs als Ganzes ist, geht er unerklärlicherweise weiter und macht genau diese fehlerhafte Verallgemeinerung!

In der Realität unterscheidet sich das Programm der Marder deutlich von den meisten genetischen Algorithmen, und daher ist Dembskis Argument durch Analogie nicht haltbar. Wahre evolutionäre Algorithmen, wie die in diesem Aufsatz diskutierten Beispiele, finden sich nicht einfach zurück zu Lösungen, die bereits von anderen Methoden entdeckt wurden – stattdessen werden sie mit Problemen konfrontiert, bei denen die optimale Lösung nicht im Voraus bekannt ist, und aufgefordert, diese Lösung eigenständig zu entdecken. Tatsächlich, wenn genetische Algorithmen nichts weiter tun könnten als Lösungen wiederzufinden, die bereits in sie programmiert sind, welchen Sinn hätte dann deren Einsatz? Es wäre ein Üben der Redundanz, dies zu tun. Allerdings zeigt das weit verbreitete wissenschaftliche (und kommerzielle) Interesse an GAs, dass es ihnen weit mehr Substanz innewohnt, als der eher triviale Versuch, den Dembski unternimmt, dieses gesamte Feld darauf zu reduzieren.

Haben wir dieses Strohmann-Argument aufgebaut und dann wieder zerlegt, geht Dembski zu seinem nächsten Argumentationsstrang über: Dass die spezifische Komplexität, die sich bei den Ergebnissen repräsentativerer evolutionärer Algorithmen zeigt, wie beim Programm „Marder" (weasel program), „geschmuggelt" wurde von den Gestaltern des Algorithmus. „Aber wir finden unweigerlich, dass wenn scheinbar spezifische Komplexität kostenlos erzeugt wird, sie tatsächlich vorbelastet, eingeschmuggelt oder vor dem Blick verborgen ist" (S. 204). Dembski schlägt vor, dass der häufigste „Versteckort" der spezifischen Komplexität in der Fitness-Funktion des GA liegt. „Was der [evolutionäre Algorithmus] getan hat, ist, dass er die in der Fitness-Funktion inhärente spezifische Komplexität ausgenutzt und sie bei der Suche und dann beim Auffinden des Ziels verwendet hat..." (S. 194). Dembski geht weiter und argumentiert, dass, bevor ein EA eine gegebene Fitness-Landschaft nach einer Lösung durchsuchen kann, zunächst ein Mechanismus eingesetzt werden muss, um diese Fitness-Landschaft aus dem von ihm als Phasenraum bezeichneten Bereich aller möglichen Fitness-Landschaften auszuwählen, und wenn dieser Mechanismus ebenfalls ein evolutionärer ist, muss zunächst ein anderer Mechanismus eingesetzt werden, um dessen Fitness-Funktion aus einem noch größeren Phasenraum auszuwählen, und so weiter. Dembski schließt daraus, dass der einzige Weg, um diesen unendlichen Regress zu stoppen, die Intelligenz ist, die er eine gewisse irreduzible, mysteriöse Fähigkeit zugeschrieben sieht, eine Fitness-Funktion aus einem gegebenen Phasenraum auszuwählen, ohne auf höherstufige Phasenräume zurückzugreifen. „Es gibt nur einen bekannten Erzeuger spezifischer Komplexität, und das ist die Intelligenz" (S. 207).

Dembski hat recht, wenn er schreibt, dass die Fitnessfunktion „einen evolutionären Algorithmus in die Zielrichtung führt" (S. 192). Allerdings ist er in seiner Behauptung falsch, dass die Auswahl der richtigen Fitnessfunktion ein Prozess ist, der die Erzeugung einer noch höheren spezifizierten Komplexität erfordert als der EA selbst produziert. Wie Koza (1999, S. 39) schreibt, sagt die Fitnessfunktion einem evolutionären Algorithmus „was zu tun ist", nicht „wie es zu tun ist". Im Gegensatz zum untypischen Beispiel des Marder-Programms gibt die Fitnessfunktion eines EA in der Regel keine bestimmte Form vor, die die Lösung annehmen sollte, und kann daher nicht behaupten, sie trage im irgendeinem sinnvollen Sinne „spezifizierte Komplexität" zur entwickelten Lösung bei.

Ein Beispiel wird den Punkt im größeren Detail veranschaulichen. Dembski behauptet, dass in Chellapilla und Fogels Schachbrett-Experiment ihre Entscheidung, das Gewinnkriterium von Spiel zu Spiel konstant zu halten, „eine enorme Menge an spezifizierter Komplexität eingefügt hat" (S. 223). Es ist sicherlich wahr, dass das Endprodukt dieses Prozesses eine große Menge an spezifizierter Komplexität aufwies (wie auch immer man diesen Begriff definieren mag). Aber ist es wahr, dass das gewählte Fitnessmaß genau so viel spezifizierte Komplexität enthielt? Hier ist, was Chellapilla und Fogel tatsächlich sagen:

"Um das erreichte Spielniveau zu würdigen, könnte es nützlich sein, das folgende Gedankenexperiment zu betrachten. Nehmen Sie an, Sie werden aufgefordert, ein Spiel auf einem achtmal acht Feldern großen Brett mit abwechselnden Farben zu spielen. Auf jeder Seite befinden sich 12 Figuren, die zu Beginn in einer bestimmten Anordnung platziert sind. Ihnen werden die Regeln erklärt, wie sich die Figuren bewegen (d. h. diagonal, erzwungene Sprünge, Könige), und es wird mitgeteilt, dass die Figuren-Differenz als Funktion verfügbar ist. Ihnen wird jedoch nicht gesagt, ob diese Differenz vorteilhaft oder nachteilig ist (es gibt eine Variante des Schachbretts namens 'Suicide-Schachbrett', bei der das Ziel darin besteht, so schnell wie möglich zu 'verlieren'), oder ob es überhaupt wertvolle Information ist. Wichtigsterweise wird Ihnen nicht das Ziel des Spiels mitgeteilt. Sie machen einfach Züge, und zu einem bestimmten Zeitpunkt erklärt ein externer Beobachter das Spiel für beendet. Er gibt jedoch keine Rückmeldung darüber, ob Sie gewonnen, verloren oder remisiert haben. Die einzigen Daten, die Sie erhalten, kommen nach mindestens fünf solchen Spielen und werden in Form eines Gesamtpunktwertes angeboten. Daher können Sie nicht mit Sicherheit wissen, welche Spiele zum Gesamtergebnis beigetragen haben oder in welchem Maße. Ihre Herausforderung besteht darin, auf Basis dieses groben Feedbacks die angemessenen Züge in jedem Spiel herbeizuführen." (Chellapilla und Fogel 2001, S. 427)

Es geht über die Grenzen des Absurden hinaus, wenn Dembski behauptet, dass dieses Fitnessmaß eine „enorme" Menge an spezifizierter Komplexität eingefügt hat. Wenn einem Menschen, der nie von Schachspielen gehört hatte, dieselben Informationen gegeben würden und wir einige Monate später zurückkehren würden, um festzustellen, dass er zu einem international rangierten Schachspieler geworden ist, sollten wir dann schließen, dass spezialisierte Komplexität erzeugt wurde?

Dembski stellt fest, dass sein Argument nur widerlegt werden kann, "wenn man zeigt, dass das Auffinden der Information, die einem evolutionären Algorithmus die Zielerreichung ermöglicht, wesentlich einfacher ist als das direkte Auffinden des Ziels durch eine blinde Suche" (S. 204). Ich behaupte, dass dies genau der Fall ist. Intuitiv sollte es nicht überraschend sein, dass die Fitnessfunktion weniger Information enthält als die evolvierte Lösung. Dies ist genau der Grund, warum GA (Genetische Algorithmen) eine so weite Verbreitung gefunden haben: Es ist einfacher (benötigt weniger Information), eine Fitnessfunktion zu schreiben, die misst, wie gut eine Lösung ist, als eine gute Lösung von Grund auf neu zu entwerfen.

In weniger formellen Begriffen betrachten wir Dembskis zwei Beispiele, die gekrümmte-Draht-Genantenne und das evolvierte Schachspiel-Neuronales Netzwerk namens Anaconda. Es erfordert eine große Menge an detaillierten Informationen über das Spiel Schach, um eine Gewinnstrategie zu entwickeln (betrachten Sie Chinook und seine enorme Bibliothek von Endspielen). Allerdings erfordert es nicht gleich detaillierte Informationen, um eine solche Strategie zu erkennen, wenn man sie sieht: alles, was wir beobachten müssen, ist, dass diese Strategie konsistent ihre Gegner besiegt. Ähnlich kann eine Person, die nichts darüber weiß, wie man eine Antenne entwirft, die gleichmäßig über einen hemisphärischen Bereich in einem gegebenen Frequenzbereich strahlt, dennoch eine solche Antenne testen und überprüfen, ob sie wie beabsichtigt funktioniert. In beiden Fällen ist die Bestimmung was hohe Fitness ausmacht, weit einfacher (erfordert weniger Informationen) als herauszufinden wie hohe Fitness erreicht wird.

Zugegeben, auch wenn die Wahl einer Fitnessfunktion für ein gegebenes Problem weniger Informationen erfordert als die tatsächliche Lösung des Problems, das durch diese Fitnessfunktion definiert ist, benötigt es doch einige Informationen, um die Fitnessfunktion überhaupt erst zu spezifizieren, und es ist eine legitime Frage, woher diese anfänglichen Informationen stammen. Dembski kann immer noch nach dem Ursprung der menschlichen Intelligenz fragen, die uns ermöglicht, uns zu entscheiden, ein Problem zu lösen oder ein anderes, oder nach dem Ursprung der Naturgesetze des Kosmos, die es ermöglichen, dass Leben existieren und gedeihen kann und dass Evolution stattfinden kann. Dies sind gültige Fragen, und Dembski ist berechtigt, sich darüber zu wundern. Allerdings hat er an dieser Stelle – scheinbar unbemerkt von ihm selbst – von seinem ursprünglichen Argument abgerückt. Er behauptet nicht mehr, dass Evolution nicht stattfinden kann; stattdessen fragt er im Wesentlichen, warum wir in einem Universum leben, in dem Evolution stattfinden kann. Mit anderen Worten, was Dembski anscheinend nicht erkennt, ist, dass die logische Schlussfolgerung seines Arguments theistische Evolution ist. Dies ist vollständig vereinbar mit einem Gott, der (wie viele Christen, einschließlich des Evolutionsbiologen Kenneth Miller, glauben) die Evolution als sein kreatives Werkzeug verwendet und das Universum so eingerichtet hat, dass es nicht nur wahrscheinlich, sondern sicher ist.

Ich werde abschließend einige zusätzliche, geringfügige Missverständnisse aus Kapitel 4 von No Free Lunch aufklären. Zum Anfang, obwohl Dembski, im Gegensatz zu Batten, sich offensichtlich des Gebiets der Multiobjektivoptimierung bewusst ist, irrtümlicherweise behauptet er, dass „bis eine Form der Eindeutigkeit erreicht ist, kann keine Optimierung beginnen" (S. 186). Die Diskussion dieses Essays über genetische Algorithmen mit mehreren Zielen zeigt die Fehlerhaftigkeit dieser Aussage. Vielleicht haben andere Design-Techniken diese Einschränkung, aber eine der Tugenden von GAs besteht gerade darin, dass sie Kompromisse eingehen und mehrere sich gegenseitig ausschließende Ziele gleichzeitig optimieren können, und die menschlichen Aufsichtsbehörden können dann aus der endgültigen Gruppe der Pareto-optimalen Lösungen diejenige auswählen, die ihre Ziele am besten erfüllt. Eine Methode zur Zusammenführung mehrerer Kriterien in eines ist nicht notwendig.

Dembski stellt ebenfalls fest, dass GAs „sich weniger geschickt bei der Konstruktion integrierter Systeme zeigen, die mehrere Teile benötigen, um neue Funktionen zu erreichen" (S. 237). Die zahlreichen Beispiele, die in diesem Aufsatz detailliert beschrieben werden (insbesondere die Verwendung von John Koza genetischer Programmierung zur Entwicklung komplexer analoger Schaltungen), zeigen ebenfalls, dass diese Behauptung falsch ist.

Schließlich erwähnt Dembski, dass INFORMS, die Fachorganisation der Operations-Research-Gemeinschaft, GAs kaum beachtet, und dies sei „Grund zur Skepsis hinsichtlich des allgemeinen Anwendungsbereichs und der Leistungsfähigkeit der Technik" (S. 237). Doch allein weil eine bestimmte wissenschaftliche Gesellschaft GAs nicht weit verbreitet einsetzt, bedeutet dies nicht, dass solche Anwendungen anderweitig oder allgemein nicht weit verbreitet sind, und dieser Aufsatz hat sich bemüht, nachzuweisen, dass dies tatsächlich der Fall ist. Evolutionäre Techniken haben in nahezu jedem wissenschaftlichen Feld, das man nennen könnte, eine Vielzahl von Anwendungen gefunden, sowie unter viele Unternehmen im kommerziellen Sektor. Hier ist eine unvollständige Liste:

Im Gegensatz dazu befindet sich Dembski angesichts des Mangels an wissenschaftlichen Entdeckungen und Forschungsergebnissen, die durch das Intelligent Design angestoßen wurden, in einer schwachen Position, um sich über den Mangel an praktischer Anwendung zu beschweren. Das Intelligent Design ist eine leere Hypothese, die uns nichts mehr als „Ein Schöpfer hat auf irgendeine Weise zu einem bestimmten Zeitpunkt etwas getan, um dieses Ergebnis zu bewirken" sagt. Im Gegensatz dazu hat diese Abhandlung hoffentlich gezeigt, dass die Evolution eine Problemlösungsstrategie mit reichlich praktischen Anwendungen ist.

Fazit
Oben

Selbst Kreationisten finden es unmöglich zu leugnen, dass die Kombination aus Mutation und natürlicher Selektion Anpassung hervorrufen kann. Dennoch versuchen sie weiterhin, ihre Ablehnung der Evolution zu rechtfertigen, indem sie den evolutionären Prozess in zwei Kategorien einteilen – „Mikroevolution" und „Makroevolution" – und behaupten, dass nur die zweite umstritten sei und jeder beobachtbare evolutionäre Wandel lediglich ein Beispiel für die erste darstellt.

Nun sind Mikroevolution und Makroevolution Termini, die für Biologen eine Bedeutung haben; sie werden jeweils als Evolution unterhalb der Art-Ebene und Evolution auf oder oberhalb der Art-Ebene definiert. Der entscheidende Unterschied zwischen der Art, wie Kreationisten diese Begriffe verwenden, und der Art, wie Wissenschaftler sie verwenden, besteht darin, dass Wissenschaftler erkennen, dass diese beiden Begriffe im Wesentlichen denselben Prozess mit denselben Mechanismen beschreiben, der lediglich auf unterschiedlichen Ebenen wirkt. Kreationisten müssen jedoch postulieren, dass eine gewisse unüberbrückbare Lücke zwischen beiden besteht, um zu leugnen, dass die Prozesse der Veränderung und Anpassung, die wir heute beobachten, extrapoliert werden können, um die gesamte Vielfalt zu erklären, die in der lebenden Welt beobachtet wird.

Jedoch machen genetische Algorithmen diese Sichtweise unhaltbar, indem sie die grundlegende Nahtlosigkeit des evolutionären Prozesses demonstrieren. Nehmen Sie beispielsweise ein Problem, das darin besteht, einen Schaltkreis zu programmieren, der zwischen einem 1-Kilohertz- und einem 10-Kilohertz-Ton unterscheidet und entsprechend mit konstanten Ausgangsspannungen von 0 und 5 Volt reagiert. Nehmen wir an, wir haben eine Kandidatenlösung, die die beiden Töne genau unterscheiden kann, deren Ausgangssignale jedoch nicht ganz konstant sind, wie erforderlich; sie erzeugen kleine Wellenformen statt der erforderlichen unveränderlichen Spannung. Vermutlich würde nach der kreationistischen Sichtweise, diesen Schaltkreis von seinem aktuellen Zustand in die perfekte Lösung zu überführen, als „Mikroevolution" bezeichnet werden, eine kleine Veränderung innerhalb der Fähigkeit von Mutation und Selektion, diese hervorzubringen. Doch sicherlich würde ein Kreationist argumentieren, dass der Weg zu diesem gleichen Endzustand von einer völlig zufälligen Anfangsanordnung von Komponenten aus als „Makroevolution" bezeichnet werden würde und jenseits der Reichweite eines evolutionären Prozesses läge. Jedoch waren genetische Algorithmen in der Lage, beides zu bewerkstelligen: Sie entwickelten das System von einer zufälligen Anordnung zur nahezu perfekten Lösung und schließlich zur perfekten, optimalen Lösung. An keinem Schritt des Weges tauchte eine unlösbare Schwierigkeit oder eine Lücke auf, die nicht überbrückt werden konnte. Zu keinem Zeitpunkt war menschliches Eingreifen erforderlich, um einen irreduzibel komplexen Kern von Komponenten zusammenzusetzen (obwohl das fertige Produkt solch etwas enthält) oder um das sich entwickelnde System über einen schwierigen Gipfel zu „leiten". Der Schaltkreis entwickelte sich, ohne jegliche intelligente Anleitung, von einem völlig zufälligen und nicht-funktionalen Zustand in einen dicht komplexen, effizienten und optimalen Zustand. Wie kann dies nicht eine überzeugende experimentelle Demonstration der Kraft der Evolution sein?

Es wurde behauptet, dass die kulturelle Evolution des Menschen die biologische überholt hat – dass wir als Spezies einen Punkt erreicht haben, an dem wir unsere Gesellschaft, unsere Umwelt und sogar unsere Gene in einem ausreichenden Maße bewusst steuern können, um den Evolutionsprozess irrelevant zu machen. Es wurde behauptet, dass die kulturellen Launen unserer sich rasch verändernden Gesellschaft, und nicht der vergleichsweise glacial langsam verlaufende Prozess genetischer Mutation und natürlicher Selektion, heute die Fitness bestimmen. In gewissem Sinne mag dies durchaus zutreffen.

Aber in einem anderen Sinne könnte nichts weiter von der Wahrheit entfernt sein. Evolution ist ein Problemlösungsprozess, dessen Kraft wir erst beginnen zu verstehen und zu nutzen; dennoch ist sie bereits überall um uns herum am Werk, formt unsere Technologie und verbessert unser Leben, und in Zukunft werden sich diese Anwendungen nur vervielfachen. Ohne ein detailliertes Verständnis des evolutionären Prozesses wären keine der unzähligen Fortschritte möglich gewesen, die wir genetischen Algorithmen verdanken. Hier gibt es eine Lehre für diejenigen, die die Kraft der Evolution leugnen, sowie für diejenigen, die bestreiten, dass Kenntnisse darüber einen praktischen Nutzen haben. So unglaublich es auch erscheinen mag, Evolution funktioniert. Wie der Dichter Lord Byron es ausgedrückt hat: "'T's seltsam, aber wahr; denn Wahrheit ist immer seltsam, seltsamer als Fiktion."

Quellen und Ressourcen
Oben

"Adaptive Learning: Fly the Brainy Skies." Wired, Bd. 10, Nr. 3 (März 2002). Online verfügbar unter http://www.wired.com/wired/archive/10.03/everywhere.html?pg=2.

Altshuler, Edward und Derek Linden. "Design of a wire antenna using a genetic algorithm." Journal of Electronic Defense, vol.20, no.7, p.50-52 (Juli 1997).

Andre, David and Astro Teller. "Evolving team Darwin United." In RoboCup-98: Robot Soccer World Cup II, Minoru Asada and Hiroaki Kitano (eds). Lecture Notes in Computer Science, vol.1604, p.346-352. Springer-Verlag, 1999.

Andreou, Andreas, Efstratios Georgopoulos und Spiridon Likothanassis. "Kursprognosen: Ein hybrides Algorithmus auf genetisch optimierten adaptiven neuronalen Netzwerken basierend." Computational Economics, Bd.20, Nr.3, S.191-210 (Dezember 2002).

Ashley, Steven. "Engineous explores the design space." Mechanical Engineering, Februar 1992, S. 49-52.

Assion, A., T. Baumert, M. Bergt, T. Brixner, B. Kiefer, V. Seyfried, M. Strehle und G. Gerber. „Kontrolle chemischer Reaktionen durch feedback-optimierte, phasenmodulierte Femtosekunden-Laserpulse." Science, Bd. 282, S. 919–922 (30. Oktober 1998).

Au, Wai-Ho, Keith Chan, und Xin Yao. "Ein neuer evolutionärer Datenmining-Algorithmus mit Anwendungen zur Churn-Vorhersage." IEEE Transactions on Evolutionary Computation, Bd. 7, Nr. 6, S. 532-545 (Dezember 2003).

Beasley, J.E., J. Sonander und P. Havelock. "Scheduling aircraft landings at London Heathrow using a population heuristic." Journal of the Operational Research Society, vol.52, no.5, p.483-493 (Mai 2001).

Begley, Sharon und Gregory Beals. „Software au naturel." Newsweek, 8. Mai 1995, S. 70.

Benini, Ernesto und Andrea Toffolo. „Optimales Design von Horizontal-Achsen-Windkraftanlagen unter Verwendung der Blatt-Element-Theorie und evolutionärer Berechnung." Journal of Solar Energy Engineering, Bd.124, Nr.4, S.357-363 (November 2002).

Burke, E.K. und J.P. Newall. "Ein mehrstufiger evolutionärer Algorithmus für das Zeitplanproblem." IEEE Transactions on Evolutionary Computation, Band 3, Nr. 1, S. 63-74 (April 1999).

Charbonneau, Paul. "Genetische Algorithmen in der Astronomie und Astrophysik." The Astrophysical Journal Supplement Series, vol.101, p.309-334 (Dezember 1995).

Chellapilla, Kumar und David Fogel. "Entwicklung eines Experten-Checkerspiels ohne menschliches Fachwissen." IEEE Transactions on Evolutionary Computation, Band 5, Nr. 4, S. 422–428 (August 2001). Online verfügbar unter http://www.natural-selection.com/NSIPublicationsOnline.htm.

Chellapilla, Kumar und David Fogel. "Anaconda besiegt Hoyle 6-0: Eine Fallstudie zum Wettbewerb eines entwickelten Schachprogramms gegen kommerziell erhältliche Software." In Proceedings of the 2000 Congress on Evolutionary Computation, S. 857-863. IEEE Press, 2000. Online verfügbar unter http://www.natural-selection.com/NSIPublicationsOnline.htm.

Chellapilla, Kumar und David Fogel. "Verifizierung der Expertenbewertung von Anaconda durch Wettkämpfe gegen Chinook: Experimente zur Ko-Evolution eines neuronalen Checkerspielers." Neurocomputing, Bd. 42, Nr. 1-4, S. 69-86 (Januar 2002).

Chryssolouris, George und Velusamy Subramaniam. "Dynamische Planung von Fertigungswerkstätten unter Verwendung genetischer Algorithmen." Journal of Intelligent Manufacturing, Bd. 12, Nr. 3, S. 281-293 (Juni 2001).

Coale, Kristi. "Darwin in a box." Wired News, 14. Juli 1997. Online verfügbar unter http://www.wired.com/news/technology/0,1282,5152,00.html.

Coello, Carlos. "An updated survey of GA-based multiobjective optimization techniques." ACM Computing Surveys, vol.32, no.2, p.109-143 (Juni 2000).

Davidson, Clive. "Creatures from primordial silicon." New Scientist, vol.156, no.2108, p.30-35 (November 15, 1997). Online verfügbar unter http://www.newscientist.com/hottopics/ai/primordial.jsp.

Dawkins, Richard. The Blind Watchmaker: Warum die Beweise für die Evolution ein Universum ohne Design offenbaren. W.W. Norton, 1996.

Dembski, William. No Free Lunch: Warum spezifizierte Komplexität ohne Intelligenz nicht erworben werden kann. Rowman & Littlefield, 2002.

Fleming, Peter und R.C. Purshouse. "Evolutionäre Algorithmen in der Regelungstechnik: Eine Übersicht." Control Engineering Practice, Bd. 10, S. 1223-1241 (2002).

Fonseca, Carlos and Peter Fleming. "An overview of evolutionary algorithms in multiobjective optimization." Evolutionäre Berechnung, vol.3, no.1, p.1-16 (1995).

Forrest, Stephanie. "Genetische Algorithmen: Prinzipien der natürlichen Selektion angewendet auf die Berechnung." Science, Bd.261, S.872-878 (1993).

Gibbs, W. Wayt. "Programmieren mit urtümlicher Brühe." Scientific American, Oktober 1996, S. 48-50.

Gillet, Valerie. "Ansätze zur Gestaltung kombinatorischer Bibliotheken auf Basis von Reaktanten und Produkten." Journal of Computer-Aided Molecular Design, vol.16, p.371-380 (2002).

Giro, R., M. Cyrillo und D.S. Galvão. "Designing conducting polymers using genetic algorithms." Chemical Physics Letters, vol.366, no.1-2, p.170-175 (25. November 2002).

Glen, R.C. und A.W.R. Payne. "Ein genetischer Algorithmus zur automatisierten Generierung von Molekülen unter Berücksichtigung von Einschränkungen." Journal of Computer-Aided Molecular Design, Bd.9, S.181-202 (1995).

Goldberg, David. Genetische Algorithmen in der Suche, Optimierung und dem maschinellen Lernen. Addison-Wesley, 1989.

Graham-Rowe, Duncan. „Radio entsteht aus der elektronischen Suppe." New Scientist, Bd. 175, Nr. 2358, S. 19 (31. August 2002). Online verfügbar unter http://www.newscientist.com/news/news.jsp?id=ns99992732.

  • Siehe auch: Bird, Jon und Paul Layzell. "The evolved radio and its implications for modelling the evolution of novel sensors." In Proceedings of the 2002 Congress on Evolutionary Computation, S. 1836-1841.

Graham-Rowe, Duncan. "Elektronische Schaltung 'evolviert' aus Flüssigkristallen." New Scientist, vol.181, no.2440, S.21 (27. März 2004).

Haas, O.C.L., K.J. Burnham und J.A. Mills. "On improving physical selectivity in the treatment of cancer: A systems modelling and optimisation approach." Control Engineering Practice, vol.5, no.12, p.1739-1745 (Dezember 1997).

Hanne, Thomas. "Global multiobjective optimization using Evolutionary Algorithms." Journal of Heuristics, vol.6, no.3, p.347-360 (August 2000).

Haupt, Randy und Sue Ellen Haupt. Praktische genetische Algorithmen. John Wiley & Sons, 1998.

He, L. und N. Mort. "Hybride genetische Algorithmen für die Routenplanung von Backup-Netzwerken in der Telekommunikation." BT Technology Journal, Band 18, Nr. 4, S. 42-50 (Oktober 2000).

Holland, John. "Genetische Algorithmen." Scientific American, Juli 1992, S. 66-72.

Hughes, Evan und Maurice Leyland. "Verwendung mehrerer genetischer Algorithmen zur Generierung von Radar-Punktreffler-Modellen." IEEE Transactions on Evolutionary Computation, Bd. 4, Nr. 2, S. 147-163 (Juli 2000).

Jensen, Mikkel. "Erstellung robuster und flexibler Fertigungspläne mittels genetischer Algorithmen." IEEE Transactions on Evolutionary Computation, vol.7, no.3, p.275-288 (Juni 2003).

Kewley, Robert und Mark Embrechts. "Computational military tactical planning system." IEEE Transactions on Systems, Man and Cybernetics, Part C - Applications and Reviews, vol.32, no.2, p.161-171 (Mai 2002).

Kirkpatrick, S., C.D. Gelatt und M.P. Vecchi. "Optimierung durch simuliertes Ausglühen." Science, Bd.220, S.671-678 (1983).

Koza, John, Forest Bennett, David Andre und Martin Keane. Genetische Programmierung III: Darwinische Erfindung und Problemlösung. Morgan Kaufmann Publishers, 1999.

Koza, John, Martin Keane, Matthew Streeter, William Mydlowec, Jessen Yu and Guido Lanza. Genetische Programmierung IV: Routinen für menschenkonkurrenzfähige Maschinenintelligenz. Kluwer Academic Publishers, 2003.
  • Siehe auch: Koza, John, Martin Keane und Matthew Streeter. "Evolving inventions." Scientific American, Februar 2003, S. 52-59.

Keane, A.J. und S.M. Brown. „Das Design einer Satellitenantenne mit verbesserter Vibrationsleistung unter Verwendung von Genetalgorithmus-Techniken." In Angepasstes Rechnen im Ingenieurwesen und der Regelungstechnik '96 - Proceedings of the Second International Conference, I.C. Parmee (Hrsg), S. 107-113. University of Plymouth, 1996.

Lee, Yonggon und Stanislaw H. Zak. "Designing a genetic neural fuzzy antilock-brake-system controller." IEEE Transactions on Evolutionary Computation, Bd. 6, Nr. 2, S. 198-211 (April 2002).

Lemley, Brad. "Machines that think." Discover, Januar 2001, S. 75-79.

Mahfoud, Sam und Ganesh Mani. „Financial forecasting using genetic algorithms." Applied Artificial Intelligence, Bd. 10, Nr. 6, S. 543–565 (1996).

Mitchell, Melanie. Einführung in genetische Algorithmen. MIT Press, 1996.

Naik, Gautam. "Back to Darwin: In sunlight and cells, science seeks answers to high-tech puzzles." The Wall Street Journal, 16. Januar 1996, S. A1.

Obayashi, Shigeru, Daisuke Sasaki, Yukihiro Takeguchi, und Naoki Hirose. "Multiobjective evolutionary computation für die Optimierung der Form supersonischer Tragflächen." IEEE Transactions on Evolutionary Computation, vol.4, no.2, S.182-187 (Juli 2000).

Petzinger, Thomas. „Bei Deere wissen sie, dass ein verrückter Wissenschaftler das größte Asset eines Unternehmens sein kann." The Wall Street Journal, 14. Juli 1995, S. B1.

Porto, Vincent, David Fogel und Lawrence Fogel. „Alternative Trainingsmethoden für neuronale Netze." IEEE Expert, Bd. 10, Nr. 3, S. 16–22 (Juni 1995).

Rao, Srikumar. "Evolution at warp speed." Forbes, Bd. 161, Nr. 1, S. 82-83 (12. Januar 1998).

Rizki, Mateen, Michael Zmuda und Louis Tamburino. "Entwickelnde Systeme zur Mustererkennung." IEEE Transactions on Evolutionary Computation, Bd. 6, Nr. 6, S. 594–609 (Dezember 2002).

Robin, Franck, Andrea Orzati, Esteban Moreno, Otte Homan und Werner Bachtold. "Simulation und evolutionäre Optimierung der Elektronenstrahllithografie mit genetischen und Simplex-Downhill-Algorithmen." IEEE Transactions on Evolutionary Computation, Bd. 7, Nr. 1, S. 69-82 (Februar 2003).

Sagan, Carl. Broca's Brain: Reflectionen über die Romantik der Wissenschaft. Ballantine, 1979.

Sambridge, Malcolm und Kerry Gallagher. "Bestimmung des Erdbebenhypozentrums mittels genetischer Algorithmen." Bulletin der Seismologischen Gesellschaft Amerikas, Bd.83, Nr.5, S.1467-1491 (Oktober 1993).

Sasaki, Daisuke, Masashi Morikawa, Shigeru Obayashi und Kazuhiro Nakahashi. "Aerodynamische Formoptimierung von Überschallflügeln mittels adaptiver Bereichsmultiobjektiver genetischer Algorithmen." In Evolutionäre Multi-Kriterien-Optimierung: Erster internationaler Konferenz, EMO 2001, Zürich, Schweiz, März 2001: Vorträge, K. Deb, L. Theile, C. Coello, D. Corne und E. Zitler (Hrsg.). Lecture Notes in Computer Science, vol.1993, S.639-652. Springer-Verlag, 2001.

Sato, S., K. Otori, A. Takizawa, H. Sakai, Y. Ando und H. Kawamura. „Anwendung genetischer Algorithmen auf das optimale Design eines Konzerthauses." Journal of Sound and Vibration, Bd. 258, Nr. 3, S. 517–526 (2002).

Schechter, Bruce. "Darwinian Spin auf den Dieselmotor geben." The New York Times, 19. September 2000, S. F3.

Srinivas, N. und Kalyanmoy Deb. "Multiobjective optimization using nondominated sorting in genetic algorithms." Evolutionary Computation, vol.2, no.3, p.221-248 (Herbst 1994).

Soule, Terrence und Amy Ball. „Ein genetischer Algorithmus mit mehreren Leserahmen." In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference, Lee Spector und Eric Goodman (Hrsg.). Morgan Kaufmann, 2001. Online verfügbar unter http://www.cs.uidaho.edu/~tsoule/research/papers.html.

Tang, K.S., K.F. Man, S. Kwong und Q. He. "Genetische Algorithmen und ihre Anwendungen." IEEE Signal Processing Magazine, Bd. 13, Nr. 6, S. 22-37 (November 1996).

Weismann, Dirk, Ulrich Hammel, und Thomas Bäck. „Robustes Design mehrschichtiger optischer Beschichtungen mittels Evolutionärer Algorithmen." IEEE Transactions on Evolutionary Computation, Bd. 2, Nr. 4, S. 162–167 (November 1998).

Williams, Edwin, William Crossley und Thomas Lang. "Average and maximum revisit time trade studies for satellite constellations using a multiobjective genetic algorithm." Journal of the Astronautical Sciences, Bd. 49, Nr. 3, S. 385-400 (Juli-September 2001).

Zitzler, Eckart und Lothar Thiele. "Multiobjective evolutionäre Algorithmen: eine vergleichende Fallstudie und der Strength Pareto-Ansatz." IEEE Transactions on Evolutionary Computation, Bd. 3, Nr. 4, S. 257-271 (November 1999).