In der künstlichen Intelligenz ist genetische Programmierung (GP) eine Algorithmus-basierte durch die biologische Evolution angeregte Entwicklungsmethodik, Computerprogramme zu finden, die eine benutzerbestimmte Aufgabe durchführen. Es ist eine Spezialisierung von genetischen Algorithmen (GA), wo jede Person ein Computerprogramm ist. Es ist eine Maschinenlerntechnik, die verwendet ist, um eine Bevölkerung von Computerprogrammen gemäß einer durch eine Fähigkeit eines Programms bestimmten Fitnesslandschaft zu optimieren, eine gegebene rechenbetonte Aufgabe durchzuführen.

Geschichte

1954 hat GP mit den Entwicklungsalgorithmen begonnen, die zuerst von auf Entwicklungssimulationen angewandtem Nils Aall Barricelli verwendet sind. In den 1960er Jahren und Anfang der 1970er Jahre sind Entwicklungsalgorithmen weit anerkannt als Optimierungsmethoden geworden. Ingo Rechenberg und seine Gruppe sind im Stande gewesen, komplizierte Technikprobleme durch Evolutionsstrategien, wie dokumentiert, in seiner 1971-Doktorarbeit und dem resultierenden 1973-Buch zu beheben. John Holland war während der 1970er Jahre hoch einflussreich.

1964 hat Lawrence J. Fogel, einer der frühsten Praktiker der GP Methodik, Entwicklungsalgorithmen auf das Problem angewandt, Zustandsautomaten zu entdecken. Später hat GP-related Arbeit aus dem Lernen classifier Systemgemeinschaft gewachsen, die Sätze von spärlichen Regeln entwickelt hat, die optimale Policen für Entscheidungsprozesse von Markov beschreiben. Die erste Behauptung der modernen "baumbasierten" Genetischen Programmierung (d. h. Verfahrenssprachen, die in baumbasierten Strukturen organisiert sind und auf durch angemessen definierte GA-Maschinenbediener bedient sind), wurde von Nichael L. Cramer (1985) gegeben. Diese Arbeit wurde später von John R. Koza, einem Hauptbefürworter von GP außerordentlich ausgebreitet, der für die Anwendung der genetischen Programmierung in verschiedenen komplizierten Optimierungs- und Suchproblemen den Weg gebahnt hat.

In den 1990er Jahren wurde GP hauptsächlich verwendet, um relativ einfache Probleme zu beheben, weil es sehr rechenbetont intensiv ist. Kürzlich hat GP viele neuartige und hervorragende Ergebnisse in Gebieten wie Quant-Computerwissenschaft, elektronisches Design, das Spielspielen, das Sortieren und die Suche, wegen Verbesserungen in der GP Technologie und des Exponentialwachstums in der Zentraleinheitsmacht erzeugt. Diese Ergebnisse schließen die Erwiderung oder Entwicklung von mehreren post-year-2000 Erfindungen ein. GP ist auch auf evolvable Hardware-sowie Computerprogramme angewandt worden.

Das Entwickeln einer Theorie für GP ist sehr schwierig gewesen und so in den 1990er Jahren GP wurde als eine Art Abfall unter Suchtechniken betrachtet. Aber nach einer Reihe von Durchbrüchen am Anfang der 2000er Jahre hat die Theorie von GP eine furchterregende und schnelle Entwicklung gehabt. So viel, so dass es möglich gewesen ist, genaue probabilistic Modelle von GP (Diagramm-Theorien, Kettenmodelle von Markov und Meta-Optimierungsalgorithmen) zu bauen.

Programm-Darstellung

GP entwickelt Computerprogramme, die traditionell im Gedächtnis als Baumstrukturen vertreten sind. Bäume können auf eine rekursive Weise leicht bewertet werden. Jeder Baumknoten lässt einen Maschinenbediener fungieren, und jeder Endknoten hat einen operand, mathematische Ausdrücke leicht machend, zu entwickeln und zu bewerten. So traditionell bevorzugt GP den Gebrauch von Programmiersprachen, die natürlich Baumstrukturen aufnehmen (zum Beispiel, Lispeln; andere funktionelle Programmiersprachen sind auch passend).

