Archiv verlassen und diese Seite im Standarddesign anzeigen : Einfach nur mal so: Genetische Algorithmen
WhiteVelvet
2011-08-25, 16:00:05
Habe eben diesen interessanten Link zum Thema "genetische Algorithmen" gefunden. Da lernt ein Computerprogramm, wie man am effektivsten ein 2D-Auto baut, um über eine Huppellandschaft zu fahren:
http://www.qubit.devisland.net/ga/
Ganz witzig anzuschauen, wie es lernt :) Ich dachte mir, ich teile den Link mal mit Euch!
AlecWhite
2011-08-25, 16:32:34
Wenn man genau ist: Das Programm lernt nicht, wie das Fahrzeug gebaut wird, sondern sucht nach der optimalen Zusammenstellung der Komponenten für einen gegeben Test-Parcour. Witzig anzuschauen und eine nette Visualisierung des Konzepts, aber nicht was mich vom Hocker hauen würde.
Unter lernen würde eher verstehen, dass man eventuell irgendwann selbstständig bestimmte Restruktionen ändert (z.b. Mehr Räder o.ä)
Marscel
2011-08-25, 16:58:50
Jo, genetische Algorithmen zeichnen sich dadurch aus, dass in erster Linie probiert wird und der beste Pfad als Ausgang für neue Kombinationen mit einer Zufallskomponente genommen wird, dann wird wieder verglichen, selektiert und so weiter.
Richtiges Lernen ist das leider nicht - mehr so "Hau-druff bis rennt", aber bequem zu programmieren. ;)
BAGZZlash
2011-08-25, 17:59:10
Richtig, "Lernen" ist das nicht. Das behauptet genetischer Code aber auch gar nicht zu tun. Es wird eben ein genetischer Reifungsprozess abgebildet: Zufällige Mutationen und survival-of-the-fittest.
Yavion
2011-08-25, 23:48:46
Dabei fällt mir das Beispiel hier ein:
http://arstechnica.com/science/news/2011/07/running-high-performance-neural-networks-on-a-gamer-gpu.ars
Hier benutzt man evolutionäre Algorithmen, um "neuronale Netzwerke" zu optimieren. Das ganze dann parallelisiert auf GPU-Clustern.
Damit könnte man auch ein neuronales Netzwerk entwickeln, dass aus einem haufen Teilen ein Vehikel konstruiert.
Für dieses Problem gibt es aber bessere Verfahren.
WhiteVelvet
2011-08-26, 09:04:33
Gut, dazu müsste man jetzt genauer definieren, was "lernen" genau ist. Der Autor sagt, dass das Programm am Anfang noch gar nicht weiß, dass die Räder auf den Boden gehören, irgendwann merkt es sich das aber. Lernen ist ja sozusagen ein ständiges ausprobieren und optimieren.
Im Studium hatte ich mal sehr interessante Videos gesehen, habe den Namen leider vergessen. Da "lernen" einfach aufgebaute Figuren, bestimmte Bewegungen zu machen: Kriechen von A nach B oder einfaches Fliegen (also Flugbewegungen um den Boden zu verlassen und aufzusteigen). Muss ich nochmal nach googlen...
Nasenbaer
2011-08-28, 21:31:01
Werden genetische Algorithmen eigentlich irgendwo in der Praxis eingesetzt oder sind die bisher eher akademischer Spielkram?
natürlich werden die in der Praxis eingesetzt. Sind doch nur Heuristiken für Optimierungsprobleme.
Mutation und Crossover sind eben nachvollziehbar sinnvoll.
da ist auch keine Magie hinter. Es sind vorgegebene Techniken zur lokalen Verbesserung.
ein einfacher lernender algorithmus könnte z.B. so aussehen
angenommen wir haben eine multimodale funktion R^n->R dessen minimum wir bestimmen wollen
a) wir wählen einen zufälligen parametervektor aus dem kompletten raum,
und merken uns den mit minimalen funktionswert, das wiederholen wir bis wir zufrieden sind,
sicher können wir uns sein das globale optimum gefunden zu haben, wenn wir den kompletten parameterraum abgesampled haben
b) anstatt den vektor aus dem gesamten raum zu nehmen, wählen wir einen vektor aus einer (kleineren) kugel um einen zufälligen startwert.
haben wir uns verbessert ist der bessere vektor unser neuer startpunkt. haben wir uns eine weile nicht verbessert, vergrößern wir den radius der kugel
c) statt einen parametervektor zu nehmen, verwenden wir k stück (im kontext ist das dann eine population) und gehen ansonsten wie bei b) vor.
d) statt einer komplett zufälligen auswahl neuer parametervektoren, kombinieren wir einen neuen vektor aus bestehenden vektoren und gehen ansonsten wie bei c) vor
Tiamat
2011-10-03, 14:02:35
Hab jetzt ne Abschlussarbeit in diesem Bereich in Aussicht.
Genetische Codierung von Neuronalen Netzen :-)
Thunderhit
2011-10-03, 15:05:48
Beschränkt auf bestimmte Netze?
Shink
2011-10-03, 15:51:43
Ganz witzig anzuschauen, wie es lernt :) Ich dachte mir, ich teile den Link mal mit Euch!
Also mich macht das eher aggressiv. Ein Beweis dafür dass man nicht alles mit genetischen Algorithmen lösen sollte auch wenn es cool klingt.:freak:
Es wäre interessant auszuprobieren wieviel schneller oder langsamer man im Durchschnitt ist wenn man Radien und Positionen von Reifen und Lasten zufällig auswählt.
Tiamat
2011-10-03, 16:06:26
Beschränkt auf bestimmte Netze?
Ich geh davon aus, aber einiges wurde noch nicht formuliert. Hab am Donnerstag die Gelegenheit den genauen Umfang zu erfragen.
Bisher weiß ich nur, das Netze mit Genetischer Programmierung erzeugt werden und über den GA lernen sollen.
Also mich macht das eher aggressiv. Ein Beweis dafür dass man nicht alles mit genetischen Algorithmen lösen sollte auch wenn es cool klingt.:freak:
Es wäre interessant auszuprobieren wieviel schneller oder langsamer man im Durchschnitt ist wenn man Radien und Positionen von Reifen und Lasten zufällig auswählt.
:)
Nicht sehr viel langsamer fürchte ich... :freak:
Dieser ganze genetische Kram kommt mir sowieso ein bisschen überbewertet vor. Im kleinen gibts bessere Methoden und für large scale Probleme kann mans auch nicht so recht gebrauchen.
Thunderhit
2011-10-03, 18:23:59
@Tiamat Hab im Rahmen eines Projekts für das Fach Evol. A. über das Lernen von KNN mittels Evo.A. geschrieben. War beschränkt auf ein vollständig vermaschtes Feed-Forwardnetz. Lief an sich ganz gut mit dem genetischen Algorithmus das Trainieren. Das Netz war zwar relativ klein, aber war doch schon ganz schick. Aber hab bei den Recherchen auch gelesen, dass evol. A. auch benutzt werden können, um die Topologie des Netzes etc. zu bestimmen. Hast also genug vor dir.
Soll es eine Bachelor- oder Masterarbeit werden?
@Shink es sollte rein durch Zufall viel langsamer sein, da keine Verbesserung bei der Auswahl der Variablen stattfindet. Der evol. A. sollte durch Rekombination, Selektion und Mutation ja schneller zum Ziel kommen.
@Gast dann hast du nicht den Sinn der genetischen Alg. verstanden. Ziel ist, wie so oft beim Softcomputing, eine gute Lösung zu finden. Dabei nimmt man in Kauf, dass die gefundene Lösung nicht die optimalste sein muss, da die optimalste selten nötig ist. Manche Probleme lassen sich vielleicht zerlegen in viele kleinere Probleme, Zusammenhänge finden etc. pp., jedoch stellt sich die Frage ob mit zu vielen Variablen oder Teilproblemen in absehbarer Zeit eine Lösung gefunden werden soll.
[...]
@Gast dann hast du nicht den Sinn der genetischen Alg. verstanden. Ziel ist, wie so oft beim Softcomputing, eine gute Lösung zu finden. Dabei nimmt man in Kauf, dass die gefundene Lösung nicht die optimalste sein muss, da die optimalste selten nötig ist. Manche Probleme lassen sich vielleicht zerlegen in viele kleinere Probleme, Zusammenhänge finden etc. pp., jedoch stellt sich die Frage ob mit zu vielen Variablen oder Teilproblemen in absehbarer Zeit eine Lösung gefunden werden soll.
Naja, so wie ich das verstanden habe ist der Vorteil dass es sehr einfach ist und auf eine große Klasse von Problemen anwendbar. Nur kann man halt wie bei vielen probabilistischen Algos keine/wenig Aussage über das Ergebnis machen (wird eine Lösung gefunden? Wird die richtige gefunden?)
Deshalb meinte ich, für kleine Probleme gibt es da durchaus bessere numerische Verfahren bei denen man auch Aussagen über Konvergenz und Existenz/Richtigkeit der Lösung machen kann. Und für große Probleme kann mans auch nicht so recht brauchen, da nimmt man convexe Methoden.
Genetischen Algos sind halt einfach und schnell implementiert, das ist schon ganz nett.
Thunderhit
2011-10-03, 23:03:31
Naja, da fehlt aber noch der mitunter wichtigste Teil genetischer Alg: Es lassen sich ziemlich gute Aussagen über das Ergebnis treffen, denn für die Bewertung der Güte der Gene (=codierte Lösung) ist eine Fitnessfunktion vonnöten. Diese weist einem Gen eine Güte zu, anhand derer ermittelt wird, welche Individuen überleben und welche nicht. Wenn ein Individuum keine gültige Lösung darstellt, sollte es dort aussortiert werden. Durch die Minimierung dieser Güte sollte im Idealfall eine Konvergenz der Güte erreicht werden. Dort kann es natürlich wie beim Gradientenverfahren passieren, dass an einem bestimmten Punkt das Verfahren konvergiert, obwohl das Ergebnis bei weitem noch nicht optimal ist. Aber auch dazu gibt es Lösungen.
Es stimmt natürlich, dass niemand einen evol. Alg. nehmen wird, wenn für das Problem bereits eine Lösung existiert (siehe mathemat. Verfahren).
Genetische Alg. müssen wie gesagt auch nicht rein für die Problemlösung genutzt werden, sondern können z.B. zur Bestimmung einer Topologie für künstliche neuronale Netze verwendet werden. Das Einsatzgebiet ist also recht groß.
Aber ja, die relativ schnelle und einfache Implementation gegenüber einer hochdurchdachten Lösung ist natürlich ein Vorteil davon.
Tiamat
2011-10-03, 23:04:52
@Tiamat Hab im Rahmen eines Projekts für das Fach Evol. A. über das Lernen von KNN mittels Evo.A. geschrieben. War beschränkt auf ein vollständig vermaschtes Feed-Forwardnetz. Lief an sich ganz gut mit dem genetischen Algorithmus das Trainieren. Das Netz war zwar relativ klein, aber war doch schon ganz schick. Aber hab bei den Recherchen auch gelesen, dass evol. A. auch benutzt werden können, um die Topologie des Netzes etc. zu bestimmen. Hast also genug vor dir.
Soll es eine Bachelor- oder Masterarbeit werden?
Bachelor-Thesis. Ja das denk ich mir =), ich habe vor zwei Semester die Vorlesung Maschinelles Lernen gehört, das sollte mir schon ne Hilfe dabei sein, d.h bei 0 muss ich nicht anfangen. Aber es reicht natürlich nicht um mal salopp die Thesis zu verfassen, Arbeit wird das noch genug :)
Aber das Thema und diesen Bereich find ich sehr interessant.
Thunderhit
2011-10-03, 23:07:42
Geht mir ähnlich, an meiner FH gibts die Vorlesung Mustererkennung im Master, die ich im kommenden Semester belege, bin schon gespannt. Wahrscheinlicheitsrechnung hurra... *g*
Hab auch vor, evt. in dem Bereich meine Master-Thesis zu schreiben... mal schaun. Aber ja, find den Bereich auch ziemlich interessant.
Laz-Y
2011-10-21, 20:14:23
Ich würde genetische Algorithmen sicher nicht als Lernen bezeichnen. Denn die Bewertungskriterien sind bereits vorgegeben und gerade da steckt die eigentlich Arbeit.
Tiamat
2011-10-22, 11:30:38
Nachdem ich bei der Vorabrecherche im Buch Simulation neuronaler Netze von Zell gelesen habe, dass es früher schon Versuche von Genetischen Algorithmen, die Neuronalen Netze codieren gegeben hat und laut ihm auch nicht erfolgreicher als moderne Lernverfahren(Backperculation, Cascade Correlation, e.t.c) waren, ist der wissenschaftliche Aspekt der Thesis wohl schon vorab in Frage gestellt.
Deswegen hab ich mich für ein anderes Thema für meine Thesis entschieden :
Rekurrente Neuronale Netze und Berechenbarkeit : Das ist selbst heute noch ein ziemliches Forschungsgebiet, weil von der Gattung her bisher nur Hopfield Netze richtig analysiert wurden.
Ich würde genetische Algorithmen sicher nicht als Lernen bezeichnen. Denn die Bewertungskriterien sind bereits vorgegeben und gerade da steckt die eigentlich Arbeit.
Finde ich auch, m.M.n. sind genetische Algos einfach numerische Optimierungsverfahren. Halt mit ein bisschen Evolutionstheorie rundherum :)
petersenk
2011-10-23, 16:11:53
Finde ich auch, m.M.n. sind genetische Algos einfach numerische Optimierungsverfahren. Halt mit ein bisschen Evolutionstheorie rundherum :)
Da bin ich aber anderer Meinung. Menschliches Lernen ist in der Regel auch nur Wiederholung. Immer und immer wieder, was genetischen Algorithmen doch recht nahe ist. IMHO überhöht ihr, in eurer Romantik, den Menschen mal wieder. Aber der Mensch ist auch "nur" eine Maschine. :)
Da bin ich aber anderer Meinung. Menschliches Lernen ist in der Regel auch nur Wiederholung. Immer und immer wieder, was genetischen Algorithmen doch recht nahe ist. IMHO überhöht ihr, in eurer Romantik, den Menschen mal wieder. Aber der Mensch ist auch "nur" eine Maschine. :)
Dagegen sagt ja niemand etwas.
IMO ging es um die Abgrenzung zum maschinellen Lernen, dort kann man nämlich auch Aussagen über unbekannte Daten treffen (z.b. Klassifikation). Während genetische Algos IMO zu den Optimierungsmethoden zählen, ähnlich Gauss-Newton und Konsorten. Es ist einfach eine Methode um Extremwerte einer gegebenen Funktion zu finden. Statt auf analytischen Weg (gradient descent) passiert das halt durch "geschicktes ausprobieren". Das ist schon was anderes wie Lernalgorithmen, wo man nach dem Training Aussagen über unbekannte Daten treffen kann.
WhiteVelvet
2011-10-25, 10:51:05
Hier ist noch so ein Beispiel... allerdings stellt sich der Algorithmus ziemlich dämlich an...
http://www.boxcar2d.com/index.html
Ich suche immer noch den Link zu den Forschungen an diesen 3D Figuren, die fliegen, krabbeln und gehen sollen...
Laz-Y
2011-10-25, 18:36:36
Da bin ich aber anderer Meinung. Menschliches Lernen ist in der Regel auch nur Wiederholung. Immer und immer wieder, was genetischen Algorithmen doch recht nahe ist. IMHO überhöht ihr, in eurer Romantik, den Menschen mal wieder. Aber der Mensch ist auch "nur" eine Maschine. :)
Menschliches Lernen ist aber vor allem Finden von Lösungsmöglichkeiten auf Grund früherer Erfahrungen.
Sowas gibts bei genetischen Algorithmen nicht. Da muss diese ganze Erfahrung hinterlegt (=programmiert) werden.
Menschliches Lernen ist aber vor allem Finden von Lösungsmöglichkeiten auf Grund früherer Erfahrungen.
Sowas gibts bei genetischen Algorithmen nicht. Da muss diese ganze Erfahrung hinterlegt (=programmiert) werden.
Schnulli
IMO ging es um die Abgrenzung zum maschinellen Lernen, dort kann man nämlich auch Aussagen über unbekannte Daten treffen (z.b. Klassifikation). Während genetische Algos IMO zu den Optimierungsmethoden zählen, ähnlich Gauss-Newton und Konsorten.
Ein Klassifikationsalgorithmus ist auch nur ein Optimierungsproblem bezogen auf eine Wahrscheinlichkeitsverteilung
Statt auf analytischen Weg (gradient descent) passiert das halt durch "geschicktes ausprobieren". Das ist schon was anderes wie Lernalgorithmen, wo man nach dem Training Aussagen über unbekannte Daten treffen kann.
Gradient Descent ist ein einfaches Optimierungsverfahren
edit: und natürlich ist es kein Problem einen Klassifikator auf Basis eines genetischen Algorithmus zu entwerfen.
Ein Klassifikationsalgorithmus ist auch nur ein Optimierungsproblem bezogen auf eine Wahrscheinlichkeitsverteilung
Gradient Descent ist ein einfaches Optimierungsverfahren
edit: und natürlich ist es kein Problem einen Klassifikator auf Basis eines genetischen Algorithmus zu entwerfen.
Ein Klassifikationsalgo modelliert die WSVerteilung aufgrund der vorliegenden Daten. Ein genetischer Algo muss immer das vollständige Modell vorliegen haben, denn mit diesem wird die Fitness der Individuen berechnet. Das ist IMO ein grosser Unterschied.
Ein Klassifikationsalgo modelliert die WSVerteilung aufgrund der vorliegenden Daten.
Bestimmte Klassen von Klassifikatoren kann man dazu verwenden die Wahrscheinlichkeitsdichte zu schätzen. Beim Bayes-Klassifikator muss sie z.B. gegeben sein.
Ein genetischer Algo muss immer das vollständige Modell vorliegen haben, denn mit diesem wird die Fitness der Individuen berechnet.
vollständiges Modell? Ich skizziere gern einen Klssifikator der "genetisch" funktioniert.
Bestimmte Klassen von Klassifikatoren kann man dazu verwenden die Wahrscheinlichkeitsdichte zu schätzen. Beim Bayes-Klassifikator muss sie z.B. gegeben sein.
Soweit ich mich erinnern kann müssen für den Bayes Classifier nur gelabelte Daten vorhanden sein (zu jedem Datum x das Klassenlabel y). Das ist ja gerade der Vorteil. Was man erhält ist ein Abschätzung der WSVerteilung sodass man neue Daten mit dieser Abschätzung auswerten kann.
vollständiges Modell? Ich skizziere gern einen Klssifikator der "genetisch" funktioniert.
Man kann es wohl irgendwie formulieren, aber das Grundprinzip von genetischen Algos ist doch wohl
1. Erzeuge Individuen mit neuen Parametern
2. Auswerten auf dem bekannten Modell (!)
3. "Gute" Individuen überleben, "schlechte" nicht, Mutation, Crossover, ... , goto 1
Die Fitness Funktion (das Modell) muss gegeben sein, sonst funktionierts nicht. Wie lange die Auswertung der Fitnessfunktion dauert ist doch sogar eine wesentliche Kenngröße ob/wann man genetische Algos sinnvoll einsetzen kann.
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.