Hallo,
ein GA beginnt ja meist mit einem zufällig generierten Genom (BitString).
Ist es für den GA wichtig, dass man sich ein Genom nehmen kann und dieses sukzessive durch geziehlte manuelle Mutation in eine perfekte Lösung transformieren kann?
Oder gibt es überhaupt ein Problem, dass sich nicht so lösen lässt?
Eigentlich nicht, oder?
Ben
Moin
Ist es für den GA wichtig, dass man sich ein Genom nehmen kann
und dieses sukzessive durch geziehlte manuelle Mutation in
eine perfekte Lösung transformieren kann?
Nein. Dem GA ist es eigentlich komplett wurscht.
Oder gibt es überhaupt ein Problem, dass sich nicht so lösen
lässt?
Es ist ein Frage der Zeit und der Bewertung der Genome. Bei Problemen mit vielen lokalen Optima wirds länger dauern.
cu
Hallo!
ein GA beginnt ja meist mit einem zufällig generierten Genom (BitString). Ist es für den GA wichtig, dass man sich ein Genom nehmen kann und dieses sukzessive durch geziehlte manuelle Mutation in eine perfekte Lösung transformieren kann?
Wenn Du das meinst: Jedes ‚Genom‘ sollte durch eine Folge von Mutationsschritten von jedem anderen aus erreichbar sein (also auch das Optimum). Je nach Art und Umfang einer Ausnahme, warum immer man die machen sollte, kann der GA trotzdem funktionieren.
Es gibt auch Ansätze, die auf problemorientierte, damit also zielgerichtete Mutationsmethoden setzen, Stichwort: memetische Algorithmen.
Oder gibt es überhaupt ein Problem, dass sich nicht so lösen lässt? Eigentlich nicht, oder?
*räusper* Aber natürlich: grundsätzlich lassen sich nur Probleme lösen, für die man eine sinnvolle Fitnessfunktion aufstellen kann (Berechenbarkeit? Dynamik?). Außerdem ist der Werteraum eines EA (evolutionäre Algorithmen, zu denen GA gehören) eine Beschränkung: ein Wert, der nicht darstellbar ist, kann bestenfalls angenähert, nicht gefunden werden (zB PI). Dann gibt es natürlich noch viele Probleme, auf denen ein GA nicht besser funktioniert als Zufallssuche, wie bei extrem nichtlinearen Zielfunktionen. Hier würde man sicher auch nicht behaupten, der EA/GA ‚löse‘ das Problem.
Gruß,
Mark
Hi,
ein GA beginnt ja meist mit einem zufällig generierten Genom
(BitString).
mit einem? eben nicht mit einem, sondern mit vielen, einer sogenannten Population.
Ist es für den GA wichtig, dass man sich ein Genom nehmen kann
und dieses sukzessive durch geziehlte manuelle Mutation in
eine perfekte Lösung transformieren kann?
Vielleicht verwechselst Du hier GA mit Simulated Annealing oder mit Treshold Acceptance. Der charakteristische Teil eines GA, jener, welcher Genome verbessert, ist der CrossingOver-Operator, der aus zwei Genomen durch Kreuzung ein neues bildet. Mutation soll hauptsächlich aus Sackgassen der Evolution heraushelfen, sprich lokale Minima überwinden helfen.
Oder gibt es überhaupt ein Problem, dass sich nicht so lösen
lässt?
Eigentlich nicht, oder?
Hüstel, probier mal zu einem verschlüsselten UNIX-Passwort per GA das Klartextpasswort zu rekonstruieren.
ciao
unimportant
Hi,
erstmal vielen Dank für die Antworten.
Die Frage war wohl etwas unpräzise formuliert. Also dass eine Lösung
nur dann gefunden werden kann wenn sie darstellbar ist und dass es
eine entspr. gute möglichst kontinuierliche Fitnessfunktion gegen muss
(nicht binär wie beim Kennwort) ist mir schon klar.
Das Problem dass ich habe, besteht darin, dass meine aktuelle Fitnessfunktion sich in lokalen Optima ‚verhäddert‘. Sie kann also nicht
entscheiden, ob bei einem Individuum ‚demnächst‘ ein Backtracking notwendig wird (was es bei GAs natürlich nicht gibt), wenn es mutiert wird.
Und nun frage ich mich, wie andere GAs damit umgehen.
Also ein Ansatz der GAs besteht darin, sehr viele Wege gleichzeitig (ein pro Individuum) zu verfolgen.
Die Frage ist, ob eine Fitnessfunktion entscheiden kann, ob das entspr.
Individuum nur noch durch Backtracking verbessert werden kann. In diesem Fall sollte sie es schlechter bewerten. Aber wenn diese Entscheidung wirklich getroffen werden kann, wenn mal also die Notwendigkeit für Backtracking erkennen könnte, dann könnte man ja auch
in klassischen Algorithmen das Backtracking abschaffen. Und das kann ich mir nicht vorstellen.
Nehmen wir z.B. mal das Damenproblem: Nehmen wir an, in jeder Spalte steht eine Dame und insgesamt schlagen sich nur zwei Damen. Es kann ja
möglich sein, diese Aufstellung nur dadurch ‚zu lösen‘ indem weit mehr als eine Dame umgesetzt werden muss (das ist Backtracking). Wenn aber
nur eine Dame umgesetzt werden muss, hat man praktisch durch eine einzige Mutation eine perfekte Lösung erzeugt.
(Den Crossover kann man in dieser Diskussion aussen vor lassen.)
Ben
Hi,
(Den Crossover kann man in dieser Diskussion aussen vor
lassen.)
dann ist es auch kein GA, dann empfehle ich Dir den TA (Treshold Acceptance)
geht so:
1.Starte mit einer zufälligen Lösung x0 (Bitstring) und bestimme einen maximalen Verschlechterungswert T für den Anfang.
setze die aktuelle Lösung xa = x0
berechne die Fitnesfunktion F(xa).
ändere ein Bit in xa und erhalte Zwischenlösung xz.
prüfe F(xz), ist der wert größer gleich F(xa)-T dann ersetze
xa durch xz
JA, xa kann sich dadurch verschlechtern, aber maximal um T je Schritt.
Gehe zu 4.
Natürlich merkst Du Dir nebenbei stets die bisher beste gefundene Lösung xm.
Ist die Iteration lange durchgelaufen, ohne nennenswerten weitere Verbesserungen gegen xm, wird T kleiner gemacht, xa wird durch xm ersetzt und weiter geht es mit 3.
wiederhole Schritt 6. solange bis T sehr klein bzw. 0 ist.
ist recht fix und gut das verfahren.
Hallo!
Ein EA/GA „entscheidet“ nichts in dem Sinn und weiß nichts über „Backtracking“, er kann natürlich auch nicht erkennen, wo lokale Optima sind, um diese zu umgehen, damit würde er eine Zielfunktion ohne lokale Optima implizieren, welche wiederum immer leicht zu lösen wäre. Die Frage, ob der EA lokale Optima überwindet, hängt nun vom Selektionsverfahren und der Stärke des Selektionsdrucks hab. Vielleicht solltest Du Dir doch mal einschlägige Fachlektüre zum Thema antun, zu finden in jeder gut sortierten Informatik-Abteilung bei Bibliotheken und Buchhandlungen.
Gruß,
Mark