Evolutionäre Berechnung – Wikipedia

Posted on by
before-content-x4

Trial-and-Error-Problemlöser mit metaheuristischem oder stochastischem Optimierungscharakter

In der Informatik, evolutionäre Berechnung ist eine Familie von Algorithmen für die globale Optimierung, die von der biologischen Evolution inspiriert sind, und das Teilgebiet der künstlichen Intelligenz und des Soft Computing, das diese Algorithmen untersucht. Technisch gesehen handelt es sich um eine Familie von populationsbasierten Trial-and-Error-Problemlösern mit metaheuristischem oder stochastischem Optimierungscharakter.

Bei der evolutionären Berechnung wird ein anfänglicher Satz von Kandidatenlösungen erzeugt und iterativ aktualisiert. Jede neue Generation wird erzeugt, indem weniger erwünschte Lösungen stochastisch entfernt und kleine zufällige Änderungen eingeführt werden. In der biologischen Terminologie wird eine Population von Lösungen einer natürlichen Selektion (oder künstlichen Selektion) und Mutation unterzogen. Als Ergebnis wird sich die Population allmählich entwickeln, um die Fitness zu erhöhen, in diesem Fall die gewählte Fitnessfunktion des Algorithmus.

Evolutionäre Rechentechniken können in einer Vielzahl von Problemstellungen hochoptimierte Lösungen liefern, was sie in der Informatik beliebt macht. Es gibt viele Varianten und Erweiterungen, die für spezifischere Problemfamilien und Datenstrukturen geeignet sind. Evolutionäre Berechnungen werden manchmal auch in der Evolutionsbiologie als in silico experimentelles Verfahren zur Untersuchung allgemeiner Aspekte allgemeiner Evolutionsprozesse.

Geschichte[edit]

Die Anwendung evolutionärer Prinzipien zur automatisierten Problemlösung hat ihren Ursprung in den 1950er Jahren. Erst in den 1960er Jahren wurden an drei verschiedenen Orten drei unterschiedliche Interpretationen dieser Idee entwickelt.

Evolutionäre Programmierung wurde von Lawrence J. Fogel in den USA eingeführt, während John Henry Holland seine Methode als genetischen Algorithmus. In Deutschland stellen Ingo Rechenberg und Hans-Paul Schwefel vor Evolutionsstrategien. Diese Gebiete haben sich etwa 15 Jahre lang getrennt entwickelt. Ab den frühen neunziger Jahren sind sie als verschiedene Vertreter (“Dialekte”) einer Technologie, genannt evolutionäres Computing. Ebenfalls Anfang der neunziger Jahre entstand ein vierter Strom, der den allgemeinen Ideen folgte – genetische Programmierung. Seit den 1990er Jahren werden von der Natur inspirierte Algorithmen ein immer wichtigerer Bestandteil der evolutionären Berechnung.

Diese Terminologien bezeichnen das Gebiet des Evolutionary Computing und betrachten evolutionäre Programmierung, Evolutionsstrategien, genetische Algorithmen und genetische Programmierung als Teilbereiche.

Die frühesten computergestützten Simulationen der Evolution mit evolutionären Algorithmen und künstlichen Lebenstechniken wurden 1953 von Nils Aall Barricelli durchgeführt.[1] mit ersten Ergebnissen, die 1954 veröffentlicht wurden.[2] Ein weiterer Pionier in den 1950er Jahren war Alex Fraser, der eine Reihe von Arbeiten zur Simulation künstlicher Selektion veröffentlichte.[3]Künstliche Evolution wurde durch die Arbeit von Ingo Rechenberg in den 1960er und frühen 1970er Jahren zu einer weithin anerkannten Optimierungsmethode, der Evolutionsstrategien zur Lösung komplexer technischer Probleme einsetzte.[4]Insbesondere genetische Algorithmen wurden durch das Schreiben von John Holland populär.[5] Als das akademische Interesse wuchs, ermöglichte ein dramatischer Anstieg der Leistungsfähigkeit von Computern praktische Anwendungen, einschließlich der automatischen Entwicklung von Computerprogrammen.[6] Evolutionäre Algorithmen werden heute verwendet, um mehrdimensionale Probleme effizienter zu lösen als von menschlichen Designern erstellte Software, und auch um das Design von Systemen zu optimieren.[7][8]

Techniken[edit]

Evolutionäre Rechentechniken beinhalten meist metaheuristische Optimierungsalgorithmen. Grob gesagt umfasst das Feld:

Evolutionäre Algorithmen[edit]

