Im Informatik-Feld der künstlichen Intelligenz ist ein genetischer Algorithmus (GA) eine heuristische Suche, der den Prozess der natürlichen Evolution nachahmt. Das heuristisch wird alltäglich verwendet, um nützliche Lösungen von Optimierungs- und Suchproblemen zu erzeugen. Genetische Algorithmen gehören der größeren Klasse von Entwicklungsalgorithmen (EA), die Lösungen von Optimierungsproblemen mit Techniken erzeugen, die durch die natürliche Evolution, wie Erbe, Veränderung, Auswahl und Überkreuzung begeistert sind.

Methodik

In einem genetischen Algorithmus entwickelt sich eine Bevölkerung von Schnuren (genannt Chromosomen oder den Genotypen des Genoms), die Kandidat-Lösungen (genannt Personen, Wesen oder Phänotypen) zu einem Optimierungsproblem verschlüsseln, zu besseren Lösungen. Traditionell werden Lösungen in der Dualzahl als Reihen von 0s und 1s vertreten, aber andere encodings sind auch möglich. Die Evolution fängt gewöhnlich von einer Bevölkerung zufällig erzeugter Personen an und geschieht in Generationen. In jeder Generation wird die Fitness jeder Person in der Bevölkerung bewertet, vielfache Personen werden von der aktuellen Bevölkerung (gestützt auf ihrer Fitness) stochastisch ausgewählt, und haben (wiederverbunden und vielleicht zufällig verändert) modifiziert, um eine neue Bevölkerung zu bilden. Die neue Bevölkerung wird dann in der folgenden Wiederholung des Algorithmus verwendet. Allgemein endet der Algorithmus, als entweder eine maximale Zahl von Generationen erzeugt worden ist, oder ein befriedigendes Fitnessniveau ist für die Bevölkerung erreicht worden. Wenn der Algorithmus wegen einer maximalen Zahl von Generationen geendet hat, kann eine befriedigende Lösung oder darf nicht erreicht worden sein.

Genetische Algorithmen finden Anwendung in bioinformatics, phylogenetics, rechenbetonter Wissenschaft, Technik, Volkswirtschaft, Chemie, Herstellung, Mathematik, Physik und anderen Feldern.

Ein typischer genetischer Algorithmus verlangt:

1. eine genetische Darstellung des Lösungsgebiets,
2. eine Fitnessfunktion, das Lösungsgebiet zu bewerten.

Eine Standarddarstellung der Lösung ist als eine Reihe von Bit. Die Reihe anderer Typen und Strukturen kann auf im Wesentlichen dieselbe Weise verwendet werden. Das Haupteigentum, das diese genetischen Darstellungen günstig macht, besteht darin, dass ihre Teile wegen ihrer festen Größe leicht ausgerichtet werden, die einfache Überkreuzungsoperationen erleichtert. Darstellungen der variablen Länge können auch verwendet werden, aber Überkreuzungsdurchführung ist in diesem Fall komplizierter. Baumähnliche Darstellungen werden in der genetischen Programmierung erforscht, und Darstellungen der Graph-Form werden in der Entwicklungsprogrammierung erforscht.

Die Fitnessfunktion wird über die genetische Darstellung definiert und misst die Qualität der vertretenen Lösung. Die Fitnessfunktion ist immer Problem-Abhängiger. Zum Beispiel im Rucksack-Problem will man den Gesamtwert von Gegenständen maximieren, die in einem Rucksack von etwas fester Kapazität gestellt werden können. Eine Darstellung einer Lösung könnte eine Reihe von Bit sein, wo jedes Bit einen verschiedenen Gegenstand vertritt, und der Wert des Bit (0 oder 1) vertritt, ob der Gegenstand im Rucksack ist. Nicht jede solche Darstellung ist gültig, weil die Größe von Gegenständen die Kapazität des Rucksacks überschreiten kann. Die Fitness der Lösung ist die Summe von Werten aller Gegenstände im Rucksack, wenn die Darstellung, oder 0 sonst gültig ist. In einigen Problemen ist es hart oder sogar unmöglich, den Fitnessausdruck zu definieren; in diesen Fällen werden interaktive genetische Algorithmen verwendet.

Sobald die genetische Darstellung und die Fitnessfunktion definiert werden, fährt ein GA fort, eine Bevölkerung von Lösungen (gewöhnlich zufällig) zu initialisieren und dann sie durch die wiederholende Anwendung der Veränderung, Überkreuzung, Inversion und Auswahl-Maschinenbediener zu verbessern.

Initialisierung

Am Anfang werden viele individuelle Lösungen (gewöhnlich) zufällig erzeugt, um eine anfängliche Bevölkerung zu bilden. Die Bevölkerungsgröße hängt von der Natur des Problems ab, aber enthält normalerweise mehrere hundert oder Tausende von möglichen Lösungen. Traditionell wird die Bevölkerung zufällig erzeugt, die komplette Reihe von möglichen Lösungen (der Suchraum) erlaubend. Gelegentlich können die Lösungen in Gebieten "entsamt" werden, wo optimale Lösungen wahrscheinlich gefunden werden.

Auswahl

Während jeder aufeinander folgenden Generation wird ein Verhältnis der vorhandenen Bevölkerung ausgewählt, um eine neue Generation zu gebären. Individuelle Lösungen werden durch einen fitnessbasierten Prozess ausgewählt, wo passendere Lösungen (wie gemessen, durch eine Fitnessfunktion) normalerweise mit größerer Wahrscheinlichkeit ausgewählt werden. Bestimmte Auswahl-Methoden schätzen die Fitness jeder Lösung ab und wählen bevorzugt die besten Lösungen aus. Andere Methode-Rate nur eine zufällige Probe der Bevölkerung, weil der letzte Prozess sehr zeitraubend sein kann.

Fortpflanzung

Der nächste Schritt soll eine zweite Generationsbevölkerung von Lösungen von denjenigen erzeugen, die durch genetische Maschinenbediener ausgewählt sind: Überkreuzung (auch genannt Wiederkombination), und/oder Veränderung.

