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

BruteForce.cc

// ---------------------------------------------------------------------
// $Id: BruteForce.cc,v 1.16 2006/08/11 14:44:02 daaugusto Exp $
//
//   BruteForce.cc (created on Fri Nov 18 20:47: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
//
// ---------------------------------------------------------------------

#include "BruteForce.hh"
#include "../util/Exception.hh"

#include <cmath>
#include <limits>

// ---------------------------------------------------------------------
void
00036 BruteForce::Evolve()
{
   if (m_params.m_verbose) cout << *this;

   Reset();

   const Params::UBigInt max_iter = 
         static_cast<Params::UBigInt>(pow(2.0L,(int)m_files.size()));

   /* Is the input size managed by Brute Force search?
     
      Test the following conditions:
       - if max_iter == 0 then 'overflow error'
       - if max_iter != 2^n then 'overflow error'

      Obs.: log2(2^n) = n, where log2(x) = log(x)/log(2)
    */
   if (max_iter == 0 || m_files.size() !=
       static_cast<size_t>(log(static_cast<long double>(max_iter))/log(2.0L))) 
   {
      throw E_BigInput("BruteForce::Evolve()");
   }

   if (m_params.m_verbose) cout << "> Trying " << max_iter 
                                << " combinations (2^input)..." << endl;

   // pick the best
   Params::Size_t best_score = numeric_limits<Params::Size_t>::max();

   vector<bool> candidate(m_files.size()), best;

   for(Params::UBigInt i=1; i<=max_iter; ++i)
   {
      // evaluate
      Params::Size_t tmp_score = Evaluate(candidate);

      if (tmp_score >= 0 && tmp_score < best_score) 
      { 
         best = candidate;
         best_score = tmp_score;

         if (m_params.m_verbose) 
            cout << "> [" << i << "] Best fit so far (diff): " 
                 << m_params.PrettySize(best_score) << endl;

         if (tmp_score <= 0.0) break; // found a perfect fit!
      }

      /* Generate a new candidate. 
       *
       * The jth value changes each 2^(size-j) iteration.
       * 
       * [a][b][c]
       *  1  2  3
       *
       *  c changes each 2^0 = 1 iterations
       *  b changes each 2^1 = 2 iterations
       *  a changes each 2^2 = 4 iterations
       */
      for(unsigned int j=0; j<m_files.size(); ++j)
      {
         if (i % (Params::UBigInt) 
                  pow(2.0L, static_cast<int>(m_files.size()-j-1)) == 0) 

            candidate[j] = !candidate[j];
      }
   }

   // make "best" a non local vector
   m_best = new vector<bool>(best);
}

// --------------------------------------------------------------------
ostream& 
00110 BruteForce::Write(ostream& s) const 
{ 
   s << endl;
   s << "> -----------------------------------" << endl;
   s << "> Brute Force search"                  << endl;
   s << "> -----------------------------------" << endl;

   Optimizer::Write(s);

   s << endl << flush;

   return s;
}

// --------------------------------------------------------------------

Generated by  Doxygen 1.6.0   Back to index