simple-gp.c

其中提到遺傳學的程式碼與應用提供給次淚相向的研究者參考下載

//Nb best program is defined to be one with highest number of hits
//regardless of fitness
*/
{
  new_population[child].fitness = fit;

  new_sumfitness += new_population[child].fitness;

  new_population[child].hits    = n_hits;

  if (max_hits < new_population[child].hits)
    {
       max_hits  = new_population[child].hits;
       best_prog = child;
    }

}/*end update_hits_etc()*/

test_fitness (int child )
/*evaluate test_fitness of child in new_population, store answer with it.*/
{
int i;
int test_hits = 0;
float error;
float total_error = 0.0;

  for ( i=0; i < num_x; i++ )
  {
     error = fabs ( y[i] - prog_value( new_population[child].string, x[i] ) );

     if (error <= THRESHOLD || error <= THRESHOLD * fabs(y[i]) ) test_hits++;

     total_error += error;

  }/*end for each test switch*/

  num_tests++;

  update_hits_etc(num_x/(total_error+num_x), test_hits, child);
/*
  update_hits_etc(1.0/(total_error+1.0), test_hits, child);
*/
}/*end test_fitness()*/

display_stats()
/*display info on new_population */
{
int i;
time_t now;

float min_fitness = FLT_MAX;
float max_fitness = -FLT_MAX;

int mi_hits  = num_x;
int mx_hits  = 0;
int sum_hits = 0;

float sum_fitness = 0.0;
float sum_squared = 0.0;
float mean;


time (&now);
printf ("\n Generation %d on %s\n", generation, ctime(&now));

for ( i=0; i < POPULATION_SIZE; i++ )
  {
    sum_fitness += new_population[i].fitness;
    sum_squared += new_population[i].fitness*new_population[i].fitness;

    if (min_fitness > new_population[i].fitness)
      min_fitness = new_population[i].fitness;

    if (max_fitness < new_population[i].fitness)
      max_fitness = new_population[i].fitness;

    if (mi_hits > new_population[i].hits)
      mi_hits = new_population[i].hits;

    if (mx_hits < new_population[i].hits)
      mx_hits = new_population[i].hits;

    sum_hits += new_population[i].hits;

  }/*end for*/

mean = sum_fitness / POPULATION_SIZE;


for ( i=0; i < POPULATION_SIZE; i++ )
  {
    if      ( parents[i].mumcross == COPY_MUM )
      printf ("copy     [%3d]=%3d             ", 
               i, parents[i].mum) ;
    else if ( parents[i].dad      == MUTATE )
      printf ("mutate   [%3d]=%3d(%2d)+(%2d)    ",
               i, parents[i].mum, parents[i].mumcross, 
                  parents[i].dadcross );
    else
      printf ("crossover[%3d]=%3d(%2d)*%3d(%2d) ",
               i, parents[i].mum, parents[i].mumcross, 
                  parents[i].dad, parents[i].dadcross );

   printf ("fit = %.5f hits = %2d pselect = %.3f %s\n",
           new_population[i].fitness,
           new_population[i].hits,
           new_population[i].fitness/mean,
           new_population[i].string );
  }

printf ("Generation %d, new_sumfitness %e %s",
  generation, new_sumfitness, ctime(&now));

printf ("Mean fitness = %.5f, variance = %.5f, min = %.5f, max = %.5f \n",
  mean,
  (sum_squared - POPULATION_SIZE*mean*mean )/POPULATION_SIZE,
  min_fitness,
  max_fitness );

printf (
"Min hits = %2d, max = %2d, best_prog = %3d, fitness = %.5f hits = %2d %s\n",
  mi_hits,
  mx_hits,
  best_prog,
  new_population[best_prog].fitness,
  new_population[best_prog].hits,  
  new_population[best_prog].string    ); 

}/*end display_stats()*/


replace_old_population()
{
int i;

  total_fitness  = new_sumfitness;
/* best_prog - retain current value until new generation*/

   for (i = 0; i < POPULATION_SIZE; i++ )
     {
         strcpy (population[i].string, new_population[i].string);
         population[i].fitness = new_population[i].fitness;
         population[i].hits    = new_population[i].hits;
     }

}/*end replace_old_population()*/



initialise_population()
{
int i;

  for ( i=0; i < POPULATION_SIZE; i++ )
    {
       population[i].string[0] = '\0';
       mutate (i,i);
       test_fitness(i);
    }

  display_stats();

  replace_old_population();

} /*end initialise_population() */


int select_parent()
/* return index or parent in old population*/
{
/*consider binary chop if POPULATION_SIZE becomes big*/

int i;

float cumlative_fitness = 0.0;
float r;

  r = total_fitness * random_number();

  for (i = 0; i < POPULATION_SIZE; i++ )
    {
        cumlative_fitness += population[i].fitness;
        if ( r <= cumlative_fitness ) return (i);
    }

  return ( POPULATION_SIZE - 1 );

}/*end select_parent() */


