Logo Search packages:      
Sourcecode: gaffitter version File versions  Download package

GeneticAlgorithm.hh

// ---------------------------------------------------------------------
// $Id: GeneticAlgorithm.hh,v 1.26 2006/01/01 09:00:25 daaugusto Exp $
//
//   GeneticAlgorithm.hh (created on Tue Nov 08 01:08:35 BRT 2005)
// 
//   Genetic Algorithm File Fitter (gaffitter)
//
//   Copyright (C) 2005-2006 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 2 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, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// ---------------------------------------------------------------------

#ifndef GeneticAlgorithm_hh
#define GeneticAlgorithm_hh

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

#include <vector>
#include <iterator>

using namespace std;

// ---------------------------------------------------------------------
/**
 * This class represents a Genome, i. e., an individual (candidate
 * solution) and its score.
 */
00045 class Genome {
public:
   Genome(int size): m_chrom(size) {}

   /** Chromosome size. */
00050    int Length() const { return m_chrom.size(); }

   /** Get the ith Gene of m_chrom. */
00053    bool Gene(int i) const { return m_chrom[i]; }
   /** Set the ith Gene of m_chrom. */
00055    void Gene(int i, bool gene) { m_chrom[i] = gene; }

   /** Returns true if the individual is bigger than target. */
00058    bool OverTarget() const { return m_diff < 0.0; }
   /** Returns true if the individual is smaller than target. */
00060    bool UnderTarget() const { return m_diff > 0.0; }
   /** Returns true if the individual is smaller (or equal) than target. */
00062    bool Feasible() const { return m_diff >= 0.0; }

   /**
    * Diff is the raw "distance" between the target and the sum of the
    * size of each file specified (gene = 1) by chromosome. The distance
    * maybe positive (smaller than target), zero (perfect fit) or
    * negative (greater than target). 
    */
00070    Params::Size_t Diff() const { return m_diff; }

   /** Sets the m_diff (\ref Diff()). */
00073    void Diff(Params::Size_t diff) { m_diff = diff; }

   /** Verify if the given size 's' can be inserted and update the \ref
    * m_diff. */
00077    void AddSize(int i, Params::Size_t s) 
   { 
      if (!Gene(i) && s<=Diff()) { Gene(i,true); m_diff -= s; }
   }
   /** 
    * Remove the 's' amount of size and update the \ref m_diff. */
00083    void DelSize(int i, Params::Size_t s) 
   { 
      if (Gene(i)) { Gene(i,false); m_diff += s; }
   }
   /** 
    * Writes the genome (vector containing '0's and '1's) in ostream
    * object (usually cout).
    */
00091    virtual ostream& Write(ostream& s) const
   {
      copy(m_chrom.begin(),m_chrom.end(),ostream_iterator<bool>(s));
      s << " [Size: " << m_chrom.size() << ", Diff: " << Diff() 
        << " bytes]"  << endl;

      return s;
   }

public:
   /**
    * Holds the list of selected files (candidate solution). '0' stands
    * for 'no selected file' and '1' stands for 'selected file'. Its
    * size is determined by the number of input files. The files are
    * sorted by size in reverse order (bigger to smaller).
    */
00107    vector<bool> m_chrom;

   /** The diff ("error") between the total size and the target. */
00110    Params::Size_t m_diff;
};

inline ostream& operator<< (ostream& s, const Genome& genome)
{
   return genome.Write(s);
}

// --------------------------------------------------------------------
/**
 * This class implements a Genetic Algorithm system as search algorithm.
 * This implementation aims to minimize the distance between a candidate
 * solution and the specified target.
 */
