Was sind gute Beispiele für genetische Algorithmen / genetische Programmierlösungen? [geschlossen]

Genetische Algorithmen (GA) und genetische Programmierung (GP) sind interessante Forschungsbereiche.

Ich würde gerne wissen, welche spezifischen Probleme Sie mit GA / GP gelöst haben und welche Bibliotheken / Frameworks Sie verwendet haben, wenn Sie keine eigenen erstellt haben.

Fragen:

• Welche Probleme haben Sie mit GA / GP gelöst?
• Welche Bibliotheken / Frameworks haben Sie verwendet?

Ich bin auf der Suche nach Erfahrungen aus erster Hand. Bitte antworten Sie nicht, es sei denn, Sie haben diese.

Keine Hausaufgaben.

Mein erster Job als professioneller Programmierer (1995) war das Schreiben eines auf genetischen Algorithmen basierenden automatisierten Handelssystems für S & P500-Futures. Die Anwendung wurde in Visual Basic 3 [!] Geschrieben und ich habe keine Ahnung, wie ich damals etwas gemacht habe, da VB3 nicht einmal Klassen hatte.

Die Anwendung begann mit einer Population zufällig generierter Strings fester Länge (der "Gen" -Teil), von denen jeder einer bestimmten Form in den minutengenauen Preisdaten der S & P500-Futures sowie einer bestimmten Reihenfolge entsprach (kaufen oder verkaufen) und Stop-Loss- und Stop-Profit-Beträge. Für jede Zeichenfolge (oder jedes "Gen") wurde die Gewinnleistung anhand eines Durchlaufs von 3 Jahren historischer Daten bewertet. Wann immer die angegebene "Form" mit den historischen Daten übereinstimmte, nahm ich den entsprechenden Kauf- oder Verkaufsauftrag an und bewertete das Handelsergebnis. Ich fügte die Einschränkung hinzu, dass jedes Gen mit einem festen Geldbetrag begann und daher möglicherweise pleite gehen und vollständig aus dem Genpool entfernt werden könnte.

Nach jeder Bewertung einer Population wurden die Überlebenden zufällig gekreuzt (indem nur Bits von zwei Elternteilen gemischt wurden), wobei die Wahrscheinlichkeit, dass ein Gen als Elternteil ausgewählt wurde, proportional zu dem Gewinn war, den es produzierte. Ich habe auch die Möglichkeit von Punktmutationen hinzugefügt, um die Dinge ein wenig aufzupeppen. Nach ein paar hundert Generationen hatte ich eine Population von Genen, die aus 5000 US-Dollar einen Durchschnitt von 10000 US-Dollar machen konnten, ohne dass die Gefahr von Tod / Bruch bestand (nach den historischen Daten natürlich).

Leider hatte ich nie die Möglichkeit, dieses System live zu nutzen, da mein Chef in weniger als drei Monaten fast 100.000 US-Dollar verloren hatte und seine Bereitschaft verlor, das Projekt fortzusetzen. Rückblickend denke ich, dass das System enorme Gewinne gemacht hätte - nicht weil ich unbedingt etwas richtig gemacht hätte, sondern weil die Population der von mir produzierten Gene zufällig um etwa 5 voreingenommen war in Richtung Kaufaufträge (im Gegensatz zu Verkaufsaufträgen): 1 Verhältnis. Und wie wir im Nachhinein wissen, ist der Markt nach 1995 etwas gestiegen.

Ich habe ein bisschen Lebewesen gemacht, die in dieser kleinen Welt lebten. Sie hatten ein neuronales Netzwerkhirn, das einige Eingaben von der Welt erhielt, und die Ausgabe war ein Vektor für Bewegung unter anderen Aktionen. Ihr Gehirn waren die "Gene".

Das Programm begann mit einer zufälligen Population von Lebewesen mit zufälligen Gehirnen. Die Eingangs- und Ausgangsneuronen waren statisch, aber was dazwischen war, war nicht.

Die Umwelt enthielt Lebensmittel und Gefahren. Essen erhöht die Energie und wenn Sie genug Energie haben, können Sie sich paaren. Die Gefahren würden die Energie reduzieren und wenn die Energie 0 wäre, würden sie sterben.

Schließlich entwickelten sich die Kreaturen, um sich um die Welt zu bewegen, Nahrung zu finden und die Gefahren zu vermeiden.

Ich beschloss dann, ein kleines Experiment zu machen. Ich gab dem Gehirn der Kreatur ein Ausgangsneuron namens "Mund" und ein Eingangsneuron namens "Ohr". Begann von vorne und stellte überrascht fest, dass sie sich weiterentwickelt hatten, um den Raum zu maximieren, und dass jede Kreatur in ihrem jeweiligen Teil bleiben würde (Nahrung wurde zufällig platziert). Sie lernten, miteinander zu kooperieren und sich nicht gegenseitig in die Quere zu kommen. Es gab immer Ausnahmen.

Dann habe ich etwas Interessantes ausprobiert. Ich tote Kreaturen würden Nahrung werden. Versuchen Sie zu erraten, was passiert ist! Es entwickelten sich zwei Arten von Kreaturen, solche, die wie in Schwärmen angriffen, und solche, die stark vermieden wurden.

Was ist die Lektion hier? Kommunikation bedeutet Zusammenarbeit. Sobald Sie ein Element einführen, bei dem das Verletzen eines anderen bedeutet, dass Sie etwas gewinnen, wird die Zusammenarbeit zerstört.

Ich frage mich, wie sich dies auf das System der freien Märkte und des Kapitalismus auswirkt. Ich meine, wenn Unternehmen ihre Konkurrenz verletzen und damit durchkommen können , dann ist klar, dass sie alles in ihrer Macht stehende tun werden, um die Konkurrenz zu schädigen.

