3. genetische Algorythmern

genetische Algorythmern

  • F

    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.

    0
  • Z

    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 neugierig

    Mein (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 werden

    lieg ich da (einigermaßen) richtig, oder hab ich da was falsch verstanden?

    0
  • F

    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.

    0

  • 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)

    0
  • F

    Siehe das drittletzte Wort das du von mir zitierst. 😉

    0

  • 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 ^^ )

    0
  • F

    Vielleicht hätte ich "Paar" groß schreiben sollen. 😃

    0

  • 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 ^^

    0
  • Z

    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?

    0
  • F

    In dem die, die schlechter getauscht werden wieder absterben.

    0
  • Z

    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

    0

  • 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.

    0

  • 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.

    0
  • Z

    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 🙂

    0

  • 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 🙂

    0
  • K

    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?

    0
  • B

    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?

    0

  • 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 😉

    0
  • K

    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 ?

    0

  • Der Code liest sich leider etwas schwer...

    Ich schreib dir nochmal die Reihenfolge hin, die ich immer einhalte:

    1. Population generieren

    BEGIN_SCHLEIFE

    2. Fitness berechnen

    3. Nach Fitness sortieren

    4. Den "Gewinner" in die neue Population hinzufügen

    5. Mutieren und Kreuzen bis die neue Population genauso groß ist wie die alte

    6. Neue Population in alte Population kopieren

    END SCHLEIFE ( solange bis gewünschte fitness erreicht )

    0
Anmelden zum Antworten