GeneticAlgorithm.cpp

/*----------------------------------------------------------------------
Pac-Man Evolution - Roberto Prieto
Copyright (C) 2018-2024 MegaStorm Systems
contact@megastormsystems.com - http://www.megastormsystems.com
 
This software is provided 'as-is', without any express or implied
warranty.  In no event will the authors be held liable for any damages
arising from the use of this software.
 
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
 
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
 
------------------------------------------------------------------------
 
Genetic Algorithm class
 
Based on the amazing docs created by Mat Buckland (http://www.ai-junkie.com/ga/intro/gat1.html)
 
------------------------------------------------------------------------ */
 
#include "GeneticAlgorithm.h"
#include "ArtificialNeuralNet.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
 
// Constructor
GeneticAlgorithm::GeneticAlgorithm(Sint32 popsize, double MutRat, double CrossRat, double MaxPerturbation, Sint32 NumElite, Sint32 NumCopiesElite, Sint32 numweights)
{
    iPopulation = popsize;
    dMutationRate = MutRat;
    dCrossoverRate = CrossRat;
    iChromoLength = numweights;
    dTotalFitness = 0;
    iGeneration = 0;
    iFittestGenome = 0;
    dFitnessBest = 0;
    dWorstFitness = 99999999;
    dFitnessAverage = 0;
    dMaxPerturbation = MaxPerturbation;
    iNumElite = NumElite;
    iNumCopiesElite = NumCopiesElite;
    iNumMutation = iNumCrossOver = 0;
}
 
// Initialize the chromosomes for each creature of this population
void GeneticAlgorithm::init(Sint32 iPopPosition,vector<double> chromosomes)
{
    Sint32 i;
 
    // Security checks
    if(iPopPosition > iPopulation) return;
    if(chromosomes.size() != iChromoLength) return;
 
    // Create a new genome
    vPopulation.push_back(Genome());
 
    // Assign chromosomes
    for(i = 0; i<iChromoLength; ++i)
    {
        vPopulation[iPopPosition].vWeights.push_back(chromosomes[i]);
    }   
}
 
// Mutates a chromosome by perturbing its weights
void GeneticAlgorithm::mutate(vector<double>& chromo)
{
    Sint32 i;
    Tool &mTool = Main::Instance().ITool();
 
    for(i = 0; i < (Sint32)chromo.size(); ++i)
    {
        // Do we perturb this weight?
        if (mTool.randRealWELL() < dMutationRate)
        {
            // Add or subtract a small value to the weight
            chromo[i] += generateWeights() * dMaxPerturbation;            
            ++iNumMutation;
            //printf("Genetic Mutation\n");
        }
    }
}
 
// Return a chromosome based on Roulette wheel sampling
// (having the higher fitness does not warranty to be the one chosen..just give it more chances!)
Genome GeneticAlgorithm::getChromoRoulette()
{
    Genome TheChosenOne;
    double FitnessSoFar = 0;
    Sint32 i;
 
    // Generate a random number between 0 & total fitness count
    double Slice = (double)(Main::Instance().ITool().randRealWELL() * dTotalFitness);
 
    for(i = 0; i < iPopulation; ++i)
    {
        FitnessSoFar += vPopulation[i].dFitness;
        // If the fitness so far > random number return the chromo at this point
        if(FitnessSoFar >= Slice)
        {
            TheChosenOne = vPopulation[i];
            break;
        }
    }
    return TheChosenOne;
}
 
// Given parents and storage for the offspring this method performs crossover according to the GAs crossover rate
void GeneticAlgorithm::crossover(const vector<double>& mum, const vector<double>& dad,  vector<double>& baby1, vector<double>& baby2)
{
    Sint32 cp,i;
    Tool &mTool = Main::Instance().ITool();
 
    // If the parents are the same, they will be also the babies
    if((mTool.randRealWELL() > dCrossoverRate) || (mum == dad))
    {
        baby1 = mum;
        baby2 = dad;
        return;
    }
    //printf("Genetic CrossOver\n");
    ++iNumCrossOver;
 
    // Determine a crossover point
    cp = mTool.randWELL() % (iChromoLength);
 
    // Create the offspring
    for(i = 0; i < cp; ++i)
    {
        baby1.push_back(mum[i]);
        baby2.push_back(dad[i]);
    }
 
    for(i = cp; i < (Sint32)mum.size(); ++i)
    {
        baby1.push_back(dad[i]);
        baby2.push_back(mum[i]);
    }
 
    return;
}
 
