Diskussion:Genetischer Algorithmus

Diversifikation

Der Artikel erwähnt (bei Mutation) die Diversifikation, verlinkt auf "Diversifikation (Biologie)". Den Artikel haben die Biologen dann gelöscht, weil ??? Wenn ich mal Zeit habe, dann kommt in hiesigen Artikel ein entsprechender Abschnitt rein, sofern's keinen massiven Widerspruch gibt. --arilou 15:06, 23. Jul. 2010 (CEST) PS: Manches sollte man wohl lieber nicht den Biologen überlassen...

Evolutionsstrategien vs. Genetische Algorithmen

Es ist nicht richtig, dass Evolutionsstrategien eine Unterart von genetischen Algorithmen sind.

Eine genetischer Algorithmus ist ein evolutionärer Algorithmus in dem die Individuen als Bitstrings codiert sind. Evolutionsstrategien hingegen codieren die Individuen in einem reelwertigen Vektor.

Ich werde den Artikel überarbeiten wenn ich mal Zeit hab....

Das stimmt. Beides sind Evolutionäre Algorithmen, die auf einer Stufe stehen. Inzwischen werden reine GAs und reine ES-Implementierungen nur noch zu "wissenschaftlichen Zwecken" benutzt. Längst gibt es zum Beispiel GAs, die reelle Zahlen benutzen. --Braeutigam

Nein das stimmt nicht. Genetische Algorithmen müssen NICHT unbedingt Bitstrings als Codierung verwenden. Das ist ein Urban Myth. --217.81.249.90 18:55, 29. Jul. 2009 (CEST)

Optimierungsverfahren

Sie werden vor allem für Probleme eingesetzt, für die keine geschlossene Lösung vorliegt

Gilt das nicht generell fuer alle Suchverfahren? Wenn man eine geschlossene Loesung fuer ein Optimierungsproblem hat, braucht man nicht mehr suchen. MH 18:59, 2. Mär 2004 (CET)

---

Nun ja, das kommt ja ganz auf die Größe des Problems an. Es muss nicht gleich ein NP-Hartes Problem sein, damit man ein Suchverfahren anwendet. Je nach Performanz des Rechners, oder eventuell auch als Eröffnungsverfahren, kann man Suchverfahren verwenden um eine "gute" Lösung oder auch Anfangslösung (in Form eines Eröffnungsverfahrens)zu bekommen.SW 84.148.225.209 23:50, 30. Jan 2006 (CET)

Textspende aus meiner Proseminar-Ausarbeitung

Ich lager hier mal einen Abschnitt aus meiner Ausarbeitung für ein Proseminar zwischen, ist noch im LaTeX-Format. Hiermit unter der GFDL freigegeben. --Head 16:18, 2. Jul 2004 (CEST)

---

Das Prinzip der genetischen Algorithmen wurden vom US-amerikanischen Mathematiker John Henry Holland (* 1929) entwickelt\footnote{John H. Holland, Adaptation in Natural and Artificial Systems: 2nd ed., MIT Press, 1992}. Mit genetischen Algorithmen wird versucht, das Konzept der Evolutionstheorie auf die Informatik zu übertragen.

Das Prinzip beruht darauf, dass jeweils zwei Zustände zu zwei neuen verschmolzen werden, in der Hoffnung, dass einer der beiden die Vorteile seiner "`Eltern"' vereint.

Grundlage jedes genetischen Algorithmus ist eine Bewertungsfunktion, die in Anlehnung an das natürliche Vorbild in diesem Zusammenhang auch \emph{Fitness-Funktion} genannt wird. Sie gibt die Güte eines Zustandes an, entsprechend den in den vorherigen Kapiteln beschriebenen heuristischen Funktionen, und entspricht der Überlebens- und Fortpflanzungsfähigkeit eines Organismus.

Zunächst werden einige (gradzahlig viele) Zustände zufällig generiert, die \emph{Anfangspopulation}. Befindet sich darunter zufällig ein Zielzustand, sind wir bereits fertig. Andernfalls wird zu jedem Zustand der Fitness-Wert berechnet; ein hoher Fitness-Wert erhöht die die Wahrscheinlichkeit, dass der Zustand beim nächsten Schritt, der \emph{Selektion}, übernommen wird.

Zustände können bei der Selektion auch mehrfach bzw. überhaupt nicht zum Zuge kommen, allerdings ist die Menge der selektierten Zustände stets so groß wie die Anfangspopulation. Je zwei selektierte Zustände bilden nun ein Paar und werden \emph{gekreuzt}, so dass zwei neue Zustände entstehen. Auch der Kreuzungsschritt kann derart implementiert werden, dass der Zufall einen Einfluss darauf hat, wie genau die Verschmelzung abläuft.

