gs.cc-old

c++编写的并行拉马克遗传算法的程序。实现分析对接程序

   for (J=0;  J < original_pop.num_individuals();  J++) {//debug
       allzero = allzero & (alloc[J] == (float)0.0);//debug
   }//debug
   if (allzero) {//debug
       (void)fprintf(logFile, "gs.cc:  W A R N I N G !  all alloc variables are zero!\n"); //debug
   }//debug
#endif

   //  Permute the individuals

#ifdef DEBUG2
   (void)fprintf(logFile, "gs.cc:  Permuting beginning: original_pop.num_individuals()= %d\n", original_pop.num_individuals()); //debug
#endif

   for (i=0;  i < original_pop.num_individuals();  i++) {
      temp_ordering = ordering[i];

      assert(ordering[i] < original_pop.num_individuals());//debug

      temp_index = ignlgi()%(original_pop.num_individuals());

      assert(ordering[temp_index] < original_pop.num_individuals());//debug

      ordering[i] = ordering[temp_index];
      ordering[temp_index] = temp_ordering;

#ifdef DEBUG2
      //(void)fprintf(logFile, "gs.cc: permuting in sel_prop: ordering check: ordering[i=%d]= %d, ordering[temp_index=%d]= %d\n", ordering[i],i, ordering[temp_index], temp_index);//debug
#endif
   }// endfor i

   //  We might get some savings here if we sorted the individuals before calling
   //  this routine
   for (i=0; (i < original_pop.num_individuals()) && (start_index < original_pop.num_individuals()); i++) {
      for (; (alloc[i] >= 1.0) && (start_index < original_pop.num_individuals());  alloc[i]-= 1.0) {
         new_pop[start_index] = original_pop[i];                //
         //new_pop[start_index].incrementAge();                        //
         ++start_index;                                                //
      }
   }

#ifdef DEBUG2
   (void)fprintf(stderr, "gs.cc/void Genetic_Algorithm::"); //debug
   (void)fprintf(stderr, "selection_proportional(Population &original_pop, Individual *new_pop)\n"); //debug
#endif

   i = 0;                                                        //

#ifdef DEBUG2
   int count = 0;//debug
   (void)fprintf(stderr, "gs.cc/beginning \"while(start_index < original_pop.num_individuals()) {\" loop\n"); //debug
#endif

   // ??? start_index = 0; // gmm, 1998-07-13 ???

   while (start_index < original_pop.num_individuals()) {        //
#ifdef DEBUG2
      (void)fprintf(stderr, "gs.cc:596/inside \"while(start_index(=%d) < original_pop.num_individuals()(=%d)) \" loop:  count= %d\n", start_index, original_pop.num_individuals(), ++count); //debug
#endif
      assert(ordering[i] < original_pop.num_individuals());//debug
#ifdef DEBUG2
      debug_ranf = ranf();
      (void)fprintf(stderr, "gs.cc:599/inside debug_ranf= %.3f, alloc[ordering[i]]= %.3e, ordering[i]= %d,  i= %d\n", debug_ranf, alloc[ordering[i]], ordering[i], i); // debug
      if (debug_ranf < alloc[ordering[i]]) {
#else
      if (ranf() < alloc[ordering[i]]) {                        // non-debug
#endif //  not DEBUG2
#ifdef DEBUG2
         (void)fprintf(stderr, "gs.cc:603/inside (debug_ranf < alloc[ordering[i]]) is true!\n"); //debug
         (void)fprintf(stderr, "gs.cc:604/inside about to increment start_index in:  \"new_pop[start_index++] = original_pop[ordering[i]];\"; right now, start_index= %d\n", start_index); //debug
#endif
         new_pop[start_index] = original_pop[ordering[i]];        //
         //new_pop[start_index].incrementAge();                        //
         start_index++;                                                //
#ifdef DEBUG2
         (void)fprintf(stderr, "gs.cc:605/inside just incremented start_index, now start_index= %d\n", start_index); //debug
#endif
      }// endif (ranf() < alloc[ordering[i]])                        //

#ifdef DEBUG2
      (void)fprintf(stderr, "gs.cc:608/inside i= %d, original_pop.num_individuals()= %d\n", i, original_pop.num_individuals()); //debug
      (void)fprintf(stderr, "gs.cc:609/inside about to \"i = (i+1)%%original_pop.num_individuals();\"\n"); //debug
#endif
      i = (i+1)%original_pop.num_individuals();                        //
#ifdef DEBUG2
      (void)fprintf(stderr, "gs.cc:611/inside just done \"i = (i+1)%%original_pop.num_individuals();\"\n"); //debug
      (void)fprintf(stderr, "gs.cc:612/inside i= %d  _____________________________________________________\n\n", i); //debug

       allzero = 1;//debug
       for (J=0;  J < original_pop.num_individuals();  J++) {//debug
           allzero = allzero & (alloc[J] == (float)0.0);//debug
       }//debug
       if (allzero) {//debug
           (void)fprintf(logFile, "gs.cc:  W A R N I N G !  all alloc variables are zero!\n"); //debug
       }//debug
#endif

   }// endwhile (start_index < original_pop.num_individuals())         //

#ifdef DEBUG2
  (void)fprintf(stderr, "gs.cc/finished \"while(start_index < original_pop.num_individuals()) \" loop\n"); //debug
#endif

}