Für jede neue Lösung, erzeugt zu werden, wird ein Paar von "Elternteil"-Lösungen ausgewählt, um sich von der Lache ausgewählt vorher fortzupflanzen. Durch das Produzieren einer "Kinder"-Lösung mit den obengenannten Methoden der Überkreuzung und Veränderung wird eine neue Lösung geschaffen, der normalerweise viele der Eigenschaften seiner "Eltern" teilt. Neue Eltern werden für jedes neue Kind ausgewählt, und der Prozess geht weiter, bis eine neue Bevölkerung von Lösungen der passenden Größe erzeugt wird.

Obwohl Reproduktionstechnik, die auf dem Gebrauch von zwei Eltern basiert, mehr "begeisterte Biologie" ist, weist etwas Forschung darauf hin, dass mehr als zwei "Eltern" höhere Qualitätschromosomen erzeugen.

Diese Prozesse laufen schließlich auf die folgende Generationsbevölkerung von Chromosomen hinaus, die von der anfänglichen Generation verschieden ist. Allgemein wird die durchschnittliche Fitness durch dieses Verfahren für die Bevölkerung zugenommen haben, da nur die besten Organismen von der ersten Generation für die Fortpflanzung zusammen mit einem kleinen Verhältnis von weniger passenden Lösungen aus Gründen ausgewählt werden, die bereits oben erwähnt sind.

Obwohl Überkreuzung und Veränderung als die genetischen Hauptmaschinenbediener bekannt sind, ist es möglich, andere Maschinenbediener wie Umgruppierung, Kolonisationserlöschen oder Wanderung in genetischen Algorithmen zu verwenden.

Beendigung

Dieser Generational-Prozess wird wiederholt, bis eine Abbruchbedingung erreicht worden ist. Allgemeine endende Bedingungen sind:

• Eine Lösung wird gefunden, dass das minimale Kriterien befriedigt
• Die festgelegte Zahl von Generationen hat erreicht
• Zugeteiltes Budget (Berechnungszeit/Geld) hat erreicht
• Die Fitness der höchsten sich aufreihenden Lösung erreicht oder hat ein solches Plateau erreicht, dass aufeinander folgende Wiederholungen nicht mehr bessere Ergebnisse erzeugen
• Manuelle Inspektion
• Kombinationen des obengenannten

Einfaches generational genetisches Algorithmus-Verfahren:

1. Wählen Sie die anfängliche Bevölkerung von Personen
2. Bewerten Sie die Fitness jeder Person in dieser Bevölkerung
3. Wiederholen Sie sich auf dieser Generation bis zur Beendigung (Frist, genügend Fitness erreicht, usw.):
4. Wählen Sie die be-passenden Personen für die Fortpflanzung aus
5. Erziehen Sie neue Personen durch die Überkreuzung und Veränderungsoperationen, um die Nachkommenschaft zur Welt zu bringen
6. Bewerten Sie die individuelle Fitness von neuen Personen
7. Ersetzen Sie am wenigsten - passende Bevölkerung mit neuen Personen

Die Baustein-Hypothese

Genetische Algorithmen sind einfach durchzuführen, aber ihr Verhalten ist schwierig zu verstehen. Insbesondere ist es schwierig zu verstehen, warum diese Algorithmen oft beim Erzeugen von Lösungen der hohen Fitness, wenn angewandt, auf praktische Probleme erfolgreich sind. Die Baustein-Hypothese (BBH) besteht aus:

1. Eine Beschreibung eines heuristischen, der Anpassung durchführt, indem er identifiziert wird und "Bausteine", d. h. niedrige Ordnung, niedrige Diagramme der Definieren-Länge mit der obengenannten durchschnittlichen Fitness wiederverbunden wird.
2. Eine Hypothese, dass ein genetischer Algorithmus Anpassung durch implizit durchführt und effizient das heuristisch durchführend.

Goldberg beschreibt das heuristische wie folgt:

: "Kurze, niedrige Ordnung und hoch passende Diagramme werden probiert, wiederverbunden hat [hinübergegangen] und hat wiederausgefallen, um Schnuren der potenziell höheren Fitness zu bilden. In gewisser Hinsicht, indem wir mit diesen besonderen Diagrammen [die Bausteine] arbeiten, haben wir die Kompliziertheit unseres Problems reduziert; anstatt Hochleistungsschnuren zu bauen, indem wir jede denkbare Kombination versuchen, bauen wir besser und bessere Schnuren von den besten teilweisen Lösungen der Vergangenheit samplings.

: "Weil hoch passende Diagramme der niedrigen Definieren-Länge und niedrig Spiel solch eine wichtige Rolle in der Handlung von genetischen Algorithmen bestellen, haben wir ihnen bereits einen speziellen Namen: Bausteine gegeben. Da ein Kind großartige Festungen durch die Einordnung von einfachen Blöcken von Holz schafft, so tut einen genetischen Algorithmus suchen nahe optimale Leistung durch die Nebeneinanderstellung von kurzen, niedriger Ordnung, Hochleistungsdiagrammen oder Bausteinen."

Beobachtungen

Es gibt mehrere allgemeine Beobachtungen über die Generation von Lösungen spezifisch über einen genetischen Algorithmus:

• Auswahl ist klar ein wichtiger genetischer Maschinenbediener, aber Meinung wird über die Wichtigkeit von der Überkreuzung gegen die Veränderung geteilt. Einige behaupten, dass Überkreuzung am wichtigsten ist, während Veränderung nur notwendig ist, um sicherzustellen, dass potenzielle Lösungen nicht verloren werden. Andere behaupten, dass die Überkreuzung in einer größtenteils gleichförmigen Bevölkerung nur dient, um Neuerungen fortzupflanzen, die ursprünglich durch die Veränderung gefunden sind, und in einer ungleichförmigen Bevölkerung eine Überkreuzung fast immer zu einer sehr großen Veränderung gleichwertig ist (der wahrscheinlich katastrophal sein wird). Es gibt viele Verweisungen in Fogel (2006), die die Wichtigkeit von der Veränderungsbasierten Suche unterstützen.
• Als mit allen aktuellen Maschinenlernproblemen lohnt es sich, die Rahmen wie Veränderungswahrscheinlichkeit, Überkreuzungswahrscheinlichkeit und Bevölkerungsgröße abzustimmen, um angemessene Einstellungen für die Problem-Klasse zu finden, die darauf wird arbeitet. Eine sehr kleine Veränderungsrate kann zu genetischem Antrieb führen (der nicht - in der Natur ist). Eine Wiederkombinationsrate, die zu hoch ist, kann zu Frühkonvergenz des genetischen Algorithmus führen. Eine Veränderungsrate, die zu hoch ist, kann zu Verlust von guten Lösungen führen, wenn es elitäre Auswahl nicht gibt. Dort sind theoretisch, aber noch nicht praktische obere und niedrigere Grenzen für diese Rahmen, die helfen können, Auswahl zu führen.
• Häufig kann BENZIN gute Lösungen sogar für große Suchräume schnell ausfindig machen. Dasselbe ist natürlich auch für Evolutionsstrategien und Entwicklungsprogrammierung wahr.