00124 class GeneticAlgorithm: public Optimizer {
public:
   /**
    * Automatically adjust population size and num. of generations. Also
    * sets Random::Seed. These parameters are static (its adjustment)
    * over the iterations, however, \ref Initialize() is called before
    * each iteration.
    */
   GeneticAlgorithm(vector<SizeName>&, Params&);
   /**
    * Free the population.
    */
   ~GeneticAlgorithm();
private:
   /** Copies are not allowed. */
   GeneticAlgorithm(const GeneticAlgorithm&);
   /** Attributions are not allowed. */
   GeneticAlgorithm& operator= (const GeneticAlgorithm&);

public:

   /** Genetic Algorithm search.
    *
    * GA searches for optimal (not guaranteed) solutions by means of
    * darwinian evolution.
    */
   void Evolve();

protected:
   /**
    * Initialize/adjust some parameters (per iteration) and prints some
    * information if required.
    */
   void Initialize();

   /**
    * Reset the GA system for a new iteration.
    */
   void Reset();

   /**
    * Create the population of individuals.
    *
    * The first created individuals are sparse (several '0' genes).
    * However the last individuals contain several '1' genes. This
    * improves the diversity and exploration of the search space.
    */
   void InitPopulation();

   /**
    * Runs the GA for one generation. Returns true if a perfect fit was
    * found; false otherwise.
    */
   bool Generation();

   /** Just for notation convenience. */
00180    Params::Size_t Score(int index) const { return Score(*m_genomes[index]); }

   /**
    * Returns how well is the given Genome. A perfect Genome is found
    * when its Score is equal to zero. Not so fitter return a positive
    * (>0) score.
    */
00187    Params::Size_t Score(const Genome& g) const { return g.Diff(); }

   /** 
    * Copy the given gene with some mistakes (determined by the mutate
    * probability).
    */
00193    bool CopyMutate(bool gene) const
   { 
      return (Random::Probability(m_prob_mutation)) ? !gene : gene;
   }

   /**
    * This genetic operator perform a local optimization upon a Genome.
    *
    * First it makes the individual feasible, from left to right or
    * vice-versa. Finally, LocalOptimizer fill the individual to
    * minimize the difference (target - sum)
    */
   void LocalOptimizer(Genome&) const;
   /**
    * Select at random a gene and then change it to better fit the
    * target.
    *
    * If 'g' is feasible then change the gene to '0', otherwise try
    * change the gene to '1'.
    */
   void DirectedMutation(Genome& g) const;

   /** Select in [a,b] a random individual. */
00216    int Select(int a, int b) const { return Random::Int(a,b); }


   /** Select in [a,b] a random individual 'r' not equal 'p'. */
00220    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'!
   }
   
   /** 
    * Promotes the crossover among two individuals, generating two
    * children.
    */
   void Reproduction(int, int, int, int) const;
   /** 
    * Choose a individual via tournament (need 2 or more competitors).
    * This is a 2 competitors optimized version.
    *
    * \sa TournamentN()
    */
   pair<int,int> Tournament2(int, int) const;
   /** 
    * Choose a individual via tournament (need 2 or more competitors).
    * This is a 3+ competitors version.
    *
    * \sa Tournament2()
    */
   pair<int,int> TournamentN(int, int) const;

   /**
    * Pointer to \ref Tournament2() or \ref TournamentN(), depending on
    * tournament size.
    */
   pair<int,int> (GeneticAlgorithm::*Tournament)(int, int) const;

   /** The population (vector) of genomes/individuals. */
00257    vector<Genome*> m_genomes;

protected:
   /** 
    * Writes some information (like algorithm name and parameters) in
    * ostream object (usually cout).
    */
   ostream& Write(ostream&) const;

protected:
00267    unsigned m_num_gen; /**< Number of generations. */
00268    unsigned m_pop_size; /**< Population size. */
00269    unsigned m_tournament_size; /**< Tournament size. */
00270    float m_prob_crossover; /**< Crossover probability. */
00271    float m_prob_mutation; /**< Mutation probability. */

private:
   /** Current population. */
00275    unsigned m_cur_gen;

   /** 
    * This function makes the probability of choosing gene "1" varying
    * between 0% and 100%. However it is biased (non uniform), making
    * most probabilities near to 0.5 (50%).
    *
    * The first created individuals contain several '0's  (very sparse).
    * On the other hand, the last individuals contain several '1's.
    */
   float NonUniformFiller(float) const;
};

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

Generated by  Doxygen 1.6.0   Back to index