Nichtbaumdarstellungen sind angedeutet und erfolgreich wie geradlinige genetische Programmierung durchgeführt worden, die passt, sehen die traditionelleren befehlenden Sprachen [zum Beispiel, Banzhaf u. a. (1998)]. Die kommerzielle GP Software Discipulus, Gebrauch-ZIEL, automatische Induktion des binären Maschinencodes, um bessere Leistung zu erreichen. µGP verwendet geleitete Mehrgraphen, um Programme zu erzeugen, die völlig die Syntax einer gegebenen Zusammenbau-Sprache ausnutzen.

Genetische Maschinenbediener

Die Hauptmaschinenbediener, die in Entwicklungsalgorithmen wie GP verwendet sind, sind Überkreuzung und Veränderung.

Überkreuzung

Überkreuzung wird an eine Person durch die einfache Schaltung von einem seiner Knoten mit einem anderen Knoten von einer anderen Person in der Bevölkerung angewandt. Mit einer baumbasierten Darstellung, einen Knoten ersetzend, bedeutet, den ganzen Zweig zu ersetzen. Das fügt größere Wirksamkeit zum Überkreuzungsmaschinenbediener hinzu. Die Ausdrücke, die sich aus Überkreuzung ergeben, sind sehr viel von ihren anfänglichen Eltern verschieden.

Veränderung

Veränderung betrifft eine Person in der Bevölkerung. Es kann einen ganzen Knoten in der ausgewählten Person ersetzen, oder es kann gerade die Information des Knotens ersetzen. Um Integrität aufrechtzuerhalten, müssen Operationen ausfallsicher sein oder der Typ der Information, die der Knoten hält, muss in Betracht gezogen werden. Zum Beispiel muss Veränderung binärer Operationsknoten bewusst sein, oder der Maschinenbediener muss im Stande sein, fehlende Werte zu behandeln.

Andere Annäherungen

Die Grundideen der genetischen Programmierung sind modifiziert und in einer Vielfalt von Wegen erweitert worden:

• Extended Compact Genetic Programming (ECGP)
• Embedded Cartesian Genetic Programming (ECGP)
• Probabilistic Incremental Program Evolution (PIPE)

MOSES

Meta-Optimizing Semantic Evolutionary Search (MOSES) ist eine Meta-Programmiertechnik, um Programme durch die wiederholende Optimierung genetischer Bevölkerungen zu entwickeln. Wie man gezeigt hat, hat es genetische und evolutionäre Programm-Lernsysteme stark überboten, und ist auf viele wirkliche Probleme, einschließlich der rechenbetonten Biologie, Gefühl-Einschätzung und Reagenz-Kontrolle erfolgreich angewandt worden. Wenn angewandt, auf beaufsichtigte Klassifikationsprobleme leistet MOSES sowie, oder besser als Unterstützungsvektor-Maschinen (SVM), während er mehr Scharfsinnigkeit in die Struktur der Daten anbietet, weil das resultierende Programm Abhängigkeiten demonstriert und in einer Weise verständlich ist, wie ein großer Vektor von Zahlen nicht ist.

MOSES ist im Stande, GP Standardsysteme aus zwei wichtigen Gründen zu überbieten. Man ist das es verwendet Bewertung von Vertriebsalgorithmen (EDA), um die Decke von Markov (d. h. die Abhängigkeiten in einem Netz von Bayesian) zwischen verschiedenen Teilen eines Programms zu bestimmen. Das schließt schnell sinnlose Veränderungen aus, die einen Teil eines Programms ändern, ohne entsprechende Änderungen in anderem, verwandten Teilen des Programms vorzunehmen. Der andere ist, dass es die Verminderung durchführt, um Programme auf die normale Form in jeder Wiederholungsbühne zu reduzieren, so Programme kleiner, kompakter machend, schneller, und menschlicher lesbar durchzuführen. Außer dem Vermeiden des Spaghetti-Codes entfernt Normalisierung Redundanzen in Programmen, so kleinere Bevölkerungen von weniger komplizierten Programmen erlaubend, Konvergenz beschleunigend.

Meta-genetische Programmierung