/* Probabilistic Binary Tournament Selection
 *
 * This type of tournament selection was described in Goldberg and Deb (1991),
 * and performs the same type of selection as is seen in linear rank
 * selection.  Two individuals are chosen at random, and the better individual
 * is selected with probability P, 0.5 <= P <= 1.  If we let 2P = C, then
 * we see that the expected number of samples generated by rank r_i is
 *
 *      N * [2P - 2(2P-1) r_i]            , 1 >= P >= 0.5
 *
 * We can again parameterize this ranking with K, the relative probability
 * between the best and worst individual.  Since 2P = C,
 * P = K/(1+K).
 */
void Genetic_Algorithm::selection_tournament(Population &original, Individual *new_pop)
{
   register int i = 0, start_index = 0;
   int temp_ordering, temp_index;

#ifdef DEBUG
   (void)fprintf(logFile, "gs.cc/void Genetic_Algorithm::");
   (void)fprintf(logFile, "selection_tournament(Population &original, Individual *new_pop)\n");
#endif /* DEBUG */

   original.msort(original.num_individuals());
   for (i=0; i<original.num_individuals(); i++) {
      alloc[i] = original.num_individuals()*(2*tournament_prob - i*(4*tournament_prob - 2));
   }

   for (i=0;  (i < original.num_individuals()) && (start_index < original.num_individuals());  i++) {
      for (; (alloc[i] >= 1.0) && (start_index < original.num_individuals());  alloc[i] -= 1.0) {
         new_pop[start_index++] = original[i];
      }
   }

   for (i=0; i < original.num_individuals(); i++) {
      temp_ordering = ordering[i];
      temp_index = ignlgi()%original.num_individuals();
      ordering[i] = ordering[temp_index];
      ordering[temp_index] = temp_ordering;
   }

   i = 0;
   while (start_index < original.num_individuals()) {
      if (ranf() < alloc[ordering[i]]) {
         new_pop[start_index++] = original[ordering[i]];
      }
      i = (i+1)%original.num_individuals();
   }
}

Individual *Genetic_Algorithm::selection(Population &solutions)
{
   Individual *next_generation;

#ifdef DEBUG
   (void)fprintf(logFile, "gs.cc/Individual *Genetic_Algorithm::selection(Population &solutions)\n");
#endif /* DEBUG */

   next_generation = new Individual[solutions.num_individuals()];
   
   set_worst(solutions);
   switch(s_mode)
   {
      case Proportional:
         selection_proportional(solutions, next_generation);
         break;
      case Tournament:
         selection_tournament(solutions, next_generation);
         break;
      case Boltzmann:
         (void)fprintf(logFile,"gs.cc/Unimplemented Selection Method - using proportional\n");
         selection_proportional(solutions, next_generation);
         break;
      default:
         (void)fprintf(logFile,"gs.cc/Unknown Selection Mode!\n");
   }

   return(next_generation);
}

