EvolutionaryAlgorithm.h

Go to the documentation of this file.

/*
 GRT MIT License
 Copyright (c) <2013> <Nicholas Gillian, Media Lab, MIT>
 
 Permission is hereby granted, free of charge, to any person obtaining a copy of this software
 and associated documentation files (the "Software"), to deal in the Software without restriction,
 including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
 and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
 subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in all copies or substantial
 portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
 LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef GRT_EVOLUTIONARY_ALGORITHM_HEADER
#define GRT_EVOLUTIONARY_ALGORITHM_HEADER

#include "Individual.h"

GRT_BEGIN_NAMESPACE

template <typename INDIVIDUAL>
class EvolutionaryAlgorithm : public MLBase{

public:
    EvolutionaryAlgorithm(const UINT populationSize = 0,const UINT geneSize = 0) : MLBase("EVO")
    {
        maxIteration = 1000;
        minNumIterationsNoChange = 1;
        storeRate = 1;
        bestIndividualIndex = 0;
        bestIndividualFitness = 0;
        mutationRate = 0.01;
        minChange = 1.0e-5;
        baiseCoeff = 2.0;
        initialized = false;
        useElitism = true;
        storeHistory = true;
        baiseWeights = true;
        
        initPopulation( populationSize, geneSize );
    }
    
    virtual ~EvolutionaryAlgorithm(){
        
    }
    
    INDIVIDUAL& operator[](const UINT &index){
        return population[ index ];
    }
    
    virtual bool initPopulation(const UINT populationSize,const UINT geneSize){
        
        initialized = false;
        this->populationSize = 0;
        this->geneSize = 0;
        bestIndividualIndex = 0;
        bestIndividualFitness = 0;
        population.clear();
        populationWeights.clear();
        accumSumLookup.clear();
        populationHistory.clear();
        fitnessHistory.clear();
        
        if( populationSize == 0 || geneSize == 0 ) return false;
        
        //Init the memory
        this->populationSize = populationSize;
        this->geneSize = geneSize;
        population.resize( populationSize );
        populationWeights.resize( populationSize );
        accumSumLookup.resize( populationSize );
        
        //Init each individual
        UINT i = 0;
        UINT index = 0;
        typename Vector< INDIVIDUAL >::iterator populationIter = population.begin();
        Vector< IndexedDouble >::iterator weightsIter = populationWeights.begin();
        VectorFloat::iterator geneIter;
        
        while( populationIter != population.end() ){
            populationIter->fitness = 0;
            populationIter->gene.resize( geneSize );
            
            //Randomize the gene
            for(i=0; i<geneSize; i++){
                populationIter->gene[ i ] = generateRandomGeneValue();
            }
            
            weightsIter->value = populationIter->fitness;
            weightsIter->index = index++;
            
            populationIter++;
            weightsIter++;
        }
        
        //Save the initial population as the parents
        parents = population;
        
        initialized = true;
        
        return true;
    }
    
    virtual bool estimatePopulationFitness( const MatrixFloat &trainingData, Float &bestFitness, UINT &bestIndex ){
        
        UINT index = 0;
        bestFitness = 0;
        bestIndex = 0;
        
        if( !initialized ) return false;
        
        typename Vector< INDIVIDUAL >::iterator populationIter = population.begin();
        Vector< IndexedDouble >::iterator weightsIter = populationWeights.begin();
        
        while( populationIter != population.end() ){
            //Compute the fitness of the current individual
            weightsIter->value = evaluateFitness( *populationIter, trainingData );
            weightsIter->index = index++;
            
            //Check to see if this is the best fitness so far
            if( weightsIter->value > bestFitness ){
                bestFitness = weightsIter->value;
                bestIndex = weightsIter->index;
            }
            
            //Update the iterators
            populationIter++;
            weightsIter++;
        }
        
        return true;
    }
    
    virtual bool evolvePopulation(){
        
        if( !initialized ) return false;
        
        UINT i=0;
        UINT index = 0;
        UINT mom = 0;
        UINT dad = 0;
        UINT crossOverPoint = 0;
        typename Vector< INDIVIDUAL >::iterator populationIter = population.begin();
        Vector< IndexedDouble >::iterator weightsIter = populationWeights.begin();
        
        //Get the current weights values
        weightsIter = populationWeights.begin();
        while( populationIter != population.end() ){
            weightsIter->value = baiseWeights ? pow( populationIter->fitness, baiseCoeff ) : populationIter->fitness;
            weightsIter->index = index++;
            
            populationIter++;
            weightsIter++;
        }
        
        //Sort the weighted values by value in ascending order (so the least likely value is first, the second least likely is second, etc...
        sort(populationWeights.begin(),populationWeights.end(),IndexedDouble::sortIndexedDoubleByValueAscending);
        
        //Create the accumulated sum lookup table
        accumSumLookup[0] = populationWeights[0].value;
        for(unsigned int i=1; i<populationSize; i++){
            accumSumLookup[i] = accumSumLookup[i-1] + populationWeights[i].value;
        }
        
        if( accumSumLookup[populationSize-1] == 0 ){
            warningLog << "evolvePopulation() - The accum sum is zero!" << std::endl;
        }
        
        //Reset the population iterator
        populationIter = population.begin();
        
        if( useElitism ){
            //The first child is simply a copy of the best parent
            populationIter->gene = parents[ bestIndividualIndex ].gene;
            populationIter++;
        }
        
        //This is the main evolve loop, at each iteration we do the following until we reach the end of the population
        //- Randomly select a mom and dad from the parents population (parents with a better fitness have a better chance of being selected)
        //- Randomly select a cross over point (this is an index that sets what point along the gene we will merge the data from mom and dad)
        //- Create two individuals (if possible) by combining the gene data from mom and dad
        //- The first child will use the following genes [mom |crossOverPoint| dad], whereas the second child will use [dad |crossOverPoint| mom]
        //- After the cross over, each gene will be randomly mutated
        index = 0;
        while( populationIter != population.end() ){
            
            //Randomly select the parents, individuals with higher weights will have a better chance of being selected
            mom = rand.getRandomNumberWeighted( populationWeights, accumSumLookup );
            dad = rand.getRandomNumberWeighted( populationWeights, accumSumLookup );
            
            //Select the cross over point
            crossOverPoint = rand.getRandomNumberInt(0, geneSize);
            
            //Generate the new individual using cross over (this is the first child)
            for(i=0; i<geneSize; i++){
                if( i < crossOverPoint ) populationIter->gene[i] = parents[ mom ].gene[i];
                else populationIter->gene[i] = parents[ dad ].gene[i];
            }
            
            //Perform random mutation
            for(i=0; i<geneSize; i++){
                if( rand.getRandomNumberUniform(0.0,1.0) <= mutationRate ){
                    populationIter->gene[ i ] = generateRandomGeneValue();
                }
            }
            
            //Update the iterator
            populationIter++;
            
            //Generate the second child (as long as we have not got to the end of the population)
            if( populationIter != population.end() ){
                
                for(i=0; i<geneSize; i++){
                    if( i < crossOverPoint ) populationIter->gene[i] = parents[ dad ].gene[i];
                    else populationIter->gene[i] = parents[ mom ].gene[i];
                }
                
                //Perform random mutation
                for(i=0; i<geneSize; i++){
                    if( rand.getRandomNumberUniform(0.0,1.0) <= mutationRate ){
                        populationIter->gene[ i ] = generateRandomGeneValue();
                    }
                }
                
                //Update the iterator
                populationIter++;
            }
            
        }
        
        //Store the parents for the next iteration
        parents = population;
        
        return true;
    }
    
    virtual Float evaluateFitness( INDIVIDUAL &individual, const MatrixFloat &trainingData ){
        
        individual.fitness = 0;
        
        if( !initialized ) return 0;
        
        if( trainingData.getNumCols() != geneSize ) return 0;
        
        UINT M = trainingData.getNumRows();
        Float error = 0;
        Float minError = grt_numeric_limits< Float >::max();
        
        for(UINT i=0; i<M; i++){
            error = 0;
            //Compute the squared distance
            for(UINT j=0; j<geneSize; j++){
                error += ( trainingData[i][j] - individual.gene[j] ) * ( trainingData[i][j] - individual.gene[j] );
            }
            if( error < minError ) minError = error;
        }
        //Make sure the minError is not zero
        minError += 0.00001;
        minError /= Float(geneSize);
        
        //Good individuals should have a high fitness
        individual.fitness = 1.0/(minError*minError);
        
        return individual.fitness;
    }

    virtual bool train(const MatrixFloat &trainingData){
        
        if( !initialized ) return false;
        
        UINT currentIteration = 0;
        UINT numIterationsNoChange = 0;
        bool keepTraining = true;
        Float lastBestFitness = 0;
        
        if( storeHistory ){
            populationHistory.reserve( maxIteration/storeRate );
            fitnessHistory.reserve( maxIteration/storeRate );
        }
        
        //Init the population
        initPopulation( populationSize, geneSize );
        
        //Compute the fitness of the initial population
        estimatePopulationFitness( trainingData, bestIndividualFitness, bestIndividualIndex );
        lastBestFitness = bestIndividualFitness;
        
        if( storeHistory ){
            populationHistory.push_back( population );
            fitnessHistory.push_back( IndexedDouble(bestIndividualIndex, bestIndividualFitness) );
        }
        
        //Start the main loop
        while( keepTraining ){
            
            //Perform the selection
            if( !evolvePopulation() ){
                errorLog << "Failed to evolve population" << std::endl;
                return false;
            }
            
            //Compute population fitness
            if( !estimatePopulationFitness( trainingData, bestIndividualFitness, bestIndividualIndex ) ){
                return false;
            }
            
            Float delta = fabs( bestIndividualFitness-lastBestFitness );
            lastBestFitness = bestIndividualFitness;
            
            trainingLog << "Iteration: " << currentIteration << "\tBestFitness: " << bestIndividualFitness << "\tBestIndex: " << bestIndividualIndex << "\tDelta: " << delta << "\tNumIterationsNoChange: " << numIterationsNoChange << std::endl;
            
            if( currentIteration >= maxIteration ){
                keepTraining = false;
                trainingLog << "Max Iteration Reached!" << std::endl;
            }
            
            if( delta <= minChange ){
                if( ++numIterationsNoChange >= minNumIterationsNoChange ){
                    keepTraining = false;
                    trainingLog << "Min Changed Reached!" << std::endl;
                }
            }else{
                numIterationsNoChange = 0;
            }
            
            if( customConvergenceCheck() ){
                keepTraining = false;
                trainingLog << "Custom Convergance Triggered!" << std::endl;
            }
            
            //Update the iteration
            currentIteration++;
            
            //Save the current population
            if( currentIteration % storeRate == 0 && storeHistory ){
                populationHistory.push_back( population );
                fitnessHistory.push_back( IndexedDouble(bestIndividualIndex, bestIndividualFitness) );
            }
        }
        
        return true;
    }
    
    UINT getPopulationSize() const{
        return populationSize;
    }
    
    bool getInitialized() const{
        return initialized;
    }
    
    Vector< INDIVIDUAL > getPopulation() const{
        return population;
    }
    
    bool setPopulationSize(const UINT populationSize){
        this->populationSize = populationSize;
        return true;
    }
    
    bool setMinNumIterationsNoChange(const UINT minNumIterationsNoChange){
        this->minNumIterationsNoChange = minNumIterationsNoChange;
        return true;
    }
    
    bool setMaxIterations(const UINT maxIteration){
        this->maxIteration = maxIteration;
        return true;
    }
    
    bool setStoreRate(const UINT storeRate){
        this->storeRate = storeRate;
        return true;
    }
    
    bool setStoreHistory(const bool storeHistory){
        this->storeHistory = storeHistory;
        return true;
    }
    
    bool setBaiseWeights(const bool baiseWeights){
        this->baiseWeights = baiseWeights;
        return true;
    }
    
    bool setBaiseCoeff(const Float baiseCoeff){
        this->baiseCoeff = baiseCoeff;
        return true;
    }
    
    bool setMutationRate(const Float mutationRate){
        this->mutationRate = mutationRate;
        return true;
    }
    
    bool setMinChange(const Float minChange){
        this->minChange = minChange;
        return true;
    }
    
    virtual bool setPopulation( const Vector< INDIVIDUAL > &newPopulation ){
        
        if( newPopulation.size() == 0 ) return false;
        
        population = newPopulation;
        populationSize = (UINT)population.size();
        populationWeights.resize( populationSize );
        accumSumLookup.resize( populationSize );
        
        UINT index = 0;
        typename Vector< INDIVIDUAL >::iterator populationIter = population.begin();
        Vector< IndexedDouble >::iterator weightsIter = populationWeights.begin();
        VectorFloat::iterator geneIter;
    
        while( populationIter != population.end() ){
            weightsIter->value = populationIter->fitness;
            weightsIter->index = index++;
            
            populationIter++;
            weightsIter++;
        }
        
        return true;
    }
    
    virtual inline Float generateRandomGeneValue(){
        return rand.getRandomNumberUniform(0.0,1.0);
    }
    
    virtual bool customConvergenceCheck(){
        return false;
    }
    
    virtual bool printBest() const{
        if( !initialized ) return false;
        
  std::cout << "BestIndividual: ";
  for(UINT i=0; i<geneSize; i++){
   std::cout << population[ bestIndividualIndex ].gene[i] << "\t";
  }
  std::cout << std::endl;
        return true;
    }
    
public:
    
    bool initialized;
    bool useElitism;
    bool storeHistory;
    bool baiseWeights;
    UINT populationSize;
    UINT geneSize;
    UINT minNumIterationsNoChange;
    UINT maxIteration;
    UINT storeRate;
    UINT bestIndividualIndex;
    Float bestIndividualFitness;
    Float mutationRate;
    Float minChange;
    Float baiseCoeff;
    Random rand;
    Vector< INDIVIDUAL > population;
    Vector< INDIVIDUAL > parents;
    Vector< IndexedDouble > populationWeights;
    Vector< Vector< INDIVIDUAL > > populationHistory;
    Vector< IndexedDouble > fitnessHistory;
    VectorFloat accumSumLookup;
};
    
GRT_END_NAMESPACE

#endif //GRT_EVOLUTIONARY_ALGORITHM_HEADER