genetische Algorythmern
-
So ich hab einige Hinweise für dich.
1. Wir sind hier im C++-Forum, was du programmierst ist ANSI-C
( aber das soll uns erstmal nicht aufhalten )2. Deine Vorgehensweise ist folgende:
- du erzeugst zufällig einen Satz von Genen.
- du berechnest die Fitness ( den Fehler )
(soweit so richtig)Aber dann machst du folgendes
for(int i=0;i<5;i++) { pop->inds[0]->genes[i]=(int)rand()%10; ... }D.h. du initialisierst das allererste Element komplett neu. Warum?
Ich schreib dir mal meine Vorgehensweise auf ( und ich würde dir empfehlen auf C++ und OOP zurückzugreifen, weil das die Sache deutlich übersichtlicher macht ):
1. Lege N Genome der Größe M an.
2. Berechne die Fitness ( oder den Fehler ) aller Genome
3. Sortiere diese Genome nach Fitness ( das beste Element sollte als ganz oben oder ganz unten in der Liste stehen )
( Tipp: wenn du deine Genome in einem std::vector lagerst, kannst du mit std::sort ganz leicht und auch einigermaßen performant sortieren )
4. Jetzt kommen die biologischen Operatoren ( Kreuzung, Mutation, Elitimus )
- Elitismus: Das Beste Element wird direkt in die nächste Generation mit übernommen
- Mutation: nimm dir einige gute Elemente ( ich nehm gern die besten 10% ) und auch das Beste, lege Kopien davon an und verändere nur ein einzelnes Gen ( rand() ). Füge diese veränderten Genome wieder der neuen Generation hinzu.
- Kreuzung: Wähle zufällig ( entweder aus den besseren Genomen, oder per Roulette-Wheel ) zwei Eltern-Genome und erzeuge daraus zwei Kinder-Genome, in dem du für jedes Gen der Kinder zufällig entscheidest, ob das Gen vom Vater oder von der Mutter kommt. Füge diese beiden neuen Genome wiederum der neuen Generation hinzu.(Du kannst auch erst eine festgelegte Anzahl von Kreuzungen machen und dann solange Mutationen bis die neue Generation ( Population ) exakt die Größe der alten Population hat. )
5. erste die alte Population durch die neue.
6. Wiederhole diese Schritte solange, bis du deine gewünschte Fitness erreicht hast ( bis der Fehler ausreichend klein ist )
Anmerkung: das ist erstmal nur eine Grundstruktur - es gibt noch sehr viele Variantionsmöglichkeiten! Genetische Algorithmen sind ein weites Feld. Ebenso wie genetische Programmierung.
-
Ein nettes "Problem" war auch immer der Travelling Salesman:
Du hast X Punkte in einem 2D-Raum. Die Aufgabe ist es die alle zu verbinden und dabei die Verbindungen zu finden die am kürzesten ist, jeden aber exakt einmal besucht.
-
Fellhuhn schrieb:
Ein nettes "Problem" war auch immer der Travelling Salesman:
Du hast X Punkte in einem 2D-Raum. Die Aufgabe ist es die alle zu verbinden und dabei die Verbindungen zu finden die am kürzesten ist, jeden aber exakt einmal besucht.wie würde man da vorgehen?
Ich hab mich ehrlich gesagt bis zu diesem Thread nicht mit dieser Art Algorithmen beschäftigt, aber jetzt bin ich neugierigMein (naiver) Vorschlag wäre folgender:
- Ausreichend viele mögliche Lösungen erzeugen, die alle Punkte einmal besuchen
- die kürzeste davon in die neue Generation übernehmen
- die etwas längeren mutieren und kreuzen und auch in die nächste Generation übernehmen
- das selbe mit der neuen Generation wiederholen, bis die neuen Generationen nicht mehr wesentlich kürzer werdenlieg ich da (einigermaßen) richtig, oder hab ich da was falsch verstanden?
-
Ja, so in etwa. Man arbeitet halt auf Listen die die IDs der Punkte beinhalten, natürlich keine doppelt und alle drin. Und dann wird bei der Mutation zufällig ein paar vertauscht und so weiter.
Als die Aufgabe allerdigns bearbeitet wurde bei dem "Programmierwochenende" während der Studienzeit (auch schon lange her) war eher Pornos auf Leinwand gucken und Bier saufen angesagt. Daher habe ich da keine Erinnerung dran.
-
Fellhuhn schrieb:
Ja, so in etwa. Man arbeitet halt auf Listen die die IDs der Punkte beinhalten, natürlich keine doppelt und alle drin. Und dann wird bei der Mutation zufällig ein paar vertauscht und so weiter.
Wobei du bei dem Travelling-Salesman immer jede Zahl ( jeden Ort ) im Genom haben musst.
D.h. bei Mutation von
123456789
kannst du nicht die 4 durch ne 9 ersetzen, weil dann der Ort 4 garnicht besucht wird und der Ort 9 zweimal.
D.h. du kannst höchstens mutieren indem du innerhalb des Genomes zwei Ziffern miteinander vertauschst.
(Sozusagen ein Spezialfall der Mutation, den ich beim Sudoku-Problem auch hatte)
-
Siehe das drittletzte Wort das du von mir zitierst.
-
Fellhuhn schrieb:
Siehe das drittletzte Wort das du von mir zitierst.
aso ok, das hatte ich anders interpretiert. Dann sind wir natürlich einer Meinung
( ich hatte jetzt zuerst an Kreuzung gedacht, denn die is bei sowas echt unangenehm ^^ )
-
Vielleicht hätte ich "Paar" groß schreiben sollen.
-
Fellhuhn schrieb:
Vielleicht hätte ich "Paar" groß schreiben sollen.
nee du hast das schon richtig geschrieben, ich war nur mit meinen Gedanken etwas durcheinander ^^
-
Fellhuhn schrieb:
Und dann wird bei der Mutation zufällig ein paar vertauscht und so weiter.
aber wenn immer nur per Zufall vorgegangen wird, wie kann ich dann sicher sein, dass die neue Generation besser ist als die alte?
-
In dem die, die schlechter getauscht werden wieder absterben.
-
hm... stimmt eigentlich
n Lösungen erstellen
die n-1 schlechtesten Lösungen mutieren
von den 2n-1 Lösungen die n besten weiterleben lassen
usw.und ich hab das Problem weit komplexer vermutet
-
zwutz schrieb:
Fellhuhn schrieb:
Und dann wird bei der Mutation zufällig ein paar vertauscht und so weiter.
aber wenn immer nur per Zufall vorgegangen wird, wie kann ich dann sicher sein, dass die neue Generation besser ist als die alte?
Aufgrund des Elitismus und des Roulettewheel.
- Elitismus: das allerbeste Element wird grundsätzlich in die neuen generation kopiert
- RouletteWheel: je besser die Fitness eines Elements, desto höher ist die Wahrscheinlichkeit, dass dieses Element für eine Paarung / Mutation verwendet wird.Über diese Operatoren wird sichergestellt, dass das beste Element nie verloren geht und allerhöchstens noch besser werden kann.
-
und ich hab das Problem weit komplexer vermutet
Die Grundlagen sind nicht sonderlich komplex. Man kann aber noch viel mehr machen ( z.B. Parallele Populationen ). Ich nehme in jede Population immer ein paar neue Genome mit rein, damit es nicht Inzucht kommt.
Man kann bei der Parametrisierung des Algorithmus auch viel versauen, wenn ihn falsch einstellt.
-
It0101 schrieb:
- RouletteWheel: je besser die Fitness eines Elements, desto höher ist die Wahrscheinlichkeit, dass dieses Element für eine Paarung / Mutation verwendet wird.
das kommt auch noch dazu. Danke schonmal, jetzt hab ich wieder ne Beschäftigung für die nächsten Tage
-
Gleich mal vorweg als Tipp.
Wenn ihr einen GenAlg konzipiert, dann plant ihn gleich so, dass er ein Objekt einer Basisklasse übernimmt, die sozusagen als "Problemcontainer" dient.
Wenn ihr dann spezielle Problem habt, könnt ihr von dieser Basisklasse eine Klasse ableiten und das Problem spezifizieren.Auf diese Art und Weise müsst ihr den dämlichen GenAlg nicht immer und immer wieder programmieren.... das ging mir nämlich irgendwann auf den Zeiger, also hab ich einmal einen richtig kompletten programmiert, dem ich immer nur dieses Objekt übergebe. Meiner ist allerdings multithreaded, das kostet schon ein paar Tage mehr
-
sagen wir die arrays werden so initialisiert, dass es kein a+b+c+d+e=10 geben kann in keiner generation wass dann einfach abbrechen nach der n-ten generation oder neuinitialisiern?
-
It0101 schrieb:
Gleich mal vorweg als Tipp.
Wenn ihr einen GenAlg konzipiert, dann plant ihn gleich so, dass er ein Objekt einer Basisklasse übernimmt, die sozusagen als "Problemcontainer" dient.
Wenn ihr dann spezielle Problem habt, könnt ihr von dieser Basisklasse eine Klasse ableiten und das Problem spezifizieren.Auf diese Art und Weise müsst ihr den dämlichen GenAlg nicht immer und immer wieder programmieren.... das ging mir nämlich irgendwann auf den Zeiger, also hab ich einmal einen richtig kompletten programmiert, dem ich immer nur dieses Objekt übergebe. Meiner ist allerdings multithreaded, das kostet schon ein paar Tage mehr
Reine Neugier: wie schaut dein Design genauer aus? Dinge wie Selektionsverfahren, Fittnessfunktion und Kreuzungs-Op muessen doch sowieso immer neu implementiert werden?
Und: was genau laeuft multithreaded? Das Evaluieren der einzelnen Loesungen? Lohnt sich das ueberhaupt?
-
Blue-Tiger schrieb:
Reine Neugier: wie schaut dein Design genauer aus? Dinge wie Selektionsverfahren, Fittnessfunktion und Kreuzungs-Op muessen doch sowieso immer neu implementiert werden?
Und: was genau laeuft multithreaded? Das Evaluieren der einzelnen Loesungen? Lohnt sich das ueberhaupt?wie schaut dein Design genauer aus?
- Ich hab eine Klasse die den Genetischen Algorithmus enthält und das Objekt der "ProblemKlasse" übernimmt.
- Diese GenAlg-Klasse enthält wiederum N (konfigurierbar) Genpools. Jeder Genpool enthält entweder eine komplette Population ( für den Fall, dass man mit mehreren Populationen spielen will ) oder den N-ten Teil einer einzigen Population.
Jeder GenPool wird von je einem Thread getrieben und die einzige Aufgabe ist die Berechung der Fitness seiner Genome. Je aufwändiger die Fitnessberechnung ( in meinem aktuellen Fall trainiert der GENALG ein automatisches Aktien-handelsssystem. ) desto mehr lohnt sich das Multithreading. Dort werden riesige Datenmengen verarbeitet - das Multithreading lohnt sich! ( Aber die Programmierung ist ein Riesenaufwand ).- Natürlich gibts auch eine Genomklasse
- Warum sollten Kreuzungsoperatoren immer anders sein? Man kombiniert zwei double-Arrays miteinander - das ist immer so. Da ich keine Sudokus oder Traveling-Salesman-Probleme bearbeite ( geht damit auch nicht ) ist mir egal wie die Genome aussehen.
- Die Fitnessfunktion liefert die an den GenAlg übergebene Instanz einer "Problemklasse". In dieser Klasse ist praktisch eine Funktion GetFitness vergraben, die man für sein aktuelles Problem in der Ableitung der Klasse einfach überschreibt. ( Die Problem-Basisklasse ist abstrakt ).
So jetzt hab ich mir die Finger wund getippt. Jetzt muss ich wieder ein bissel für meinen Chef arbeiten
-
so meiner meinung nach mutieren meine zahlen sehr viel aber es kommt leider kein ergenis raus:( mein code:
#include <stdlib.h> #include <stdarg.h> #include <limits.h> #include <time.h> #include <assert.h> #include <math.h> #include <iostream.h> typedef struct { /* --- an individual --- */ int fitness; /* fitness (number of collisions) */ int n; /* number of genes (number of rows) */ int genes[4]; /* genes (queen positions in rows) */ } IND; /* (individual) */ typedef struct { /* --- a population --- */ int size; /* number of individuals */ IND **inds; /* vector of individuals */ IND **buf; /* buffer for individuals */ IND *best; /* best individual */ } POP; /* (population) */ void pop_init(POP *pop); void ind_init(IND *ind,POP *pop); void checkFitness(IND *ind); void findTheBest(POP *pop); void changeGenes(POP *pop,IND*ind1,IND*ind2); void CreateNewInd(int i,POP *pop); void swap(int *pa,int *pb); int Zahl; int main (int argc, char *argv[]) { srand (time(NULL)); int i,k; cout<<"Zahl: "; cin>>Zahl; POP *pop=(POP*)malloc(sizeof(POP)*5); pop->size=5; pop_init(pop); while(!(pop->inds[0]->fitness==Zahl)){ if(pop->best->fitness>-30){ for(int i=0;i<pop->size;i++){ cout <<pop->best->genes[i]<<" "; } cout<<endl; } findTheBest(pop); for(int i=0;i<pop->size;i++){ checkFitness(pop->inds[i]); } if((pop->best->fitness==0)){ cout<<"Fitness ist 0 abbruch"<<endl; break; } } cout <<pop->best->genes[0]<<" " <<pop->best->genes[1]<<" " <<pop->best->genes[2]<<" " <<pop->best->genes[3]<<" " <<pop->best->genes[4]<<" " <<endl; system("Pause"); return 0; } /* main()*/ void pop_init(POP *pop) { pop->inds=(IND**)malloc(sizeof(IND)*5); pop->best=(IND*)malloc(sizeof(IND)*5); pop->inds[0]=(IND*)malloc(sizeof(IND)*5); pop->inds[1]=(IND*)malloc(sizeof(IND)*5); pop->inds[2]=(IND*)malloc(sizeof(IND)*5); pop->inds[3]=(IND*)malloc(sizeof(IND)*5); pop->inds[4]=(IND*)malloc(sizeof(IND)*5); pop->best->fitness=0; for(int i=0;i<pop->size;i++){ pop->inds[i]->n=i; ind_init(pop->inds[i],pop); } } void ind_init(IND *ind,POP *pop){ for(int i=0;i<5;i++){ ind->genes[i]=rand() % Zahl ; checkFitness(ind); pop->best->genes[i]=0; } } void checkFitness(IND *ind){ int sum=0; for(int i=0;i<5;i++){ sum=sum+ind->genes[i]; } if(sum==Zahl){ ind->fitness=abs(sum-Zahl); } else ind->fitness=-abs(sum-Zahl); } void findTheBest(POP *pop){; int a; for(int obergrenze=4;obergrenze>0;--obergrenze) { for(int pos=0;pos<4;pos++) { if(pop->inds[pos]->fitness>pop->inds[pos+1]->fitness){ swap(pop->inds[pos]->genes,pop->inds[pos+1]->genes); swap(&pop->inds[pos]->fitness,&pop->inds[pos+1]->fitness); } } } pop->best=pop->inds[0]; CreateNewInd(3,pop); CreateNewInd(4,pop); changeGenes(pop,pop->inds[1],pop->inds[2]); } void changeGenes(POP *pop,IND*ind1,IND*ind2){ int i,t; i=(rand() %5); t = ind1->genes[i]; ind1->genes[i] = ind2->genes[i]; ind2->genes[i] = t; } void CreateNewInd(int i,POP *pop){ for(int index=0;index<5;index++){ pop->inds[i]->genes[index]=pop->inds[rand()%5]->genes[index]; } } void swap(int *pa,int *pb) { int tmp=*pa; *pa=*pb; *pb=tmp; }habt ihr noch ein paar tipps für mich ?
