Genetischer Algorithmus – Wikipedia

Posted on by
before-content-x4

Kompetitiver Algorithmus zum Durchsuchen eines Problemraums

Die 2006 NASA ST5 Raumfahrzeugantenne. Diese komplizierte Form wurde von einem evolutionären Computerdesignprogramm gefunden, um das beste Strahlungsmuster zu erzeugen. Es ist als weiterentwickelte Antenne bekannt.
 after-content-x4

In der Informatik und Operations Research, a genetischen Algorithmus (GA) ist eine Metaheuristik, die vom Prozess der natürlichen Selektion inspiriert ist und zur größeren Klasse der evolutionären Algorithmen (EA) gehört. Genetische Algorithmen werden häufig verwendet, um qualitativ hochwertige Lösungen für Optimierungs- und Suchprobleme zu generieren, indem auf biologisch inspirierte Operatoren wie Mutation, Crossover und Selektion zurückgegriffen wird.

Methodik[edit]

Optimierungsprobleme[edit]

In einem genetischen Algorithmus wird eine Population von Kandidatenlösungen (Individuen, Kreaturen oder Phänotypen genannt) für ein Optimierungsproblem zu besseren Lösungen entwickelt. Jede Kandidatenlösung hat eine Reihe von Eigenschaften (ihre Chromosomen oder ihr Genotyp), die mutiert und verändert werden können. Traditionell werden Lösungen binär als Zeichenfolgen von 0 und 1 dargestellt, es sind jedoch auch andere Codierungen möglich.

Die Evolution beginnt normalerweise mit einer Population zufällig generierter Individuen und ist ein iterativer Prozess, wobei die Population in jeder Iteration als a bezeichnet wird Generation. In jeder Generation wird die Fitness jedes Einzelnen in der Bevölkerung bewertet; Die Fitness ist normalerweise der Wert der Zielfunktion in dem zu lösenden Optimierungsproblem. Die passenderen Individuen werden stochastisch aus der aktuellen Population ausgewählt, und das Genom jedes Individuums wird modifiziert (rekombiniert und möglicherweise zufällig mutiert), um eine neue Generation zu bilden. Die neue Generation von Kandidatenlösungen wird dann in der nächsten Iteration des Algorithmus verwendet. Im Allgemeinen wird der Algorithmus beendet, wenn entweder eine maximale Anzahl von Generationen erzeugt wurde oder ein zufriedenstellendes Fitnessniveau für die Bevölkerung erreicht wurde.

Ein typischer genetischer Algorithmus erfordert:

  1. eine genetische Darstellung der Lösungsdomäne,
  2. eine Fitnessfunktion zur Bewertung der Lösungsdomäne.

Eine Standarddarstellung jeder Kandidatenlösung ist ein Array von Bits. Arrays anderer Typen und Strukturen können im Wesentlichen auf die gleiche Weise verwendet werden. Die Haupteigenschaft, die diese genetischen Darstellungen bequem macht, besteht darin, dass ihre Teile aufgrund ihrer festen Größe leicht ausgerichtet werden können, was einfache Überkreuzungsoperationen erleichtert. Darstellungen mit variabler Länge können ebenfalls verwendet werden, aber die Crossover-Implementierung ist in diesem Fall komplexer. Baumähnliche Darstellungen werden in der genetischen Programmierung untersucht, und grafische Darstellungen werden in der evolutionären Programmierung untersucht. Bei der Programmierung der Genexpression wird eine Mischung aus linearen Chromosomen und Bäumen untersucht.

after-content-x4

Sobald die genetische Repräsentation und die Fitnessfunktion definiert sind, initialisiert eine GA eine Population von Lösungen und verbessert sie dann durch wiederholte Anwendung der Mutations-, Crossover-, Inversions- und Selektionsoperatoren.

Initialisierung[edit]

Die Bevölkerungsgröße hängt von der Art des Problems ab, enthält jedoch in der Regel mehrere Hundert oder Tausende möglicher Lösungen. Oft wird die anfängliche Grundgesamtheit zufällig generiert, wodurch die gesamte Bandbreite möglicher Lösungen (der Suchraum) berücksichtigt wird. Gelegentlich können die Lösungen in Bereichen “ausgesät” werden, in denen wahrscheinlich optimale Lösungen gefunden werden.

Auswahl[edit]

Während jeder nachfolgenden Generation wird ein Teil der bestehenden Population ausgewählt, um eine neue Generation zu züchten. Individuelle Lösungen werden durch a ausgewählt Fitness-basiert Prozess, bei dem fitter Lösungen (gemessen anhand einer Fitnessfunktion) in der Regel eher ausgewählt werden. Bestimmte Auswahlmethoden bewerten die Eignung jeder Lösung und wählen vorzugsweise die besten Lösungen aus. Andere Methoden bewerten nur eine zufällige Stichprobe der Bevölkerung, da der erstere Prozess sehr zeitaufwändig sein kann.

Die Fitnessfunktion wird über die genetische Repräsentation definiert und misst die Qualität der dargestellten Lösung. Die Fitnessfunktion ist immer problemabhängig. Zum Beispiel möchte man beim Rucksackproblem den Gesamtwert von Objekten maximieren, die in einen Rucksack mit fester Kapazität gesteckt werden können. Eine Darstellung einer Lösung kann ein Array von Bits sein, wobei jedes Bit ein anderes Objekt darstellt und der Wert des Bits (0 oder 1) angibt, ob sich das Objekt im Rucksack befindet oder nicht. Nicht jede solche Darstellung ist gültig, da die Größe der Objekte die Kapazität des Rucksacks überschreiten kann. Das Fitness der Lösung ist die Summe der Werte aller Objekte im Rucksack, wenn die Darstellung gültig ist, oder 0, wenn dies nicht der Fall ist.

Bei einigen Problemen ist es schwierig oder sogar unmöglich, den Fitnessausdruck zu definieren. In diesen Fällen kann eine Simulation verwendet werden, um den Fitnessfunktionswert eines Phänotyps zu bestimmen (z. B. wird die rechnergestützte Fluiddynamik verwendet, um den Luftwiderstand eines Fahrzeugs zu bestimmen, dessen Form als Phänotyp codiert ist), oder es werden sogar interaktive genetische Algorithmen verwendet.

Genetische Operatoren[edit]

Der nächste Schritt besteht darin, eine Population von Lösungen der zweiten Generation aus den durch eine Kombination genetischer Operatoren ausgewählten Lösungen zu generieren: Crossover (auch als Rekombination bezeichnet) und Mutation.

Für jede neue zu produzierende Lösung wird ein Paar “Eltern” -Lösungen zur Züchtung aus dem zuvor ausgewählten Pool ausgewählt. Durch die Herstellung einer “Kind” -Lösung unter Verwendung der oben genannten Methoden der Überkreuzung und Mutation wird eine neue Lösung geschaffen, die typischerweise viele der Merkmale ihrer “Eltern” teilt. Für jedes neue Kind werden neue Eltern ausgewählt, und der Prozess wird fortgesetzt, bis eine neue Population von Lösungen geeigneter Größe generiert wird. Obwohl Reproduktionsmethoden, die auf der Verwendung von zwei Elternteilen basieren, eher “biologisch inspiriert” sind, gibt es einige Untersuchungen[3][4] legt nahe, dass mehr als zwei “Eltern” Chromosomen höherer Qualität erzeugen.

Diese Prozesse führen letztendlich zu einer Chromosomenpopulation der nächsten Generation, die sich von der ursprünglichen Generation unterscheidet. Im Allgemeinen hat sich die durchschnittliche Fitness durch dieses Verfahren für die Population erhöht, da nur die besten Organismen der ersten Generation für die Zucht ausgewählt werden, zusammen mit einem kleinen Anteil weniger geeigneter Lösungen. Diese weniger geeigneten Lösungen gewährleisten die genetische Vielfalt innerhalb des genetischen Pools der Eltern und damit die genetische Vielfalt der nachfolgenden Kindergeneration.

Die Meinung ist geteilt über die Bedeutung von Crossover gegenüber Mutation. In Fogel (2006) gibt es viele Referenzen, die die Bedeutung der mutationsbasierten Suche unterstützen.

Obwohl Crossover und Mutation als die wichtigsten genetischen Operatoren bekannt sind, ist es möglich, andere Operatoren wie Umgruppierung, Kolonisierung-Extinktion oder Migration in genetischen Algorithmen zu verwenden.[citation needed]

