Bobot_ga.c

#include "../game/g_local.h"
#include "bobot.h"
#include "bobot_ga.h"
#include "bobot_controller.h"
double        bestFitnessSoFar = -999999;
int            timePerGeneration = BOBOT_TIME_PER_GENERATION;
void    BOBOT_changeTimePerGeneration(int deltatime)
{    timePerGeneration += deltatime*1000;
    G_Printf("BOBOT time per generation : %d\n",timePerGeneration/1000);
}
void    CreateSGenome(SGenome* genome,double* w, double f,int typeOfCreation,int numWeights)
{    if(typeOfCreation == 1)
    { genome->dFitness = 0; }
    else
    {    int i;
        for(i=0;i<numWeights;i++) //was for(i=0;i<numWeightsEvolving;i++)
        { genome->vecWeights[i] = w[i]; }
        genome->dFitness = f;
    }
}
/*-----------------------------------constructor-------------------------
    sets up the population with random floats
-----------------------------------------------------------------------*/
void CreateCGenAlg(CGenAlg* genAlg,int popsize,double MutRat,double    CrossRat,int numweights,int    brainType)
{    int i,j;

    genAlg->popSize                = popsize;
    genAlg->mutationRate        = MutRat;
    genAlg->crossoverRate        = CrossRat;
    genAlg->chromoLength        = numweights;
    genAlg->totalFitness        = 0;
    genAlg->generationCounter    = 0;
    genAlg->fittestGenome        = 0;
    genAlg->bestFitness            = 0;
    genAlg->worstFitness        = 99999999;
    genAlg->averageFitness        = 0;
    genAlg->brainType            = brainType;

    /*    initialise population with chromosomes consisting of random
        weights and all fitnesses set to zero */
    for (i=0; i<genAlg->popSize; ++i)
    {    CreateSGenome(&(genAlg->vecPop[i]),NULL,0,1,genAlg->chromoLength);
        for (j=0; j<genAlg->chromoLength; ++j)
        { genAlg->vecPop[i].vecWeights[j] = RandomClamped(); }
    }
}

/*---------------------------------Mutate--------------------------------
    mutates a chromosome by perturbing its weights by an amount not
    greater than CParams::dMaxPerturbation
-------------------------------------------------------------------------*/
void Mutate(CGenAlg* genAlg, double* chromo)
{    int i;

    /*    traverse the chromosome and mutate each weight dependent on the mutation rate */
    for (i=0; i<genAlg->chromoLength; ++i)
    {    if (RandFloat() < genAlg->mutationRate)                            //do we perturb this weight?
        { chromo[i] += (RandomClamped() * BOBOT_MAX_PERTURBATION); }    //add or subtract a small value to the weight
    }
}

/*----------------------------------GetChromoRoulette()------------------
    returns a chromo based on roulette wheel sampling
-----------------------------------------------------------------------*/
void GetChromoRoulette(CGenAlg* genAlg, SGenome* TheChosenOne)
{    int i,j;
    /*    generate a random number between 0 & total fitness count */
    double Slice = (double)(RandFloat() * genAlg->totalFitness);

    /*    go through the chromosones adding up the fitness so far*/
    double FitnessSoFar = 0;
    for (i=0; i<genAlg->popSize; ++i)
    {    FitnessSoFar += genAlg->vecPop[i].dFitness;
        /*    if the fitness so far > random number return the chromo at this point */
        if (FitnessSoFar >= Slice)
        {    TheChosenOne->dFitness = genAlg->vecPop[i].dFitness;
            for(j=0;j<genAlg->chromoLength;j++)
            { TheChosenOne->vecWeights[j] = genAlg->vecPop[i].vecWeights[j]; }
            break;
        }
    }
}

/*-------------------------------------Crossover()-----------------------
    given parents and storage for the offspring this method performs
    crossover according to the GAs crossover rate
--------------------------------------------------------------------------*/
void Crossover(CGenAlg* genAlg,const double* mum,const double* dad,double* baby1,double*  baby2)
{    int i,cp;

    /*    just return parents as offspring dependent on the rate or if parents are the same*/
    if ( (RandFloat() > genAlg->crossoverRate) || (mum == dad))
    {    for(i=0; i<genAlg->chromoLength; i++)
        {    baby1[i] = mum[i];
            baby2[i] = dad[i];
        }
        return;
    }

    /*    determine a crossover point */
    cp = RandInt(0, genAlg->chromoLength - 1);

    /*    create the offspring */
    for (i=0; i<cp; ++i)
    {    baby1[i] = mum[i];
        baby2[i] = dad[i];
    }
    for (i=cp; i<genAlg->chromoLength; ++i)
    {    baby1[i] = dad[i];
        baby2[i] = mum[i];
    }
    return;
}

