Diskussion:Genetischer Algorithmus
aus Wikipedia, der freien Enzyklopädie
Inhaltsverzeichnis |
[Bearbeiten] 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
[Bearbeiten] 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)
[Bearbeiten] 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
[Bearbeiten] 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)
- 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)
[Bearbeiten] 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)
[Bearbeiten] 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)
[Bearbeiten] 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...
[Bearbeiten] 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...
[Bearbeiten] 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)