Es lohnt sich, Parameter wie die Mutationswahrscheinlichkeit, die Überkreuzungswahrscheinlichkeit und die Populationsgröße zu optimieren, um angemessene Einstellungen für die Problemklasse zu finden, an der gearbeitet wird. Eine sehr geringe Mutationsrate kann zu einer genetischen Drift führen (die nicht ergodischer Natur ist). Eine zu hohe Rekombinationsrate kann zu einer vorzeitigen Konvergenz des genetischen Algorithmus führen. Eine zu hohe Mutationsrate kann zum Verlust guter Lösungen führen, sofern keine elitäre Selektion angewendet wird. Eine angemessene Populationsgröße stellt eine ausreichende genetische Vielfalt für das jeweilige Problem sicher, kann jedoch zu einer Verschwendung von Rechenressourcen führen, wenn ein Wert festgelegt wird, der größer als erforderlich ist.

Heuristik[edit]

Zusätzlich zu den oben genannten Hauptoperatoren können andere Heuristiken verwendet werden, um die Berechnung schneller oder robuster zu machen. Das Speziation Heuristik bestraft Überkreuzung zwischen zu ähnlichen Kandidatenlösungen; Dies fördert die Bevölkerungsvielfalt und trägt dazu bei, eine vorzeitige Konvergenz zu einer weniger optimalen Lösung zu verhindern.[5][6]

Beendigung[edit]

Dieser Generationsprozess wird wiederholt, bis eine Beendigungsbedingung erreicht ist. Übliche Kündigungsbedingungen sind:

  • Es wird eine Lösung gefunden, die Mindestkriterien erfüllt
  • Feste Anzahl von Generationen erreicht
  • Zugewiesenes Budget (Rechenzeit / Geld) erreicht
  • Die Fitness der Lösung mit dem höchsten Rang erreicht oder hat ein Plateau erreicht, sodass aufeinanderfolgende Iterationen keine besseren Ergebnisse mehr liefern
  • Manuelle Inspektion
  • Kombinationen der oben genannten

Die Bausteinhypothese[edit]

Genetische Algorithmen sind einfach zu implementieren, aber ihr Verhalten ist schwer zu verstehen. Insbesondere ist es schwer zu verstehen, warum es diesen Algorithmen häufig gelingt, Lösungen mit hoher Fitness zu generieren, wenn sie auf praktische Probleme angewendet werden. Die Bausteinhypothese (BBH) besteht aus:

  1. Eine Beschreibung einer Heuristik, die eine Anpassung durch Identifizieren und Rekombinieren von “Bausteinen” durchführt, dh Schemata niedriger Ordnung mit geringer definierter Länge und überdurchschnittlicher Fitness.
  2. Eine Hypothese, dass ein genetischer Algorithmus eine Anpassung durch implizite und effiziente Implementierung dieser Heuristik durchführt.

Goldberg beschreibt die Heuristik wie folgt:

“Schemata mit kurzer, niedriger Ordnung und hoher Anpassung werden abgetastet und neu kombiniert [crossed over]und neu abgetastet, um Saiten mit potenziell höherer Fitness zu bilden. In gewisser Weise durch die Arbeit mit diesen bestimmten Schemata [the building blocks]haben wir die Komplexität unseres Problems reduziert; Anstatt Hochleistungs-Strings zu erstellen, indem wir jede erdenkliche Kombination ausprobieren, konstruieren wir immer bessere Strings aus den besten Teillösungen vergangener Samples.
“Weil hochpassende Schemata von geringer Definitionslänge und niedriger Ordnung eine so wichtige Rolle bei der Wirkung genetischer Algorithmen spielen, haben wir ihnen bereits einen besonderen Namen gegeben: Bausteine. So wie ein Kind durch die Anordnung einfacher Blöcke großartige Festungen schafft Holz, so sucht ein genetischer Algorithmus eine nahezu optimale Leistung durch das Nebeneinander von kurzen Schemata niedriger Ordnung, hoher Leistung oder Bausteinen. “

Trotz des fehlenden Konsenses über die Gültigkeit der Bausteinhypothese wurde sie im Laufe der Jahre konsequent bewertet und als Referenz verwendet. Beispielsweise wurden viele Schätzungen von Verteilungsalgorithmen vorgeschlagen, um eine Umgebung bereitzustellen, in der die Hypothese gelten würde.[8][9] Obwohl für einige Problemklassen gute Ergebnisse berichtet wurden, bleibt die Skepsis hinsichtlich der Allgemeinheit und / oder Praktikabilität der Bausteinhypothese als Erklärung für die Effizienz der GA bestehen. In der Tat gibt es einen angemessenen Arbeitsaufwand, der versucht, seine Grenzen unter dem Gesichtspunkt der Schätzung von Verteilungsalgorithmen zu verstehen.[10][11][12]

Einschränkungen[edit]

Die Verwendung eines genetischen Algorithmus unterliegt im Vergleich zu alternativen Optimierungsalgorithmen Einschränkungen:

  • Die wiederholte Bewertung der Fitnessfunktion bei komplexen Problemen ist häufig das unerschwinglichste und einschränkendste Segment künstlicher evolutionärer Algorithmen. Um die optimale Lösung für komplexe hochdimensionale, multimodale Probleme zu finden, sind häufig sehr teure Fitnessfunktionsbewertungen erforderlich. Bei realen Problemen wie Strukturoptimierungsproblemen kann eine einzelne Funktionsbewertung mehrere Stunden bis mehrere Tage der vollständigen Simulation erfordern. Typische Optimierungsmethoden können solche Probleme nicht lösen. In diesem Fall kann es erforderlich sein, auf eine genaue Bewertung zu verzichten und eine ungefähre Fitness zu verwenden, die rechnerisch effizient ist. Es ist offensichtlich, dass die Zusammenführung von Näherungsmodellen einer der vielversprechendsten Ansätze sein kann, um GA überzeugend zur Lösung komplexer realer Probleme einzusetzen.
  • Genetische Algorithmen lassen sich nicht gut mit der Komplexität skalieren. Das heißt, wenn die Anzahl der Elemente, die einer Mutation ausgesetzt sind, groß ist, nimmt die Größe des Suchraums häufig exponentiell zu. Dies macht es äußerst schwierig, die Technik bei Problemen wie dem Entwurf eines Motors, eines Hauses oder eines Flugzeugs anzuwenden. Um solche Probleme für die evolutionäre Suche zugänglich zu machen, müssen sie in eine möglichst einfache Darstellung zerlegt werden. Daher sehen wir normalerweise evolutionäre Algorithmen, die Konstruktionen für Lüfterflügel anstelle von Triebwerken, Gebäudeformen anstelle detaillierter Baupläne und Tragflächen anstelle ganzer Flugzeugkonstruktionen codieren. Das zweite Problem der Komplexität ist die Frage, wie Teile, die sich entwickelt haben, um gute Lösungen darzustellen, vor weiteren zerstörerischen Mutationen geschützt werden können, insbesondere wenn ihre Fitnessbewertung erfordert, dass sie sich gut mit anderen Teilen kombinieren lassen.
  • Die “bessere” Lösung ist nur im Vergleich zu anderen Lösungen. Infolgedessen ist das Stoppkriterium nicht bei jedem Problem klar.
  • Bei vielen Problemen tendieren GAs eher zu lokalen Optima oder sogar zu beliebigen Punkten als zum globalen Optimum des Problems. Dies bedeutet, dass es nicht “weiß”, wie man kurzfristige Fitness opfert, um längerfristige Fitness zu erlangen. Die Wahrscheinlichkeit, dass dies auftritt, hängt von der Form der Fitnesslandschaft ab: Bestimmte Probleme können einen einfachen Aufstieg zu einem globalen Optimum ermöglichen, andere können es der Funktion erleichtern, die lokalen Optima zu finden. Dieses Problem kann durch Verwendung einer anderen Fitnessfunktion, Erhöhung der Mutationsrate oder durch Verwendung von Auswahltechniken, die eine vielfältige Population von Lösungen aufrechterhalten, gelindert werden.[13] obwohl das No Free Lunch Theorem[14] beweist, dass es für dieses Problem keine allgemeine Lösung gibt. Eine übliche Technik zur Aufrechterhaltung der Vielfalt besteht darin, eine “Nischenstrafe” zu verhängen, bei der jeder Gruppe von Personen mit ausreichender Ähnlichkeit (Nischenradius) eine Strafe hinzugefügt wird, die die Repräsentation dieser Gruppe in nachfolgenden Generationen verringert und andere (weniger ähnliche) zulässt ) Personen, die in der Bevölkerung erhalten bleiben sollen. Dieser Trick ist jedoch je nach Landschaft des Problems möglicherweise nicht effektiv. Eine andere mögliche Technik wäre, einfach einen Teil der Bevölkerung durch zufällig erzeugte Individuen zu ersetzen, wenn der größte Teil der Bevölkerung einander zu ähnlich ist. Diversität ist bei genetischen Algorithmen (und bei der genetischen Programmierung) wichtig, da das Überqueren einer homogenen Population keine neuen Lösungen liefert. In Evolutionsstrategien und in der evolutionären Programmierung ist Diversität aufgrund einer stärkeren Abhängigkeit von Mutationen nicht wesentlich.
  • Die Bearbeitung dynamischer Datensätze ist schwierig, da die Genome frühzeitig zu Lösungen konvergieren, die für spätere Daten möglicherweise nicht mehr gültig sind. Es wurden verschiedene Methoden vorgeschlagen, um dies zu beheben, indem die genetische Vielfalt irgendwie erhöht und eine frühe Konvergenz verhindert wird, entweder indem die Wahrscheinlichkeit einer Mutation erhöht wird, wenn die Lösungsqualität sinkt (genannt) ausgelöste Hypermutation) oder durch gelegentliches Einführen völlig neuer, zufällig erzeugter Elemente in den Genpool (genannt zufällige Einwanderer). Auch hier können Evolutionsstrategien und evolutionäre Programmierung mit einer sogenannten “Kommastrategie” implementiert werden, bei der Eltern nicht gepflegt werden und neue Eltern nur aus Nachkommen ausgewählt werden. Dies kann bei dynamischen Problemen effektiver sein.
  • GAs können Probleme nicht effektiv lösen, bei denen die einzige Fitnessmaßnahme eine einzelne richtige / falsche Maßnahme ist (wie Entscheidungsprobleme), da es keine Möglichkeit gibt, auf die Lösung zu konvergieren (kein Hügel zum Klettern). In diesen Fällen kann eine zufällige Suche eine Lösung so schnell finden wie eine GA. Wenn die Situation jedoch ermöglicht, dass der Erfolgs- / Misserfolgsversuch wiederholt wird und (möglicherweise) unterschiedliche Ergebnisse liefert, bietet das Verhältnis von Erfolg zu Misserfolg ein geeignetes Fitnessmaß.
  • Für bestimmte Optimierungsprobleme und Problemfälle können andere Optimierungsalgorithmen hinsichtlich der Konvergenzgeschwindigkeit effizienter sein als genetische Algorithmen. Alternative und komplementäre Algorithmen umfassen Evolutionsstrategien, evolutionäre Programmierung, simuliertes Tempern, Gaußsche Anpassung, Bergsteigen und Schwarmintelligenz (z. B. Ameisenkolonieoptimierung, Partikelschwarmoptimierung) und Methoden, die auf ganzzahliger linearer Programmierung basieren. Die Eignung genetischer Algorithmen hängt von der Kenntnis des Problems ab. Bekannte Probleme haben oft bessere, spezialisiertere Ansätze.

