genetische Algorythmern

[Blue-Tiger]

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?

[It0101]

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

[klg71]

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 ?

[It0101]

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 )

[klg71]

als o in meinem code wird zuerst jedes ge eines individum mit einer zufallszahl initialisiert und best mit 0.
Danach wir eine Schleife angefangen in der zuerst geprüft wird ob jetzt schon eine fitness biss zu 30 herausgekommen ist wenn ja gibt er sie aus wenn nein nicht. so dann werden die gene erstmal nach ihrer güte sortiert das erste wird beibehalten ,das zweite mit dem dritten mutiert und aus dem 4. letztem ind enstehen kinder aus zufälligen elternpaaren und aus zufälligen aus dem elternpaar übernommene gene danach wird für jedes ind die fitness überprüft und wenn sie gleich 0 ist wird abgebrochen und es werden die gene ausgegeben ansonsten läuft ie Schleife weiter.

Nur mein problem ist mein programm bekommt keine sinvolle Lösung:)

[It0101]

Mutationen werden immer nur auf einem Genom durchgeführt.
Kreuzung werden zwischen zwei Elterngenomen durchgeführt -> woraus wiederum zwei Kinder entstehen.

Also:
- Mutation: Genome kopieren und ein oder mehrere Gene ändern
- Kreuzung: nimm zwei Elterngenome, erzeuge von jedem eine Kopie ( Kinde ) und tausche zufällige Gene der beiden Kinder untereinander aus.
Dadurch erhält jedes Kind ein bestimmtes Gen entweder vom Vater oder von der Mutter.

Versuch nicht festzulegen, welches Genome mit welchem kombiniert wird. Das sollte entweder der Zufall entscheiden oder eben das Roulette-Wheel.

[klg71]

problem gelöst mein programm mutiert einwandfrei:D
Wenn ihr mir dann abnehmt dass dass ein genetischer Algorytmus ist bin ich glücklich:D

#include <iostream>
#include <stdlib.h>

#include <iostream>
#include <time.h>
#include <math.h>
#define drand()  (rand()*(1.0/(RAND_MAX +1.0)))

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 swap(int *pa,int *pb);
void mutate(IND*ind, double prob);

int Zahl;
using namespace std;

int main (int argc, char *argv[])
{

    srand (time(NULL));
    int a;
    cout<<"Zahl: ";
    cin>>Zahl;
    POP *pop=(POP*)malloc(sizeof(POP)*5);
    pop->size=5;
    pop_init(pop);
    for(int i=0;i<pop->size;i++){
            checkFitness(pop->inds[i]);
            }
    while(1){

            if(pop->best->fitness>-5){//wenn die fitness in einem grenzwert ist ausgeben
                for(int i=0;i<5;i++){
                    cout<<pop->best->genes[i]<<" ";
                }
                cout<<"Fitness : "<<pop->best->fitness<<endl;
            }

            findTheBest(pop);
            for (int i = 0; i < pop->size-2; i += 2) {
                changeGenes(pop,pop->inds[i],pop->inds[i+1]);
            }
            for(int i=0;i<pop->size;i++){
                mutate(pop->inds[i],0.2);
            }

            for(int i=0;i<pop->size;i++){
            checkFitness(pop->inds[i]);
            }

            if((pop->best->fitness==0)){//wenn fitness 0 abbrechen und ausgeben
                cout<<"Fitness ist 0 abbruch\n"<<"Gene der Zahl:"<<endl;
                break;
            }

    }
    //Ergebnis ausgeben
cout  <<pop->best->genes[0]<<" "
        <<pop->best->genes[1]<<" "
        <<pop->best->genes[2]<<" "
        <<pop->best->genes[3]<<" "
        <<pop->best->genes[4]<<" "
        <<endl;
  return 0;
}  /* main()*/

void pop_init(POP *pop)//pop initialisieren
{
    pop->inds=(IND**)malloc(sizeof(IND));
    pop->best=(IND*)malloc(sizeof(IND));
    pop->inds[0]=(IND*)malloc(sizeof(IND));
    pop->inds[1]=(IND*)malloc(sizeof(IND));
    pop->inds[2]=(IND*)malloc(sizeof(IND));
    pop->inds[3]=(IND*)malloc(sizeof(IND));
    pop->inds[4]=(IND*)malloc(sizeof(IND));
    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++){//es gib nur die 5 Gene
    ind->genes[i]=Zahl*drand() ;
    checkFitness(ind);
    pop->best->genes[i]=0;
    }
}

void checkFitness(IND *ind){//fitness überprüfen
    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){//Ind sortieren und bestes ind Best schreiben
            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];
}

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 swap(int *pa,int *pb)
{
   int tmp=*pa;
   *pa=*pb;
   *pb=tmp;
}

void mutate(IND*ind, double prob){
    if (drand() >= prob) return;
    do ind->genes[(int)(5 *drand())] = (int)(Zahl *drand());
  while (drand() < prob);
}

[It0101]

Ich sag mal: Nicht schön, aber selten.

Hab grad das Script durchgelesen.... jetzt weiß ich auch woher du auf die Idee mit diesem gruseligen ANSI-C-Code gekommen bist. Ich glaube ich hab dir das Script sogar empfohlen - ich wusste ja nicht, dass da noch so uralter fürchterlicher Code drin steht

[klg71]

ja weißt du zufällig ne modernere seit für sowas?

[It0101]

klg71 schrieb:

ja weißt du zufällig ne modernere seit für sowas?

naja ich hatte ne bessere Vorlesung als die, die ich verlinkt habe. Aber davon gibts keine Scripte. Du kannst auch einfach versuchen den gleichen Inhalt mit OOP in C++ zu machen.

[klg71]

gut werde ich machen und ich lasse den thread jetzt erstmal verschwinden werde versuchen einen oop anstatz zu bauen danke für deine hilfe:D