Bearbeiten:

Ich habe es in C ++ ohne Frameworks geschrieben. Schrieb mein eigenes neuronales Netz und GA-Code. Eric, danke, dass du gesagt hast, dass es plausibel ist. Die Leute glauben normalerweise nicht an die Kräfte von GA (obwohl die Einschränkungen offensichtlich sind), bis sie damit gespielt haben. GA ist einfach, aber nicht simpel.

Für die Zweifler hat sich gezeigt, dass neuronale Netze jede Funktion simulieren können, wenn sie mehr als eine Schicht haben. GA ist eine ziemlich einfache Methode, um in einem Lösungsbereich zu navigieren und ein lokales und möglicherweise globales Minimum zu finden. Kombinieren Sie GA mit neuronalen Netzen und Sie haben eine ziemlich gute Möglichkeit, Funktionen zu finden, die ungefähre Lösungen für generische Probleme finden. Da wir neuronale Netze verwenden, optimieren wir die Funktion für einige Eingaben, nicht für einige Eingaben in eine Funktion, da andere GA verwenden

Hier ist der Demo-Code für das Überlebensbeispiel: http://www.mempko.com/darcs/neural/demos/eaters/ Bauanleitung:

• Installieren Sie darcs, libboost, liballegro, gcc, cmake, make
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake .
• make
• cd demos/eaters
• ./eaters

Ich habe eine GA verwendet, um die Sitzplatzzuweisungen bei meinem Hochzeitsempfang zu optimieren. 80 Gäste an 10 Tischen. Die Bewertungsfunktion basierte darauf, Menschen mit ihren Daten zu halten, Menschen mit Gemeinsamkeiten zusammenzubringen und Menschen mit extrem gegensätzlichen Ansichten an getrennten Tischen zu halten.

Ich habe es mehrmals ausgeführt. Jedes Mal bekam ich neun gute Tische und einen mit all den seltsamen Bällen. Am Ende erledigte meine Frau die Sitzplatzzuweisungen.

Mein Optimierer für reisende Verkäufer verwendete eine neuartige Zuordnung von Chromosomen zu Reiseroute, die es trivial machte, die Chromosomen zu züchten und zu mutieren, ohne das Risiko, ungültige Touren zu generieren.

Update : Weil ein paar Leute gefragt haben, wie ...

Beginnen Sie mit einer Reihe von Gästen (oder Städten) in einer beliebigen, aber konsistenten Reihenfolge, z. B. alphabetisch. Nennen Sie dies die Referenzlösung. Stellen Sie sich den Index eines Gastes als seine Sitznummer vor.

Anstatt zu versuchen, diese Reihenfolge direkt im Chromosom zu codieren, codieren wir Anweisungen zum Umwandeln der Referenzlösung in eine neue Lösung. Insbesondere behandeln wir die Chromosomen als Listen von Indizes im Array, die ausgetauscht werden sollen. Um ein Chromosom zu dekodieren, beginnen wir mit der Referenzlösung und wenden alle durch das Chromosom angegebenen Swaps an. Das Austauschen von zwei Einträgen im Array führt immer zu einer gültigen Lösung: Jeder Gast (oder jede Stadt) wird immer noch genau einmal angezeigt.

Somit können Chromosomen zufällig erzeugt, mutiert und mit anderen gekreuzt werden und ergeben immer eine gültige Lösung.

Im Januar 2004 wurde ich von Philips New Display Technologies kontaktiert, die die Elektronik für die erste kommerzielle E-Ink entwickelten, die Sony Librie, die erst in Japan veröffentlicht wurde, Jahre bevor Amazon Kindle und die anderen in den USA auf den Markt kamen ein Europa.

Die Philips Ingenieure hatten ein großes Problem. Einige Monate bevor das Produkt auf den Markt kommen sollte, wurden beim Seitenwechsel immer noch Geisterbilder auf dem Bildschirm angezeigt. Das Problem waren die 200 Treiber, die das elektrostatische Feld erzeugten. Jeder dieser Treiber hatte eine bestimmte Spannung, die genau zwischen Null und 1000 mV oder so eingestellt werden musste. Aber wenn Sie einen von ihnen ändern würden, würde dies alles ändern.

Eine individuelle Optimierung der Spannung jedes Fahrers kam daher nicht in Frage. Die Anzahl der möglichen Wertekombinationen lag in Milliarden, und es dauerte ungefähr 1 Minute, bis eine spezielle Kamera eine einzelne Kombination ausgewertet hatte. Die Ingenieure hatten viele Standardoptimierungstechniken ausprobiert, aber nichts würde in die Nähe kommen.

Der Chefingenieur hat mich kontaktiert, weil ich zuvor eine Genetic Programming-Bibliothek für die Open-Source-Community freigegeben hatte. Er fragte, ob GP / GAs helfen würden und ob ich mich engagieren könnte. Ich habe es getan, und ungefähr einen Monat lang haben wir zusammengearbeitet, indem ich die GA-Bibliothek für synthetische Daten geschrieben und optimiert habe und er sie in ihr System integriert hat. Dann, eines Wochenendes, ließen sie es mit der realen Sache live laufen.

Am folgenden Montag erhielt ich diese leuchtenden E-Mails von ihm und seinem Hardware-Designer darüber, wie niemand die erstaunlichen Ergebnisse glauben konnte, die der GA gefunden hatte. Das war's. Später in diesem Jahr kam das Produkt auf den Markt.

Ich habe keinen Cent dafür bezahlt bekommen, aber ich habe "prahlende" Rechte bekommen. Sie sagten von Anfang an, sie hätten bereits das Budget überschritten, also wusste ich, was der Deal war, bevor ich anfing, daran zu arbeiten. Und es ist eine großartige Geschichte für Anwendungen von GAs. :) :)