void    sort(SGenome list[],int n, int numWeights)
{    int i, j, k, min;

    SGenome temp[BOBOT_NUM_BOTS];
    for (i = 0; i<n-1; i++)
    {    min=i;       
        for (j=i+1; j<n; j++) 
        {    if (list[j].dFitness < list[min].dFitness)
            { min=j; }
        }
        temp->dFitness = list[i].dFitness;
        list[i].dFitness = list[min].dFitness;
        list[min].dFitness = temp->dFitness;
        for(k=0;k<numWeights;k++)
        { temp->vecWeights[k] = list[i].vecWeights[k]; }
        for(k=0;k<numWeights;k++)
        { list[i].vecWeights[k] = list[min].vecWeights[k];}
        for(k=0;k<numWeights;k++)
        { list[min].vecWeights[k] = temp->vecWeights[k]; }
    }
}

/*-----------------------------------Epoch()-----------------------------
    takes a population of chromosones and runs the algorithm through one
    cycle.     Returns a new population of chromosones.
-----------------------------------------------------------------------*/
void Epoch(CGenAlg* genAlg, SGenome* old_pop)
{    int i,j;
    /*    create a temporary vector to store new chromosomes */
    SGenome vecNewPop[BOBOT_NUM_BOTS];

    /*    assign the given population to the classes population */
    for(i=0;i<genAlg->popSize;i++)
    {    genAlg->vecPop[i].dFitness = old_pop[i].dFitness;
        for(j=0;j<genAlg->chromoLength;j++)
        { genAlg->vecPop[i].vecWeights[j] = old_pop[i].vecWeights[j]; }
    }
   
    /*    reset the appropriate variables */
    Reset(genAlg);

    /*    calculate best, worst, average and total fitness */
    CalculateBestWorstAvTot(genAlg);
   
    /*    on sauvegarde le meilleur bot */
    if(genAlg->bestFitness > bestFitnessSoFar)
    {    bestFitnessSoFar = genAlg->bestFitness;
        BOBOT_CONTROL_SaveBestBrain(BOBOT_BEST_SO_FAR,genAlg->brainType);
    }
    BOBOT_CONTROL_SaveBestBrain(BOBOT_LAST_BEST,genAlg->brainType);
    G_Printf("FITNESS : ");
    G_Printf("BestSoFar : %f | ",bestFitnessSoFar);
   
    /*    sort the population (for scaling and elitism) */
    sort(genAlg->vecPop,genAlg->popSize,genAlg->chromoLength);

    /*    sauvegarde des stats sur les Fitness, en vue de l'astuce qui suit */
    genAlg->reallyBestFitness = genAlg->bestFitness;
    genAlg->reallyFittestGenome = genAlg->fittestGenome;
    genAlg->reallyTotalFitness = genAlg->totalFitness;
    genAlg->reallyAverageFitness = genAlg->averageFitness;
    genAlg->reallyWorstFitness = genAlg->worstFitness;

    /*    astuce pour éviter les fitness négatifs (ce qui faisait foirer la roulette) */
    for(i=0;i<genAlg->popSize;i++)
    { genAlg->vecPop[i].dFitness -= genAlg->worstFitness; }

    /*    du coup on doit recalculer les Fitness, etc. */
    CalculateBestWorstAvTot(genAlg);

    /*    Now to add a little elitism we shall add in some copies of the
        fittest genomes. Make sure we add an EVEN number or the roulette
        wheel sampling will crash */
    i=0;
    if (!(BOBOT_NUM_COPIES_ELITE * BOBOT_NUM_ELITE % 2))
    {    GrabNBest(genAlg,BOBOT_NUM_ELITE, BOBOT_NUM_COPIES_ELITE, vecNewPop);
        i += BOBOT_NUM_COPIES_ELITE * BOBOT_NUM_ELITE;
    }
   
    /*    now we enter the GA loop repeat until a new population is generated */
    for(;i<genAlg->popSize;)
    {    SGenome mum,dad;
        /*    create some offspring via crossover */
        double        baby1[BOBOT_MAX_NUM_WEIGHTS];
        double        baby2[BOBOT_MAX_NUM_WEIGHTS];

        /*    grab two chromosones */
        GetChromoRoulette(genAlg,&mum);
        GetChromoRoulette(genAlg,&dad);
        Crossover(genAlg,mum.vecWeights, dad.vecWeights, baby1, baby2);
       
        /*    now we mutate */
        Mutate(genAlg,baby1);
        Mutate(genAlg,baby2);
   
        /*    now copy into vecNewPop population */
        CreateSGenome(&vecNewPop[i],baby1, 0, 2, genAlg->chromoLength);
        i++;
        if(i<genAlg->popSize)
        {    CreateSGenome(&vecNewPop[i],baby2, 0, 2, genAlg->chromoLength);
            i++;
        }
    }

    /*    finished so assign new pop back into vecPop and old_pop */
    for(i=0;i<genAlg->popSize;i++)
    {    genAlg->vecPop[i].dFitness = 0;
        old_pop[i].dFitness = 0;
        for(j=0;j<genAlg->chromoLength;j++)
        {    genAlg->vecPop[i].vecWeights[j] = vecNewPop[i].vecWeights[j];
            old_pop[i].vecWeights[j] = vecNewPop[i].vecWeights[j];
        }
    }
}