Varianten[edit]

Chromosomendarstellung[edit]

Der einfachste Algorithmus repräsentiert jedes Chromosom als Bitfolge. In der Regel können numerische Parameter durch Ganzzahlen dargestellt werden, obwohl Gleitkomma-Darstellungen verwendet werden können. Die Gleitkomma-Darstellung ist für Evolutionsstrategien und evolutionäre Programmierung selbstverständlich. Der Begriff der realwertigen genetischen Algorithmen wurde angeboten, ist jedoch eine Fehlbezeichnung, da er nicht wirklich die von John Henry Holland in den 1970er Jahren vorgeschlagene Bausteintheorie darstellt. Diese Theorie ist jedoch nicht ohne Unterstützung, basierend auf theoretischen und experimentellen Ergebnissen (siehe unten). Der Basisalgorithmus führt Crossover und Mutation auf Bitebene durch. Andere Varianten behandeln das Chromosom als eine Liste von Zahlen, die Indizes in einer Anweisungstabelle, Knoten in einer verknüpften Liste, Hashes, Objekte oder jede andere vorstellbare Datenstruktur sind. Crossover und Mutation werden durchgeführt, um Datenelementgrenzen zu respektieren. Für die meisten Datentypen können bestimmte Variationsoperatoren entworfen werden. Verschiedene chromosomale Datentypen scheinen für verschiedene spezifische Problembereiche besser oder schlechter zu funktionieren.

Wenn Bit-String-Darstellungen von ganzen Zahlen verwendet werden, wird häufig eine Gray-Codierung verwendet. Auf diese Weise können kleine Änderungen in der Ganzzahl leicht durch Mutationen oder Überkreuzungen beeinflusst werden. Es wurde festgestellt, dass dies dazu beiträgt, eine vorzeitige Konvergenz bei sogenannten zu verhindern Wände hämmern, bei denen zu viele gleichzeitige Mutationen (oder Crossover-Ereignisse) auftreten müssen, um das Chromosom in eine bessere Lösung umzuwandeln.

Andere Ansätze umfassen die Verwendung von Arrays mit reellen Zahlen anstelle von Bitfolgen zur Darstellung von Chromosomen. Ergebnisse aus der Schematheorie legen nahe, dass die Leistung im Allgemeinen umso besser ist, je kleiner das Alphabet ist. Für Forscher war es jedoch zunächst überraschend, dass mit der Verwendung von Chromosomen mit echtem Wert gute Ergebnisse erzielt wurden. Dies wurde als die Menge der realen Werte in einer endlichen Population von Chromosomen als Bildung von a erklärt virtuelles Alphabet (wenn Selektion und Rekombination dominieren) mit einer viel geringeren Kardinalität, als dies von einer Gleitkomma-Darstellung zu erwarten wäre.[15][16]

Eine Erweiterung der für den genetischen Algorithmus zugänglichen Problemdomäne kann durch komplexere Codierung der Lösungspools erhalten werden, indem mehrere Arten heterogen codierter Gene zu einem Chromosom verkettet werden.[17] Dieser spezielle Ansatz ermöglicht die Lösung von Optimierungsproblemen, die sehr unterschiedliche Definitionsdomänen für die Problemparameter erfordern. Beispielsweise kann bei Problemen der kaskadierten Reglerabstimmung die interne Schleifenreglerstruktur zu einem herkömmlichen Regler mit drei Parametern gehören, während die externe Schleife einen Sprachregler (wie ein Fuzzy-System) implementieren könnte, der eine inhärent andere Beschreibung hat. Diese spezielle Form der Codierung erfordert einen speziellen Crossover-Mechanismus, der das Chromosom abschnittsweise rekombiniert, und ist ein nützliches Werkzeug für die Modellierung und Simulation komplexer adaptiver Systeme, insbesondere von Evolutionsprozessen.

Elitismus[edit]

Eine praktische Variante des allgemeinen Prozesses zum Aufbau einer neuen Population besteht darin, den besten Organismen der aktuellen Generation unverändert auf den nächsten zu übertragen. Diese Strategie ist bekannt als elitäre Auswahl und garantiert, dass die von der GA erhaltene Lösungsqualität nicht von einer Generation zur nächsten abnimmt.[18]

Parallele Implementierungen[edit]

Parallele Implementierungen genetischer Algorithmen gibt es in zwei Varianten. Grobkörnige parallele genetische Algorithmen setzen eine Population auf jedem der Computerknoten und die Migration von Individuen zwischen den Knoten voraus. Feinkörnige parallele genetische Algorithmen setzen auf jedem Prozessorknoten ein Individuum voraus, das mit benachbarten Individuen zur Auswahl und Reproduktion zusammenarbeitet. Andere Varianten, wie genetische Algorithmen für Online-Optimierungsprobleme, führen zu Zeitabhängigkeit oder Rauschen in der Fitnessfunktion.

Adaptive GAs[edit]