Meta-genetische Programmierung ist der vorgeschlagene meta das Lernen der Technik, ein genetisches Programmiersystem mit der genetischen Programmierung von sich zu entwickeln. Es weist darauf hin, dass Chromosomen, Überkreuzung und Veränderung selbst deshalb wie ihr echtes Leben entwickelt wurden, das Kopien erlaubt werden sollte, selbstständig zu ändern, anstatt durch einen menschlichen Programmierer bestimmt zu werden. Meta-GP wurde von Jürgen Schmidhuber 1987 formell vorgeschlagen, aber einige frühere Anstrengungen können als Beispiele derselben Technik einschließlich Euriskos von Doug Lenat betrachtet werden. Es ist ein rekursiver, aber endender Algorithmus, ihm erlaubend, unendlichen recursion zu vermeiden.

Kritiker dieser Idee sagen häufig, dass diese Annäherung im Spielraum allzu breit ist. Jedoch könnte es möglich sein, das Fitnesskriterium auf eine allgemeine Klasse von Ergebnissen zu beschränken, und so einen entwickelten GP zu erhalten, der Ergebnisse für Unterklassen effizienter erzeugen würde. Das könnte die Form entwickelten GP von Meta annehmen, um menschliche Wandern-Algorithmen zu erzeugen, der dann verwendet wird, um das menschliche Laufen, Springen usw. zu entwickeln. Das auf den Meta GP angewandte Fitnesskriterium würde einfach eine der Leistungsfähigkeit sein.

Für allgemeine Problem-Klassen kann es keine Weise geben zu zeigen, dass Meta GP Ergebnisse effizienter zuverlässig erzeugen wird als ein geschaffener Algorithmus außer der Erschöpfung. Dasselbe hält für normalen GP und andere Suchalgorithmen.

Durchführungen

Vielleicht am meisten verwendet:

• ECJ - Entwicklungsberechnung / Genetisches Programmierforschungssystem (Java)
• Lil-Gp genetisches Programmiersystem (C).
• Beagle - Öffnet BEAGLE, ein vielseitiges Fachwerk der europäischen Gemeinschaft (C ++ mit STL)
• EO Entwicklungsberechnungsfachwerk (C ++ mit statischem polymorphism)

Anderer:

NB. Sie sollten die Lizenz und Urheberrechtsbegriffe auf der Website des Programms/Bibliothek vor dem Gebrauch überprüfen.

Siehe auch

• Lebensbegeisterte Computerwissenschaft
• Genausdruck, programmierend
• Genetische Darstellung
• Grammatische Evolution
• Fitnessannäherung
• Geradlinige genetische Programmierung
• Fortpflanzung des Diagramms

Verweisungen und Zeichen

Bibliografie

