ga_optim.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

    plog(LOG_VERBOSE, "*** Fitness Evaluations ***");

/* 
 * A thread is created for each fitness evaluation upto
 * a maximum of max_threads at which point we wait for 
 * results before creating more.
 *
 * Skip evaluations for entities that have been previously evaluated.
 *
 * FIXME: This lump of code is almost identical to that in
 * gaul_ensure_evaluations_threaded() and shouldn't really be duplicated.
 */
  thread_num = 0;
  eval_num = 0;

  /* Skip to the next entity which needs evaluating. */
  while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;

  while (thread_num < max_threads && eval_num < pop->size)
    {
    threaddata[thread_num].thread_num = thread_num;
    threaddata[thread_num].eval_num = eval_num;

    if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
      {       /* Error in thread creation. */
      dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
      }

    thread_num++;
    eval_num++;

    /* Skip to the next entity which needs evaluating. */
    while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS)
      eval_num++;
    }

  num_threads = thread_num;

  /* Wait for a thread to finish and, if needed, create another. */
  /* Also, find which entity this thread was evaluating. */
  thread_num=0;
  while (num_threads > 0)
    {
    while (threaddata[thread_num].thread_num >= 0)
      {
      thread_num++;
      if (thread_num==max_threads)
        {
        thread_num=0;
/* FIXME: Insert short sleep here? */
        }
      }

#if GA_DEBUG>2
printf("DEBUG: Thread %d finished.  num_threads=%d eval_num=%d/%d\n", thread_num, num_threads, eval_num, pop->size);
#endif

    if ( pthread_join(threaddata[thread_num].pid, NULL) < 0 )
      {
      dief("Error %d in pthread_join. (%s)", errno, errno==ESRCH?"ESRCH":errno==EINVAL?"EINVAL":errno==EDEADLK?"EDEADLK":"unknown");
      }

    if (eval_num < pop->size)
      {       /* New thread. */
      threaddata[thread_num].thread_num = thread_num;
      threaddata[thread_num].eval_num = eval_num;

      if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
        {       /* Error in thread creation. */
        dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
        }

      eval_num++;

      /* Skip to the next entity which needs evaluating. */
      while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS)
        eval_num++;
      }
    else
      {
      threaddata[thread_num].thread_num = 0;
      threaddata[thread_num].eval_num = -1;
      num_threads--;
      }
    }

    return;
    }
  else
    {	/* Some kind of adaptation is required.  First reevaluate parents, as needed, then children. */

    plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");

    if ( (pop->scheme & GA_SCHEME_BALDWIN_PARENTS)!=0 )
      {
      for (i=0; i<pop->orig_size; i++)
        {
        adult = pop->adapt(pop, pop->entity_iarray[i]);
        pop->entity_iarray[i]->fitness=adult->fitness;
        ga_entity_dereference(pop, adult);
        }
      }
    else if ( (pop->scheme & GA_SCHEME_LAMARCK_PARENTS)!=0 )
      {
      for (i=0; i<pop->orig_size; i++)
        {
        adult = pop->adapt(pop, pop->entity_iarray[i]);
        adultrank = ga_get_entity_rank(pop, adult);
        gaul_entity_swap_rank(pop, i, adultrank);
        ga_entity_dereference_by_rank(pop, adultrank);
        }
      }

    if ( (pop->scheme & GA_SCHEME_BALDWIN_CHILDREN)!=0 )
      { 
      for (i=pop->orig_size; i<pop->size; i++)
        {
        adult = pop->adapt(pop, pop->entity_iarray[i]);
        pop->entity_iarray[i]->fitness=adult->fitness;
        ga_entity_dereference(pop, adult);
        }
      }
    else if ( (pop->scheme & GA_SCHEME_LAMARCK_CHILDREN)!=0 )
      {
      for (i=pop->orig_size; i<pop->size; i++)
        {
        adult = pop->adapt(pop, pop->entity_iarray[i]);
        adultrank = ga_get_entity_rank(pop, adult);
        gaul_entity_swap_rank(pop, i, adultrank);
        ga_entity_dereference_by_rank(pop, adultrank);
        }
      }
    }

  return;
  }
#endif


/**********************************************************************
  gaul_survival()
  synopsis:	Survival of the fittest.
		Enforce elitism, apply crowding operator, reduce
		population back to its stable size and rerank entities,
		as required.

		*** FIXME: crowding analysis incomplete. ***

  parameters:	population *pop
  return:	none
  last updated:	18 Mar 2003
 **********************************************************************/