Ich habe genetische Algorithmen (sowie einige verwandte Techniken) verwendet, um die besten Einstellungen für ein Risikomanagementsystem zu ermitteln, mit dem versucht wurde, Goldfarmer davon abzuhalten, gestohlene Kreditkarten zur Bezahlung von MMOs zu verwenden. Das System würde mehrere tausend Transaktionen mit "bekannten" Werten (Betrug oder nicht) aufnehmen und herausfinden, wie die beste Kombination von Einstellungen darin besteht, die betrügerischen Transaktionen richtig zu identifizieren, ohne zu viele Fehlalarme zu haben.

Wir hatten Daten zu mehreren Dutzend (booleschen) Merkmalen einer Transaktion, von denen jedes einen Wert erhielt und summierte. Wenn die Summe höher als ein Schwellenwert war, handelte es sich bei der Transaktion um Betrug. Die GA würde eine große Anzahl zufälliger Wertesätze erstellen, diese anhand eines Korpus bekannter Daten bewerten, diejenigen auswählen, die am besten abschneiden (sowohl bei der Betrugserkennung als auch bei der Begrenzung der Anzahl falsch positiver Ergebnisse), und dann die besten paar davon kreuzen jede Generation, um eine neue Generation von Kandidaten zu produzieren. Nach einer bestimmten Anzahl von Generationen wurde der Wertesatz mit der besten Punktzahl als Sieger gewertet.

Die Achillesferse des Systems bestand darin, das Korpus bekannter Daten zu erstellen, gegen die getestet werden sollte. Wenn Sie auf Rückbuchungen gewartet haben, waren Sie einige Monate im Rückstand, als Sie versuchten, auf die Betrüger zu reagieren. Daher musste jemand eine große Anzahl von Transaktionen manuell überprüfen, um diesen Datenbestand aufzubauen, ohne zu lange warten zu müssen.

Dies führte dazu, dass die überwiegende Mehrheit des Betrugs identifiziert wurde, der jedoch bei den am stärksten von Betrug betroffenen Artikeln nicht unter 1% lag (da 90% der eingehenden Transaktionen Betrug sein konnten, lief dies ziemlich gut).

Ich habe das alles mit Perl gemacht. Ein Lauf der Software auf einer ziemlich alten Linux-Box würde 1-2 Stunden dauern (20 Minuten, um Daten über eine WAN-Verbindung zu laden, der Rest der Zeit, die für das Knirschen aufgewendet wurde). Die Größe einer bestimmten Generation wurde durch den verfügbaren RAM begrenzt. Ich habe es immer wieder mit geringfügigen Änderungen an den Parametern ausgeführt und nach einer besonders guten Ergebnismenge gesucht.

Alles in allem wurden einige der Probleme vermieden, die mit dem manuellen Versuch einhergingen, die relativen Werte von Dutzenden von Betrugsindikatoren zu optimieren, und es wurden durchweg bessere Lösungen gefunden, als ich von Hand erstellen konnte. AFAIK, es wird immer noch verwendet (ungefähr 3 Jahre nachdem ich es geschrieben habe).

Fußball-Trinkgeld. Ich habe ein GA-System aufgebaut, um das wöchentliche Ergebnis von Spielen in der AFL (Aussie Rules Football) vorherzusagen.

Vor ein paar Jahren langweilte mich der Standard-Fußballfußball, alle gingen einfach online und nahmen die Tipps von einem Experten in der Presse entgegen. Also dachte ich mir, es könnte nicht zu schwer sein, ein paar Majors des Rundfunkjournalismus zu schlagen, oder? Mein erster Gedanke war, die Ergebnisse von Massey Ratings zu übernehmen und am Ende der Saison meine Strategie zu enthüllen, nachdem ich Ruhm und Ehre gewonnen hatte. Aus Gründen, die ich nie entdeckt habe, verfolgt Massey AFL jedoch nicht. Der Zyniker in mir glaubt, dass das Ergebnis jedes AFL-Spiels im Grunde genommen zufällig geworden ist, aber meine Beschwerden über die jüngsten Regeländerungen gehören in ein anderes Forum.

Das System berücksichtigte im Wesentlichen Offensivstärke, Defensivstärke, Heimvorteil, wöchentliche Verbesserung (oder deren Fehlen) und die Geschwindigkeit der Änderungen an jedem dieser Faktoren. Dies erzeugte einen Satz von Polynomgleichungen für jedes Team während der Saison. Der Gewinner und die Punktzahl für jedes Spiel für ein bestimmtes Datum könnten berechnet werden. Das Ziel war es, den Koeffizientensatz zu finden, der dem Ergebnis aller vergangenen Spiele am ehesten entspricht, und diesen Satz zu verwenden, um das Spiel der kommenden Wochen vorherzusagen.

In der Praxis würde das System Lösungen finden, die über 90% der vergangenen Spielergebnisse genau vorhersagen. Es würde dann erfolgreich etwa 60-80% der Spiele für die kommende Woche auswählen (das ist die Woche, die nicht im Trainingssatz enthalten ist).

Das Ergebnis: knapp über der Mitte der Packung. Weder ein großer Geldpreis noch ein System, mit dem ich Vegas schlagen könnte. Es hat Spaß gemacht.

Ich habe alles von Grund auf neu gebaut, kein Framework verwendet.

Neben einigen der häufigsten Probleme, wie dem Travelling Salesman und einer Variation von Roger Alsings Mona Lisa-Programm , habe ich auch einen evolutionären Sudoku-Löser geschrieben (der meinerseits etwas originellere Überlegungen erforderte, anstatt nur neu zu implementieren die Idee eines anderen). Es gibt zuverlässigere Algorithmen zur Lösung von Sudokus, aber der evolutionäre Ansatz funktioniert ziemlich gut.