Genetische Algorithmen mit adaptiven Parametern (adaptive genetische Algorithmen, AGAs) sind eine weitere bedeutende und vielversprechende Variante genetischer Algorithmen. Die Wahrscheinlichkeiten von Crossover (pc) und Mutation (pm) bestimmen maßgeblich den Grad der Lösungsgenauigkeit und die Konvergenzgeschwindigkeit, die genetische Algorithmen erzielen können. Anstatt feste Werte von zu verwenden pc und UhrAGAs nutzen die Bevölkerungsinformationen in jeder Generation und passen die adaptiv an pc und Uhr um die Bevölkerungsvielfalt zu erhalten und die Konvergenzkapazität aufrechtzuerhalten. In AGA (adaptiver genetischer Algorithmus),[19] die Einstellung von pc und Uhr hängt von den Fitnesswerten der Lösungen ab. Im CAGA (Clustering-basierter adaptiver genetischer Algorithmus),[20] durch die Verwendung der Clusteranalyse zur Beurteilung der Optimierungszustände der Bevölkerung wird die Anpassung von pc und Uhr hängt von diesen Optimierungszuständen ab. Es kann sehr effektiv sein, GA mit anderen Optimierungsmethoden zu kombinieren. GA ist in der Regel recht gut darin, allgemein gute globale Lösungen zu finden, aber ziemlich ineffizient darin, die letzten Mutationen zu finden, um das absolute Optimum zu finden. Andere Techniken (wie einfaches Bergsteigen) sind sehr effizient, um in einer begrenzten Region ein absolutes Optimum zu finden. Abwechselndes GA und Bergsteigen können die Effizienz von GA verbessern[citation needed] während die mangelnde Robustheit des Bergsteigens überwunden wird.

Dies bedeutet, dass die Regeln der genetischen Variation im natürlichen Fall eine andere Bedeutung haben können. Zum Beispiel kann – vorausgesetzt, dass Schritte in aufeinanderfolgender Reihenfolge gespeichert werden – das Überkreuzen eine Anzahl von Schritten von der mütterlichen DNA summieren, indem eine Anzahl von Schritten von der väterlichen DNA hinzugefügt wird und so weiter. Dies ist wie das Hinzufügen von Vektoren, die eher einem Kamm in der phänotypischen Landschaft folgen können. Somit kann die Effizienz des Prozesses um viele Größenordnungen erhöht werden. Darüber hinaus hat der Inversionsoperator die Möglichkeit, Schritte in aufeinanderfolgender Reihenfolge oder in einer anderen geeigneten Reihenfolge zugunsten des Überlebens oder der Effizienz zu platzieren.[21]

Eine Variation, bei der sich die Population als Ganzes und nicht ihre einzelnen Mitglieder entwickelt, wird als Genpoolrekombination bezeichnet.

Es wurde eine Reihe von Variationen entwickelt, um zu versuchen, die Leistung von GAs bei Problemen mit einem hohen Grad an Fitness-Epistase zu verbessern, dh wenn die Fitness einer Lösung aus der Interaktion von Teilmengen ihrer Variablen besteht. Solche Algorithmen zielen darauf ab, diese vorteilhaften phänotypischen Wechselwirkungen (vor dem Ausnutzen) zu lernen. Als solche stimmen sie mit der Bausteinhypothese überein, indem sie die störende Rekombination adaptiv reduzieren. Prominente Beispiele für diesen Ansatz sind die mGA,[22] GEMGA[23] und LLGA.[24]

Problemdomänen[edit]

Zu den Problemen, die für die Lösung durch genetische Algorithmen besonders geeignet zu sein scheinen, gehören Zeitplan- und Planungsprobleme, und viele Planungssoftwarepakete basieren auf GAs[citation needed]. GAs wurden auch auf das Engineering angewendet[25] und die Länge der psychologischen Fragebögen zu reduzieren.[26] Genetische Algorithmen werden häufig als Ansatz zur Lösung globaler Optimierungsprobleme eingesetzt.

Als allgemeine Faustregel können genetische Algorithmen in Problembereichen nützlich sein, die eine komplexe Fitnesslandschaft aufweisen, da das Mischen, dh die Mutation in Kombination mit Crossover, die Bevölkerung von lokalen Optima wegbewegt, damit ein traditioneller Bergsteigeralgorithmus stecken bleibt Beachten Sie, dass häufig verwendete Crossover-Operatoren keine einheitliche Grundgesamtheit ändern können. Eine Mutation allein kann eine Ergodizität des gesamten genetischen Algorithmusprozesses liefern (als Markov-Kette angesehen).

Beispiele für Probleme, die durch genetische Algorithmen gelöst werden, sind: Spiegel, die Sonnenlicht zu einem Sonnenkollektor leiten sollen,[27] Antennen zur Aufnahme von Funksignalen im Weltraum,[28] Gehmethoden für Computerfiguren,[29] Optimale Auslegung aerodynamischer Körper in komplexen Strömungsfeldern[30]

In seinem Algorithmus-Design-Handbuch, Skiena rät von genetischen Algorithmen für jede Aufgabe ab:

[I]Es ist ziemlich unnatürlich, Anwendungen in Bezug auf genetische Operatoren wie Mutation und Crossover auf Bitstrings zu modellieren. Die Pseudobiologie erhöht die Komplexität zwischen Ihnen und Ihrem Problem. Zweitens dauern genetische Algorithmen bei nicht trivialen Problemen sehr lange. […] [T]Die Analogie zur Evolution – wo bedeutende Fortschritte erforderlich sind [sic] Millionen von Jahren – kann durchaus angemessen sein.

[…]

Ich bin nie auf ein Problem gestoßen, bei dem mir genetische Algorithmen der richtige Weg waren, es anzugreifen. Außerdem habe ich noch nie Rechenergebnisse mit genetischen Algorithmen gesehen, die mich positiv beeindruckt haben. Halten Sie sich an das simulierte Tempern für Ihre heuristischen Such-Voodoo-Anforderungen.

– –Steven Skiena[31]::267

Geschichte[edit]

1950 schlug Alan Turing eine “Lernmaschine” vor, die den Prinzipien der Evolution entsprechen würde.[32] Die Computersimulation der Evolution begann bereits 1954 mit der Arbeit von Nils Aall Barricelli, der den Computer am Institute for Advanced Study in Princeton, New Jersey, verwendete.[33][34] Seine Veröffentlichung von 1954 wurde nicht allgemein wahrgenommen. Ab 1957[35] Der australische quantitative Genetiker Alex Fraser veröffentlichte eine Reihe von Arbeiten zur Simulation der künstlichen Selektion von Organismen mit mehreren Loci, die ein messbares Merkmal steuern. Von diesen Anfängen an wurde die Computersimulation der Evolution durch Biologen in den frühen 1960er Jahren immer häufiger, und die Methoden wurden in Büchern von Fraser und Burnell (1970) beschrieben.[36] und Crosby (1973).[37] Frasers Simulationen umfassten alle wesentlichen Elemente moderner genetischer Algorithmen. Darüber hinaus veröffentlichte Hans-Joachim Bremermann in den 1960er Jahren eine Reihe von Arbeiten, in denen auch eine Reihe von Lösungen für Optimierungsprobleme vorgestellt wurden, die einer Rekombination, Mutation und Selektion unterzogen wurden. Bremermanns Forschung umfasste auch die Elemente moderner genetischer Algorithmen.[38] Andere bemerkenswerte frühe Pioniere sind Richard Friedberg, George Friedman und Michael Conrad. Viele frühe Arbeiten wurden von Fogel (1998) nachgedruckt.[39]

Obwohl Barricelli in seiner Arbeit, über die er 1963 berichtete, die Entwicklung der Fähigkeit simuliert hatte, ein einfaches Spiel zu spielen,[40]Die künstliche Evolution wurde erst durch die Arbeit von Ingo Rechenberg und Hans-Paul Schwefel in den 1960er und frühen 1970er Jahren zu einer weithin anerkannten Optimierungsmethode. Die Gruppe von Rechenberg konnte komplexe technische Probleme durch Evolutionsstrategien lösen.[41][42][43][44] Ein anderer Ansatz war die evolutionäre Programmiertechnik von Lawrence J. Fogel, die zur Erzeugung künstlicher Intelligenz vorgeschlagen wurde. Bei der evolutionären Programmierung wurden ursprünglich Finite-State-Maschinen zur Vorhersage von Umgebungen verwendet und Variationen und Auswahl zur Optimierung der Vorhersagelogik verwendet. Insbesondere genetische Algorithmen wurden durch die Arbeit von John Holland in den frühen 1970er Jahren und insbesondere durch sein Buch populär Anpassung in natürlichen und künstlichen Systemen (1975). Seine Arbeit entstand aus Studien über zelluläre Automaten, die von Holland und seinen Studenten an der Universität von Michigan durchgeführt wurden. Holland führte einen formalisierten Rahmen zur Vorhersage der Qualität der nächsten Generation ein, der als Hollands Schemasatz bekannt ist. Die Forschung in GAs blieb bis Mitte der 1980er Jahre weitgehend theoretisch, als in Pittsburgh, Pennsylvania, die erste internationale Konferenz über genetische Algorithmen stattfand.

