ROOT logo
// @(#)root/tmva $Id: GeneticAlgorithm.cxx 38475 2011-03-17 10:46:00Z evt $    
// Author: Peter Speckmayer

/**********************************************************************************
 * Project: TMVA - a Root-integrated toolkit for multivariate data analysis       *
 * Package: TMVA                                                                  *
 * Class  : TMVA::GeneticAlgorithm                                                *
 * Web    : http://tmva.sourceforge.net                                           *
 *                                                                                *
 * Description:                                                                   *
 *      Implementation (see header for description)                               *
 *                                                                                *
 * Authors (alphabetical):                                                        *
 *      Peter Speckmayer <speckmay@mail.cern.ch> - CERN, Switzerland              *
 *                                                                                *
 * Copyright (c) 2005:                                                            *
 *      CERN, Switzerland                                                         *
 *      MPI-K Heidelberg, Germany                                                 *
 *                                                                                *
 * Redistribution and use in source and binary forms, with or without             *
 * modification, are permitted according to the terms listed in LICENSE           *
 * (http://tmva.sourceforge.net/LICENSE)                                          *
 **********************************************************************************/

//_______________________________________________________________________
//                                                                      
// Base definition for genetic algorithm                                
//_______________________________________________________________________

#include <iostream>
#include <algorithm>
#include <float.h>

#ifdef _GLIBCXX_PARALLEL
#include <omp.h>
#endif

#include "TMVA/GeneticAlgorithm.h"
#include "TMVA/Interval.h"
#include "TMVA/IFitterTarget.h"

#include "TMVA/MsgLogger.h"

namespace TMVA {
   const Bool_t GeneticAlgorithm__DEBUG__ = kFALSE;
}

ClassImp(TMVA::GeneticAlgorithm)
   
//_______________________________________________________________________
TMVA::GeneticAlgorithm::GeneticAlgorithm( IFitterTarget& target, Int_t populationSize, 
                                          const std::vector<Interval*>& ranges, UInt_t seed )
   : fConvCounter(-1),
     fFitterTarget( target ),
     fConvValue(0.),
     fLastResult(DBL_MAX),
     fSpread(0.1),
     fMirror(kTRUE),
     fFirstTime(kTRUE),
     fMakeCopies(kFALSE),
     fPopulationSize(populationSize),
     fRanges( ranges ),
     fPopulation(ranges, populationSize, seed),
     fBestFitness(DBL_MAX),
     fLogger( new MsgLogger("GeneticAlgorithm") )
{
   // Constructor
   // Parameters: 
   //     int populationSize : defines the number of "Individuals" which are created and tested 
   //                          within one Generation (Iteration of the Evolution)
   //     vector<TMVA::Interval*> ranges : Interval holds the information of an interval, where the GetMin 
   //                          gets the low and GetMax gets the high constraint of the variable
   //                          the size of "ranges" is the number of coefficients which are optimised
   // Purpose: 
   //     Creates a random population with individuals of the size ranges.size()
   fPopulation.SetRandomSeed( seed );
}

TMVA::GeneticAlgorithm::~GeneticAlgorithm() 
{
   // destructor; deletes fLogger
   delete fLogger;
}


//_______________________________________________________________________
void TMVA::GeneticAlgorithm::Init()
{
   // calls evolution, but if it is not the first time. 
   // If it's the first time, the random population created by the
   // constructor is still not evaluated, .. therefore we wait for the 
   // second time init is called. 
   if ( fFirstTime ) fFirstTime = kFALSE;
   else {
      Evolution();
   }
}

//_______________________________________________________________________
Double_t TMVA::GeneticAlgorithm::NewFitness( Double_t /*oldValue*/, Double_t newValue )
{
   // if the "fitnessFunction" is called multiple times for one set of 
   // factors (because i.e. each event of a TTree has to be assessed with 
   // each set of Factors proposed by the Genetic Algorithm) the value 
   // of the current calculation has to be added(? or else) to the value
   // obtained up to now. 
   // example: some chi-square is calculated for every event, 
   // after every event the new chi-square (newValue) has to be simply
   // added to the oldValue. 
   //
   // this function has to be overridden eventually 
   // it might contain only the following return statement.
   //        return oldValue + newValue;
   return newValue;
}