In den letzten Tagen habe ich mit einem Evolutionsprogramm herumgespielt, um "Cold Decks" für Poker zu finden, nachdem ich diesen Artikel auf Reddit gesehen habe. Es ist im Moment nicht ganz zufriedenstellend, aber ich denke, ich kann es verbessern.

Ich habe mein eigenes Framework , das ich für evolutionäre Algorithmen verwende.

Ich entwickelte ein Home Brew GA für ein 3D-Laseroberflächenprofilsystem, das mein Unternehmen 1992 für die Frachtindustrie entwickelt hatte. Das System stützte sich auf eine dreidimensionale Triangulation und verwendete einen benutzerdefinierten Laserlinienscanner, eine 512x512-Kamera (mit benutzerdefiniertem Erfassungs-Hardware). Der Abstand zwischen Kamera und Laser würde niemals genau sein und der Brennpunkt der Kameras befand sich nicht in der von Ihnen erwarteten Position von 256.256!

Es war ein Albtraum, die Kalibrierungsparameter unter Verwendung von Standardgeometrie und simulierter Lösung von Glühgleichungen zu erarbeiten.

Der genetische Algorithmus wurde an einem Abend entwickelt und ich habe einen Kalibrierungswürfel erstellt, um ihn zu testen. Ich kannte die Würfelabmessungen mit hoher Genauigkeit und daher war die Idee, dass mein GA einen Satz von benutzerdefinierten Triangulationsparametern für jede Scaneinheit entwickeln könnte, um Produktionsschwankungen zu überwinden.

Der Trick war ein Vergnügen. Ich war gelinde gesagt verblüfft! Innerhalb von ungefähr 10 Generationen sah mein "virtueller" Würfel (der aus dem Rohscan generiert und aus den Kalibrierungsparametern neu erstellt wurde) tatsächlich wie ein Würfel aus! Nach ungefähr 50 Generationen hatte ich die Kalibrierung, die ich brauchte.

Es ist oft schwierig, eine genaue Farbkombination zu erhalten, wenn Sie planen, Ihr Haus zu streichen. Oft haben Sie etwas Farbe im Sinn, aber es ist keine der Farben, die Ihnen der Anbieter zeigt.

Gestern hat mein Prof., ein GA-Forscher, über eine wahre Geschichte in Deutschland gesprochen (sorry, ich habe keine weiteren Referenzen, ja, ich kann es herausfinden, wenn jemand danach fragt). Dieser Typ (nennen wir ihn den Farbigen ) ging von Tür zu Tür, um den Leuten zu helfen, den genauen Farbcode (in RGB ) zu finden, der den Schrank für das darstellt, was der Kunde vorhatte. So würde er es machen:

Der Farbige trug immer ein Softwareprogramm mit sich, das GA verwendete. Er begann mit 4 verschiedenen Farben, die jeweils als codiertes Chromosom codiert waren (dessen decodierter Wert ein RGB-Wert wäre). Der Verbraucher wählt 1 der 4 Farben aus (welche ist diejenige, die ihm am nächsten kommt). Das Programm würde dann dieser Person die maximale Fitness zuweisen und mithilfe von Mutation / Crossover zur nächsten Generation übergehen . Die oben genannten Schritte , bis der Verbraucher wiederholt werden würde hatte die genaue Farbe gefunden und dann Farbe Typ verwendet ihn die RGB - Kombination zu erzählen!

Durch die Zuordnung maximale Fitness an der Farbe schließt zu dem, was der Verbraucher im Auge hat, die Farbe Kerl ‚s Programm, um die Chancen zu konvergieren auf die Farbe zu erhöhen, hat der Verbraucher im Auge genau. Ich fand es ziemlich lustig!

Jetzt, wo ich eine -1 habe, wenn Sie mehr -1 planen, pls. Erklären Sie den Grund dafür!

Vor ein paar Wochen schlug ich eine Lösung für SO unter Verwendung genetischer Algorithmen vor, um ein Problem des Diagrammlayouts zu lösen. Dies ist ein Beispiel für ein eingeschränktes Optimierungsproblem.

Auch im Bereich des maschinellen Lernens habe ich ein GA-basiertes Framework für Klassifizierungsregeln in c / c ++ von Grund auf neu implementiert.
Ich habe GA auch in einem Beispielprojekt zum Trainieren künstlicher neuronaler Netze (ANN) verwendet, anstatt den berühmten Backpropagation-Algorithmus zu verwenden .

Darüber hinaus habe ich im Rahmen meiner Abschlussforschung GA zum Trainieren von Hidden-Markov-Modellen als zusätzlichen Ansatz für den EM-basierten Baum-Welch- Algorithmus verwendet (wieder in c / c ++).

Im Rahmen meines CompSci-Studiums wurde uns das Problem zugewiesen, optimale JVM-Flags für die virtuelle Jikes-Forschungsmaschine zu finden. Dies wurde mithilfe der Dicappo-Benchmark-Suite bewertet, die eine Zeit an die Konsole zurückgibt. Ich habe einen verteilten Gentic-Algorithmus geschrieben, der diese Flags umschaltete, um die Laufzeit der Benchmark-Suite zu verbessern, obwohl die Ausführung Tage dauerte, um Hardware-Jitter zu kompensieren, der die Ergebnisse beeinflusst. Das einzige Problem war, dass ich die Compilertheorie (die die Absicht der Aufgabe war) nicht richtig kennengelernt habe.

Ich hätte die anfängliche Population mit den vorhandenen Standardflags setzen können, aber was interessant war, war, dass der Algorithmus eine sehr ähnliche Konfiguration wie die O3-Optimierungsstufe fand (aber in vielen Tests tatsächlich schneller war).

