GeneticAlgorithm.h

Go to the documentation of this file.

// ---------------------------------------------------------------------------
// $Id: GeneticAlgorithm.h 230 2008-08-14 01:45:04Z daaugusto $
//
//   GeneticAlgorithm.h (created on Tue Nov 08 01:08:35 BRT 2005)
// 
//   Genetic Algorithm File Fitter (gaffitter)
//
//   Copyright (C) 2005-2008 Douglas A. Augusto
// 
// This file is part of gaffitter.
// 
// gaffitter is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3 of the License, or (at
// your option) any later version.
// 
// gaffitter is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with gaffitter; if not, see <http://www.gnu.org/licenses/>.
//
// ---------------------------------------------------------------------------

#ifndef GeneticAlgorithm_hh
#define GeneticAlgorithm_hh

#include "../Input.h"
#include "../util/Random.h"
#include "../Optimizer.h"

#include <vector>
#include <iterator>

static const Params::Size_t WORST_FITNESS = 0.0;
static const Params::Size_t BEST_FITNESS = 1.0;

// ---------------------------------------------------------------------------
class Individual {
public:
   Individual(): m_fitness( WORST_FITNESS ) {}

   Params::Size_t Fitness() const { return m_fitness; }
   void Fitness( Params::Size_t f ) { m_fitness = f; }

   bool operator==( const Individual& i ) const
   {
      if( !AlmostEqual( Fitness(), i.Fitness() ) ) return false;

      return Genome() == i.Genome();
   }

   friend bool operator>( Individual &a, Individual &b ) 
   { 
      return a.m_fitness > b.m_fitness; 
   }

   BinSet& Genome() { return m_genome; }
   const BinSet& Genome() const { return m_genome; }

   Bin& Genome(int i) { return m_genome[i]; }
   const Bin& Genome(int i) const { return m_genome[i]; }

public:
   BinSet m_genome; 
   Params::Size_t m_fitness; 
};

// ---------------------------------------------------------------------------
class GeneticAlgorithm: public Optimizer {
public:
   GeneticAlgorithm( Input& );
private:
   GeneticAlgorithm( const GeneticAlgorithm& );
   GeneticAlgorithm& operator=( const GeneticAlgorithm& );

public:

   void Evolve();
 
   bool Evaluate( int i ) { return Evaluate( m_individuals[i] ); }
   bool Evaluate( Individual& );

protected:
   bool InitPopulation();

   bool Generation();

   Params::Size_t Fitness( int index ) const 
   { 
      return Fitness( m_individuals[index] ); 
   }

   Params::Size_t Fitness( const Individual& i ) const { return i.Fitness(); }

   int Select( int a, int b ) const { return Random::Int( a, b ); }

   int Select( int a, int b, int p ) const 
   { 
      int r = Select( a, b );
      
      // equals?
      if( r == p ) return r > a ? r - 1 : a + 1;

      return r; // Ok: 'b' not equal 'a'!
   }

   int Select( int a, int b, int p1, int p2 ) const 
   { 
      int r = Select( a, b );

      if( p1 > p2 ) std::swap( p1, p2 );

      if( r == p1 )
      {
         if( p1 == a ) return p1 + 1 == p2 ? r + 2 : r + 1;
         if( p1 > a ) return r - 1;
      }

      if( r == p2 )
      {
         if( p2 == b ) return p2 == p1 + 1 ? r - 2 : r - 1;
         if( p2 < b ) return r + 1;
      }

      return r;
   }
   
   bool Crossover( unsigned, unsigned, unsigned, unsigned );

   void Mutate( int i );

   std::pair<int,int> Tournament2( int, int ) const;

   std::pair<int,int> TournamentN( int, int ) const;

   std::pair<int,int> (GeneticAlgorithm::*Tournament)( int, int ) const;

   Individual& Individuals( int i ) { return m_individuals[i]; }
   const Individual& Individuals( int i ) const { return m_individuals[i]; }

   std::vector<Individual>& Individuals() { return m_individuals; }
   const std::vector<Individual>& Individuals() const { return m_individuals; }
   
   std::vector<Individual> m_individuals; 
   Individual m_best_individual; 
public:
   void FirstFit( BinSet&, const std::vector<const SizeName*>& ) const;
   void FirstFitDecreasing( BinSet&, std::vector<const SizeName*>& ) const;
   void DominanceOptimizer( BinSet& bs, std::vector<const SizeName*>& 
                            unassigned ) const;
private:
   int DominanceForOne( Bin& bin, std::vector<const SizeName*>& 
                        unassigned ) const;
   int DominanceForTwo( Bin& bin, std::vector<const SizeName*>& 
                        unassigned ) const;
   int DominanceForThree( Bin& bin, std::vector<const SizeName*>& 
                          unassigned ) const;
protected:
   std::ostream& Write( std::ostream& ) const;

private:
   int m_cur_gen; 
   unsigned m_tournament_size; 
};

// ---------------------------------------------------------------------------
#endif