//_______________________________________________________________________
Double_t TMVA::GeneticAlgorithm::CalculateFitness()
{
   // starts the evaluation of the fitness of all different individuals of
   // the population. 
   //
   // this function calls implicitly (many times) the "fitnessFunction" which
   // has been overridden by the user. 
   fBestFitness = DBL_MAX;
#ifdef _GLIBCXX_PARALLEL

   const int nt = omp_get_num_threads();
   Double_t bests[nt];
   for ( int i =0; i < nt; ++i )
      bests[i] = fBestFitness;

#pragma omp parallel
   {
      int thread_number = omp_get_thread_num();
#pragma omp for
      for ( int index = 0; index < fPopulation.GetPopulationSize(); ++index )
      {
         GeneticGenes* genes = fPopulation.GetGenes(index);
         Double_t fitness = NewFitness( genes->GetFitness(), 
                                        fFitterTarget.EstimatorFunction(genes->GetFactors()) );
         genes->SetFitness( fitness );
         
         if ( bests[thread_number] > fitness )
            bests[thread_number] = fitness;
      }
   }
   
   fBestFitness = *std::min_element(bests, bests+nt);

#else 

   for ( int index = 0; index < fPopulation.GetPopulationSize(); ++index ) {
      GeneticGenes* genes = fPopulation.GetGenes(index);
      Double_t fitness = NewFitness( genes->GetFitness(),
                                     fFitterTarget.EstimatorFunction(genes->GetFactors()) );
      genes->SetFitness( fitness );
      
      if ( fBestFitness  > fitness )
         fBestFitness = fitness;
      
   }

#endif

   fPopulation.Sort();

   return fBestFitness; 
}

//_______________________________________________________________________
void TMVA::GeneticAlgorithm::Evolution()
{
   // this function is called from "init" and controls the evolution of the 
   // individuals. 
   // the function can be overridden to change the parameters for mutation rate
   // sexual reproduction and so on.
   if ( fMakeCopies ) 
      fPopulation.MakeCopies( 5 );
   fPopulation.MakeChildren();

   fPopulation.Mutate( 10, 3, kTRUE, fSpread, fMirror );
   fPopulation.Mutate( 40, fPopulation.GetPopulationSize()*3/4 );
}

//_______________________________________________________________________
Double_t TMVA::GeneticAlgorithm::SpreadControl( Int_t ofSteps, Int_t successSteps, Double_t factor )
{
   // this function provides the ability to change the stepSize of a mutation according to
   // the success of the last generations. 
   // 
   // Parameters:
   //      int ofSteps :  = if OF the number of STEPS given in this variable (ofSteps)
   //      int successSteps : >sucessSteps Generations could improve the result
   //      double factor : than multiply the stepSize ( spread ) by this factor
   // (if ofSteps == successSteps nothing is changed, if ofSteps < successSteps, the spread
   // is divided by the factor) 
   //
   // using this function one can increase the stepSize of the mutation when we have 
   // good success (to pass fast through the easy phase-space) and reduce the stepSize
   // if we are in a difficult "territory" of the phase-space. 
   //

   // < is valid for "less" comparison
   if ( fBestFitness < fLastResult || fSuccessList.size() <=0 ) { 
      fLastResult = fBestFitness;
      fSuccessList.push_front( 1 ); // it got better
   } 
   else {
      fSuccessList.push_front( 0 ); // it stayed the same
   }
   Int_t n = 0;
   Int_t sum = 0;
   std::deque<Int_t>::iterator vec = fSuccessList.begin();
   for (; vec != fSuccessList.end() ; vec++) {
      sum += *vec;
      n++;
   }

   if ( n >= ofSteps ) {
      fSuccessList.pop_back();
      if ( sum > successSteps ) { // too much success
         fSpread /= factor;
         if (GeneticAlgorithm__DEBUG__) Log() << kINFO << ">" << std::flush;
      }
      else if ( sum == successSteps ) { // on the optimal path
         if (GeneticAlgorithm__DEBUG__) Log() << "=" << std::flush;
      }
      else {        // not very successful
         fSpread *= factor;
         if (GeneticAlgorithm__DEBUG__) Log() << "<" << std::flush;
      }
   }

   return fSpread;
}

