Habt ihr schonmal mit genetischen Algorithmen professionell gearbeitet?
-
Hallo,
habt ihr schonmal professionell mit solchen Algorithmen gearbeitet; diese für eine Firma, z.B. in der Auto- oder Luftfahrtindustrie programmiert oder daran mitgewirkt?
Dann würde mich mal interessieren, auf welche Probleme ihr gestoßen seid und welche Ergebnisse aus einer Bachelor- und oder Masterarbeit euch geholfen hätten?Danke,
Thilo
-
Ich habe noch nie mit genetischen Algorithmen gearbeitet, habe sie aber konzeptuell im Studium kennengelernt. Generell bin ich sehr skeptisch, wenn ich diesen Begriff höre. Ich assoziiere ihn mit katastrophalem Konvergenzverhalten und denke, dass es in den meisten Fällen wesentlich effizientere Herangehensweisen an entsprechende Problemstellungen gibt. Letztendlich setzt man derartige Algorithmen ja im Zusammenhang mit Optimierung ein. Ich gehe aber davon aus, dass in dem Zusammenhang zum Beispiel Gradientenabstiegsverfahren oder vielleicht Quasi-Newton-Verfahren im Allgemeinen besser geeignet sind.
Ich würde mich aber auch freuen, wenn mich Leute hier eines besseren belehren. Wo seht Ihr die Stärken von genetischen Algorithmen?
EDIT: Naja, es hängt natürlich von der "Fehlerfunktion" ab, bezüglich der man optimieren muss. Wenn diese sehr viele kleine lokale Minima hat, dann muss man irgendetwas bauen, was einen davon abhält, in ein solches lokales Minimum hineinzukonvergieren. Genetische Algorithmen sind diesbezüglich wohl nicht sehr anfällig. Aber man könnte sicherlich auch etwas in Richtung Simulated Annealing bauen.
-
Ja, das ist richtig. Genetische Algorithmen sind oftmals langsamer als andere Algorithmen. Ich hatte auch mal im Vergleich das 8-Damen-Problem einmal mit einem genetischen Algorithmus und dann mit Backtracking gelöst - da war Backtracking viel schneller.
Die Stärke genetischer Algorithmen sehe ich aber darin, dass sie auf sehr viele Probleme ohne große Änderungen angewendet werden können. Stehen Codierung und Fitnessfunktion fest, laufen sie ja schon - mehr oder weniger gut, aber sie laufen und finden oft gute Lösungen. Man braucht also nicht so viel über das Problem zu wissen, um es mit einem genetischen Algorithmus lösen zu können.
Schafft man, das Konvergenzverhalten allgemein zu verbessern, so dass sie mit anderen Algorithmen mithalten können, dann würden sie wohl die erste Wahl darstellen, wenn man gute Lösungen für ein Problem sucht.
-
Thilo87 schrieb:
Die Stärke genetischer Algorithmen sehe ich aber darin, dass sie auf sehr viele Probleme ohne große Änderungen angewendet werden können. Stehen Codierung und Fitnessfunktion fest, laufen sie ja schon - mehr oder weniger gut, aber sie laufen und finden oft gute Lösungen. Man braucht also nicht so viel über das Problem zu wissen, um es mit einem genetischen Algorithmus lösen zu können.
Schafft man, das Konvergenzverhalten allgemein zu verbessern, so dass sie mit anderen Algorithmen mithalten können, dann würden sie wohl die erste Wahl darstellen, wenn man gute Lösungen für ein Problem sucht.
Ich denke, es gibt da einen Tradeoff. Um gutes Konvergenzverhalten zu kriegen, muss Dein Algorithmus auf die Problemstellung angepasst sein. Oder andersherum: Wenn Du etwas über die Problemstellung weißt, dann nutze es.
-
Gute Frage
Wenn ich darf, würde ich die gerne erweitern, ob jemand überhaupt irgendwas aus dem Bereich 'Soft computing' mal außerhalb des Studiums produktiv eingesetzt hat.Ich hab in dem Bereich meine Diplomarbeit geschrieben, aber hat mir eigentlich wenig gebracht, da ich
- überproportional viel vergessen habe
- es nie irgendwo eingesetzt habe
Also auf deine Frage ein klares 'Nein'.
-
Ich hab das auch noch nie gebraucht und bin auch eher etwas skeptisch, ob es dafür tatsächlich sinnvolle Anwendungsfälle gibt.
In der c´t gabs mal irgendein Demoprogramm, das mit Hilfe von genetischen Algorithmen ein Bild auf eine bestimmte Art verfremdet hat. Aber keine Ahnung, ob es dafür nicht auch schnellere Algorithmen gibt, vermute aber schon.
-
In Sachen genetische Algorithmen stimme ich meinen Vorrednern zu.
Jockelx schrieb:
Wenn ich darf, würde ich die gerne erweitern, ob jemand überhaupt irgendwas aus dem Bereich 'Soft computing' mal außerhalb des Studiums produktiv eingesetzt hat.
Da da ja wohl auch Fuzzy Logic dazu gehört, ja damit hab ich zu tun. In C++ bei der Steuerung von Industrierobotern.
Neuronale Netze gehören wohl auch dahin, die findet man auch in der Bildverarbeitung. Da kenne ich mich aber nicht so aus.
-
Hm, ist auch interessant zu wissen, dass diese Art von Algorithmus in der Praxis anscheinend selten eingesetzt wird
Aber gut, genetische Algorithmen gehen ja in Richtung der künstlichen Intelligenz, was ein enorm komplexes Thema ist, also ist es auch nicht verwunderlich, dass diese noch keine großartigen Ergebnisse liefern. Aber vielleicht haben sie ja das Potenzial dazu.
Da man sie eben ohne große Änderungen an viele verschiedene Probleme anwenden kann, sind sie ja zumindest schonmal anpassungsfähiger als spezielle Algorithmen, was ein Zeichen von Intelligenz ist. Ziel der künstlichen Intelligenz ist es ja, Algorithmen zu haben, die selbständig die Eigenschaften eines Problems erkennen und nutzen, um dieses zu lösen.
Deswegen finde ich sie auch so interessant.
-
nn schrieb:
Jockelx schrieb:
Wenn ich darf, würde ich die gerne erweitern, ob jemand überhaupt irgendwas aus dem Bereich 'Soft computing' mal außerhalb des Studiums produktiv eingesetzt hat.
Da da ja wohl auch Fuzzy Logic dazu gehört, ja damit hab ich zu tun. In C++ bei der Steuerung von Industrierobotern.
Neuronale Netze gehören wohl auch dahin, die findet man auch in der Bildverarbeitung. Da kenne ich mich aber nicht so aus.
"Fuzzy Logic" erscheint mir persönlich wesentlich interessanter als die genannten Genetischen Algorithmen zu sein. Ich sehe Fuzzy Logic vor allem da, wo "Expertenwissen" nicht genau zu quantifizieren ist. Menschen arbeiten nunmal mit sehr schwammigen Begriffen. Um so etwas zu modellieren, ist Fuzzy Logic gemacht.
Künstliche Neuronale Netze sehe ich hingegen ähnlich skeptisch wie die Genetischen Algorithmen. Letztendlich haben sie auch ähnliche Eigenschaften... Man versucht, um die Modellierung der Problemstellung herumzukommen oder sie zumindest nicht sehr detailliert machen zu müssen. In dem Fall bieten sich KNNs an. Wenn man aber mehr über die Problemstellung weiß, dann gibt es bessere Alternativen. Zum Beispiel, wenn man einen Klassifikator baut: Im Optimalfall kann man die Problemstellung dann gut genug modellieren, um einen Bayes-Klassifikator zu bauen. Eine Lösung mit KNNs ist eher zweite Wahl.
Ok, vielleicht sind KNNs durchaus häufiger sinnvoll anzuwenden als GA. Aber man sollte sich eben bewusst sein, dass es bessere Werkzeuge geben könnte.
-
Und wenn man genetische Algorithmen und KNNs einsetzt (einsetzen könnte), um bessere Algorithmen für spezielle Probleme zu generieren?
Das wär doch eine Aufgabe der künstlichen Intelligenz. Gibts in dieser Richtung Algorithmen, die soetwas können?
-
Finde ich jetzt wenig erfolgversprechend. Ein Algorithmus ist eine Abstraktion, so etwas wird ein KNN (in der heutigen Form) oder GA nie finden.
-
Ein Programm, das zufällige Zeichenfolgen erzeugt wird auch irgendwann den optimalen Algorithmus für jedes Problem finden
Genetische Algorithmen arbeiten da effizienter, also dass sie einen optimalen Algorithmus "nie" finden würden, ist nicht richtig. Die Frage ist blos, wie man sie dazu kriegt, dass sie intelligenter arbeiten, so dass man keine 1000 Jahre warten muss.
-
Die Zielfunktion stelle ich mir schwierig vor, Woran erkennst du denn einen guten Algorithmus? Mal einen Gang runtergeschaltet, woran erkennt man einen korrekten Algorithmus? Richtig, gar nicht.
-
Warum sollte man einen korrekten Algorithmus nicht erkennen können? Man kann beweisen, dass er funktioniert
Natürlich müsste dafür ein KNN oder etwas Ähnliches erst einmal die Prädikatenlogik beherrschen, aber das ist ja ein Klacks (Ironie).
-
Thilo87 schrieb:
Warum sollte man einen korrekten Algorithmus nicht erkennen können? Man kann beweisen, dass er funktioniert
Halteproblem, Satz von Rice?
Natürlich müsste dafür ein KNN oder etwas Ähnliches erst einmal die Prädikatenlogik beherrschen, aber das ist ja ein Klacks (Ironie).
Vergleichsweise ja, ohne Ironie.
-
Halteproblem, Satz von Rice?
Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.
(Dafür ist natürlich ein Referenzalgorithmus nötig)
-
Arcoth schrieb:
(Dafür ist natürlich ein Referenzalgorithmus nötig)
lol
-
Thilo87 schrieb:
Und wenn man genetische Algorithmen und KNNs einsetzt (einsetzen könnte), um bessere Algorithmen für spezielle Probleme zu generieren?
Also der da hat geschnallt, was ihm passierte und schaltete einen Schritt zurück:
http://www.acooke.org/malbolge.html
-
Arcoth schrieb:
Halteproblem, Satz von Rice?
Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.
Im Allgemeinen geht das so nicht. Bashar hat ja schon das Halteproblem erwähnt. Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird? Du kannst das Ergebnis des Algorithmus also nicht mit einer Referenz vergleichen, weil Du unter Umständen kein Ergebnis vom Algorithmus kriegst. Jenseits davon ist der Ansatz nicht praktikabel, da es wohl meistens in Abhängigkeit der Problemgröße exponentiell viele Instanzen einer Problemstellung geben kann. Wenn man also so an die Sache herangeht, dann wird man nie fertig.
Was allerdings teilweise funktioniert ist eine formelle Übersetzung von "Code" in andere Darstellungen bzw. Semantiken, so dass man den Code auf eine Form zurückführt, die der formellen Spezifikation des Algorithmus entspricht. Allerdings geht das nur bei stark eingeschränkten Sprachen.
...siehe zum Beispiel da: https://de.wikipedia.org/wiki/Formale_Semantik#Formale_Semantik_in_der_Informatik
-
Arcoth schrieb:
Halteproblem, Satz von Rice?
Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.
Schon bei sowas einfachem wie sort() kann ich nicht glauben, daß man mit Rumprobieren und Vergleichen weit kommt.
Alle vector<int> aufzuzählen stelle ich mir ein wenig mühsam vor. Wieviele gibt es davon nochmal?
Vielleicht tut das zu testende Programm gar nicht bei allen Eingaben anhalten? Das macht das Testen recht mühsam. Man bräuchte schon eine sagenumwobene Cray(1).