• Banzhaf, W., Nordin, P., Keller, R.E. und Francone, F.D. (1998), genetische Programmierung: Eine Einführung: Auf der automatischen Evolution von Computerprogrammen und seinen Anwendungen, Morgan Kaufmann
• Barricelli, Nils Aall (1954), Esempi numerici di processi di evoluzione, Methodos, Seiten 45-68.
• Brameier, M. und Banzhaf, W. (2007), geradlinige genetische Programmierung, Springer, New York
• Crosby, Jack L. (1973), Computersimulation in Genetics, John Wiley & Sons, London.
• Cramer, Nichael Lynn (1985), "Eine Darstellung für die Anpassungsfähige Generation von Einfachen Folgenden Programmen" in Verhandlungen einer Internationalen Konferenz für Genetische Algorithmen und die Anwendungen, Grefenstette, John J. (Hrsg.). Universität von Carnegie Mellon
• Fogel, David B. (2000) Entwicklungsberechnung: Zu einer neuen Philosophie der Maschinenintelligenz IEEE Presse, New York.
• Fogel, David B. (Redakteur) (1998) Entwicklungsberechnung: Die Fossil-Aufzeichnung, IEEE Presse, New York.
• Forsyth, Richard (1981), SCHNÜFFELT Eine darwinistische Annäherung an die Muster-Anerkennung Kybernetes, Vol AUS. 10, Seiten 159-166.
• Fraser, Alex S. (1957), Simulation von Genetischen Systemen durch Automatische Digitalcomputer. Ich. Einführung. Australische Zeitschrift von Biologischen Wissenschaften vol. 10 484-491.
• Fraser, Alex und Donald Burnell (1970), Computermodelle in der Genetik, dem McGraw-Hügel, New York.
• Holland, John H (1975), Anpassung in natürlichen und künstlichen Systemen, Universität der Michiganer Presse, Laube von Ann
• Korns, Michael (2007), groß angelegte, zeitgezwungene, symbolische Klassifikation des rückwärts Gehens, in der genetischen Programmiertheorie und Praxis V. Springer, New York.
• Korns, Michael (2009), symbolisches rückwärts Gehen von bedingten Zielausdrücken, in der genetischen Programmiertheorie und Praxis VII. Springer, New York.
• Korns, Michael (2010), abstrakte Ausdruck-Grammatik symbolisches rückwärts Gehen, in der genetischen Programmiertheorie und Praxis VIII. Springer, New York.
• Koza, J.R. (1990), Genetische Programmierung: Ein Paradigma, um Bevölkerungen von Computerprogrammen Genetisch Zu gebären, um Probleme, Universitätsinformatik-Abteilung von Stanford technischer Bericht STAN CS 90 1314 Zu beheben. Ein gründlicher Bericht, der vielleicht als ein Entwurf an sein 1992-Buch verwendet ist.
• Koza, J.R. (1992), genetische Programmierung: Auf der Programmierung von Computern mittels der Zuchtwahl, MIT Presse
• Koza, J.R. (1994), genetische Programmierung II: Automatische Entdeckung von Mehrwegprogrammen, MIT Presse
• Koza, J.R. Bennett, F.H. Andre, D., und Keane, M.A. (1999), genetische Programmierung III: Das darwinistische Erfindungs- und Problem-Lösen, Morgan Kaufmann
• Koza, J.R. Keane, M.A. Streeter, M.J. Mydlowec, W., Yu, J., Lanza, G. (2003), genetische Programmierung IV: Alltägliche Menschlich-Wettbewerbsmaschinenintelligenz, Kluwer akademische Herausgeber
• Langdon, W. B., Genetische Programmierung und Datenstrukturen, internationale Springer-Standardbuchnummer 0-7923-8135-1
• Langdon, W. B., Poli, R. (2002), Fundamente der Genetischen Programmierung, internationale Standardbuchnummer des Springers-Verlag 3-540-42451-2
• Nordin, J.P. (1997) Entwicklungsprogramm-Induktion des Binären Maschinencodes und seiner Anwendung. Krehl Verlag, Muenster, Deutschland.
• Rechenberg, I. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (Doktorarbeit). Nachgedruckt durch Fromman-Holzboog (1973).
• Schmidhuber, J. (1987). Entwicklungsgrundsätze im Selbstverweisungslernen. (Erfahrend, wie man erfährt: Die meta-meta-haken sich... fest.) Diplom-These, Institut f. Informatik, Technologie. Univ. München.
• Schmied, S.F. (1980), Ein Lernen des Systems, das auf Genetischen Anpassungsfähigen Algorithmen, Doktordoktorarbeit (Universität Pittsburghs) basiert

ist

• Schmied, Jeff S. (2002), eine Bessere Lösung, Entwickler-Netzzeitschrift, Problem im März 2002 Entwickelnd
• Shu-Heng Chen u. a. (2008), Genetische Programmierung: Ein Erscheinendes Technikwerkzeug, Internationale Zeitschrift des Wissensbasierten Intelligenten Techniksystems, 12 (1): 1-2, 2008.
• Weise, T, Globale Optimierungsalgorithmen: Theorie und Anwendung, 2008

Links

• Riccardo Poli, William B. Langdon, Nicholas F. McPhee, John R. Koza, "Ein Feldhandbuch zur genetischen Programmierung" (2008)
• DigitalBiology.NET Vertikaler Suchmotor für GA/GP Mittel
• Aymen S Saket & Mark C Sinclair
• Das Handbuch des Trampers zur Entwicklungsberechnung
• GP Bibliografie
• Leute, die an GP arbeiten