Kritiken

Es gibt mehrere Kritiken des Gebrauches eines genetischen Algorithmus im Vergleich zu alternativen Optimierungsalgorithmen:

• Die wiederholte Fitnessfunktionseinschätzung für komplizierte Probleme ist häufig das am meisten untersagende und beschränkende Segment von künstlichen Entwicklungsalgorithmen. Die Entdeckung der optimalen Lösung komplizierter hoher dimensionaler, mehrmodaler Probleme verlangt häufig sehr teure Fitnessfunktionseinschätzungen. In echten Weltproblemen wie Strukturoptimierungsprobleme kann eine einzelne Funktionseinschätzung mehrere Stunden zu mehreren Tagen der ganzen Simulation verlangen. Typische Optimierungsmethoden können sich mit solchen Typen des Problems nicht befassen. In diesem Fall kann es notwendig sein, auf eine genaue Einschätzung zu verzichten und eine näher gekommene Fitness zu verwenden, die rechenbetont effizient ist. Es ist offenbar, dass die Fusion von ungefähren Modellen eine der viel versprechendsten Annäherungen sein kann, um GA überzeugend zu verwenden, um komplizierte echte Lebensprobleme zu beheben.
• Genetische Algorithmen klettern gut mit der Kompliziertheit nicht. D. h. wo die Zahl der Elemente, die zur Veränderung ausgestellt werden, groß ist, gibt es häufig eine Exponentialzunahme in der Suchraumgröße. Das macht es äußerst schwierig, die Technik auf Problemen wie das Entwerfen eines Motors, eines Hauses oder Flugzeugs zu verwenden. Um solche Probleme lenksam zur Entwicklungssuche zu machen, müssen sie unten in die einfachste mögliche Darstellung zerbrochen werden. Folglich sehen wir normalerweise Entwicklungsalgorithmen Designs für Anhänger-Klingen statt Motoren verschlüsseln, Gestalten statt ausführlicher Baupläne, Tragflächen statt ganzer Flugzeugsdesigns bauend. Das zweite Problem der Kompliziertheit ist das Problem dessen, wie man Teile schützt, die sich entwickelt haben, um gute Lösungen von der weiteren zerstörenden Veränderung besonders zu vertreten, wenn ihre Fitnessbewertung verlangt, dass sie sich gut mit anderen Teilen verbinden. Es ist von einigen in der Gemeinschaft darauf hingewiesen worden, dass eine Entwicklungsannäherung an entwickelte Lösungen einige der Probleme des Schutzes überwinden konnte, aber das bleibt eine offene Forschungsfrage.
• Die "bessere" Lösung ist nur im Vergleich mit anderen Lösungen. Infolgedessen ist das Halt-Kriterium in jedem Problem nicht klar.
• In vielen Problemen kann BENZIN eine Tendenz haben, zu lokalen Optima oder sogar willkürlichen Punkten aber nicht dem globalen Optimum des Problems zusammenzulaufen. Das bedeutet, dass es nicht "weiß, wie man" Kurzzeitfitness opfert, um längerfristige Fitness zu gewinnen. Die Wahrscheinlichkeit dieses Auftretens hängt von der Gestalt der Fitnesslandschaft ab: Bestimmte Probleme können einen leichten Aufstieg zu einem globalen Optimum zur Verfügung stellen, andere können es leichter für die Funktion machen, die lokalen Optima zu finden. Dieses Problem kann durch das Verwenden einer verschiedenen Fitnessfunktion, die Erhöhung der Rate der Veränderung, oder durch das Verwenden von Auswahl-Techniken erleichtert werden, die eine verschiedene Bevölkerung von Lösungen unterstützen, obwohl Kein Freier Mittagessen-Lehrsatz beweist, dass es keine allgemeine Lösung dieses Problems gibt. Eine allgemeine Technik, um Ungleichheit aufrechtzuerhalten, soll eine "Nische-Strafe" auferlegen, worin jede Gruppe von Personen der genügend Ähnlichkeit (Nische-Radius) eine Strafe hinzufügen ließ, die die Darstellung dieser Gruppe in nachfolgenden Generationen reduzieren wird, anderen (weniger ähnlichen) Personen erlaubend, in der Bevölkerung unterstützt zu werden. Dieser Trick kann jedoch abhängig von der Landschaft des Problems nicht wirksam sein. Eine andere mögliche Technik würde einfach einen Teil der Bevölkerung mit zufällig erzeugten Personen ersetzen sollen, wenn der grösste Teil der Bevölkerung einander zu ähnlich ist. Ungleichheit ist in genetischen Algorithmen wichtig (und genetische Programmierung), weil das Hinübergehen einer homogenen Bevölkerung neue Lösungen nicht nachgibt. In Evolutionsstrategien und Entwicklungsprogrammierung ist Ungleichheit wegen eines größeren Vertrauens auf der Veränderung nicht notwendig.
• Das Funktionieren auf dynamischen Dateien ist schwierig, weil Genome beginnen, bald zu Lösungen zusammenzulaufen, die für spätere Daten nicht mehr gültig sein können. Mehrere Methoden sind vorgeschlagen worden, um das durch die Erhöhung genetischer Ungleichheit irgendwie und das Verhindern früher Konvergenz, irgendeines durch die Erhöhung der Wahrscheinlichkeit der Veränderung zu beheben, wenn die Lösungsqualität (genannt ausgelöste Hyperveränderung), oder durch das gelegentliche Einführen völlig neu fällt, zufällig erzeugte Elemente in die Genlache (hat zufällige Einwanderer genannt). Wieder können Evolutionsstrategien und Entwicklungsprogrammierung mit einer so genannten "Komma-Strategie" durchgeführt werden, in der Eltern nicht unterstützt werden und neue Eltern nur von der Nachkommenschaft ausgewählt werden. Das kann auf dynamischen Problemen wirksamer sein.
• BENZIN kann Probleme nicht effektiv beheben, in denen das einzige Fitnessmaß ein einzelnes richtiges/falsches Maß (wie Entscheidungsprobleme) ist, weil es keine Weise gibt, auf der Lösung (kein Hügel zusammenzulaufen, um zu klettern). In diesen Fällen kann eine zufällige Suche eine Lösung so schnell finden wie ein GA. Jedoch, wenn die Situation der Probe des Erfolgs/Misserfolgs erlaubt, wiederholt zu werden (vielleicht) verschiedene Ergebnisse gebend, dann stellt das Verhältnis von Erfolgen zu Misserfolgen ein passendes Fitnessmaß zur Verfügung.
• Für spezifische Optimierungsprobleme und Problem-Beispiele können andere Optimierungsalgorithmen bessere Lösungen finden als genetische Algorithmen (gegeben derselbe Betrag der Berechnungszeit). Alternative und ergänzende Algorithmen schließen Evolutionsstrategien, Entwicklungsprogrammierung ein, hat das Ausglühen, die Anpassung von Gaussian, das Hügel-Klettern und die Schwarm-Intelligenz vorgetäuscht (z.B: Ameise-Kolonie-Optimierung, Partikel-Schwarm-Optimierung), und Methoden haben auf der ganzen Zahl geradlinige Programmierung gestützt. Die Frage der, falls etwa, wird Problemen genetischen Algorithmen angepasst (im Sinn, dass solche Algorithmen besser sind als andere), ist offen und umstritten.