crossover ( int mum, int dad, int child )

/*choose a random point in program from old population and another
//also from old population to produce a child which is stored in the new
//population */
{ 
int mum_end1;
int mum_start2, mum_end2;
int dad_start, dad_end;

int sanity = 0;

do {
  assert (sanity++ < 1000);

  mum_end1   = random_point ( population[mum].string );
  mum_start2 = matching_point ( population[mum].string, mum_end1 ); 
  mum_end2   = strlen ( population[mum].string );

  dad_start = random_point ( population[dad].string );
  dad_end   = matching_point ( population[dad].string, dad_start );

} while (splice ( 
         new_population[child].string, MAX_PROG_SIZE+1,
         population[mum].string, mum_end1,
         &population[dad].string[dad_start], dad_end - dad_start,
         &population[mum].string[mum_start2], mum_end2 - mum_start2 ) != 0 );

/*display data */
parents[child].mum       = mum;
parents[child].mumcross  = mum_end1;
parents[child].dad       = dad;
parents[child].dadcross  = dad_start;

}/*end crossover ()*/


copy (int mum, int child)
/*copy from old population to new_population, including test_fitness*/

{
  strcpy (new_population[child].string, population[mum].string);

/*display data */
parents[child].mum       = mum;
parents[child].mumcross  = COPY_MUM;

  update_hits_etc (population[mum].fitness, population[mum].hits, child );

}/*end copy()*/


push_string ( char value[] )
{
char a[LINE_WIDTH];
char result[LINE_WIDTH];

if ( (stack <= 0) || (op_stack[stack-1] != 0) ) /*operator on top of stack*/
  {                                             /*or stack empty          */
    op_stack [ stack ]  = 0;                /*operand on top of stack*/
    strcpy (output_stack[stack], value);
    stack++;
  }
else
  {
    --stack;
    strcpy (a, output_stack[stack]);      /*pop first operand*/
    switch (op_stack[--stack])            /*pop operator*/
      {
        case '+':  sprintf (result, "%s+%s", a, value);
                   break;

        case '-':  sprintf (result, "(%s)-(%s)", a, value);
                   break;

        case '*':  sprintf (result, "(%s)*(%s)", a, value);
                   break;

        case '/':  sprintf (result, "div(%s,%s)", a, value);
                   break;

        default:
                   assert (11 == 0 ); /* opps!*/
                   break;
      }

    push_string ( result );
  }

}/*end push_string()*/


output_program (char string[] )
/* Convert string to c format*/
{
char buff [] = " ";
int i;
FILE *stream;

stack = 0;

for ( i = 0; string[i] != 0; i++ )
  {
      switch (string [i])
      {
        case '+':
        case '-':
        case '*':
        case '/':         push_operator(string[i]);
                          break;

        default:          buff [ 0 ] = string [i];
                          push_string( buff );
                          break;
      }
  }/*end for*/

assert (stack == 1);

if ((stream=fopen(output_file,"w"))==NULL)
  {printf("Failed to open file %s for output! Stopping!\n", output_file);
   exit (EXIT_FAILURE);}

fprintf (stream, "\nfloat div ( float top, float bot )\n");
fprintf (stream, "{if (bot == 0.0)\n");
fprintf (stream, "   return (1.0);\n");
fprintf (stream, " else\n");
fprintf (stream, "   return ( top/bot );\n");
fprintf (stream, "}\n");
                 
fprintf (stream, "\nfloat gp( float x )\n{\n");
fprintf (stream, "  return (%s);\n}\n", output_stack[--stack] );

fclose (stream);

}/*end output_program()*/



int main()
{
int i, mum, dad;

  read_inputs();

  generation = 0;

  new_sumfitness = 0.0;
  max_hits       = -1;

  initialise_population();

  while ((++generation <= MAX_GEN) && (max_hits < required_hits))
  {
    new_sumfitness = 0.0;
    max_hits       = -1;

    for (i = 0; i < POPULATION_SIZE; i++)
    {
       mum = select_parent();
       if (random_number() < PCROSS)
       {
         dad = select_parent();
         crossover (mum, dad, i);
         test_fitness(i);
         }
       else if (random_number() < PMUT)
         {
         mutate(mum,i);
         test_fitness(i);
         }
       else
         {
         copy (mum,i);
         };
    }/*end for - create new_population */
  
    display_stats();

    replace_old_population();

  } /*end while */

  output_program( population[best_prog].string );

  printf("GP done. %d tests completed\n", num_tests );

  return (0);

}/*end main() */


/*end program GP*/