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

void BruteForce::Evolve (  )  [virtual]

"Evolve" via Brute Force search.

This search algorithm tries all possible combinations. Exponential complexity (2^n, where n=|input|). This algorithm produces guaranteed globally optimal solutions, but it becomes very very slow when 'n' grows. Uses carefully!

Implements Optimizer.

Definition at line 36 of file BruteForce.cc.

References Optimizer::Evaluate(), Optimizer::m_best, Optimizer::m_files, Optimizer::m_params, Params::m_verbose, Params::PrettySize(), and Optimizer::Reset().

{
   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);
}


Generated by  Doxygen 1.6.0   Back to index