/*-------------------------GrabNBest----------------------------------
    This works like an advanced form of elitism by inserting NumCopies
    copies of the NBest most fittest genomes into a population vector
--------------------------------------------------------------------*/
void GrabNBest(CGenAlg* genAlg,int NBest,const int NumCopies, SGenome* Pop)
{    int globali=0;

    /*    add the required amount of copies of the n most fittest to the supplied vector*/
    while(NBest--)
    {    int i,j;
        for (i=0; i<NumCopies; ++i)
        {    Pop[globali].dFitness = genAlg->vecPop[(genAlg->popSize - 1) - NBest].dFitness;
            for(j=0; j<genAlg->chromoLength; j++)
            { Pop[globali].vecWeights[j] = genAlg->vecPop[(genAlg->popSize - 1) - NBest].vecWeights[j]; }
            globali++;
        }
    }
}

/*-----------------------CalculateBestWorstAvTot-----------------------   
    calculates the fittest and weakest genome and the average/total
    fitness scores
---------------------------------------------------------------------*/
void CalculateBestWorstAvTot(CGenAlg* genAlg)
{    int i;
    double HighestSoFar = -9999999;
    double LowestSoFar  = 9999999;

    genAlg->totalFitness = 0;
    for (i=0; i<genAlg->popSize; ++i)
    {    /*    update fittest if necessary */
        if (genAlg->vecPop[i].dFitness > HighestSoFar)
        {    HighestSoFar     = genAlg->vecPop[i].dFitness;
            genAlg->fittestGenome = i;
            genAlg->bestFitness     = HighestSoFar;
        }

        /*    update worst if necessary */
        if (genAlg->vecPop[i].dFitness < LowestSoFar)
        {    LowestSoFar = genAlg->vecPop[i].dFitness;
            genAlg->worstFitness = LowestSoFar;
        }
        genAlg->totalFitness    += genAlg->vecPop[i].dFitness;
    }    //next chromo
    genAlg->averageFitness = genAlg->totalFitness / genAlg->popSize;
}

/*    -------------------------Reset()------------------------------
    resets all the relevant variables ready for a new generation
-----------------------------------------------------------------*/
void Reset(CGenAlg* genAlg)
{
    genAlg->totalFitness    = 0;
    genAlg->bestFitness        = 0;
    genAlg->worstFitness    = 9999999;
    genAlg->averageFitness    = 0;
}
SGenome*    GetChromos(CGenAlg* genAlg)
{ return genAlg->vecPop; }

double        AverageFitness(CGenAlg* genAlg)
{ return genAlg->reallyTotalFitness / genAlg->popSize; }

double        BestFitness(CGenAlg* genAlg)
{ return genAlg->reallyBestFitness; }

Créer un site gratuit avec e-monsite - Signaler un contenu illicite sur ce site