Bearbeiten: Außerdem habe ich mein eigenes genetisches Algorithmus-Framework in Python für die Zuweisung geschrieben und nur die Popen-Befehle verwendet, um die verschiedenen Benchmarks auszuführen. Wenn es sich jedoch nicht um eine bewertete Zuweisung handelte, hätte ich mir pyEvolve angesehen.

Zunächst einmal ist "Genetic Programming" von Jonathan Koza ( auf Amazon ) so ziemlich DAS Buch über genetische und evolutionäre Algorithmen / Programmiertechniken mit vielen Beispielen. Ich empfehle dringend, es auszuprobieren.

Für meine eigene Verwendung eines genetischen Algorithmus habe ich einen (einheimischen) genetischen Algorithmus verwendet, um einen Schwarmalgorithmus für ein Szenario zum Sammeln / Zerstören von Objekten zu entwickeln (praktischer Zweck könnte das Löschen eines Minenfelds gewesen sein). Hier ist ein Link zum Papier . Der interessanteste Teil meiner Arbeit war die mehrstufige Fitnessfunktion, die eine Notwendigkeit war, da die einfachen Fitnessfunktionen nicht genügend Informationen lieferten, damit der genetische Algorithmus ausreichend zwischen Mitgliedern der Bevölkerung unterscheiden konnte.

Ich bin Teil eines Teams, das die Verwendung von Evolutionary Computation (EC) untersucht, um Fehler in vorhandenen Programmen automatisch zu beheben. Wir haben eine Reihe von echten Fehlern in realen Softwareprojekten erfolgreich behoben (siehe die Homepage dieses Projekts ).

Wir haben zwei Anwendungen dieser EG-Reparaturtechnik.

• Die erste ( Code- und Reproduktionsinformationen, die auf der Projektseite verfügbar sind ) entwickelt die abstrakten Syntaxbäume, die aus vorhandenen C-Programmen analysiert wurden, und wird in Ocaml mithilfe unserer eigenen benutzerdefinierten EC-Engine implementiert.

• Die zweite ( Code- und Reproduktionsinformationen, die auf der Projektseite verfügbar sind ), mein persönlicher Beitrag zum Projekt, entwickelt die x86-Assembly oder den Java-Bytecode, der aus Programmen kompiliert wurde, die in einer Reihe von Programmiersprachen geschrieben wurden. Diese Anwendung ist in Clojure implementiert und verwendet auch eine eigene EC-Engine.

Ein schöner Aspekt der evolutionären Berechnung ist die Einfachheit der Technik, die es ermöglicht, Ihre eigenen benutzerdefinierten Implementierungen ohne allzu große Schwierigkeiten zu schreiben. Einen guten, frei verfügbaren Einführungstext zur genetischen Programmierung finden Sie im Feldhandbuch zur genetischen Programmierung .

Ein Mitarbeiter und ich arbeiten an einer Lösung für das Laden von Fracht auf Lastwagen anhand der verschiedenen Kriterien, die unser Unternehmen benötigt. Ich habe an einer genetischen Algorithmuslösung gearbeitet, während er einen Branch And Bound mit aggressivem Schnitt verwendet. Wir sind noch dabei, diese Lösung zu implementieren, aber bisher haben wir gute Ergebnisse erzielt.

Vor einigen Jahren habe ich ga's verwendet, um asr-Grammatiken (automatische Spracherkennung) für bessere Erkennungsraten zu optimieren. Ich begann mit ziemlich einfachen Auswahllisten (bei denen das ga Kombinationen möglicher Begriffe für jeden Slot testete) und arbeitete mich zu offeneren und komplexeren Grammatiken vor. Die Fitness wurde durch Messen des Abstands zwischen Begriffen / Sequenzen unter einer Art phonetischer Distanzfunktion bestimmt. Ich habe auch experimentiert, um schwach äquivalente Variationen einer Grammatik vorzunehmen, um eine zu finden, die zu einer kompakteren Darstellung kompiliert wurde (am Ende habe ich einen direkten Algorithmus gewählt, der die Größe der "Sprache", die wir in Anwendungen verwenden konnten, drastisch vergrößerte). .

In jüngerer Zeit habe ich sie als Standardhypothese verwendet, um die Qualität von Lösungen zu testen, die aus verschiedenen Algorithmen generiert wurden. Dies beinhaltete größtenteils Kategorisierung und verschiedene Arten von Anpassungsproblemen (dh Erstellen einer "Regel", die eine Reihe von Entscheidungen erklärt, die von Prüfern über einen oder mehrere Datensätze getroffen wurden).

Ich habe ein vollständiges GA-Framework namens "GALAB" erstellt, um viele Probleme zu lösen:

• Lokalisieren von GSM-ANTs (BTS), um Überlappungs- und Leerstellen zu verringern.
• Projektplanung für Ressourcenbeschränkungen.
• Evolutionäre Bilderzeugung. ( Evopic )
• Problem mit reisenden Verkäufern.
• N-Queen & N-Color Probleme.
• Knight's Tour & Rucksack Probleme.
• Magic Square & Sudoku Rätsel.
• String-Komprimierung, basierend auf dem Superstring-Problem.
• 2D-Verpackungsproblem.
• Winziges künstliches Leben APP.
• Rubik Puzzle.

Ich habe einmal eine GA verwendet, um eine Hash-Funktion für Speicheradressen zu optimieren. Die Adressen hatten eine Seitengröße von 4 KB oder 8 KB, daher zeigten sie eine gewisse Vorhersagbarkeit im Bitmuster der Adresse (niedrigstwertige Bits alle Null; mittlere Bits werden regelmäßig erhöht usw.). Die ursprüngliche Hash-Funktion war "klobig" - sie neigte dazu, Treffer zu gruppieren bei jedem dritten Hash-Eimer. Der verbesserte Algorithmus hatte eine nahezu perfekte Verteilung.