Kommerzielle Produkte[edit]

In den späten 1980er Jahren begann General Electric mit dem Verkauf des weltweit ersten genetischen Algorithmusprodukts, eines auf Mainframes basierenden Toolkits für industrielle Prozesse.[45]

1989 veröffentlichte Axcelis, Inc. Evolver, das weltweit erste kommerzielle GA-Produkt für Desktop-Computer. Der Technologie-Autor der New York Times, John Markoff, schrieb[46] über Evolver im Jahr 1990, und es blieb der einzige interaktive kommerzielle genetische Algorithmus bis 1995.[47] Evolver wurde 1997 an Palisade verkauft, in mehrere Sprachen übersetzt und befindet sich derzeit in der 6. Version.[48] Seit den 1990er Jahren hat MATLAB drei heuristische Algorithmen zur derivatfreien Optimierung (simuliertes Tempern, Partikelschwarmoptimierung, genetischer Algorithmus) und zwei direkte Suchalgorithmen (Simplex-Suche, Mustersuche) eingebaut.[49]

Verwandte Techniken[edit]

Übergeordnete Felder[edit]

Genetische Algorithmen sind ein Unterfeld:

Verwandte Felder[edit]

Evolutionäre Algorithmen[edit]

Evolutionäre Algorithmen sind ein Teilgebiet des evolutionären Rechnens.

  • Evolutionsstrategien (ES, siehe Rechenberg, 1994) entwickeln Individuen durch Mutation und intermediäre oder diskrete Rekombination. ES-Algorithmen wurden speziell entwickelt, um Probleme im Real-Value-Bereich zu lösen.[50] Sie verwenden die Selbstanpassung, um die Steuerparameter der Suche anzupassen. Die De-Randomisierung der Selbstanpassung hat zur zeitgenössischen Covariance Matrix Adaptation Evolution Strategy (CMA-ES) geführt.
  • Die evolutionäre Programmierung (EP) umfasst Populationen von Lösungen mit hauptsächlich Mutation und Selektion sowie willkürlichen Darstellungen. Sie verwenden die Selbstanpassung zum Anpassen von Parametern und können andere Variationsoperationen umfassen, z. B. das Kombinieren von Informationen von mehreren Eltern.
  • Die Schätzung des Verteilungsalgorithmus (EDA) ersetzt herkömmliche Reproduktionsoperatoren durch modellgesteuerte Operatoren. Solche Modelle werden aus der Bevölkerung unter Verwendung von Techniken des maschinellen Lernens gelernt und als probabilistische grafische Modelle dargestellt, aus denen neue Lösungen entnommen werden können[51][52] oder aus geführter Frequenzweiche generiert.[53]
  • Die Genexpressionsprogrammierung (GEP) verwendet auch Populationen von Computerprogrammen. Diese komplexen Computerprogramme werden in einfacheren linearen Chromosomen fester Länge codiert, die anschließend als Expressionsbäume ausgedrückt werden. Expressionsbäume oder Computerprogramme entwickeln sich, weil die Chromosomen auf ähnliche Weise wie die kanonische GA mutiert und rekombiniert werden. Dank der speziellen Organisation der GEP-Chromosomen führen diese genetischen Veränderungen jedoch immer zu gültigen Computerprogrammen.[54]
  • Genetische Programmierung (GP) ist eine von John Koza verbreitete Technik, bei der Computerprogramme anstelle von Funktionsparametern optimiert werden. Bei der genetischen Programmierung werden häufig baumbasierte interne Datenstrukturen verwendet, um die Computerprogramme zur Anpassung anstelle der für genetische Algorithmen typischen Listenstrukturen darzustellen.
  • Der gruppengenetische Algorithmus (GGA) ist eine Weiterentwicklung der GA, bei der der Fokus von einzelnen Elementen, wie bei klassischen GAs, auf Gruppen oder Teilmengen von Elementen verlagert wird.[55] Die Idee hinter dieser von Emanuel Falkenauer vorgeschlagenen GA-Entwicklung ist die Lösung einiger komplexer Probleme, auch bekannt als Clustering oder Partitionierung Probleme, bei denen eine Reihe von Elementen auf optimale Weise in disjunkte Gruppen von Elementen aufgeteilt werden muss, sollten besser dadurch erreicht werden, dass die Eigenschaften der Elementgruppen den Genen gleichgestellt werden. Zu diesen Problemen gehören das Packen von Behältern, das Ausgleichen von Linien, das Clustering in Bezug auf ein Abstandsmaß, gleiche Stapel usw., bei denen sich klassische GAs als schlecht erwiesen haben. Um Gene äquivalent zu Gruppen zu machen, sind Chromosomen mit im Allgemeinen variabler Länge und spezielle genetische Operatoren erforderlich, die ganze Gruppen von Gegenständen manipulieren. Insbesondere für das Verpacken von Behältern ist eine GGA, die mit dem Dominanzkriterium von Martello und Toth hybridisiert ist, wohl die bisher beste Technik.
  • Interaktive evolutionäre Algorithmen sind evolutionäre Algorithmen, die die menschliche Bewertung verwenden. Sie werden normalerweise auf Bereiche angewendet, in denen es schwierig ist, eine rechnergestützte Fitnessfunktion zu entwerfen, z. B. die Entwicklung von Bildern, Musik, künstlerischen Designs und Formen, um den ästhetischen Vorlieben der Benutzer zu entsprechen.

Schwarmintelligenz[edit]

Schwarmintelligenz ist ein Teilgebiet des evolutionären Rechnens.

  • Optimierung der Ameisenkolonie (ACO) verwendet viele Ameisen (oder Agenten), die mit einem Pheromonmodell ausgestattet sind, um den Lösungsraum zu durchqueren und lokal produktive Bereiche zu finden. Obwohl als Schätzung des Verteilungsalgorithmus angesehen,[56]
  • Die Partikelschwarmoptimierung (PSO) ist eine Berechnungsmethode für die Mehrparameteroptimierung, die auch einen bevölkerungsbasierten Ansatz verwendet. Eine Population (Schwarm) von Kandidatenlösungen (Partikeln) bewegt sich im Suchraum, und die Bewegung der Partikel wird sowohl von ihrer eigenen bekanntesten Position als auch von der weltweit bekanntesten Position des Schwarms beeinflusst. Wie genetische Algorithmen hängt die PSO-Methode vom Informationsaustausch zwischen den Bevölkerungsmitgliedern ab. Bei einigen Problemen ist das PSO häufig rechnerisch effizienter als die GAs, insbesondere bei uneingeschränkten Problemen mit kontinuierlichen Variablen.[57]

Andere evolutionäre Rechenalgorithmen[edit]