Varianten

Der einfachste Algorithmus vertritt jedes Chromosom als wenig Schnur. Gewöhnlich können numerische Rahmen durch ganze Zahlen vertreten werden, obwohl es möglich ist, Schwimmpunkt-Darstellungen zu verwenden. Die Schwimmpunkt-Darstellung ist zu Evolutionsstrategien und Entwicklungsprogrammierung natürlich. Der Begriff von reellwertigen genetischen Algorithmen ist angeboten worden, aber ist wirklich eine falsche Bezeichnung, weil er die Baustein-Theorie nicht wirklich vertritt, die von John Henry Holland in den 1970er Jahren vorgeschlagen wurde. Diese Theorie ist nicht ohne Unterstützung obwohl, gestützt auf theoretischen und experimentellen Ergebnissen (sieh unten). Der grundlegende Algorithmus führt Überkreuzung und Veränderung am Bit-Niveau durch. Andere Varianten behandeln das Chromosom als eine Liste von Zahlen, die Indizes in einen Instruktionstisch, Knoten in einer verbundenen Liste, Kuddelmuddel, Gegenständen oder jeder anderen vorstellbaren Datenstruktur sind. Überkreuzung und Veränderung werden durchgeführt, um Datenelement-Grenzen zu respektieren. Für die meisten Datentypen können spezifische Schwankungsmaschinenbediener entworfen werden. Verschiedene chromosomale Datentypen scheinen, besser oder schlechter für verschiedene spezifische Problem-Gebiete zu arbeiten.

Wenn Darstellungen der Bit-Schnur von ganzen Zahlen verwendet werden, wird Gray, der codiert, häufig angestellt. Auf diese Weise können kleine Änderungen in der ganzen Zahl durch Veränderungen oder Überkreuzungen sogleich bewirkt werden. Wie man gefunden hat, hat das geholfen, Frühkonvergenz an so genannten Wänden von Hamming zu verhindern, in denen zu viele gleichzeitige Veränderungen (oder Überkreuzungsereignisse) vorkommen müssen, um das Chromosom zu einer besseren Lösung zu ändern.

Andere Annäherungen sind mit Verwenden-Reihe von reellwertigen Zahlen statt Bit-Schnuren verbunden, um Chromosomen zu vertreten. Theoretisch, je kleiner das Alphabet, desto besser die Leistung, aber paradoxerweise, gute Ergebnisse dabei erhalten worden sind, reellwertige Chromosomen zu verwenden.

Eine sehr erfolgreiche (geringe) Variante des allgemeinen Prozesses, eine neue Bevölkerung zu bauen, soll einigen der besseren Organismen von der aktuellen Generation erlauben, zum folgenden, unveränderten vorzutragen. Diese Strategie ist als elitäre Auswahl bekannt.

Parallele Durchführungen von genetischen Algorithmen kommen in zwei Geschmäcken. Grobkörnige parallele genetische Algorithmen nehmen eine Bevölkerung auf jedem der Computerknoten und Wanderung von Personen unter den Knoten an. Feinkörnige parallele genetische Algorithmen nehmen eine Person auf jedem Verarbeiter-Knoten an, der mit benachbarten Personen für die Auswahl und Fortpflanzung handelt.

Andere Varianten, wie genetische Algorithmen für Online-Optimierungsprobleme, führen Zeitabhängigkeit oder Geräusch in der Fitnessfunktion ein.

Genetische Algorithmen mit anpassungsfähigen Rahmen (anpassungsfähige genetische Algorithmen, AGAs) ist eine andere bedeutende und viel versprechende Variante von genetischen Algorithmen. Die Wahrscheinlichkeiten der Überkreuzung (pc) und Veränderung (Premierminister) bestimmen außerordentlich den Grad der Lösungsgenauigkeit und der Konvergenz-Geschwindigkeit, die genetische Algorithmen erhalten können. Anstatt befestigte Werte von pc und Premierminister zu verwenden, verwerten AGAs die Bevölkerungsinformation in jeder Generation und passen anpassungsfähig den pc und Premierminister an, um die Bevölkerungsungleichheit aufrechtzuerhalten sowie die Konvergenz-Kapazität zu stützen. In AGA (anpassungsfähiger genetischer Algorithmus) hängt die Anpassung von pc und Premierminister von den Fitnesswerten der Lösungen ab. In CAGA (Sammeln-basierter anpassungsfähiger genetischer Algorithmus), durch den Gebrauch der sich sammelnden Analyse, um die Optimierungsstaaten der Bevölkerung zu beurteilen, hängt die Anpassung von pc und Premierminister von diesen Optimierungsstaaten ab.