static void gaul_survival(population *pop)
  {
  int		i;			/* Loop variable over entity ranks. */

  plog(LOG_VERBOSE, "*** Survival of the fittest ***");

/*
 * Need to kill parents, or rescore parents?
 */
  if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
    {
    while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
      {
      pop->orig_size--;
      ga_entity_dereference_by_rank(pop, pop->orig_size);
      }
    }
  else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
    {
    plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");

#pragma omp parallel for \
   shared(pop) private(i) \
   schedule(static)
    for (i=pop->orig_size; i<pop->size; i++)
      {
      if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
        pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
      }
    }

/*
 * Sort all population members by fitness.
 */
  sort_population(pop);

/*
 * Enforce the type of crowding desired.
 *
 * Rough crowding doesn't actual check whether two chromosomes are
 * identical - just assumes they are if they have identical
 * fitness.  Exact elitism does make the full check.
 */
#if 0
    if (pop->elitism == GA_ELITISM_EXACT || pop->elitism == GA_ELITISM_ROUGH)
      { /* Fatal version */
      i = 1;

      while (i<pop->size && i<pop->stable_size)
        {
        if (pop->entity_iarray[i]->fitness==pop->entity_iarray[i-1]->fitness &&
            (pop->elitism != GA_ELITISM_EXACT ||
             ga_compare_genome(pop, pop->entity_iarray[i], pop->entity_iarray[i-1])) )
          {
          ga_entity_dereference_by_rank(pop, i);
          }
        else
          {
          i++;
          }
        }
      }
    else if (pop->elitism == GA_ELITISM_EXACT_COMP || pop->elitism == GA_ELITISM_ROUGH_COMP)
      { /* Increased competition version */
      i = MIN(pop->size, pop->stable_size);
      elitism_penalty = fabs(pop->entity_iarray[0]->fitness*GA_ELITISM_MULTIPLIER)
                        + GA_ELITISM_CONSTANT;

      while (i>0)
        {
        if (pop->entity_iarray[i]->fitness==pop->entity_iarray[i-1]->fitness &&
            (pop->elitism != GA_ELITISM_EXACT_COMP ||
             ga_compare_genome(pop, pop->entity_iarray[i], pop->entity_iarray[i-1])) )
          {
          pop->entity_iarray[i]->fitness -= elitism_penalty;
          }
        i--;
        }

      plog(LOG_VERBOSE, "*** Sorting again ***");

      sort_population(pop);     /* FIXME: We could possibly (certianly) choose
                                         a more optimal sort algorithm here. */
      }
#endif

/*
 * Least fit population members die to restore the
 * population size to its stable size.
 */
  ga_genocide(pop, pop->stable_size);
  ga_genocide_by_fitness(pop, GA_MIN_FITNESS);

  return;
  }


/**********************************************************************
  gaul_survival_mp()
  synopsis:	Survival of the fittest.
		Enforce elitism, apply crowding operator, reduce
		population back to its stable size and rerank entities,
		as required.

		*** FIXME: crowding analysis incomplete. ***

  parameters:	population *pop
  return:	none
  last updated:	18 Mar 2003
 **********************************************************************/

#if HAVE_MPI == 1
static void gaul_survival_mp(population *pop)
  {
  int		i;			/* Loop variable over entity ranks. */

  plog(LOG_FIXME, "Need to parallelise this!");

  plog(LOG_VERBOSE, "*** Survival of the fittest ***");

/*
 * Need to kill parents, or rescore parents?
 */
  if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
    {
    while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
      {
      pop->orig_size--;
      ga_entity_dereference_by_rank(pop, pop->orig_size);
      }
    }
  else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
    {
    plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");

#pragma omp parallel for \
   shared(pop) private(i) \
   schedule(static)
    for (i=pop->orig_size; i<pop->size; i++)
      {
      if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
        pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
      }
    }

/*
 * Sort all population members by fitness.
 */
  sort_population(pop);

/*
 * Enforce the type of crowding desired.
 *
 * Rough crowding doesn't actual check whether two chromosomes are
 * identical - just assumes they are if they have identical
 * fitness.  Exact elitism does make the full check.
 *
 * FIXME: Crowding code missing!!!
 */

/*
 * Least fit population members die to restore the
 * population size to its stable size.
 */
  ga_genocide(pop, pop->stable_size);
  ga_genocide_by_fitness(pop, GA_MIN_FITNESS);

  return;
  }
#endif


/**********************************************************************
  gaul_survival_mpi()
  synopsis:	Survival of the fittest.
		Enforce elitism, apply crowding operator, reduce
		population back to its stable size and rerank entities,
		as required.

		*** FIXME: crowding analysis incomplete. ***

  parameters:	population *pop
  return:	none
  last updated:	10 May 2004
 **********************************************************************/

#if HAVE_MPI == 1
static void gaul_survival_mpi(population *pop)
  {
  int		i;			/* Loop variable over entity ranks. */

  plog(LOG_VERBOSE, "*** Survival of the fittest ***");

/*
 * Need to kill parents, or rescore parents?
 */
  if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
    {
    while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
      {
      pop->orig_size--;
      ga_entity_dereference_by_rank(pop, pop->orig_size);
      }
    }
  else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
    {
    plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");
    plog(LOG_FIXME, "Need to parallelise this!");

#pragma omp parallel for \
   shared(pop) private(i) \
   schedule(static)
    for (i=pop->orig_size; i<pop->size; i++)
      {
      if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
        pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
      }
    }

/*
 * Sort all population members by fitness.
 */
  sort_population(pop);

/*
 * Enforce the type of crowding desired.
 *
 * Rough crowding doesn't actual check whether two chromosomes are
 * identical - just assumes they are if they have identical
 * fitness.  Exact elitism does make the full check.
 *
 * FIXME: Crowding code missing!!!
 */

/*
 * Least fit population members die to restore the
 * population size to its stable size.
 */
  ga_genocide(pop, pop->stable_size);
  ga_genocide_by_fitness(pop, GA_MIN_FITNESS);

  return;
  }
#endif


/**********************************************************************
  gaul_survival_forked()
  synopsis:	Survival of the fittest.
		Enforce elitism, apply crowding operator, reduce
		population back to its stable size and rerank entities,
		as required.
		Forked processing version.

		*** FIXME: crowding analysis incomplete. ***

  parameters:	population *pop
  return:	none
  last updated:	18 Mar 2003
 **********************************************************************/

#if W32_CRIPPLED != 1
static void gaul_survival_forked(population *pop,
			const int num_processes,
			int *eid, pid_t *pid, const int *evalpipe)
  {
  int		fork_num;		/* Index of current forked process