Was sind einige reale Anwendungen für genetische Algorithmen?

13

Was sind einige reale Probleme, die mit einem genetischen Algorithmus gelöst wurden? Worin besteht das Problem? Was ist der Fitnesstest, um dieses Problem zu lösen?

Der Turm
quelle
1
Dies sollte ein Community-Wiki sein (vorausgesetzt, es ist ein Thema).
Shane
4
Ich bin nicht sicher, ob genetische Algorithmen im Bereich liegen. Wir sollten es hier diskutieren: meta.cstheory.stackexchange.com/questions/73/…
Suresh Venkat
7
Dies ist nicht zum Thema.
Marcos Villagra
5
Eine interessante Frage könnte gewesen sein: Gibt es Szenarien, die nachweisliche Garantien für GAs zulassen?
Suresh Venkat
2
Dabei geht es aber nicht um eine Anwendung der Theorie. Es geht um eine Anwendung der Praxis.
Jeffs

Antworten:

11

Der Optimierer in relationalen Datenbanken. Beispiele sind PostgreSQL und H2 ; Andere Datenbanken verwenden höchstwahrscheinlich auch einen genetischen Algorithmus. Das Problem ist: Die Auswahl des besten Abfrageplans (der mit den niedrigsten geschätzten Kosten) ist NP-schwer. Der Fitnesstest ist der geschätzte Preis.

Thomas Müller
quelle
8

Der Lamarcksche genetische Algorithmus wird in der Chemoinformatik verwendet, um nach potenziellen neuen Arzneimittelverbindungen zu suchen, die an einen bestimmten Rezeptor binden können.

Das rechnerische Problem besteht darin, in einer chemischen Datenbank nach Kandidaten zu suchen, die sich korrekt orientieren können (in Bezug auf die möglichen Orientierungen des Moleküls, das den Rezeptor enthält), und dies mit einer Konformationssuche zu kombinieren (dh einer Suche, die die möglichen drehbaren Torsionen des Moleküls berücksichtigt) , die die Reaktion stark beeinflussen können ).

Bisher war es möglich, entweder eine Orientierungssuche oder eine Konformationssuche durchzuführen, aber nicht beides. LGA nutzt die Computer-Beschleunigung und kombiniert die globale Suche eines genetischen Algorithmus mit einer lokalen Suche.

Aaron Sterling
quelle
6

Die Nasa hat einen genetischen Algorithmus für das Antennendesign entwickelt .

Der Fitnesstest ist wie folgt:

Die zur Antennenbewertung verwendete Fitnessfunktion ist eine Funktion des Stehwellenverhältnisses (VSWR) und der Verstärkungswerte der Sende- und Empfangsfrequenzen. VSWR ist eine Methode zur Quantifizierung der Interferenz reflektierter Wellen und damit des Betrags der Impedanzfehlanpassung an der Verbindungsstelle. VSWR ist das Verhältnis zwischen der höchsten und der niedrigsten Spannung in der Signalhüllkurve entlang einer Übertragungsleitung.

Der Turm
quelle
6

Diese werden häufig im Finanzbereich eingesetzt, insbesondere bei Problemen mit der Portfoliooptimierung. Es gibt viele Artikel zu diesem Thema, aber siehe zum Beispiel Genetische Algorithmen in der Portfoliooptimierung .

Shane
quelle
6

Ich habe GAs verwendet, um Planungsprobleme in Fertigung und Ausbildung zu lösen. Die Fitnessfunktion im ersten Fall war, wie viel der angeforderten Artikel im gegebenen Zeitrahmen hergestellt wurden, während im zweiten Fall die Fitness auf der Bestrafung von Zeitplänen mit Konflikten beruhte.

Wenn Sie sich für Anwendungen interessieren, finden Sie hier einen Link zu mehr als 20.000 Artikeln über citeseerx

Steven A. Lowe
quelle
4