Es kann ziemlich wirksam sein, GA mit anderen Optimierungsmethoden zu verbinden. GA neigt dazu, gut ganz allgemein gute globale Lösungen, aber ziemlich ineffizient bei der Entdeckung der letzten paar Veränderungen finden zu können, das absolute Optimum zu finden. Andere Techniken (wie das einfache Hügel-Klettern) sind bei der Entdeckung absoluten Optimums in einem beschränkten Gebiet ziemlich effizient. Das Wechseln von GA und dem Hügel-Klettern kann die Leistungsfähigkeit von GA verbessern, während es den Mangel an der Robustheit des Hügel-Kletterns überwindet.

Das bedeutet, dass die Regeln der genetischen Schwankung eine verschiedene Bedeutung im natürlichen Fall haben können. Zum Beispiel - vorausgesetzt, dass Schritte in der Konsekutivordnung versorgt werden - kann das Hinübergehen mehrere Schritte von der mütterlichen DNA summieren, die mehrere Schritte von der väterlichen DNA und so weiter hinzufügt. Das ist dem Hinzufügen von Vektoren ähnlich, die wahrscheinlicher einem Kamm in der phenotypic Landschaft folgen können. So kann die Leistungsfähigkeit des Prozesses durch viele Größenordnungen vergrößert werden. Außerdem hat der Inversionsmaschinenbediener die Gelegenheit, Schritte in die Konsekutivordnung oder jede andere passende Ordnung zu Gunsten vom Überleben oder der Leistungsfähigkeit zu legen. (Sieh zum Beispiel oder Beispiel im Handlungsreisender-Problem, insbesondere der Gebrauch eines Rand-Wiederkombinationsmaschinenbedieners.)

Eine Schwankung, wo die Bevölkerung als Ganzes aber nicht seine individuellen Mitglieder entwickelt wird, ist als Genlache-Wiederkombination bekannt.

Verbindungslernen

Mehrere Schwankungen sind entwickelt worden, um zu versuchen, Leistung von BENZIN auf Problemen mit einem hohen Grad der Fitness epistasis zu verbessern, d. h. wo die Fitness einer Lösung aus aufeinander wirkenden Teilmengen seiner Variablen besteht. Solche Algorithmen haben zum Ziel zu erfahren (vor auszunutzen) diese vorteilhaften phenotypic Wechselwirkungen. Als solcher werden sie nach der Baustein-Hypothese im anpassungsfähigen Reduzieren störender Wiederkombination ausgerichtet. Prominente Beispiele dieser Annäherung schließen den mGA, GEMGA und LLGA ein.

Problem-Gebiete

Probleme, die scheinen, besonders für die Lösung durch genetische Algorithmen passend zu sein, schließen timetabling und Terminplanungsprobleme ein, und viele Terminplanungssoftwarepakete basieren auf BENZIN. BENZIN Ist auch auf die Technik angewandt worden. Genetische Algorithmen werden häufig als eine Annäherung angewandt, um globale Optimierungsprobleme zu lösen.

Als eine allgemeine Faustregel könnten genetische Algorithmen in Problem-Gebieten nützlich sein, die eine komplizierte Fitnesslandschaft haben, weil das Mischen, d. h., Veränderung in der Kombination mit der Überkreuzung, entworfen wird, um die Bevölkerung von lokalen Optima wegzuschieben, in denen ein traditioneller Hügel-Steigalgorithmus stecken bleiben könnte. Bemerken Sie, dass allgemein verwendete Überkreuzungsmaschinenbediener keine gleichförmige Bevölkerung ändern können. Veränderung allein kann ergodicity des gesamten genetischen Algorithmus-Prozesses (gesehen als eine Kette von Markov) zur Verfügung stellen.

Beispiele von durch genetische Algorithmen behobenen Problemen schließen ein: Spiegel haben vorgehabt, Sonnenlicht einem Sonnensammler einzutrichtern, Antennen haben vorgehabt, Radiosignale im Raum und Wandern-Methoden für Computerzahlen aufzunehmen. Viele ihrer Lösungen, sind verschieden von irgendetwas hoch wirksam gewesen, was ein menschlicher Ingenieur, und unergründlich betreffs erzeugt hätte, wie sie diese Lösung erreicht haben.

Geschichte

Computersimulationen der Evolution haben schon in 1954 mit der Arbeit von Nils Aall Barricelli angefangen, der den Computer am Institut für die Fortgeschrittene Studie in Princeton, New Jersey verwendete. Seine 1954-Veröffentlichung wurde nicht weit bemerkt. 1957 anfangend, hat der australische quantitative Genetiker Alex Fraser eine Reihe von Papieren auf der Simulation der künstlichen Auswahl an Organismen mit vielfachen geometrischen Orten veröffentlicht, einen messbaren Charakterzug kontrollierend. Von diesen Anfängen ist die Computersimulation der Evolution durch Biologen mehr am Anfang der 1960er Jahre üblich geworden, und die Methoden wurden in Büchern von Fraser und Burnell (1970) und Crosby (1973) beschrieben. Die Simulationen von Fraser haben alle wesentlichen Elemente von modernen genetischen Algorithmen eingeschlossen. Außerdem hat Hans-Joachim Bremermann eine Reihe von Papieren in den 1960er Jahren veröffentlicht, die auch eine Bevölkerung der Lösung von Optimierungsproblemen angenommen haben, Wiederkombination, Veränderung und Auswahl erlebend. Die Forschung von Bremermann hat auch die Elemente von modernen genetischen Algorithmen eingeschlossen. Andere beachtenswerte frühe Pioniere schließen Richard Friedberg, George Friedman und Michael Conrad ein. Viele frühe Papiere werden von Fogel (1998) nachgedruckt.