Die evolutionäre Berechnung ist ein Teilgebiet der metaheuristischen Methoden.

  • Der Electimize-Algorithmus ist ein evolutionärer Algorithmus, der das Phänomen des Elektronenflusses und der elektrischen Leitfähigkeit simuliert. Einige aktuelle Forschungen haben gezeigt, dass Electimize bei der Lösung von NP-harten Optimierungsproblemen effizienter ist als herkömmliche evolutionäre Algorithmen. Der Algorithmus bietet eine höhere Kapazität für die umfassende Suche im Lösungsraum und die Identifizierung global optimaler Alternativen. Im Gegensatz zu anderen evolutionären Algorithmen bewertet Electimize die Qualität der Werte in der Lösungszeichenfolge unabhängig.[58]
  • Memetischer Algorithmus (MA), oft genannt hybrider genetischer Algorithmus ist unter anderem eine bevölkerungsbasierte Methode, bei der Lösungen auch lokalen Verbesserungsphasen unterliegen. Die Idee der memetischen Algorithmen stammt von Memen, die sich im Gegensatz zu Genen anpassen können. In einigen Problembereichen wird gezeigt, dass sie effizienter sind als herkömmliche evolutionäre Algorithmen.
  • Bakteriologische Algorithmen (BA), inspiriert von der Evolutionsökologie und insbesondere der bakteriologischen Anpassung. Evolutionsökologie ist die Untersuchung lebender Organismen im Kontext ihrer Umwelt mit dem Ziel herauszufinden, wie sie sich anpassen. Das Grundkonzept besteht darin, dass es in einer heterogenen Umgebung keine Person gibt, die zur gesamten Umgebung passt. Man muss also auf Bevölkerungsebene argumentieren. Es wird auch angenommen, dass BAs erfolgreich bei komplexen Positionierungsproblemen (Antennen für Mobiltelefone, Stadtplanung usw.) oder Data Mining eingesetzt werden können.[59]
  • Der kulturelle Algorithmus (CA) besteht aus der Populationskomponente, die fast identisch mit der des genetischen Algorithmus ist, und zusätzlich aus einer Wissenskomponente, die als Glaubensraum bezeichnet wird.
  • Differential Evolution (DS), inspiriert von der Migration von Superorganismen.[60]
  • Die Gaußsche Anpassung (normale oder natürliche Anpassung, abgekürzt NA, um Verwechslungen mit GA zu vermeiden) dient der Maximierung der Herstellungsausbeute von Signalverarbeitungssystemen. Es kann auch für die gewöhnliche parametrische Optimierung verwendet werden. Es beruht auf einem bestimmten Satz, der für alle Bereiche der Akzeptanz und alle Gaußschen Verteilungen gilt. Die Effizienz von NA beruht auf der Informationstheorie und einem bestimmten Effizienzsatz. Seine Effizienz ist definiert als Information geteilt durch die Arbeit, die erforderlich ist, um die Information zu erhalten.[61] Da NA eher die mittlere Fitness als die Fitness des Einzelnen maximiert, wird die Landschaft so geglättet, dass Täler zwischen Gipfeln verschwinden können. Daher hat es einen gewissen “Ehrgeiz”, lokale Spitzen in der Fitnesslandschaft zu vermeiden. NA ist auch gut darin, scharfe Kämme durch Anpassung der Momentenmatrix zu besteigen, da NA die Störung (Durchschnittsinformation) des Gaußschen maximieren und gleichzeitig die mittlere Fitness konstant halten kann.

Andere metaheuristische Methoden[edit]

Metaheuristische Methoden fallen weitgehend unter stochastische Optimierungsmethoden.

  • Simulated Annealing (SA) ist eine verwandte globale Optimierungstechnik, die den Suchraum durchläuft, indem zufällige Mutationen an einer einzelnen Lösung getestet werden. Eine Mutation, die die Fitness erhöht, wird immer akzeptiert. Eine Mutation, die die Fitness senkt, wird wahrscheinlich aufgrund des Unterschieds in der Fitness und eines abnehmenden Temperaturparameters akzeptiert. Im SA-Sprachgebrauch spricht man davon, die niedrigste Energie anstelle der maximalen Fitness zu suchen. SA kann auch innerhalb eines Standard-GA-Algorithmus verwendet werden, indem mit einer relativ hohen Mutationsrate begonnen und diese im Laufe der Zeit nach einem bestimmten Zeitplan verringert wird.
  • Die Tabu-Suche (TS) ähnelt dem simulierten Tempern dahingehend, dass beide den Lösungsraum durchqueren, indem sie Mutationen einer einzelnen Lösung testen. Während simuliertes Tempern nur eine mutierte Lösung erzeugt, erzeugt die Tabu-Suche viele mutierte Lösungen und bewegt sich zu der Lösung mit der niedrigsten Energie der erzeugten. Um das Radfahren zu verhindern und eine größere Bewegung durch den Lösungsraum zu fördern, wird eine Tabu-Liste mit Teillösungen oder vollständigen Lösungen geführt. Es ist verboten, zu einer Lösung zu wechseln, die Elemente der Tabu-Liste enthält, die aktualisiert wird, wenn die Lösung den Lösungsbereich durchquert.
  • Extremal Optimization (EO) Im Gegensatz zu GAs, die mit einer Population von Kandidatenlösungen arbeiten, entwickelt EO eine einzige Lösung und nimmt lokale Änderungen an den schlechtesten Komponenten vor. Dies erfordert die Auswahl einer geeigneten Darstellung, die es ermöglicht, einzelnen Lösungskomponenten ein Qualitätsmaß (“Fitness”) zuzuweisen. Das maßgebliche Prinzip hinter diesem Algorithmus ist das von emergent Verbesserung durch selektives Entfernen von Komponenten geringer Qualität und Ersetzen durch eine zufällig ausgewählte Komponente. Dies steht entschieden im Widerspruch zu einer GA, die gute Lösungen auswählt, um bessere Lösungen zu finden.

Andere stochastische Optimierungsmethoden[edit]

  • Die Cross-Entropy (CE) -Methode generiert Kandidatenlösungen über eine parametrisierte Wahrscheinlichkeitsverteilung. Die Parameter werden durch Kreuzentropieminimierung aktualisiert, um in der nächsten Iteration bessere Abtastwerte zu generieren.
  • Die reaktive Suchoptimierung (RSO) befürwortet die Integration sub-symbolischer Techniken des maschinellen Lernens in Suchheuristiken zur Lösung komplexer Optimierungsprobleme. Das Wort reaktiv weist auf eine schnelle Reaktion auf Ereignisse während der Suche durch eine interne Online-Rückkopplungsschleife zur Selbstoptimierung kritischer Parameter hin. Zu den für die reaktive Suche interessanten Methoden gehören maschinelles Lernen und Statistiken, insbesondere Verstärkungslernen, aktives Lernen oder Abfragenlernen, neuronale Netze und Metaheuristiken.

Siehe auch[edit]