//-----------------------------------Epoch()-----------------------------
//  takes a population of chromosones and runs the algorithm through one cycle.
//  Returns a new population of chromosones.
//-----------------------------------------------------------------------
vector<Genome> GeneticAlgorithm::epoch(vector<Genome>& old_pop)
{
    vPopulation = old_pop;
    reset();
 
    // Sort the population (for scaling and elitism)
    sort(vPopulation.begin(), vPopulation.end());
 
    // Calculate best, worst, average and total fitness
    calculateStats();
 
    // Create a temporary vector to store new chromosones
    vector <Genome> vecNewPop;
 
    // Now to add a little elitism we shall add in some copies of the fittest genomes. 
    if((iNumCopiesElite * iNumElite) < iPopulation)
    {
        grabNBest(iNumElite, iNumCopiesElite, vecNewPop);
    }   
 
    // Repeat until a new population is generated
    while((Sint32)vecNewPop.size() < iPopulation)
    {
        vector<double> baby1, baby2;
 
        // Get the mum and dad
        Genome mum = getChromoRoulette();
        Genome dad = getChromoRoulette();
 
        // Crossover
        crossover(mum.vWeights, dad.vWeights, baby1, baby2);
        // Mutate
        mutate(baby1);
        mutate(baby2);
 
        // Support odd populations
        vecNewPop.push_back(Genome(baby1, 0));
        if((Sint32)vecNewPop.size() < iPopulation) vecNewPop.push_back(Genome(baby2, 0));
    }
 
    // Return the new population
    vPopulation = vecNewPop;
    return vPopulation;
}
 
vector<Genome> GeneticAlgorithm::getChromos() const
{
    return vPopulation;
}
 
double GeneticAlgorithm::fitnessAverage() const
{
    return dFitnessAverage;
}
 
double GeneticAlgorithm::fitnessBest() const
{
    return dFitnessBest;
}
 
Sint32 GeneticAlgorithm::getMutation() const
{
    return iNumMutation;
}
 
Sint32 GeneticAlgorithm::getCrossOver() const
{
    return iNumCrossOver;
}
 
//  This works like an advanced form of elitism by inserting NumCopies
//  copies of the NBest most fittest genomes into a population vector
void GeneticAlgorithm::grabNBest(Sint32 NBest, const Sint32 NumCopies, vector<Genome>& Pop)
{
    Sint32 i;
 
    // Add the required amount of copies of the n most fittest to the supplied vector
    while(NBest--)
    {
        for(i = 0; i < NumCopies; ++i)
        {
            Pop.push_back(vPopulation[(iPopulation - 1) - NBest]);
        }
    }
}
 
// Calculates some stats of the current generation
void GeneticAlgorithm::calculateStats()
{
    Sint32 i;   
    double HighestSoFar = 0;
    double LowestSoFar  = 9999999;
    dTotalFitness = 0;
 
    for(i = 0; i < iPopulation; ++i)
    {
        if(vPopulation[i].dFitness > HighestSoFar)
        {
            HighestSoFar = vPopulation[i].dFitness;
            iFittestGenome = i;
            dFitnessBest = HighestSoFar;
        }
 
        if(vPopulation[i].dFitness < LowestSoFar)
        {
            LowestSoFar = vPopulation[i].dFitness;  
            dWorstFitness = LowestSoFar;
        }       
        dTotalFitness   += vPopulation[i].dFitness;     
    }
 
    dFitnessAverage = dTotalFitness / iPopulation;
}
 
// Resets all the relevant variables ready for a new generation
void GeneticAlgorithm::reset()
{
    dTotalFitness       = 0;
    dFitnessBest        = 0;
    dWorstFitness       = 9999999;
    dFitnessAverage = 0;
    iNumMutation = iNumCrossOver = 0;
}