Obwohl Barricelli, in der Arbeit, die er 1963 gemeldet hat, die Evolution der Fähigkeit vorgetäuscht hatte, ein einfaches Spiel zu spielen, ist künstliche Evolution eine weit anerkannte Optimierungsmethode infolge der Arbeit von Ingo Rechenberg und Hans-Paul Schwefel in den 1960er Jahren und Anfang der 1970er Jahre geworden - die Gruppe von Rechenberg ist im Stande gewesen, komplizierte Technikprobleme durch Evolutionsstrategien zu beheben. Eine andere Annäherung war die Entwicklungsprogrammiertechnik von Lawrence J. Fogel, der vorgeschlagen wurde, um künstliche Intelligenz zu erzeugen. Entwicklungsprogrammierung ursprünglich verwendeter Zustandsmaschinen, um vorauszusagen, dass Umgebungen, und verwendete Schwankung und Auswahl die prophetische Logik optimieren. Genetische Algorithmen sind insbesondere populär durch die Arbeit von John Holland am Anfang der 1970er Jahre und besonders seines Buches Anpassung in Natürlichen und Künstlichen Systemen (1975) geworden. Seine Arbeit ist mit Studien von Zellautomaten entstanden, die von Holland und seinen Studenten an der Universität Michigans geführt sind. Holland hat ein formalisiertes Fachwerk eingeführt, für die Qualität der folgenden Generation vorauszusagen, die als der Diagramm-Lehrsatz von Holland bekannt ist. Die Forschung in BENZIN ist größtenteils theoretisch bis zur Mitte der 1980er Jahre geblieben, als Die Erste Internationale Konferenz für Genetische Algorithmen in Pittsburgh, Pennsylvanien gehalten wurde.

Da akademisches Interesse gewachsen ist, hat die dramatische Zunahme in der rechenbetonten Tischmacht praktische Anwendung der neuen Technik berücksichtigt. Gegen Ende der 1980er Jahre hat General Electric angefangen, das erste genetische Algorithmus-Produkt in der Welt, ein Großrechner-basiertes für Industrieprozesse entworfenes Werkzeug zu verkaufen. 1989 hat Axcelis, Inc. Evolver, das erste kommerzielle GA Produkt in der Welt für Tischcomputer befreit. Der Technologieschriftsteller der New York Times John Markoff hat über Evolver 1990 geschrieben.

Zusammenhängende Techniken

Elternteilfelder

Genetische Algorithmen sind ein Teilfeld:

• Entwicklungsalgorithmen
• Entwicklungscomputerwissenschaft
• Metaheuristics
• Stochastische Optimierung
• Optimierung

Zusammenhängende Felder

Entwicklungsalgorithmen

Entwicklungsalgorithmen sind ein Teilfeld der Entwicklungscomputerwissenschaft.

• Evolutionsstrategien (ES, sieh Rechenberg, 1994) entwickeln Personen mittels der Veränderung und getrennten oder Zwischenwiederkombination. ES Algorithmen werden besonders entworfen, um Probleme im Gebiet des echten Werts zu beheben. Sie verwenden Selbstanpassung, um Kontrollrahmen der Suche anzupassen. De-randomization der Selbstanpassung hat zur zeitgenössischen Kovarianz-Matrixanpassungsevolutionsstrategie (CMA-ES) geführt.
• Entwicklungsprogrammierung (EP) ist mit Bevölkerungen von Lösungen mit in erster Linie der Veränderung und der Auswahl und den willkürlichen Darstellungen verbunden. Sie verwenden Selbstanpassung, um Rahmen anzupassen, und können andere Schwankungsoperationen wie sich verbindende Information von vielfachen Eltern einschließen.
• Genetische Programmierung (GP) ist eine zusammenhängende Technik, die von John Koza verbreitet ist, in dem Computerprogramme, anstatt Rahmen zu fungieren, optimiert werden. Genetische Programmierung verwendet häufig baumbasierte innere Datenstrukturen, um die Computerprogramme für die Anpassung statt der für genetische Algorithmen typischen Listenstrukturen zu vertreten.
• Gruppierung genetischen Algorithmus (GGA) ist eine Evolution des GA, wohin der Fokus von individuellen Sachen, wie in klassischem BENZIN, zu Gruppen oder Teilmenge von Sachen ausgewechselt wird. Die Idee hinter dieser GA von Emanuel Falkenauer vorgeschlagenen Evolution ist das, einige komplizierte Probleme, a.k.a. sich sammelnde oder verteilende Probleme behebend, wo eine Reihe von Sachen in die zusammenhanglose Gruppe von Sachen auf eine optimale Weise gespalten werden muss, würde durch das Bilden von Eigenschaften der Gruppen von zu Genen gleichwertigen Sachen besser erreicht. Ähnliche Probleme schließen Behälter-Verpackung, das Linienausgleichen, Sammeln in Bezug auf ein Entfernungsmaß, gleiche Stapel usw. ein, auf dem sich klassisches BENZIN erwiesen hat, schlecht zu leisten. Das Bilden von zu Gruppen gleichwertigen Genen bezieht Chromosomen ein, die im General der variablen Länge und den speziellen genetischen Maschinenbedienern sind, die ganze Gruppen von Sachen manipulieren. Für die Behälter-Verpackung insbesondere ein GGA, der mit dem Überlegenheitskriterium von Martello und Toth gekreuzt ist, ist wohl die beste Technik bis heute.
• Interaktive Entwicklungsalgorithmen sind Entwicklungsalgorithmen diese Gebrauch-Mensch-Einschätzung. Sie werden gewöhnlich auf Gebiete angewandt, wo es hart ist, eine rechenbetonte Fitnessfunktion zu entwerfen, zum Beispiel Images, Musik, künstlerische Designs und Formen entwickelnd, um die ästhetische Vorliebe von Benutzern zu passen.

Schwarm-Intelligenz

Schwarm-Intelligenz ist ein Teilfeld der Entwicklungscomputerwissenschaft.