Verweise[edit]

  1. ^ Eiben, AE et al. (1994). “Genetische Algorithmen mit Rekombination mehrerer Elternteile”. PPSN III: Vorträge der Internationalen Konferenz über evolutionäre Berechnungen. Die dritte Konferenz zur parallelen Problemlösung aus der Natur: 78–87. ISBN 3-540-58484-6.
  2. ^ Ting, Chuan-Kang (2005). “Zur mittleren Konvergenzzeit von genetischen Algorithmen mit mehreren Elternteilen ohne Selektion”. Fortschritte im künstlichen Leben: 403–412. ISBN 978-3-540-28848-0.
  3. ^ Deb, Kalyanmoy; Spears, William M. (1997). “C6.2: Speziationsmethoden”. Handbuch der evolutionären Berechnung. Institut für Physikverlag. S2CID 3547258.
  4. ^ Shir, Ofer M. (2012). “Niching in evolutionären Algorithmen”. In Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (Hrsg.). Handbuch des natürlichen Rechnens. Springer Berlin Heidelberg. S. 1035–1069. doi:10.1007 / 978-3-540-92910-9_32. ISBN 9783540929093.
  5. ^ Harik, Georges R.; Lobo, Fernando G.; Sastry, Kumara (1. Januar 2006). Verknüpfungslernen durch probabilistische Modellierung im Extended Compact Genetic Algorithm (ECGA). Skalierbare Optimierung durch probabilistische Modellierung. Studien in Computational Intelligence. 33. S. 39–61. doi:10.1007 / 978-3-540-34954-9_3. ISBN 978-3-540-34953-2.
  6. ^ Pelikan, Martin; Goldberg, David E.; Cantú-Paz, Erick (1. Januar 1999). BOA: Der Bayes’sche Optimierungsalgorithmus. Vorträge der 1. Jahreskonferenz über genetische und evolutionäre Berechnungen – Band 1. Gecco’99. S. 525–532. ISBN 9781558606111.
  7. ^ Sarg, David; Smith, Robert E. (1. Januar 2008). Verknüpfungslernen bei der Schätzung von Verteilungsalgorithmen. Verknüpfung in der evolutionären Berechnung. Studien in Computational Intelligence. 157. S. 141–156. doi:10.1007 / 978-3-540-85068-7_7. ISBN 978-3-540-85067-0.
  8. ^ Echegoyen, Carlos; Mendiburu, Alexander; Santana, Roberto; Lozano, Jose A. (8. November 2012). “Zur Taxonomie von Optimierungsproblemen bei der Schätzung von Verteilungsalgorithmen”. Evolutionsberechnung. 21 (3): 471–495. doi:10.1162 / EVCO_a_00095. ISSN 1063-6560. PMID 23136917. S2CID 26585053.
  9. ^ Sadowski, Krzysztof L.; Bosman, Peter AN; Thierens, Dirk (1. Januar 2013). Zur Nützlichkeit der Verknüpfungsverarbeitung zur Lösung von MAX-SAT. Vorträge der 15. Jahreskonferenz über genetische und evolutionäre Berechnungen. Gecco ’13. S. 853–860. doi:10.1145 / 2463372.2463474. hdl:1874/290291. ISBN 9781450319638. S2CID 9986768.
  10. ^ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad Hadi (19. November 2012). “Ein effizienter Algorithmus zur Funktionsoptimierung: modifizierter Stammzellenalgorithmus”. Mitteleuropäisches Journal of Engineering. 3 (1): 36–50. doi:10.2478 / s13531-012-0047-8.
  11. ^ Wolpert, DH, Macready, WG, 1995. Keine Theoreme zum freien Mittagessen zur Optimierung. Santa Fe Institut, SFI-TR-05-010, Santa Fe.
  12. ^ Goldberg, David E. (1991). “Die Theorie der virtuellen Alphabete”. Parallele Problemlösung aus der Natur. Parallele Problemlösung aus der Natur, Vorlesungsunterlagen in der Informatik. Vorlesungsunterlagen in Informatik. 496. S. 13–22. doi:10.1007 / BFb0029726. ISBN 978-3-540-54148-6.
  13. ^ Janikow, CZ; Michalewicz, Z. (1991). “Ein experimenteller Vergleich von Binär- und Gleitkomma-Darstellungen in genetischen Algorithmen” (PDF). Vorträge der vierten internationalen Konferenz über genetische Algorithmen: 31–36. Abgerufen 2. Juli 2013.
  14. ^ Patrascu, M.; Stancu, AF; Pop, F. (2014). “HELGA: ein heterogener codierender lebensechter genetischer Algorithmus für die Modellierung und Simulation der Populationsentwicklung”. Soft Computing. 18 (12): 2565–2576. doi:10.1007 / s00500-014-1401-y. S2CID 29821873.
  15. ^ Baluja, Shumeet; Caruana, Rich (1995). Entfernen der Genetik aus dem genetischen Standardalgorithmus (PDF). ICML.
  16. ^ Srinivas, M.; Patnaik, L. (1994). “Adaptive Wahrscheinlichkeiten von Crossover und Mutation in genetischen Algorithmen” (PDF). IEEE-Transaktionen zu System, Mensch und Kybernetik. 24 (4): 656–667. doi:10.1109 / 21.286385.
  17. ^ Zhang, J.; Chung, H.; Lo, WL (2007). “Clustering-basierte adaptive Crossover- und Mutationswahrscheinlichkeiten für genetische Algorithmen”. IEEE-Transaktionen zur evolutionären Berechnung. 11 (3): 326–335. doi:10.1109 / TEVC.2006.880727. S2CID 2625150.
  18. ^ Siehe zum Beispiel Evolution auf den Punkt gebracht Archiviert 15. April 2016 an der Wayback-Maschine oder Beispiel bei einem Problem mit reisenden Verkäufern, insbesondere die Verwendung eines Kantenrekombinationsoperators.
  19. ^ Goldberg, DE; Korb, B.; Deb, K. (1989). “Messy Genetic Algorithms: Motivationsanalyse und erste Ergebnisse”. Komplexe Systeme. 5 (3): 493–530.
  20. ^ Genexpression: Das fehlende Glied in der evolutionären Berechnung
  21. ^ Harik, G. (1997). Lernverknüpfung zur effizienten Lösung von Problemen mit begrenzten Schwierigkeiten mithilfe genetischer Algorithmen (PhD). Institut für Informatik, Universität von Michigan, Ann Arbor.
  22. ^ Tomoiag B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimale Rekonfiguration von Energieverteilungssystemen mithilfe eines genetischen Algorithmus basierend auf NSGA-II. Energien. 2013; 6 (3): 1439-1455.
  23. ^ Noetel M., Ciarrochi J., Sahdra B., Lonsdale C. (2019). “Verwendung genetischer Algorithmen zur Abkürzung des Mindfulness Inventory for Sport: Eine inhaltlich-methodologische Synthese”. Sport- und Bewegungspsychologie. 45 (101545): 101545. doi:10.1016 / j.psychsport.2019.101545.
  24. ^ Gross, Bill. “Eine Solaranlage, die die Sonne verfolgt”. TED. Abgerufen 20. November 2013.
  25. ^ Hornby, GS; Linden, DS; Lohn, JD, Automatisiertes Antennendesign mit evolutionären Algorithmen (PDF)
  26. ^ “Flexible muskelbasierte Fortbewegung für zweibeinige Kreaturen”.
  27. ^ Evans, B.; Walton, SP (Dezember 2017). “Aerodynamische Optimierung eines Hyperschall-Wiedereintrittsfahrzeugs basierend auf der Lösung der Boltzmann-BGK-Gleichung und der evolutionären Optimierung”. Angewandte mathematische Modellierung. 52: 215–240. doi:10.1016 / j.apm.2017.07.024. ISSN 0307-904X.
  28. ^ Skiena, Steven (2010). Das Algorithmus-Design-Handbuch (2. Aufl.). Springer Science + Business Media. ISBN 978-1-849-96720-4.
  29. ^ Turing, Alan M. (Oktober 1950). “Rechenmaschinen und Intelligenz”. Verstand. LIX (238): 433–460. doi:10.1093 / mind / LIX.236.433.
  30. ^ Barricelli, Nils Aall (1954). “Esempi numerici di processi di evoluzione”. Methodos: 45–68.
  31. ^ Barricelli, Nils Aall (1957). “Symbiogenetische Evolutionsprozesse, die mit künstlichen Methoden realisiert werden”. Methodos: 143–182.
  32. ^ Fraser, Alex (1957). “Simulation genetischer Systeme durch automatische digitale Computer. I. Einführung”. Aust. J. Biol. Sci. 10 (4): 484–491. doi:10.1071 / BI9570484.
  33. ^ Fraser, Alex; Burnell, Donald (1970). Computermodelle in der Genetik. New York: McGraw-Hill. ISBN 978-0-07-021904-5.
  34. ^ Crosby, Jack L. (1973). Computersimulation in der Genetik. London: John Wiley & Sons. ISBN 978-0-471-18880-3.
  35. ^ 27.02.96 – Der emeritierte Professor und Pionier der mathematischen Biologie, Hans Bremermann von der UC Berkeley, ist im Alter von 69 Jahren verstorben
  36. ^ Fogel, David B. (Herausgeber) (1998). Evolutionsberechnung: Der Fossilienbestand. New York: IEEE Press. ISBN 978-0-7803-3481-6.CS1-Wartung: zusätzlicher Text: Autorenliste (Link)
  37. ^ Barricelli, Nils Aall (1963). “Numerische Prüfung von Evolutionstheorien. Teil II. Vorläufige Prüfung von Leistung, Symbiogenese und terrestrischem Leben”. Acta Biotheoretica. 16 (3–4): 99–126. doi:10.1007 / BF01556602. S2CID 86717105.
  38. ^ Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 978-3-7728-0373-4.
  39. ^ Schwefel, Hans-Paul (1974). Numerische Fähigkeiten von Computer-Modelle (Doktorarbeit).
  40. ^ Schwefel, Hans-Paul (1977). Numerische Herausforderungen von Computor-Modelle mittels der Evolutionsstrategie: mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Basel; Stuttgart: Birkhäuser. ISBN 978-3-7643-0876-6.
  41. ^ Schwefel, Hans-Paul (1981). Numerische Optimierung von Computermodellen (Übersetzung von 1977 Numerische Fähigkeiten von Computor-Modelle mittels der Evolutionsstrategie. Chichester; New York: Wiley. ISBN 978-0-471-09988-8.
  42. ^ Aldawoodi, Namir (2008). Ein Ansatz zum Entwerfen eines unbemannten Hubschrauberautopiloten unter Verwendung genetischer Algorithmen und simuliertem Tempern. p. 99. ISBN 978-0549773498 – über Google Books.
  43. ^ Markoff, John (29. August 1990). “Was ist die beste Antwort? Es ist das Überleben der Stärksten”. New York Times. Abgerufen 13. Juli 2016.
  44. ^ Ruggiero, Murray A. (1. August 2009) Fünfzehn Jahre und Zählen Archiviert 30. Januar 2016 an der Wayback-Maschine. Futuresmag.com. Abgerufen am 2013-08-07.
  45. ^ Evolver: Anspruchsvolle Optimierung für Tabellenkalkulationen. Palisade. Abgerufen am 2013-08-07.
  46. ^ Benchmarks zur Bewertung von Optimierungsalgorithmen und zum Benchmarking von MATLAB-derivatfreien Optimierern für den schnellen Zugriff von Praktikern, IEEE Access, Band 7, 2019.
  47. ^ Cohoon, J; et al. (2002). Evolutionäre Algorithmen für das physikalische Design von VLSI-Schaltungen (PDF). Fortschritte im evolutionären Rechnen: Theorie und Anwendungen. Springer, S. 683-712, 2003. ISBN 978-3-540-43330-9.
  48. ^ Pelikan, Martin; Goldberg, David E.; Cantú-Paz, Erick (1. Januar 1999). BOA: Der Bayes’sche Optimierungsalgorithmus. Vorträge der 1. Jahreskonferenz über genetische und evolutionäre Berechnungen – Band 1. Gecco’99. S. 525–532. ISBN 9781558606111.
  49. ^ Pelikan, Martin (2005). Hierarchischer Bayes’scher Optimierungsalgorithmus: Auf dem Weg zu einer neuen Generation evolutionärer Algorithmen (1. Aufl.). Berlin [u.a.]: Springer. ISBN 978-3-540-23774-7.
  50. ^ Thierens, Dirk (11. September 2010). “Der genetische Algorithmus des Verknüpfungsbaums”. Parallele Problemlösung aus der Natur, PPSN XI. S. 264–273. doi:10.1007 / 978-3-642-15844-5_27. ISBN 978-3-642-15843-8.
  51. ^ Ferreira, C. “Genexpressionsprogrammierung: Ein neuer adaptiver Algorithmus zur Lösung von Problemen” (PDF). Complex Systems. 13, Ausgabe 2: 87-129.
  52. ^ Falkenauer, Emanuel (1997). Genetische Algorithmen und Gruppierungsprobleme. Chichester, England: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  53. ^ Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (1. Oktober 2004). “Modellbasierte Suche nach kombinatorischer Optimierung: Eine kritische Umfrage”. Annals of Operations Research. 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427. doi:10.1023 / B: ANOR.0000039526.52305.af. ISSN 0254-5330. S2CID 63137.
  54. ^ Rania Hassan, Babak Cohanim, Olivier de Weck und Gerhard Vente (2005) Ein Vergleich der Partikelschwarmoptimierung und des genetischen Algorithmus
  55. ^ Khalafallah Ahmed; Abdel-Raheem Mohamed (1. Mai 2011). “Electimize: Neuer evolutionärer Algorithmus zur Optimierung mit Anwendung im Bauwesen”. Journal of Computing im Bauingenieurwesen. 25 (3): 192–201. doi:10.1061 / (ASCE) CP.1943-5487.0000080.
  56. ^ Baudry, Benoit; Franck Fleurey; Jean-Marc Jézéquel; Yves Le Traon (März – April 2005). “Automatische Testfalloptimierung: Ein bakteriologischer Algorithmus” (PDF). IEEE-Software. 22 (2): 76–82. doi:10.1109 / MS.2005.30. S2CID 3559602. Abgerufen 9. August 2009.
  57. ^ Civicioglu, P. (2012). “Transformation geozentrischer kartesischer Koordinaten in geodätische Koordinaten unter Verwendung des Differential-Suchalgorithmus”. Computer & Geowissenschaften. 46: 229–247. Bibcode:2012CG ….. 46..229C. doi:10.1016 / j.cageo.2011.12.011.
  58. ^ Kjellström, G. (Dezember 1991). “Zur Effizienz der Gaußschen Anpassung”. Zeitschrift für Optimierungstheorie und -anwendungen. 71 (3): 589–597. doi:10.1007 / BF00941405. S2CID 116847975.

Literaturverzeichnis[edit]

  • Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetische Programmierung – Eine Einführung. San Francisco, Kalifornien: Morgan Kaufmann. ISBN 978-1558605107.
  • Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). “Ein auf genetischen Algorithmen basierender, hybrider Ansatz des maschinellen Lernens zur Modellauswahl”. Zeitschrift für Pharmakokinetik und Pharmakodynamik. 33 (2): 196–221. doi:10.1007 / s10928-006-9004-6. PMID 16565924. S2CID 39571129.
  • Cha, Sung-Hyuk; Tappert, Charles C. (2009). “Ein genetischer Algorithmus zur Konstruktion kompakter binärer Entscheidungsbäume”. Journal of Pattern Recognition Research. 4 (1): 1–13. CiteSeerX 10.1.1.154.8314. doi:10.13176 / 11.44.
  • Fraser, Alex S. (1957). “Simulation genetischer Systeme durch automatische digitale Computer. I. Einführung”. Australisches Journal of Biological Sciences. 10 (4): 484–491. doi:10.1071 / BI9570484.
  • Goldberg, David (1989). Genetische Algorithmen in Suche, Optimierung und maschinellem Lernen. Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673.
  • Goldberg, David (2002). Das Design von Innovation: Lehren aus und für kompetente genetische Algorithmen. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.
  • Fogel, David (2006). Evolutionäre Berechnung: Auf dem Weg zu einer neuen Philosophie der Maschinenintelligenz (3. Aufl.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.
  • Holland, John (1992). Anpassung in natürlichen und künstlichen Systemen. Cambridge, MA: MIT Press. ISBN 978-0262581110.
  • Koza, John (1992). Genetische Programmierung: Zur Programmierung von Computern mittels natürlicher Selektion. Cambridge, MA: MIT Press. ISBN 978-0262111706.
  • Michalewicz, Zbigniew (1996). Genetische Algorithmen + Datenstrukturen = Evolutionsprogramme. Springer-Verlag. ISBN 978-3540606765.
  • Mitchell, Melanie (1996). Eine Einführung in genetische Algorithmen. Cambridge, MA: MIT Press. ISBN 9780585030944.
  • Poli, R.; Langdon, WB; McPhee, NF (2008). Ein Leitfaden zur genetischen Programmierung. Lulu.com, frei verfügbar im Internet. ISBN 978-1-4092-0073-4.[self-published source?]
  • Rechenberg, Ingo (1994): Evolutionsstrategie ’94, Stuttgart: Fromman-Holzboog.
  • Schmitt, Lothar M.; Nehaniv, Chrystopher L.; Fujii, Robert H. (1998). “Lineare Analyse genetischer Algorithmen”. Theoretische Informatik. 208: 111–148.
  • Schmitt, Lothar M. (2001). “Theorie genetischer Algorithmen”. Theoretische Informatik. 259 (1–2): 1–61. doi:10.1016 / S0304-3975 (00) 00406-0.
  • Schmitt, Lothar M. (2004). “Theorie genetischer Algorithmen II: Modelle für genetische Operatoren über die String-Tensor-Darstellung von Populationen und die Konvergenz zu globalen Optima für eine beliebige Fitnessfunktion unter Skalierung”. Theoretische Informatik. 310 (1-3): 181-231. doi:10.1016 / S0304-3975 (03) 00393-1.
  • Schwefel, Hans-Paul (1974): Numerische Arbeiten von Computer-Modelle. Nachdruck von Birkhäuser (1977).
  • Vose, Michael (1999). Der einfache genetische Algorithmus: Grundlagen und Theorie. Cambridge, MA: MIT Press. ISBN 978-0262220583.
  • Whitley, Darrell (1994). “Ein Tutorial für genetische Algorithmen” (PDF). Statistik und Datenverarbeitung. 4 (2): 65–85. CiteSeerX 10.1.1.184.3999. doi:10.1007 / BF00175354. S2CID 3447126.
  • Hingston, Philip; Barone, Luigi; Michalewicz, Zbigniew (2008). Design by Evolution: Fortschritte im evolutionären Design. Springer. ISBN 978-3540741091.
  • Eiben, Agoston; Smith, James (2003). Einführung in das evolutionäre Rechnen. Springer. ISBN 978-3540401841.

Externe Links[edit]

Ressourcen[edit]

Tutorials[edit]


after-content-x4