//_______________________________________________________________________
Bool_t TMVA::GeneticAlgorithm::HasConverged( Int_t steps, Double_t improvement )
{
   // gives back true if the last "steps" steps have lead to an improvement of the
   // "fitness" of the "individuals" of at least "improvement"
   // 
   // this gives a simple measure of if the fitness of the individuals is
   // converging and no major improvement is to be expected soon. 
   //
   if (fConvCounter < 0) {
      fConvValue = fBestFitness;
   }
   if (TMath::Abs(fBestFitness - fConvValue) <= improvement || steps<0) {
      fConvCounter ++;
   } 
   else {
      fConvCounter = 0;
      fConvValue = fBestFitness;
   }
   if (GeneticAlgorithm__DEBUG__) Log() << "." << std::flush;
   if (fConvCounter < steps) return kFALSE;
   return kTRUE;
}
 GeneticAlgorithm.cxx:1
 GeneticAlgorithm.cxx:2
 GeneticAlgorithm.cxx:3
 GeneticAlgorithm.cxx:4
 GeneticAlgorithm.cxx:5
 GeneticAlgorithm.cxx:6
 GeneticAlgorithm.cxx:7
 GeneticAlgorithm.cxx:8
 GeneticAlgorithm.cxx:9
 GeneticAlgorithm.cxx:10
 GeneticAlgorithm.cxx:11
 GeneticAlgorithm.cxx:12
 GeneticAlgorithm.cxx:13
 GeneticAlgorithm.cxx:14
 GeneticAlgorithm.cxx:15
 GeneticAlgorithm.cxx:16
 GeneticAlgorithm.cxx:17
 GeneticAlgorithm.cxx:18
 GeneticAlgorithm.cxx:19
 GeneticAlgorithm.cxx:20
 GeneticAlgorithm.cxx:21
 GeneticAlgorithm.cxx:22
 GeneticAlgorithm.cxx:23
 GeneticAlgorithm.cxx:24
 GeneticAlgorithm.cxx:25
 GeneticAlgorithm.cxx:26
 GeneticAlgorithm.cxx:27
 GeneticAlgorithm.cxx:28
 GeneticAlgorithm.cxx:29
 GeneticAlgorithm.cxx:30
 GeneticAlgorithm.cxx:31
 GeneticAlgorithm.cxx:32
 GeneticAlgorithm.cxx:33
 GeneticAlgorithm.cxx:34
 GeneticAlgorithm.cxx:35
 GeneticAlgorithm.cxx:36
 GeneticAlgorithm.cxx:37
 GeneticAlgorithm.cxx:38
 GeneticAlgorithm.cxx:39
 GeneticAlgorithm.cxx:40
 GeneticAlgorithm.cxx:41
 GeneticAlgorithm.cxx:42
 GeneticAlgorithm.cxx:43
 GeneticAlgorithm.cxx:44
 GeneticAlgorithm.cxx:45
 GeneticAlgorithm.cxx:46
 GeneticAlgorithm.cxx:47
 GeneticAlgorithm.cxx:48
 GeneticAlgorithm.cxx:49
 GeneticAlgorithm.cxx:50
 GeneticAlgorithm.cxx:51
 GeneticAlgorithm.cxx:52
 GeneticAlgorithm.cxx:53
 GeneticAlgorithm.cxx:54
 GeneticAlgorithm.cxx:55
 GeneticAlgorithm.cxx:56
 GeneticAlgorithm.cxx:57
 GeneticAlgorithm.cxx:58
 GeneticAlgorithm.cxx:59
 GeneticAlgorithm.cxx:60
 GeneticAlgorithm.cxx:61
 GeneticAlgorithm.cxx:62
 GeneticAlgorithm.cxx:63
 GeneticAlgorithm.cxx:64
 GeneticAlgorithm.cxx:65
 GeneticAlgorithm.cxx:66
 GeneticAlgorithm.cxx:67
 GeneticAlgorithm.cxx:68
 GeneticAlgorithm.cxx:69
 GeneticAlgorithm.cxx:70
 GeneticAlgorithm.cxx:71
 GeneticAlgorithm.cxx:72
 GeneticAlgorithm.cxx:73
 GeneticAlgorithm.cxx:74
 GeneticAlgorithm.cxx:75
 GeneticAlgorithm.cxx:76
 GeneticAlgorithm.cxx:77
 GeneticAlgorithm.cxx:78
 GeneticAlgorithm.cxx:79
 GeneticAlgorithm.cxx:80
 GeneticAlgorithm.cxx:81
 GeneticAlgorithm.cxx:82
 GeneticAlgorithm.cxx:83
 GeneticAlgorithm.cxx:84
 GeneticAlgorithm.cxx:85
 GeneticAlgorithm.cxx:86
 GeneticAlgorithm.cxx:87
 GeneticAlgorithm.cxx:88
 GeneticAlgorithm.cxx:89
 GeneticAlgorithm.cxx:90
 GeneticAlgorithm.cxx:91
 GeneticAlgorithm.cxx:92
 GeneticAlgorithm.cxx:93
 GeneticAlgorithm.cxx:94
 GeneticAlgorithm.cxx:95
 GeneticAlgorithm.cxx:96
 GeneticAlgorithm.cxx:97
 GeneticAlgorithm.cxx:98
 GeneticAlgorithm.cxx:99
 GeneticAlgorithm.cxx:100
 GeneticAlgorithm.cxx:101
 GeneticAlgorithm.cxx:102
 GeneticAlgorithm.cxx:103
 GeneticAlgorithm.cxx:104
 GeneticAlgorithm.cxx:105
 GeneticAlgorithm.cxx:106
 GeneticAlgorithm.cxx:107
 GeneticAlgorithm.cxx:108
 GeneticAlgorithm.cxx:109
 GeneticAlgorithm.cxx:110
 GeneticAlgorithm.cxx:111
 GeneticAlgorithm.cxx:112
 GeneticAlgorithm.cxx:113
 GeneticAlgorithm.cxx:114
 GeneticAlgorithm.cxx:115
 GeneticAlgorithm.cxx:116
 GeneticAlgorithm.cxx:117
 GeneticAlgorithm.cxx:118
 GeneticAlgorithm.cxx:119
 GeneticAlgorithm.cxx:120
 GeneticAlgorithm.cxx:121
 GeneticAlgorithm.cxx:122
 GeneticAlgorithm.cxx:123
 GeneticAlgorithm.cxx:124
 GeneticAlgorithm.cxx:125
 GeneticAlgorithm.cxx:126
 GeneticAlgorithm.cxx:127
 GeneticAlgorithm.cxx:128
 GeneticAlgorithm.cxx:129
 GeneticAlgorithm.cxx:130
 GeneticAlgorithm.cxx:131
 GeneticAlgorithm.cxx:132
 GeneticAlgorithm.cxx:133
 GeneticAlgorithm.cxx:134
 GeneticAlgorithm.cxx:135
 GeneticAlgorithm.cxx:136
 GeneticAlgorithm.cxx:137
 GeneticAlgorithm.cxx:138
 GeneticAlgorithm.cxx:139
 GeneticAlgorithm.cxx:140
 GeneticAlgorithm.cxx:141
 GeneticAlgorithm.cxx:142
 GeneticAlgorithm.cxx:143
 GeneticAlgorithm.cxx:144
 GeneticAlgorithm.cxx:145
 GeneticAlgorithm.cxx:146
 GeneticAlgorithm.cxx:147
 GeneticAlgorithm.cxx:148
 GeneticAlgorithm.cxx:149
 GeneticAlgorithm.cxx:150
 GeneticAlgorithm.cxx:151
 GeneticAlgorithm.cxx:152
 GeneticAlgorithm.cxx:153
 GeneticAlgorithm.cxx:154
 GeneticAlgorithm.cxx:155
 GeneticAlgorithm.cxx:156
 GeneticAlgorithm.cxx:157
 GeneticAlgorithm.cxx:158
 GeneticAlgorithm.cxx:159
 GeneticAlgorithm.cxx:160
 GeneticAlgorithm.cxx:161
 GeneticAlgorithm.cxx:162
 GeneticAlgorithm.cxx:163
 GeneticAlgorithm.cxx:164
 GeneticAlgorithm.cxx:165
 GeneticAlgorithm.cxx:166
 GeneticAlgorithm.cxx:167
 GeneticAlgorithm.cxx:168
 GeneticAlgorithm.cxx:169
 GeneticAlgorithm.cxx:170
 GeneticAlgorithm.cxx:171
 GeneticAlgorithm.cxx:172
 GeneticAlgorithm.cxx:173
 GeneticAlgorithm.cxx:174
 GeneticAlgorithm.cxx:175
 GeneticAlgorithm.cxx:176
 GeneticAlgorithm.cxx:177
 GeneticAlgorithm.cxx:178
 GeneticAlgorithm.cxx:179
 GeneticAlgorithm.cxx:180
 GeneticAlgorithm.cxx:181
 GeneticAlgorithm.cxx:182
 GeneticAlgorithm.cxx:183
 GeneticAlgorithm.cxx:184
 GeneticAlgorithm.cxx:185
 GeneticAlgorithm.cxx:186
 GeneticAlgorithm.cxx:187
 GeneticAlgorithm.cxx:188
 GeneticAlgorithm.cxx:189
 GeneticAlgorithm.cxx:190
 GeneticAlgorithm.cxx:191
 GeneticAlgorithm.cxx:192
 GeneticAlgorithm.cxx:193
 GeneticAlgorithm.cxx:194
 GeneticAlgorithm.cxx:195
 GeneticAlgorithm.cxx:196
 GeneticAlgorithm.cxx:197
 GeneticAlgorithm.cxx:198
 GeneticAlgorithm.cxx:199
 GeneticAlgorithm.cxx:200
 GeneticAlgorithm.cxx:201
 GeneticAlgorithm.cxx:202
 GeneticAlgorithm.cxx:203
 GeneticAlgorithm.cxx:204
 GeneticAlgorithm.cxx:205
 GeneticAlgorithm.cxx:206
 GeneticAlgorithm.cxx:207
 GeneticAlgorithm.cxx:208
 GeneticAlgorithm.cxx:209
 GeneticAlgorithm.cxx:210
 GeneticAlgorithm.cxx:211
 GeneticAlgorithm.cxx:212
 GeneticAlgorithm.cxx:213
 GeneticAlgorithm.cxx:214
 GeneticAlgorithm.cxx:215
 GeneticAlgorithm.cxx:216
 GeneticAlgorithm.cxx:217
 GeneticAlgorithm.cxx:218
 GeneticAlgorithm.cxx:219
 GeneticAlgorithm.cxx:220
 GeneticAlgorithm.cxx:221
 GeneticAlgorithm.cxx:222
 GeneticAlgorithm.cxx:223
 GeneticAlgorithm.cxx:224
 GeneticAlgorithm.cxx:225
 GeneticAlgorithm.cxx:226
 GeneticAlgorithm.cxx:227
 GeneticAlgorithm.cxx:228
 GeneticAlgorithm.cxx:229
 GeneticAlgorithm.cxx:230
 GeneticAlgorithm.cxx:231
 GeneticAlgorithm.cxx:232
 GeneticAlgorithm.cxx:233
 GeneticAlgorithm.cxx:234
 GeneticAlgorithm.cxx:235
 GeneticAlgorithm.cxx:236
 GeneticAlgorithm.cxx:237
 GeneticAlgorithm.cxx:238
 GeneticAlgorithm.cxx:239
 GeneticAlgorithm.cxx:240
 GeneticAlgorithm.cxx:241
 GeneticAlgorithm.cxx:242
 GeneticAlgorithm.cxx:243
 GeneticAlgorithm.cxx:244
 GeneticAlgorithm.cxx:245
 GeneticAlgorithm.cxx:246
 GeneticAlgorithm.cxx:247
 GeneticAlgorithm.cxx:248
 GeneticAlgorithm.cxx:249
 GeneticAlgorithm.cxx:250
 GeneticAlgorithm.cxx:251
 GeneticAlgorithm.cxx:252
 GeneticAlgorithm.cxx:253
 GeneticAlgorithm.cxx:254
 GeneticAlgorithm.cxx:255
 GeneticAlgorithm.cxx:256
 GeneticAlgorithm.cxx:257
 GeneticAlgorithm.cxx:258
 GeneticAlgorithm.cxx:259
 GeneticAlgorithm.cxx:260