Schließlich werden die entstandenen Zustände - ebenfalls nach dem Zufallsprinzip - minimal geändert, bevor von vorne begonnen wird. Diese \emph{Mutation} ist extrem wichtig, um zu verhindern, dass der Algorithmus in eine Endlosschleife läuft; schließlich ist es denkbar, dass nur ein einziger Zustand selektiert wird. Auch hier diente die Natur als Vorbild, wo mangelnde Vielfalt zu Inzucht führt.

Genetische Algorithmen werden meist eingesetzt, wenn auch ein nur lokales Maximum eine akzeptable Lösung darstellt. Doch wenngleich sie sehr effizient arbeiten und sich einfach parallelisieren lassen, fanden sie lange kaum praktische Anwendung; dies hat sich in den letzten Jahren geändert. So werden sie etwa Telekommunikationsfirmen eingesetzt, um Mobilfunkmasten möglichst effizient zu positionieren, also mit möglichst wenig Masten eine möglichst hohe Abdeckung zu erreichen. 2001 entwickelten Forscher der Purdue University (Indiana, USA) ein entsprechendes Verfahren zur Optimierung von Netzwerken von nicht-geostationären Satelliten\footnote{New Scientist, 16. Oktober 2001, http://www.newscientist.com/news/news.jsp?id=ns99991437}.

Eine weitere Anwendungsmöglichkeit zeigten jüngst zwei Londoner Informatiker auf, die mittels genetischer Algorithmen Formel-1-Rennwagen optimierten, wobei die Simulation allerdings mit einem Computerspiel durchführt wurde\footnote{New Scientist, Ausgabe vom 19.06.2004, S. 22; http://www.newscientist.com/news/news.jsp?id=ns99996019}. Als Bewertungsfunktion diente hier die Rundenzeit; diese konnte durch Variation der 68 Eigenschaften wie Schaltübersetzung oder Reifendruck merkbar verbessert werden. Tatsächlich beschränkt sich die Anwendung genetischer Algorithmen in der Formel 1 jedoch noch auf Gebiete wie Boxenstoppstrategien und Komponentendesign.

---

Der aktuelle Text ist leider fachlich inkorrekt, da er Evolutionsstrategien als Variante Gentischer Algorrithmen nennt. Ebenso bleiben einige Hauptcharakteristike Genetischer Algorithmen (z.B. binäre Repräsentation der Individuen) völlig unerwähnt. Die Textspende von Head ist schon besser, hat aber auch noch Schwächen (Warum "Zustände" statt "Lösungen" oder "Individuen"?). Ich versuche kurzfristig bei meinen Artikeln etwas auszugraben, was noch FDL-fähig ist. --Joscho 17:51, 22. Sep 2004 (CEST)

Das stimmt, beides sind Evolutionäre Algorithmen und stehen damit auf einer Stufe. Hauptcharakteristika gibt es aber nicht mehr. Das war ursprünglich mal so. Inzwischen werden reine GAs und reine ES-Implementierungen nur noch zu "wissenschaftlichen Zwecken" (lies: Übungen für undergraduate students) benutzt. Längst gibt es zum Beispiel GAs, die reelle Zahlen benutzen und auch weitere Eigenschaften von ES-implementierungen haben, ohne ihre Vorteile aufzugeben (große Populationen z.B.). Braeutigam

Minimum vs. Maximum

Man sollte das Problem Minimierung vs. Maximierung ansprechen.

kwaxi 11:22, 9. Mär 2005 (CET)

Hi! Da kommt man über zwei Links hin: Optimierungsproblem. Allerdings ist mir dieser Artikel etwas unklar, was ich dort diskutieren werde (Diskussion:Optimierungsproblem). Szs 11:03, 11. Mär 2005 (CET)

Hab jetzt gesehen das auf der Seite Optimum die über nur einen Link, der allerdings in einem Beispiel weiter unten versteckt ist, erreichbar ist ebenfalls von Min-Max die Rede ist. Dennoch wird an zu wenig prominenter stelle darauf hingewiesen finde ich. kwaxi 22:12, 12. Mär 2005 (CET)

Aber Min-Max ist doch im tiefsten innern schon ein Optimierungsproblem, daher ist das auch vernünftig, dass an dieser Stelle darüber geschrieben wird. Aber es wird Dir keiner einen Strick draus drehen, wenn Du das hier auch nochmal einfügst, oder einen extra Artikel drüber schreibst.Szs 02:00, 13. Mär 2005 (CET)

Minimierung und Maximierung ist technisch dasselbe. Wenn man einen GA geschrieben hat zur Maximierung (mit der Fitnessfunktion f) dann kann man damit auch minimieren indem man einfach f negiert( siehe Van den Bergh,f(2006) An Analysis of PSO S.7) (nicht signierter Beitrag von 77.181.112.100 (Diskussion) 19:50, 24. Okt. 2007)

Verständlichkeit

Bitte überarbeitet den Artikel nochmal, so dass man ihn auch verstehen kann, wenn man sich nicht mit genetischen Algorithmen auskennt. Ich stehe selbst auf dem Standpunkt, dass ein gewisses fachbezogenes Wissen vorausgesetzt werden kann. Aber in diesem Fall wird Wissen vorausgesetzt, das eigentlich in diesem Eintrag vermittelt werden soll. --Cerno 04:01, 2. Mai 2005 (CEST)

Habe einen Einleitungssatz geschrieben, der für den interessierten Laien verständlich sein sollte. Der Rest des Artikels ist meiner Meinung nach verständlich. Szs 13:26, 20. Mai 2005 (CEST)

mutation binärer zahlen

Hi! Ist die bei dem Beispiel veränderte Stelle nicht eher die 4.? Denn es müssen ja die Stellen mutiert werden, die nicht allzugroße Veränderungen herbeiführen. Oder liege ich da falsch?

Gruß, Szs 15:32, 24. Okt 2005 (CEST)

Hi! Tut mir leid, ich bin 13 und kenne mich damit nicht aus, aber ich habe das auf eine Anweisung von einem Benutzer übernommen (siehe Diskussion:Mutation binärer Zahlen).

--FarinUrlaub @me (+)] 19:43, 24. Okt 2005 (CEST)

Evolutionärer Algorithmus vs. genetischer Algorithmus

Aus den Definitionen von beiden ist nicht eindeutig zu erkennen, dass ein Unterschied vorliegt. Gibt es überhaupt einen oder werden beide Begriffe nicht synonym verwendet? Ich konnte in der Fachliteratur keine eindeutige Aussage darüber entdecken.

kdot 23:13, 2. Mar 2006 (CEST)

Hallöchen. Nach meinen bisherigen Erfahrungen besteht der Einzige Unterschied zwischen Genetischen und evolutionären Algorithmen darin, dass GA soweit ich weiß ausschließlich binäre Codierung des "Genoms" benutzen. Evolutionäre Algorithmen hingegen können auch aus reellen Zahlen aufgebaut sein. Welches der beiden Verfahren das vorteilhaftere ist, wage ich nicht zu beurteilen. Fakt ist nur, dass Computer von "Natur aus" binärzahlen verarbeiten und somit sowieso eine Umwandluing der reelen Zahlen in Binärcode stattfindet. m.E. nach ist dieses Vorgehen nicht besonders effektiv. Da kann man auch gleich mit binären Genomen arbeiten. in eigenen Test lief der reine Genetische Algorithmus mit binärcodierung wesentlich Schneller als der mit reellen zahlen, da sich Operatoren wie Mutation und Kreuzung schneller und einfacher implementieren ließen. Beide Verfahren haben aber ihre Vor- und Nachteile. Im Zweifelsfall würde ich immer die binärcodierung bevorzugen, da sich damit wesentlich kürzere Laufzeiten des Algorithmus ergeben. Das wird vor allem bei der Anwendung der GA in der Genetischen Programmierung deutlich. Ich bitte hiermit um Korrekturen und Ergänzungen. Wer Rechtschreibfehler findet, darf sie behalten...

Genetische Algorithmen und Sudoku

Ist Sudoku nicht ein relativ schlechtes Beispiel wenn es um die lösung NP-schwerer Probleme mittels GA's geht ? Die Erwähnung von Sudoku suggeriert das sich das Spiel mittels eines GA's lösen lässt. Das mag schon der Fall sein allerdings ist meiner Meinung nach ein Genetischer Algorithmus eine denkbar schlechte Methode um ein Sudoku zu lösen...

Linkliste

die müsste gelegentlich mal aktualisiert werden. der erste link ist tot, und der zum mit ebenfalls. --Discipline 07:53, 13. Jan. 2007 (CET)

Binäre Zahl vs. Dualzahl

Sollte es statt Mutation binärer Zahlen nicht heißen Mutation von Dualzahlen? --Head 16:01, 26. Jun. 2007 (CEST)

Weblinks

Nach welchen Kriterien wurden hier die Weblinks entfernt, bzw. stehengelassen? Ich hab mir WP:WEB angeschaut und diese Rechtfertigt diese massive Loeschaktion nicht. Cheers, Pedro.Gonnet 11:56, 28. Jun. 2007 (CEST)

Anwendungsgebiete

Ich finde die Liste der Anwendungsbeispiele höchst bearbeitungsbedürftig. Ich denke sie sollte Beispiele für den praktischen Einsatz genetischer Algorithmen bieten, die ohne zusätzlicher Erklärung vom Leser erfasst werden können. Optimalerweise sollten Beispiele gefunden werden, bei denen genetischen Algorithmen bewusst der Vorzug gegenüber anderen Optimierungsverfahren gegeben wird. Hier "Optimierung" zu nennen ist völlig sinnfrei, da das selbstverständlich das einzige Ziel von genetischen Algorithmen ist. Was genetische Algorithmen mit der "Untersuchung des Fermatschen Satzes" zu tun haben (was auch immer damit genau gemeint ist) ist wiederum gänzlich unbegreiflich. Ich denke, dass hier handfestere Beispiele nötig sind, ansonsten ist die Liste an sich sinnlos. Vorschläge? --Iurtz with an i 23:28, 20. Nov. 2009 (CET)

das sehe ich ähnlich, zumindest die angesprochenen Dinge habe ich mal geändert, und Fermat entfernt weil ich das gar nicht verstehe. --Tinz 18:02, 4. Jan. 2011 (CET)

Ich habe das Kapitel Anwendungen jetzt grundlegend überarbeitet - in der alten Version waren ja konkrete Anwendungen und ganze Anwendungsgebiete ohne jegliche Unterscheidung zusammen gelistet. Die praktischen Anwendungen habe ich so belassen wie sie sind, allerdings mit einleitenden Kommentaren. Iurtz' Kommentar ist inhaltich voll zuzustimmen, allerdings werden genetische Algorithmen meines Wissens nach in der Praxis überhaupt nur dann eingesetzt, wenn für das spezifische Problem kein extra zugeschnittener Lösungsalgorithmus bekannt ist, und der Analyst aus irgendeinem Grund auf den Einsatz recheneffizienterer Verfahren (gradientenbasierte, bzw Simulated Annealing wenn die Fitnesslandschaft arg zerklüftet ist) verzichten will (GA klingt exotischer, lässt sich gut verkaufen). Wenn überhaupt, werden sie in der Praxis mWn nur zur Modellkalibierung wie beispielsweise bei neuronalen Netzen eingesetzt. Allerdings habe ich hierfür keinen Quellennachweis - wenn jemand einen solchen liefern könnte, könnte man das im Text hinzufügen. Die Genetische Programmierung ist ein eigenes Verfahren und keine direkte Anwendung der GA, deshalb habe ich sie herausgenommen - alle anderen Punkte aus der früheren Aufzählung habe ich belassen. Außerdem habe ich noch einen Absatz zu den Anwendungen in der theoretischen Forschung hinzugefügt. (nicht signierter Beitrag von 81.217.9.35 (Diskussion) 23:39, 15. Jan. 2011 (CET))

DNA

Weiß jemand von Euch, mit welchem Algorithmus man bei der DNA den codierenden DNA-Strang von dem nicht codierenden unterscheiden kann? Wie würde man diesen dann nennen? Die Unterscheidung zwischen codierendem und nicht codierendem Strang ist ja eine Informatik-Anwendung im Forschungsbereich Genetik. Vielleicht sollte man das Adjektiv 'genetisch' genauer definieren, damit sich die verschiedenen Wissenschaftszweige nicht ins Gehege kommen. Was erzeugt er denn, der genetische Algorithmus? -- Rilu 04:32, 4. Jan. 2011 (CET)

Ein Genetischer Algorithmus hat nichts mit der DNA zu tun, da hast Du was falsch verstanden. --P.C. ✉

Die Terminologie genetischer Algorithmen ist aus biologischer Sicht leider ziemlich unexakt, das ist ein allgemeines Problem aller evolutionären Algorithmen - aber das kann man nur so feststellen, wir können hier keine Definitionen "verbessern" oder neue einführen. Es gibt schon ein Äquivalent zur biologischen DNA, nämlich die Bitcodierung der Lösung, allerdings ist es nicht üblich, dort nichtcodierende Sequenzen einzufügen, weil das den Ressourcenverbrauch bei der Berechnung erhöhen würde und für den Zweck von GA wohl kaum Vorteile brächte. Der Genetische Algorithmus erzeugt auch nicht wirklich etwas - es wird nur eine zufällige Startpopulation von Lösungen für ein Optimierungsproblem erzeugt, und diese Lösungen werden dann in Hinsicht auf die Zielfunktion des Problems optimiert (die eigentliche Aufgabe von GA). Mit DNA-Sequenzierung haben GA also gar nichts zu tun. (nicht signierter Beitrag von 81.217.9.35 (Diskussion) 23:31, 16. Jan. 2011 (CET))

Complexity

Vielleicht könnte man vom Englischen 'Complexity management' etwas lernen? Oder umgekehrt: vielleicht könnte der genetische Algorithmus im Umgang mit komplexen Systemen hilfreich sein. -- Rilu 04:52, 4. Jan. 2011 (CET)

Kann schon sein, aber die Wikipedia ist kein Forum. --P.C. ✉ 14:09, 4. Jan. 2011 (CET)