Ich weiß nicht, ob Hausaufgaben zählen ...

Während meines Studiums haben wir unser eigenes Programm entwickelt, um das Problem des Handlungsreisenden zu lösen.

Die Idee war, einen Vergleich mit mehreren Kriterien durchzuführen (Schwierigkeit, das Problem, die Leistung usw. abzubilden), und wir verwendeten auch andere Techniken wie simuliertes Tempern .

Es hat ziemlich gut funktioniert, aber wir haben eine Weile gebraucht, um zu verstehen, wie man die "Reproduktions" -Phase richtig macht: Das Modellieren des vorliegenden Problems in etwas, das für die genetische Programmierung geeignet ist, hat mich wirklich als den schwierigsten Teil empfunden ...

Es war ein interessanter Kurs, da wir uns auch mit neuronalen Netzen und dergleichen beschäftigt haben.

Ich würde gerne wissen, ob jemand diese Art der Programmierung im Produktionscode verwendet hat.

Ich habe eine einfache GA erstellt, um nützliche Muster aus dem Frequenzspektrum der Musik zu extrahieren, während sie abgespielt wird. Die Ausgabe wurde verwendet, um grafische Effekte in einem Winamp-Plugin zu steuern.

• Eingabe: einige FFT-Frames (stellen Sie sich ein 2D-Array von Floats vor)
• Ausgabe: Einzel-Float-Wert (gewichtete Summe der Eingaben) mit einem Schwellenwert von 0,0 oder 1,0
• Gene: Eingabegewichte
• Fitnessfunktion: Kombination von Arbeitszyklus, Impulsbreite und BPM in einem vernünftigen Bereich.

Ich hatte ein paar GAs, die auf verschiedene Teile des Spektrums sowie verschiedene BPM-Grenzwerte abgestimmt waren, so dass sie nicht dazu neigten, gegen dasselbe Muster zu konvergieren. Die Ausgaben der Top 4 aus jeder Population wurden an die Rendering-Engine gesendet.

Ein interessanter Nebeneffekt war, dass die durchschnittliche Fitness in der Bevölkerung ein guter Indikator für Veränderungen in der Musik war, obwohl es im Allgemeinen 4 bis 5 Sekunden dauerte, um dies herauszufinden.

Im Rahmen meiner Diplomarbeit habe ich ein generisches Java-Framework für den Multi-Objective-Optimierungsalgorithmus mPOEMS (Multiobjective Prototype Optimization mit weiterentwickelten Verbesserungsschritten) geschrieben, bei dem es sich um eine GA handelt, die evolutionäre Konzepte verwendet. Es ist generisch in einer Weise, dass alle problemunabhängigen Teile von den problemabhängigen Teilen getrennt wurden und eine Schnittstelle bereitgestellt wird, um das Framework zu verwenden, wobei nur die problemabhängigen Teile hinzugefügt werden. Wer also den Algorithmus verwenden möchte, muss nicht bei Null beginnen und erleichtert die Arbeit erheblich.

Den Code finden Sie hier .

Die Lösungen, die Sie mit diesem Algorithmus finden können, wurden in einer wissenschaftlichen Arbeit mit den neuesten Algorithmen SPEA-2 und NSGA verglichen, und es wurde nachgewiesen, dass der Algorithmus je nach den von Ihnen verwendeten Metriken eine vergleichbare oder sogar bessere Leistung erbringt Nehmen Sie, um die Leistung zu messen, und insbesondere abhängig von dem Optimierungsproblem, das Sie betrachten.

Sie finden es hier .

Auch im Rahmen meiner Diplomarbeit und meines Arbeitsnachweises habe ich diesen Rahmen auf das Problem der Projektauswahl im Portfoliomanagement angewendet. Es geht darum, die Projekte auszuwählen, die dem Unternehmen den größten Mehrwert bieten, die Strategie des Unternehmens am meisten unterstützen oder andere willkürliche Ziele unterstützen. ZB Auswahl einer bestimmten Anzahl von Projekten aus einer bestimmten Kategorie oder Maximierung von Projektsynergien, ...

Meine These, die diesen Rahmen auf das Problem der Projektauswahl anwendet: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

Danach arbeitete ich in einer Portfoliomanagementabteilung in einem der Fortune 500, wo sie eine kommerzielle Software verwendeten, die auch eine GA auf das Projektauswahlproblem / die Portfoliooptimierung anwendete.

Weitere Ressourcen:

Die Dokumentation des Frameworks: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS-Präsentationspapier: http://portal.acm.org/citation.cfm?id=1792634.1792653

Mit ein wenig Begeisterung konnte jeder den Code des generischen Frameworks leicht an ein beliebiges Optimierungsproblem mit mehreren Zielen anpassen.

Bei der Arbeit hatte ich folgendes Problem: Was war bei M Aufgaben und N DSPs der beste Weg, um DSPs Aufgaben zuzuweisen? "Best" wurde definiert als "Minimieren der Last des am meisten geladenen DSP". Es gab verschiedene Arten von Aufgaben, und verschiedene Aufgabentypen hatten unterschiedliche Leistungsauswirkungen, je nachdem, wo sie zugewiesen wurden. Daher habe ich den Satz von Job-zu-DSP-Zuweisungen als "DNA-String" codiert und dann einen genetischen Algorithmus zum "Züchten" verwendet. die beste Zuweisungszeichenfolge, die ich konnte.

Es funktionierte ziemlich gut (viel besser als meine vorherige Methode, bei der jede mögliche Kombination bewertet wurde ... bei nicht trivialen Problemgrößen hätte es Jahre gedauert!), Das einzige Problem war, dass es keine Möglichkeit gab, dies zu sagen ob die optimale Lösung erreicht wurde oder nicht. Sie konnten nur entscheiden, ob die aktuelle "beste Leistung" gut genug war, oder sie länger laufen lassen, um zu sehen, ob sie besser abschneiden könnte.