Das Antennendesign wurde bereits erwähnt, und es ist eine äußerst reiche Domäne. (Es ist sehr direkt, was meine Bewegung von der Elektrotechnik zur Informatik (in den späten 90ern) und insbesondere zu bioinspiriertem Rechnen und künstlicher Intelligenz (in den letzten fünf Jahren oder so) begann.)

Aus dem gleichen Grund werde ich eine Antennen- Array- Optimierung hinzufügen , insbesondere für die Phased-Array-Optimierung, die alle Probleme des Antennendesigns und mehr mit sich bringt. Es gibt wirklich Möglichkeiten im gesamten Bereich des Designs elektromagnetischer Geräte: Antennen, Antennenarrays, Mikrowellenfilter, optische Gitter, Design von Metamaterial-Geräten - alles auf den ersten Blick. Eine datierte Umfrage ist die elektromagnetische Optimierung durch genetische Algorithmen , und eine neuere Umfrage ist Genetische Algorithmen in der Elektromagnetik . (Ich sollte das zweite wirklich kaufen.

Ich habe auch viele gute Arbeiten zum Design nicht-elektromagnetischer Schaltkreise gesehen: GAs, die mit wettbewerbsfähigen Operationsverstärkern oder anderen integrierten Schaltkreisdesigns aufwarten, "lernen", die analogen Unvollkommenheiten in FPGAs zu nutzen, um analoge Funktionen wie zu implementieren Uhren usw. Auch ein so einfaches wie dummes Filterdesign mit diskreten Elementen kann ein Ziel für GAs sein: Ich habe gesehen, dass Q-Faktoren, Toleranzen, diskrete Werte und lötparasitäre Modelle berücksichtigt werden, um gute, herstellbare Filter aus dem Filter zu erhalten Teile, die Sie zur Hand haben.

Dabei handelt es sich häufig um (für mich jedenfalls) neuartige Schaltkreisdarstellungen, um die genetischen Operatoren an das Paradigma anzupassen, sowie um Chromosomen variabler Größe.

Novak
quelle
ja, es wurde gezeigt, dass das Schaltungsdesignbeispiel patentierte Designs wiederentdeckt oder sogar übertrifft. Hier ist eine frühe Veröffentlichung in dieser Richtung, viel spätere Forschung. Entwurf eines Hochleistungs-Operationsverstärkers und anderer Schaltkreise mittels genetischer Programmierung von Koza et al. 1997
vzn
3

Vor kurzem gab es eine Frage zur Verwendung von GAs zur Entwicklung von Windturbinenblattkonstruktionen unter Verwendung fluiddynamischer Simulationen der als Fitnessfunktion erzeugten physikalischen Leistung. [1]

Dieses Video zeigt die Verwendung eines genetischen Algorithmus zur Entwicklung von VAWT-Windturbinenblättern. Eine der resultierenden Klingen ist ganz anders und scheint gut zu simulieren. Die Zuchtsoftware wurde in Perl geschrieben, die Anzeigesoftware Java und die CFD-Software war OpenFoam. Für die Erstellung dieses Videos wurden mehr als 672 CPU-Stunden aufgewendet. Hinweis: Seitdem habe ich festgestellt, dass ich bei diesem Experiment die falsche Viskosität für Luft verwendet habe, sodass die Ergebnisse für die Verwendung auf der Erde nicht gültig sind. (Vielleicht Jupiter.)

[1] "Evolving Wind Turbinenblätter" auf YouTube von "sjh7132". Zitiert von / aus der TCS.se-Frage: Inwieweit ist es möglich, mithilfe genetischer Algorithmen die Effizienz von Windmühlen-Turbinenblättern zu steigern?

vzn
quelle
3

Es gibt einige Untersuchungen zur Verwendung von GAs für die Weinklassifizierung. es klassifiziert genau die Rebsorte und den Produktionsort ("Ursprungsbezeichnung"). [1] Dies ist eine Teilmenge der Verwendung von GAs in landwirtschaftlichen Systemen, für die es viele Anwendungen gibt. [2]

[1] Algorithmen zur Merkmalsauswahl unter Verwendung chilenischer Weinchromatogramme von NHBeltran et al

[2] Stand der Technik bei genetischen Algorithmen für landwirtschaftliche Systeme von Bolboaca et al

vzn
quelle
1

Es gibt viele Veröffentlichungen zur Verwendung von GAs für die Flugsteuerung in der Luft- und Raumfahrt. Viele davon werden vom IEEE-Explorer veröffentlicht oder können durchsucht werden . Die Fitnessfunktion misst im Allgemeinen, wie gut / effektiv der Algorithmus den Flug steuert.

[1] Design und Optimierung von Flugsteuerungssystemen mit einem genetischen Algorithmus von Fantinutto et al

[2] Anwendung genetischer Algorithmen auf die Überschallflugkontrolle. Austin, Jacobs.

[3] Multi-Core-Implementierung des Flugoberflächen-Kontrollsystems F-16 unter Verwendung des auf dem Genetic Algorithm basierenden adaptiven Kontrollalgorithmus Xiaoru Wang

[4] Fuzzy-Logik-Steuerung basierend auf einem genetischen Algorithmus zur integrierten Flugsteuerung für Überschallfahrzeuge. von Wang Jian

vzn
quelle
1

Ein bemerkenswerter, sogar außergewöhnlicher oder paradigmenwechselnder Einsatz von GAs, der in späteren Umfragen häufig zitiert wurde, wurde von Koza als Vorreiter bei der Lösung eines "Problems" des Videospiels eingesetzt - nämlich Pac Man als Beweis für das Prinzip, aber das Konzept kann wahrscheinlich auf möglicherweise beinahe angewendet werden jedes Videospiel, und die Ergebnisse sind definitiv alles andere als trivial oder "Spielzeug".

Das heißt, er entwickelte Algorithmen, die das tatsächliche Verhalten implementieren , um das Spiel über längere Zeiträume zu gewinnen. Die Ergebnisse liegen auf dem Leistungsniveau von Amateurspielern oder sogar fortgeschrittenen menschlichen Spielern. Bei einer Fitness-Funktion kann es sich entweder um Punkte handeln, die durch den Algorithmus erzielt wurden, oder um die Dauer des Spiels (in letzterem Fall werden vermutlich Algorithmen entwickelt, die überleben, ohne Punkte zu erzielen, z. B. ein klassischer Fall, in dem Raumschiffe im Spiel Asteroids "gejagt" werden). Das Verhalten wird mit "Primitiven" (z. B. Monster erkennen / durch Drehen handeln usw.) und Bäumen implementiert, die die Kombinationen primitiver Strategien darstellen.

[1] Entwicklung verschiedener Pac-Man- Spielagenten mithilfe genetischer Programmierung von Atif M. Alhejali und Simon M. Lucas

[2] Pac-Man lernen: Ein evolutionärer, regelbasierter Ansatz von Gallagher und Ryan

[3] Lernen, mit regelbasierten Richtlinien mit geringer Komplexität zu spielen: Illustrationen durch Frau Pac-Man von István Szita András L'Orincz

vzn
quelle
Um sehr wählerisch zu sein, würde ich zwischen genetischer Programmierung und genetischen Algorithmen unterscheiden. Sicher sind sie jedoch eng miteinander verwandt.
Novak
@novak stimmte & thx zu, um den Unterschied herauszuarbeiten, der hier verschwommen war. In etwa ist GP die Verwendung von GAs , um Algorithmen zu entdecken, oder? ja, das gefundene / konstruierte Verhalten entspricht im Wesentlichen einem Algorithmus . & Natürlich ist die Technik außerhalb von Videospielen wahrscheinlich weit verbreitet, obwohl viele Beispiele bisher noch nicht bekannt sind von Koza's, die Bäume immer noch auf clevere Art und Weise nutzen!
vzn
1

Die jährliche GECCO-Konferenz (fast der erste Veranstaltungsort für Evolutionsberechnungsforschung) bietet einen Track mit dem Titel "Real World Applications".

Siehe auch diese aktuelle Präsentation:

NietzscheanAI
quelle