//  For right now global search is taken to be a GA
int Genetic_Algorithm::search(Population &solutions)
{
   int i, outputEveryNgens = 1;
   unsigned int oldest = 0, oldestIndividual = 0, fittestIndividual = 0;
   double fittest = BIG;

   struct tms tms_genStart;
   struct tms tms_genEnd;

   Clock genStart;
   Clock genEnd;

#ifdef DEBUG
   (void)fprintf(logFile, "gs.cc/int Genetic_Algorithm::search(Population &solutions)\n");
#endif /* DEBUG */

   genStart = times( &tms_genStart );

#ifdef DEBUG3
   (void)fprintf(logFile,"[Pre-Mapping] (solutions)\n");
   for (i=0; i<solutions.num_individuals(); i++) {
       (void)fprintf(logFile,"%d ", solutions[i].age);
   }
   (void)fprintf(logFile,"\n");
#endif /* DEBUG3 */

   for (i=0; i<solutions.num_individuals(); i++) {
      solutions[i].mapping();
   }
   
#ifdef DEBUG3
   (void)fprintf(logFile,"[Pre-Selection] (solutions)\n");
   for (i=0; i<solutions.num_individuals(); i++) {
       (void)fprintf(logFile,"%ld ", solutions[i].age);
   }
   (void)fprintf(logFile,"\n");
#endif /* DEBUG3 */

   //  Perform selection
   Population newPop(solutions.num_individuals(), selection(solutions));

#ifdef DEBUG3
   (void)fprintf(logFile,"[Pre-Crossover] (newPop)\n");
   for (i=0; i<solutions.num_individuals(); i++) {
       (void)fprintf(logFile,"%ld ", newPop[i].age);
   }
   (void)fprintf(logFile,"\n");
#endif /* DEBUG3 */

   //  Perform crossover
   crossover(newPop);

#ifdef DEBUG3
   (void)fprintf(logFile,"[Pre-Mutation] (newPop)\n");
   for (i=0; i<solutions.num_individuals(); i++) {
       (void)fprintf(logFile,"%ld ", newPop[i].age);
   }
   (void)fprintf(logFile,"\n");
#endif /* DEBUG3 */

   //  Perform mutation
   mutation(newPop);

#ifdef DEBUG3
   (void)fprintf(logFile,"[Pre-Elitism] (newPop)\n");
   for (i=0; i<solutions.num_individuals(); i++) {
       (void)fprintf(logFile,"%ld ", newPop[i].age);
   }
   (void)fprintf(logFile,"\n");
#endif /* DEBUG3 */

   //  Copy the n best individuals to the next population, if the elitist flag is set.
   if (elitism>0) {
      solutions.msort(elitism);
      for (i=0; i<elitism; i++) {
         newPop[solutions.num_individuals()-1-i] = solutions[i];
      }
   }

#ifdef DEBUG3
   (void)fprintf(logFile,"[Pre-UpdateCurrentGeneration] (newPop)\n");
   for (i=0; i<solutions.num_individuals(); i++) {
       (void)fprintf(logFile,"%ld ", newPop[i].age);
   }
   (void)fprintf(logFile,"\n");
#endif /* DEBUG3 */

   // Update current generation...
   solutions = newPop;
   generations++;

   // Increment age of surviving individuals...
   for (i=0; i<solutions.num_individuals(); i++) {
       solutions[i].incrementAge();
   }

   if (generations%outputEveryNgens == 0) {
       oldest  = 0L;
       fittest = BIG;
       for (i=0; i<solutions.num_individuals(); i++) {
          if (solutions[i].age >= oldest) {
              oldest = solutions[i].age;
              oldestIndividual = i;
          }
          if (solutions[i].value(Normal_Eval) <= fittest) {
              fittest = solutions[i].value(Normal_Eval);
              fittestIndividual = i;
          }
       }
       if (outputEveryNgens > 1) {
#ifndef DEBUG3
           (void)fprintf(logFile,"Generation: %3u,  Oldest individual's energy: %.3f;   Lowest energy: %.3f;   Time taken for last %d generations: ", 
           generations, solutions[oldestIndividual].value(Normal_Eval), solutions[fittestIndividual].value(Normal_Eval), 
           outputEveryNgens);
#else
           (void)fprintf(logFile,"Generation: %3u,  Oldest individual: %u/%u, age: %uld, energy: %.3f;   Lowest energy individual: %u/%u, age: %uld, energy: %.3f;   Time taken for last %d generations: ", 
           generations, oldestIndividual+1L, solutions.num_individuals(), solutions[oldestIndividual].age, 
           solutions[oldestIndividual].value(Normal_Eval), fittestIndividual+1L, solutions.num_individuals(), 
           solutions[fittestIndividual].age, solutions[fittestIndividual].value(Normal_Eval), outputEveryNgens);
#endif /* DEBUG3 */
       } else {
#ifndef DEBUG3
           (void)fprintf(logFile,"Generation: %3u,  Oldest individual's energy: %.3f;   Lowest energy: %.3f;   Time taken: ", 
           generations, solutions[oldestIndividual].value(Normal_Eval), solutions[fittestIndividual].value(Normal_Eval));
#else
           (void)fprintf(logFile,"Generation: %3u,  Oldest individual: %u/%u, age: %uld, energy: %.3f;   Lowest energy individual: %u/%u, age: %uld, energy: %.3f;   Time taken: ", 
           generations, oldestIndividual+1L, solutions.num_individuals(), solutions[oldestIndividual].age, 
           solutions[oldestIndividual].value(Normal_Eval), fittestIndividual+1L, solutions.num_individuals(), 
           solutions[fittestIndividual].age, solutions[fittestIndividual].value(Normal_Eval));
#endif /* DEBUG3 */
       }
       genEnd = times( &tms_genEnd );
       timesyshms( genEnd - genStart, &tms_genStart, &tms_genEnd );
       //genStart = times( &tms_genStart );
   }

   return(0);
}