ga_optim.c

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

      MPI_Send(&instruction, 1, MPI_INT, status.MPI_SOURCE, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
      if (buffer_max==0)
        {
        pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &chromo, &buffer_max);
        MPI_Send(chromo, buffer_len, MPI_CHAR, status.MPI_SOURCE, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
        }
      else
        {
        pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &buffer, &buffer_len);
        MPI_Send(buffer, buffer_len, MPI_CHAR, status.MPI_SOURCE, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
        }

      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
      {
      eid[status.MPI_SOURCE-1] = -1;
      process_num--;
      }
    }

  return;
  }
#endif


/**********************************************************************
  gaul_ensure_evaluations_forked()
  synopsis:	Fitness evaluations.
		Evaluate all previously unevaluated entities.
		No adaptation.
  parameters:	population *pop
  return:	none
  last updated:	30 Jun 2002
 **********************************************************************/

#if W32_CRIPPLED != 1
static void gaul_ensure_evaluations_forked(population *pop, const int num_processes,
			int *eid, pid_t *pid, const int *evalpipe)
  {
  int		fork_num;		/* Index of current forked process. */
  int		num_forks;		/* Number of forked processes. */
  int		eval_num;		/* Index of current entity. */
  pid_t		fpid;			/* PID of completed child process. */

/*
 * A forked process is started for each fitness evaluation upto
 * a maximum of max_processes at which point we wait for
 * results before forking more.
 *
 * Skip evaluations for entities that have been previously evaluated.
 */
  fork_num = 0;
  eval_num = 0;

  /* Fork initial processes. */
  /* 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 (fork_num < num_processes && eval_num < pop->size)
    {
    eid[fork_num] = eval_num;
    pid[fork_num] = fork();

    if (pid[fork_num] < 0)
      {       /* Error in fork. */
      dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
      }
    else if (pid[fork_num] == 0)
      {       /* This is the child process. */
      if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
        pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;

      write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));

      fsync(evalpipe[2*fork_num+1]);	/* Ensure data is written to pipe. */
      _exit(1);
      }

    fork_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++;
#ifdef NEED_MOSIX_FORK_HACK
    usleep(10);
#endif
    }
  num_forks = fork_num;

  /* Wait for a forked process to finish and, if needed, fork another. */
  while (num_forks > 0)
    {
    fpid = wait(NULL);

    if (fpid == -1) die("Error in wait().");

    /* Find which entity this forked process was evaluating. */
    fork_num = 0;
    while (fpid != pid[fork_num]) fork_num++;

    if (eid[fork_num] == -1) die("Internal error.  eid is -1");

    read(evalpipe[2*fork_num], &(pop->entity_iarray[eid[fork_num]]->fitness), sizeof(double));

    if (eval_num < pop->size)
      {       /* New fork. */
      eid[fork_num] = eval_num;
      pid[fork_num] = fork();

      if (pid[fork_num] < 0)
        {       /* Error in fork. */
        dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
        }
      else if (pid[fork_num] == 0)
        {       /* This is the child process. */
        if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
          pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;

        write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));

        fsync(evalpipe[2*fork_num+1]);	/* Ensure data is written to pipe. */
        _exit(1);
        }

      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
      {
      pid[fork_num] = -1;
      eid[fork_num] = -1;
      num_forks--;
      }
    }

  return;
  }
#endif


/**********************************************************************
  gaul_ensure_evaluations_threaded()
  synopsis:	Fitness evaluations.
		Evaluate all previously unevaluated entities.
		No adaptation.
		Threaded processing version.
  parameters:	population *pop
  return:	none
  last updated:	18 Sep 2002
 **********************************************************************/

#if HAVE_PTHREADS == 1

typedef struct threaddata_s
  {
  int thread_num;
  int eval_num;
  population *pop;
  pthread_t pid;
  } threaddata_t;

/*
 * This is the child thread code used by gaul_ensure_evaluations_threaded(),
 * gaul_adapt_and_evaluate_threaded() and gaul_survival_threaded() to evaluate entities.
 */
static void *_evaluation_thread( void *data )
  {
  int		eval_num = ((threaddata_t *)data)->eval_num;
  population	*pop = ((threaddata_t *)data)->pop;

  if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
    pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;

#if GA_DEBUG>2
printf("DEBUG: Thread %d has evaluated entity %d\n", ((threaddata_t *)data)->thread_num, eval_num);
#endif

  ((threaddata_t *)data)->thread_num = -1;	/* Signal that this thread is finished. */

  pthread_exit(NULL);

  return NULL;	/* Keep Compaq's C/C++ compiler happy. */
  }

static void gaul_ensure_evaluations_threaded( population *pop, const int max_threads, threaddata_t *threaddata )
  {
  int		thread_num;		/* Index of current thread. */
  int		num_threads;		/* Number of threads currently in use. */
  int		eval_num;		/* Index of current entity. */

/*
 * A thread is created for each fitness evaluation upto
 * a maximum of max_threads at which point we wait for
 * results before continuing.
 *
 * Skip evaluations for entities that have been previously evaluated.
 */
  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;
  }
#endif /* HAVE_PTHREADS */


/**********************************************************************
  gaul_adapt_and_evaluate()
  synopsis:	Fitness evaluations.
		Evaluate the new entities produced in the current
		generation, whilst performing any necessary adaptation.
		Simple sequential version.
  parameters:	population *pop
  return:	none
  last updated:	11 Jun 2002
 **********************************************************************/

static void gaul_adapt_and_evaluate(population *pop)
  {
  int		i;			/* Loop variable over entity ranks. */
  entity	*adult=NULL;		/* Adapted entity. */
  int		adultrank;		/* Rank of adapted entity. */

  if (pop->scheme == GA_SCHEME_DARWIN)
    {	/* This is pure Darwinian evolution.  Simply assess fitness of all children.  */

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

#pragma omp parallel for \
   shared(pop) private(i) \
   schedule(static)
    for (i=pop->orig_size; i<pop->size; i++)
      {
/*printf("DEBUG: gaul_adapt_and_evaluate() parallel for %d on %d/%d.\n", i, omp_get_thread_num(), omp_get_num_threads());*/
      if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
        pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
      }

    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 )
      {
#pragma omp parallel for \
   shared(pop) private(i,adult) \
   schedule(static)
      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 )
      {
#pragma omp parallel for \
   shared(pop) private(i,adult,adultrank) \
   schedule(static)
      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 )
      { 
#pragma omp parallel for \
   shared(pop) private(i,adult) \
   schedule(static)
      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 )
      {
#pragma omp parallel for \
   shared(pop) private(i,adult,adultrank) \
   schedule(static)
      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;
  }


/**********************************************************************
  gaul_adapt_and_evaluate_mp()
  synopsis:	Fitness evaluations.
		Evaluate the new entities produced in the current
		generation, whilst performing any necessary adaptation.
		MPI version.
  parameters:	population *pop
  return:	none
  last updated:	03 Feb 2003
 **********************************************************************/

#if HAVE_MPI == 1
static void gaul_adapt_and_evaluate_mp(population *pop)
  {
  int		i;			/* Loop variable over entity ranks. */
  entity	*adult=NULL;		/* Adapted entity. */
  int		adultrank;		/* Rank of adapted entity. */

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

  if (pop->scheme == GA_SCHEME_DARWIN)
    {	/* This is pure Darwinian evolution.  Simply assess fitness of all children.  */

    plog(LOG_VERBOSE, "*** Fitness 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;
      }

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