• Ameise-Kolonie-Optimierung (ACO) verwendet viele Ameisen (oder Agenten), um den Lösungsraum zu überqueren und lokal produktive Gebiete zu finden. Während gewöhnlich untergeordnet, genetischen Algorithmen und anderen Formen der lokalen Suche ist es im Stande zu erzeugen läuft auf Probleme hinaus, wo keine globale oder aktuelle Perspektive erhalten werden kann, und so die anderen Methoden nicht angewandt werden können.
• Partikel-Schwarm-Optimierung (PSO) ist eine rechenbetonte Methode für die Mehrparameter-Optimierung, die auch bevölkerungsbasierte Annäherung verwendet. Eine Bevölkerung (Schwarm) von Kandidat-Lösungen (Partikeln) Bewegungen im Suchraum und die Bewegung der Partikeln wird sowohl durch ihre eigene am besten bekannte Position als auch durch die globale am besten bekannte Position des Schwarms beeinflusst. Wie genetische Algorithmen hängt die PSO Methode von Information ab, die sich unter Bevölkerungsmitgliedern teilt. In einigen Problemen ist der PSO häufig mehr rechenbetont effizient als das BENZIN besonders in zwanglosen Problemen mit dauernden Variablen.
• Intelligente Wasserfälle oder der IWD Algorithmus sind ein Natur-inspirierter Optimierungsalgorithmus, der von natürlichen Wasserfällen begeistert ist, die ihre Umgebung ändern, um den fast optimalen oder optimalen Pfad zu ihrem Bestimmungsort zu finden. Das Gedächtnis ist das Bett des Flusses, und was durch die Wasserfälle modifiziert wird, ist der Betrag von Boden auf dem Bett des Flusses.

Andere Entwicklungsrechenalgorithmen

Entwicklungsberechnung ist ein Teilfeld der metaheuristic Methoden.

• Harmonie-Suche (HS) ist ein Algorithmus, der die Handlungsweisen von Musikern im Prozess der Improvisation nachahmt.
• Algorithmus von Memetic (MA), auch genannt hybriden genetischen Algorithmus unter anderen, ist eine relativ neue Entwicklungsmethode, wo lokale Suche während des Entwicklungszyklus angewandt wird. Die Idee von memetic Algorithmen kommt aus memes, den verschieden von Genen, selbst anpassen kann. In einigen Problem-Gebieten, wie man zeigt, sind sie effizienter als traditionelle Entwicklungsalgorithmen.
• Bakteriologische Algorithmen (BA), die durch die Entwicklungsökologie und, mehr besonders, bakteriologische Anpassung begeistert sind. Entwicklungsökologie ist die Studie von lebenden Organismen im Zusammenhang ihrer Umgebung mit dem Ziel des Entdeckens, wie sie sich anpassen. Sein grundlegendes Konzept ist, dass in einer heterogenen Umgebung Sie eine Person nicht finden können, die die ganze Umgebung passt. Also, Sie müssen am Bevölkerungsniveau vernünftig urteilen. Es wird auch geglaubt, dass BAs auf komplizierte Positionierungsprobleme (Antennen für Mobiltelefone, städtische Planung, und so weiter) oder Datenbergwerk erfolgreich angewandt werden konnte.
• Kultureller Algorithmus (CA) besteht aus dem Bevölkerungsbestandteil, der fast zu diesem des genetischen Algorithmus und außerdem identisch ist, ein Kenntnisse-Bestandteil hat den Glaube-Raum genannt.
• Anpassung von Gaussian (normale oder natürliche Anpassung, abgekürzter NA, um Verwirrung mit GA zu vermeiden), ist für die Maximierung des Produktionsertrags von Signalverarbeitungssystemen beabsichtigt. Es kann auch für die gewöhnliche parametrische Optimierung verwendet werden. Es verlässt sich auf einen bestimmten Lehrsatz, der für alle Gebiete der Annehmbarkeit und den ganzen Vertrieb von Gaussian gültig ist. Die Leistungsfähigkeit von NA verlässt sich auf die Informationstheorie und einen bestimmten Lehrsatz der Leistungsfähigkeit. Seine Leistungsfähigkeit wird definiert, weil durch die Arbeit geteilte Information die Information bekommen musste. Weil NA Mittelfitness aber nicht die Fitness der Person maximiert, wird die Landschaft solch geglättet, dass Täler zwischen Spitzen verschwinden können. Deshalb hat es einen bestimmten "Ehrgeiz", lokale Spitzen in der Fitnesslandschaft zu vermeiden. NA kann gut auch scharfe Kämme durch die Anpassung der Moment-Matrix besteigen, weil NA die Unordnung (durchschnittliche Information) Gaussian maximieren kann, der gleichzeitig die unveränderliche Mittelfitness behält.

Andere metaheuristic Methoden

Methoden von Metaheuristic fallen weit gehend innerhalb von stochastischen Optimierungsmethoden.

• Vorgetäuschte Ausglühen (SA) ist eine zusammenhängende globale Optimierungstechnik, die den Suchraum durch die Prüfung zufälliger Veränderungen auf einer individuellen Lösung überquert. Eine Veränderung, die Fitness vergrößert, wird immer akzeptiert. Eine Veränderung, die Fitness senkt, wird probabilistically akzeptiert, der auf dem Unterschied in der Fitness und einem abnehmenden Temperaturparameter gestützt ist. Im SA Sprachgebrauch spricht man davon, die niedrigste Energie statt der maximalen Fitness zu suchen. SA kann auch innerhalb eines GA Standardalgorithmus durch das Starten mit einer relativ hohen Rate der Veränderung und das Verringern davon mit der Zeit entlang einer gegebenen Liste verwendet werden.
• Tabu Suche (TS) ist dem vorgetäuschten Ausglühen in dieser Beide-Überquerung der Lösungsraum durch die Prüfung von Veränderungen einer individuellen Lösung ähnlich. Während vorgetäuscht, erzeugt das Ausglühen nur eine veränderte Lösung, tabu Suche erzeugt viele veränderte Lösungen und bewegt sich zur Lösung mit der niedrigsten Energie von denjenigen, die erzeugt sind. Um zu verhindern Rad zu fahren und größere Bewegung durch den Lösungsraum zu fördern, wird eine tabu Liste teilweiser oder vollständiger Lösungen aufrechterhalten. Es wird verboten, sich zu einer Lösung zu bewegen, die Elemente der tabu Liste enthält, die aktualisiert wird, weil die Lösung den Lösungsraum überquert.
• Die Optimierung von Extremal (EO) Verschieden von BENZIN, die mit einer Bevölkerung von Kandidat-Lösungen, EO arbeiten, entwickelt eine einzelne Lösung und macht lokale Modifizierungen zu den schlechtesten Bestandteilen. Das verlangt, dass eine passende Darstellung ausgewählt wird, der individuellen Lösungsbestandteilen erlaubt, ein Qualitätsmaß ("Fitness") zugeteilt zu werden. Der Regierungsgrundsatz hinter diesem Algorithmus ist der der auftauchenden Verbesserung durch auswählend umziehende Bestandteile der niedrigen Qualität und das Ersetzen von ihnen mit einem zufällig ausgewählten Bestandteil. Das ist entschieden uneins mit einem GA, der gute Lösungen in einem Versuch auswählt, bessere Lösungen zu machen.