Evolutionäre Algorithmen bilden eine Untermenge der evolutionären Berechnung, da sie im Allgemeinen nur Techniken beinhalten, die Mechanismen implementieren, die von der biologischen Evolution inspiriert sind, wie Reproduktion, Mutation, Rekombination, natürliche Selektion und Überleben des Stärkeren. Kandidatenlösungen für das Optimierungsproblem spielen die Rolle von Individuen in einer Population, und die Kostenfunktion bestimmt die Umgebung, in der die Lösungen “leben” (siehe auch Fitnessfunktion). Die Populationsentwicklung erfolgt dann nach wiederholter Anwendung der obigen Operatoren.

In diesem Prozess gibt es zwei Hauptkräfte, die die Grundlage evolutionärer Systeme bilden: Rekombination Mutation und Überkreuzung schaffen die notwendige Vielfalt und ermöglichen so Neues, während Auswahl wirkt als qualitätssteigernde Kraft.

Viele Aspekte eines solchen evolutionären Prozesses sind stochastisch. Veränderte Informationen aufgrund von Rekombination und Mutation werden zufällig ausgewählt. Andererseits können Auswahloperatoren entweder deterministisch oder stochastisch sein. Im letzteren Fall haben Personen mit einer höheren Fitness eine höhere Chance, ausgewählt zu werden als Personen mit einer geringeren Fitness, aber typischerweise haben auch die schwachen Personen eine Chance, Eltern zu werden oder zu überleben.

Evolutionäre Algorithmen und Biologie[edit]

Genetische Algorithmen liefern Methoden zur Modellierung biologischer Systeme und der Systembiologie, die mit der Theorie dynamischer Systeme verknüpft sind, da sie verwendet werden, um die zukünftigen Zustände des Systems vorherzusagen. Dies ist nur eine anschauliche (aber vielleicht irreführende) Art, auf den geordneten, kontrollierten und stark strukturierten Charakter der Entwicklung in der Biologie aufmerksam zu machen.

Aber auch der Einsatz von Algorithmen und Informatik, insbesondere der Computertheorie, über die Analogie zu dynamischen Systemen hinaus, ist für das Verständnis der Evolution selbst relevant.

Diese Ansicht hat den Vorzug, anzuerkennen, dass es keine zentrale Kontrolle der Entwicklung gibt; Organismen entwickeln sich als Ergebnis lokaler Interaktionen innerhalb und zwischen Zellen. Die vielversprechendsten Ideen über Parallelen in der Programmentwicklung scheinen uns diejenigen zu sein, die auf eine scheinbar enge Analogie zwischen Prozessen innerhalb von Zellen und dem Low-Level-Betrieb moderner Computer hinweisen.[9] Somit sind biologische Systeme wie Rechenmaschinen, die Eingabeinformationen verarbeiten, um nächste Zustände zu berechnen, so dass biologische Systeme näher an einer Berechnung sind als klassische dynamische Systeme.[10]

Darüber hinaus sind Mikroprozesse in biologischen Organismen nach Konzepten der Computertheorie grundsätzlich unvollständig und unentscheidbar (Vollständigkeit (Logik)), was impliziert, dass „hinter der Analogie zwischen Zellen und Computern mehr als eine grobe Metapher steckt.[11]

Die Analogie zur Berechnung erstreckt sich auch auf die Beziehung zwischen Vererbungssystemen und biologischer Struktur, von der oft angenommen wird, dass sie eines der dringendsten Probleme bei der Erklärung der Ursprünge des Lebens aufdeckt.

Evolutionäre Automaten[12][13][14], eine Verallgemeinerung von Evolutionäre Turing-Maschinen[15][16], wurden eingeführt, um die Eigenschaften biologischer und evolutionärer Berechnungen genauer zu untersuchen. Insbesondere ermöglichen sie neue Ergebnisse zur Aussagekraft evolutionärer Berechnungen[14][17]. Dies bestätigt das erste Ergebnis über die Unentscheidbarkeit natürlicher Evolution und evolutionärer Algorithmen und Prozesse. Evolutionäre endliche Automaten, die einfachste Unterklasse evolutionärer Automaten, die in Terminalmodus kann beliebige Sprachen über ein gegebenes Alphabet akzeptieren, einschließlich nicht-rekursiv aufzählbarer (z. B. Diagonalisierungssprache) und rekursiv aufzählbarer, aber nicht rekursiver Sprachen (z. B. Sprache der universellen Turing-Maschine)[18].

Bemerkenswerte Praktiker[edit]

Die Liste der aktiven Forscher ist natürlich dynamisch und nicht erschöpfend. Eine Netzwerkanalyse der Community wurde 2007 veröffentlicht.[19]

Konferenzen[edit]

Zu den wichtigsten Konferenzen im Bereich Evolutionary Computing gehören

Siehe auch[edit]

Externe Links[edit]

Literaturverzeichnis[edit]