Auf codechef.com gab es einen Wettbewerb (übrigens eine großartige Website, monatliche Programmierwettbewerbe), bei dem man ein unlösbares Sudoku lösen sollte (man sollte so nah wie möglich mit so wenig falschen Spalten / Zeilen / usw. wie möglich kommen).

Was ich tun würde, war, zuerst ein perfektes Sudoku zu erzeugen und dann die Felder zu überschreiben, die gegeben wurden. Von dieser ziemlich guten Basis aus habe ich genetische Programmierung verwendet, um meine Lösung zu verbessern.

Ich konnte mir in diesem Fall keinen deterministischen Ansatz vorstellen, da das Sudoku 300 x 300 war und die Suche zu lange gedauert hätte.

Ich habe einen einfachen genetischen Algorithmus verwendet, um das Signal-Rausch-Verhältnis einer Welle zu optimieren, die als binäre Zeichenfolge dargestellt wurde. Durch Umdrehen der Bits über mehrere Millionen Generationen hinweg konnte ich eine Transformation erzeugen, die zu einem höheren Signal-Rausch-Verhältnis dieser Welle führte. Der Algorithmus hätte auch "Simuliertes Tempern" sein können, wurde aber in diesem Fall nicht verwendet. Im Kern sind genetische Algorithmen einfach, und dies war ungefähr so ​​einfach wie ein Anwendungsfall, den ich gesehen habe. Daher habe ich kein Framework für die Erstellung und Auswahl von Generationen verwendet - nur einen zufälligen Startwert und das Signal-Rausch-Verhältnis Funktion zur Hand.

In einem Seminar in der Schule entwickeln wir eine Anwendung, um Musik im Musikmodus zu generieren. Das Programm wurde in Java erstellt und die Ausgabe war eine MIDI-Datei mit dem Song. Wir verwenden verschiedene Ansätze von GA, um die Musik zu erzeugen. Ich denke, dieses Programm kann nützlich sein, um neue Kompositionen zu erkunden.

Im Undergrad haben wir NERO (eine Kombination aus neuronalen Netzwerken und genetischen Algorithmen) verwendet, um In-Game-Robotern beizubringen, intelligente Entscheidungen zu treffen. Es war ziemlich cool.

Ich entwickelte eine Multithread-Swing-basierte Simulation der Roboternavigation durch eine Reihe von randomisierten Gittergebieten von Nahrungsquellen und Minen und entwickelte eine auf genetischen Algorithmen basierende Strategie zur Erforschung der Optimierung des Roboterverhaltens und des Überlebens der besten Gene für ein Roboterchromosom. Dies wurde unter Verwendung von Diagrammen und Mapping jedes Iterationszyklus durchgeführt.

Seitdem habe ich noch mehr Spielverhalten entwickelt. Eine Beispielanwendung, die ich kürzlich für mich selbst erstellt habe, war ein genetischer Algorithmus zur Lösung des Problems der reisenden Verkäufer bei der Routenfindung in Großbritannien unter Berücksichtigung von Start- und Zielzuständen sowie eines / mehrerer Verbindungspunkte, Verzögerungen, Stornierungen, Bauarbeiten, Hauptverkehrszeiten, öffentliche Streiks, Berücksichtigung zwischen schnellsten und billigsten Strecken. Geben Sie dann eine ausgewogene Empfehlung für die Route an einem bestimmten Tag.

Im Allgemeinen besteht meine Strategie darin, eine POJO-basierte Darstellung von Genen zu verwenden und dann spezifische Schnittstellenimplementierungen für Auswahl, Mutation, Crossover-Strategien und den Kriterienpunkt anzuwenden. Meine Fitnessfunktion wird dann im Grunde genommen ziemlich komplex, basierend auf der Strategie und den Kriterien, die ich als heuristische Maßnahme anwenden muss.

Ich habe mich auch mit der Anwendung des genetischen Algorithmus auf automatisierte Tests innerhalb von Code unter Verwendung systematischer Mutationszyklen befasst, bei denen der Algorithmus die Logik versteht und versucht, einen Fehlerbericht mit Empfehlungen für Codekorrekturen zu ermitteln. Grundsätzlich eine Möglichkeit, meinen Code zu optimieren und Verbesserungsvorschläge zu geben sowie die Entdeckung neuen programmatischen Codes zu automatisieren. Ich habe auch versucht, genetische Algorithmen unter anderem auf die Musikproduktion anzuwenden.

Im Allgemeinen finde ich evolutionäre Strategien wie die meisten metaheuristischen / globalen Optimierungsstrategien. Sie lernen zunächst nur langsam, beginnen jedoch zu lernen, wenn die Lösungen immer näher an den Zielzustand heranrücken und solange Ihre Fitnessfunktion und Heuristiken gut aufeinander abgestimmt sind diese Konvergenz innerhalb Ihres Suchraums.

Ich habe einmal versucht, einen Computerspieler für das Go-Spiel zu entwickeln, der ausschließlich auf genetischer Programmierung basiert. Jedes Programm würde als Bewertungsfunktion für eine Folge von Zügen behandelt. Die produzierten Programme waren jedoch nicht sehr gut, selbst auf einem eher kleinen 3x4-Board.

Ich habe Perl verwendet und alles selbst codiert. Ich würde die Dinge heute anders machen.

Nachdem ich The Blind Watchmaker gelesen hatte , interessierte ich mich für das Pascal-Programm, das Dawkins entwickelt hatte, um Modelle von Organismen zu erstellen, die sich im Laufe der Zeit entwickeln könnten. Ich war interessiert genug, meine eigenen mit Swarm zu schreiben . Ich habe nicht alle ausgefallenen Critter-Grafiken gemacht, die er gemacht hat, aber meine "Chromosomen" kontrollierten Eigenschaften, die die Überlebensfähigkeit der Organismen beeinflussten. Sie lebten in einer einfachen Welt und konnten sie gegeneinander und gegen ihre Umgebung ausspielen.