Andere stochastische Optimierungsmethoden

• Die Methode des Quer-Wärmegewichtes (CE) erzeugt Kandidat-Lösungen über einen parametrisierten Wahrscheinlichkeitsvertrieb. Die Rahmen werden über die Quer-Wärmegewicht-Minimierung aktualisiert, um bessere Proben in der folgenden Wiederholung zu erzeugen.
• Reaktive Suchoptimierung (RSO) verteidigt die Integration von subsymbolischen Maschinenlerntechniken in die Suchheuristik, um komplizierte Optimierungsprobleme zu lösen. Das Wort reaktive Hinweise bei einer bereiten Antwort auf Ereignisse während der Suche durch eine innere Online-Feed-Back-Schleife für die Selbsteinstimmung von kritischen Rahmen. Methodiken von Interesse für die Reaktive Suche schließen das Maschinenlernen und die Statistik, im besonderen Verstärkungslernen, aktiv oder dem Anfragenlernen, den Nervennetzen und der Meta-Heuristik ein.

Siehe auch

• Liste von genetischen Algorithmus-Anwendungen
• Fortpflanzung des Diagramms
• Universaler Darwinismus

Bibliografie

• Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, offenherzig (1998) genetische Programmierung - eine Einführung, Morgan Kaufmann, San Francisco, Kalifornien
• Goldberg, David E (1989), genetische Algorithmen in Suche, Optimierung und dem Maschinenlernen, Kluwer akademische Herausgeber, Boston, Massachusetts
• Goldberg, David E (2002), das Design der Neuerung: Lehren von und für fähige genetische Algorithmen, Addison-Wesley, das Lesen, Massachusetts
• Fogel, David B (2006), Entwicklungsberechnung: Zu einer neuen Philosophie der Maschinenintelligenz, IEEE Presse, Piscataway, New Jersey. Die dritte Ausgabe
• Holland, John H (1975), Anpassung in natürlichen und künstlichen Systemen, Universität der Michiganer Presse, Laube von Ann
• Koza, John (1992), Genetische Programmierung: Auf der Programmierung von Computern mittels der Zuchtwahl, MIT Presse. Internationale Standardbuchnummer 0-262-11170-5
• Michalewicz, Zbigniew (1999), genetische Algorithmen + Datenstrukturen = Evolutionsprogramme, Springer-Verlag.
• Mitchell, Melanie, (1996), eine Einführung in genetische Algorithmen, MIT Presse, Cambridge, Massachusetts
• Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.
• Schmitt, Lothar M; Nehaniv, Chrystopher L; Fujii, Robert H (1998), Geradlinige Analyse von genetischen Algorithmen, Theoretische Informatik 208: 111-148
• Schmitt, Lothar M (2001), Theorie von Genetischen Algorithmen, Theoretische Informatik 259: 1-61
• Schmitt, Lothar M (2004), Theorie von Genetischen Algorithmen II: Modelle für genetische Maschinenbediener über die Darstellung des Schnur-Tensor von Bevölkerungen und Konvergenz zu globalen Optima für die willkürliche Fitness fungieren unter dem Schuppen, Theoretische Informatik 310: 181-231
• Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (Doktorarbeit). Nachgedruckt von Birkhäuser (1977).
• Vose, Michael D (1999), der einfache genetische Algorithmus: Fundamente und Theorie, MIT Presse, Cambridge, Massachusetts
• Whitley, D. (1994). Ein genetischer Algorithmus-Tutorenkurs. Statistik und Computerwissenschaft 4, 65-85.
• Hingston, Philip F.; Barone, Luigi C.; Michalewicz, Zbigniew (2008) Design durch die Evolution: Fortschritte in Entwicklungsdesign:297
• Eiben, Agoston E.; Schmied, James E. (2003) Einführung in die Entwicklungscomputerwissenschaft

Außenverbindungen

Mittel

• DigitalBiology.NET Vertikaler Suchmotor für GA/GP Mittel
• Genetische Algorithmen Versehen Die Seite Mit einem Inhaltsverzeichnis, die Genetisches Programmiernotizbuch einem strukturierten Quellenzeigestock zu Webseiten im genetischen Algorithmus-Feld zur Verfügung stellt

Tutorenkurse

• Genetische Algorithmus-Computerprogramme, die "sich" auf Weisen "entwickeln", die Zuchtwahl ähneln, können komplizierte Probleme beheben sogar ihre Schöpfer verstehen Keine ausgezeichnete Einführung in GA durch John Holland und mit einer Anwendung auf das Dilemma des Gefangenen völlig
• Ein GA interaktiver Online-Demonstrant, um sich zu üben oder zu erfahren, wie ein GA arbeitet. Erfahren Sie nach und nach oder beobachten Sie globale Konvergenz in Gruppe, Änderungsbevölkerungsgröße, Überkreuzungsrate, Veränderungsrate und Auswahl-Mechanismus, und fügen Sie Einschränkungen hinzu.
• Ein Genetischer Algorithmus-Tutorenkurs durch die Informatik-Abteilung von Darrell Whitley Colorado Staatliche Universität Ein ausgezeichneter Tutorenkurs mit viel Theorie
• "Hauptsache von Metaheuristics", 2009 (225 p). Freier offener Text von Sean Luke.
• Globale Optimierungsalgorithmen - Theorie und Anwendung
• "Demystifying Genetische Algorithmen" Tutorenkurs darauf, wie Genetische Algorithmen mit Beispielen arbeiten.

Beispiele

• Einführung in Genetische Algorithmen mit dem interaktiven Java applets. Um mit BENZIN online zu experimentieren.
• Böse Disziplin-Beispiel-Anwendungen für BENZIN mit Verweisungen.
• Ein interaktiver applet, der sich entwickelnde Fahrzeuge zeigt.