ga_optim.c

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

#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;
  }
#endif


/**********************************************************************
  gaul_adapt_and_evaluate_mpi()
  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:	24 Jun 2004
 **********************************************************************/

#if HAVE_MPI == 1
static void gaul_adapt_and_evaluate_mpi( population *pop, int *eid,
                        byte *buffer, int buffer_len, int buffer_max )
  {
  int		i;			/* Loop variable over entity ranks. */
  entity	*adult=NULL;		/* Adapted entity. */
  int		adultrank;		/* Rank of adapted entity. */
  MPI_Status	status;			/* MPI status structure. */
  double	single_double;		/* Recieve buffer. */
  int		instruction=2;		/* Detach instruction. */
  int		mpi_size;		/* Number of slave processes. */
  int		process_num;		/* Number of remote processes running calculations. */
  int		eval_num;		/* Id of entity being processed. */
  byte		*chromo=NULL;		/* Chromosome in byte form. */

  MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);

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

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

/*
 * A process is notifed to begin each fitness evaluation until
 * all processes are busy, at which point we wait for
 * results before initiating more.
 *
 * Skip evaluations for entities that have been previously evaluated.
 */
    process_num = 0;
    eval_num = pop->orig_size;	/* These solutions must already be evaluated. */

    /* 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 (process_num < mpi_size-1 && eval_num < pop->size)
      {
      eid[process_num] = eval_num;

/* Send instruction and required data. */
      MPI_Send(&instruction, 1, MPI_INT, process_num+1, 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, process_num+1, 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, process_num+1, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
        }

      process_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++;
      }

    while (process_num > 0)
      { /* Wait for a process to finish. */
      MPI_Recv(&single_double, 1, MPI_DOUBLE, MPI_ANY_SOURCE, GA_TAG_FITNESS, MPI_COMM_WORLD, &status);
      /* FIXME: Check status here. */

      /* Find which entity this process was evaluating. */
      if (eid[status.MPI_SOURCE-1] == -1) die("Internal error.  eid is -1");

      pop->entity_iarray[eid[status.MPI_SOURCE-1]]->fitness = single_double;

      if (eval_num < pop->size)
        {
        eid[status.MPI_SOURCE-1] = eval_num;

        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;
    }
  else
    {	/* Some kind of adaptation is required.  First reevaluate parents, as needed, then children. */

    plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");
    plog(LOG_FIXME, "Need to parallelise this!");

    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;
  }
#endif


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

#if W32_CRIPPLED != 1
static void gaul_adapt_and_evaluate_forked(population *pop,
	       		const int num_processes,
			int *eid, pid_t *pid, const int *evalpipe)
  {
  int		i;			/* Loop variable over entity ranks. */
  entity	*adult=NULL;		/* Adapted entity. */
  int		adultrank;		/* Rank of adapted entity. */
  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. */

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

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

/* 
 * 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.
 *
 * FIXME: This lump of code is almost identical to that in
 * gaul_ensure_evaluations_forked() and shouldn't really be duplicated.
 */
    fork_num = 0;
    eval_num = pop->orig_size;

    /* Fork initial processes. */
    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++;
#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++;
        }
      else
        {
        pid[fork_num] = -1;
        eid[fork_num] = -1;
        num_forks--;
        }
      }

    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_adapt_and_evaluate_threaded()
  synopsis:	Fitness evaluations.
		Evaluate the new entities produced in the current
		generation, whilst performing any necessary adaptation.
		Threaded processing version.
  parameters:	population *pop
  return:	none
  last updated:	15 Apr 2004
 **********************************************************************/

#if HAVE_PTHREADS == 1
static void gaul_adapt_and_evaluate_threaded(population *pop,
	       		const int max_threads,
			threaddata_t *threaddata)
  {
  int		i;			/* Loop variable over entity ranks. */
  entity	*adult=NULL;		/* Adapted entity. */
  int		adultrank;		/* Rank of adapted entity. */
  int		thread_num;		/* Index of current thread. */
  int		num_threads;		/* Number of threads currently in use. */
  int		eval_num;		/* Index of current entity. */

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