Organismen lebten oder starben teilweise zufällig, aber auch basierend darauf, wie effektiv sie sich an ihre lokale Umgebung anpassten, wie gut sie Nährstoffe konsumierten und wie erfolgreich sie sich vermehrten. Es hat Spaß gemacht, aber auch meiner Frau mehr bewiesen, dass ich ein Geek bin.

Es ist eine Weile her, aber ich habe einen GA gewürfelt, um die eigentlichen Bildverarbeitungskerne zu entwickeln und kosmische Strahlenspuren aus Hubble Space Telescope (HST) -Bildern zu entfernen. Der Standardansatz besteht darin, mit dem Hubble mehrere Belichtungen aufzunehmen und nur das Material beizubehalten, das in allen Bildern gleich ist. Da die HST-Zeit so wertvoll ist, bin ich ein Astronomie-Fan und hatte kürzlich am Kongress für evolutionäre Berechnungen teilgenommen. Ich dachte darüber nach, eine GA zu verwenden, um Einzelbelichtungen zu bereinigen.

Die Individuen hatten die Form von Bäumen, die einen Bereich von 3 × 3 Pixeln als Eingabe verwendeten, einige Berechnungen durchführten und eine Entscheidung darüber ergaben, ob und wie das mittlere Pixel geändert werden sollte. Die Fitness wurde durch Vergleichen der Ausgabe mit einem auf herkömmliche Weise bereinigten Bild (dh Stapeln von Belichtungen) beurteilt.

Es hat tatsächlich irgendwie funktioniert, aber nicht gut genug, um auf den ursprünglichen Ansatz zu verzichten. Wenn ich durch meine These nicht zeitlich eingeschränkt gewesen wäre, hätte ich möglicherweise den für den Algorithmus verfügbaren Behälter für genetische Teile erweitert. Ich bin mir ziemlich sicher, dass ich es deutlich hätte verbessern können.

Verwendete Bibliotheken: Wenn ich mich richtig erinnere, IRAF und cfitsio für die astronomische Bilddatenverarbeitung und E / A.

Ich habe in meiner Jugend mit GA experimentiert. Ich habe einen Simulator in Python geschrieben, der wie folgt funktioniert.

Die Gene codierten die Gewichte eines neuronalen Netzwerks.

Die Eingänge des neuronalen Netzwerks waren "Antennen", die Berührungen erkannten. Höhere Werte bedeuteten sehr nahe und 0 bedeutete nicht berühren.

Die Ausgänge waren auf zwei "Räder". Wenn beide Räder vorwärts gingen, ging der Typ vorwärts. Wenn die Räder in entgegengesetzte Richtungen waren, drehte sich der Typ um. Die Stärke der Leistung bestimmte die Drehzahl des Rades.

Ein einfaches Labyrinth wurde erzeugt. Es war wirklich einfach - sogar dumm. Es gab den Start am unteren Bildschirmrand und ein Tor am oberen Rand mit vier Wänden dazwischen. An jeder Wand wurde zufällig ein Platz herausgenommen, sodass es immer einen Weg gab.

Ich habe am Anfang zufällige Typen gestartet (ich habe sie als Bugs angesehen). Sobald ein Mann das Ziel erreicht hatte oder ein Zeitlimit erreicht war, wurde die Fitness berechnet. Es war umgekehrt proportional zur damaligen Entfernung zum Tor.

Ich habe sie dann gepaart und "gezüchtet", um die nächste Generation zu erschaffen. Die Wahrscheinlichkeit, für die Zucht ausgewählt zu werden, war proportional zu seiner Fitness. Manchmal bedeutete dies, dass man wiederholt mit sich selbst gezüchtet wurde, wenn es eine sehr hohe relative Fitness hatte.

Ich dachte, sie würden ein Verhalten entwickeln, das die linke Wand umarmt, aber sie schienen immer etwas weniger Optimalem zu folgen. In jedem Experiment konvergierten die Fehler zu einem Spiralmuster. Sie würden sich nach außen drehen, bis sie eine Wand rechts berührten. Sie würden dem folgen, und wenn sie an der Lücke ankamen, würden sie sich nach unten (von der Lücke weg) und herum drehen. Sie würden eine 270-Grad-Drehung nach links machen und dann normalerweise in die Lücke eintreten. Dies würde sie durch einen Großteil der Mauern und oft zum Ziel bringen.

Eine Funktion, die ich hinzugefügt habe, war das Einfügen eines Farbvektors in die Gene, um die Verwandtschaft zwischen Individuen zu verfolgen. Nach ein paar Generationen würden sie alle die gleiche Farbe haben, was mir sagt, dass ich eine bessere Zuchtstrategie haben sollte.

Ich habe versucht, sie dazu zu bringen, eine bessere Strategie zu entwickeln. Ich habe das neuronale Netz kompliziert - eine Erinnerung und alles hinzugefügt. Es hat nicht geholfen. Ich habe immer die gleiche Strategie gesehen.

Ich habe verschiedene Dinge ausprobiert, wie separate Genpools, die erst nach 100 Generationen rekombinierten. Aber nichts würde sie zu einer besseren Strategie bringen. Vielleicht war es unmöglich.

Eine weitere interessante Sache ist die grafische Darstellung der Fitness im Laufe der Zeit. Es gab bestimmte Muster, wie die maximale Fitness, die nach unten ging, bevor sie nach oben ging. Ich habe noch nie ein Evolutionsbuch über diese Möglichkeit sprechen sehen.