Verweise[edit]

  1. ^ Taylor, Tim; Dorin, Alan (2020). Aufstieg der Selbstreplikatoren: Frühe Visionen von Maschinen, KI und Robotern, die sich reproduzieren und weiterentwickeln können. Cham: Springer International Publishing. mach:10.1007/978-3-030-48234-3. ISBN 978-3-030-48233-6. S2CID 220855726. Zusammenfassung legen.
  2. ^ Barricelli, Nils Aall (1954). “Esempi Numerici di processi di evoluzione”. Methoden: 45–68.
  3. ^ Fraser AS (1958). „Monte-Carlo-Analysen von genetischen Modellen“. Natur. 181 (4603): 208–9. Bibcode:1958Natur.181..208F. mach:10.1038/181208a0. PMID 13504138. S2CID 4211563.
  4. ^ Rechenberg, Ingo (1973). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (Dissertation) (auf Deutsch). Fromman-Holzboog.
  5. ^ Holland, John H. (1975). Anpassung in natürlichen und künstlichen Systemen. University of Michigan Presse. ISBN 978-0-262-58111-0.
  6. ^ Koza, John R. (1992). Genetische Programmierung: Zur Programmierung von Computern durch natürliche Selektion. MIT-Presse. ISBN 978-0-262-11170-6.
  7. ^ GC Onwubolu und BV Babu, Onwubolu, Godfrey C.; Babu, BV (21. Januar 2004). Neue Optimierungstechniken im Engineering. ISBN 9783540201670. Abgerufen 17. September, 2016.
  8. ^ Jamshidi M. (2003). „Werkzeuge für intelligente Steuerung: Fuzzy-Controller, neuronale Netze und genetische Algorithmen“. Philosophische Transaktionen der Royal Society A. 361 (1809): 1781-808. Bibcode:2003RSPTA.361.1781J. mach:10.1098/rsta.2003.1225. PMID 12952685. S2CID 34259612.
  9. ^ “Biologische Informationen”. Die Stanford Encyclopedia of Philosophy Philosoph. Metaphysik-Forschungslabor, Stanford University. 2016.
  10. ^ JG Diaz Ochoa (2018). „Elastic Multi-scale Mechanisms: Computation and Biological Evolution“. Zeitschrift für molekulare Evolution. 86 (1): 47–57. Bibcode:2018JMolE..86…47D. mach:10.1007/s00239-017-9823-7. PMID 29248946. S2CID 22624633.
  11. ^ A. Danchin (2008). “Bakterien als Computer, die Computer machen”. FEMS Mikrobiol. Rev. 33 (1): 3–26. mach:10.1111/j.1574-6976.2008.00137.x. PMC 2704931. PMID 19016882.
  12. ^ Burgin, Markus; Eberbach, Eugen (2013). „Rekursiv generierte evolutionäre Turingmaschinen und evolutionäre Automaten“. In Xin-She Yang (Hrsg.). Künstliche Intelligenz, Evolutionary Computing und Metaheuristik. Studium der Computergestützten Intelligenz. 427. Springer-Verlag. S. 201–230. mach:10.1007/978-3-642-29694-9_9. ISBN 978-3-642-29693-2.
  13. ^ Burgin, M. und Eberbach, E. (2010)Bounded and Periodic Evolutionary Machines, in Proc. 2010 Congress on Evolutionary Computation (CEC’2010), Barcelona, ​​Spanien, 2010, S. 1379-1386
  14. ^ ein b Burgin, M.; Eberbach, E. (2012). „Evolutionäre Automaten: Ausdruckskraft und Konvergenz der Evolutionären Berechnung“. Das Computerjournal. 55 (9): 1023–1029. mach:10.1093/comjnl/bxr099.
  15. ^ Eberbach E. (2002)On Expressiveness of Evolutionary Computation: Is EC Algorithmic?, Proc. 2002 World Congress on Computational Intelligence WCCI’2002, Honolulu, HI, 2002, 564-569.
  16. ^ Eberbach, E. (2005)Toward a Theory of Evolutionary Computing, BioSystems, V. 82, S. 1-19.
  17. ^ Eberbach, Eugen; Burgin, Markus (2009). „Evolutionäre Automaten als Grundlage evolutionärer Berechnungen: Larry Fogel hatte Recht“. 2009 IEEE Congress on Evolutionary Computing. IEEE. S. 2149–2156. mach:10.1109/CEC.2009.4983207. ISBN 978-1-4244-2958-5. S2CID 2869386.
  18. ^ Hopcroft, JE, R. Motwani und JD Ullman (2001) Einführung in Automatentheorie, Sprachen und Berechnung, Addison Wesley, Boston/San Francisco/New York
  19. ^ JJ Merelo und C. Cotta (2007). “Wer ist der am besten verbundene EC-Forscher? Zentralitätsanalyse des komplexen Netzwerks von Autoren in der evolutionären Berechnung”. arXiv:0708.2021 [cs.CY].


after-content-x4