qga.c

遗传算法与回朔法对比 解决n皇后问题c源码

  pop->buf  = pop->inds +size; /* create vectors of individuals */
  pop->size = size;            /* note the population size */
  for (size *= 2; --size >= 0; ) {
    pop->inds[size] = ind_create(n);
    if (!pop->inds[size]) { pop_delete(pop); return NULL; }
  }                            /* create the individuals */
  return pop;                  /* return the created population */
}  /* pop_create() */

/*--------------------------------------------------------------------*/

void pop_init (POP *pop)
{                              /* --- initialize a population */
  int i;                       /* loop variable */

  assert(pop);                 /* check the function argument */
  for (i = pop->size; --i >= 0; )
    ind_init(pop->inds[i]);    /* initialize all individuals */
}  /* pop_init() */

/*--------------------------------------------------------------------*/

int pop_eval (POP *pop)
{                              /* --- evaluate a population */
  int i;                       /* loop variable */
  IND *best;                   /* best individual */

  assert(pop);                 /* check the function argument */
  ind_eval(best = pop->inds[0]);
  for (i = pop->size; --i > 0; )
    if (ind_eval(pop->inds[i]) >= best->fitness)
      best = pop->inds[i];     /* find the best individual */
  pop->best = best;            /* note the best individual */
  return best->fitness;        /* and return its fitness */
}  /* pop_eval() */

/*--------------------------------------------------------------------*/

IND* pop_tmsel (POP *pop, int tmsize)
{                              /* --- tournament selection */
  IND *ind, *best;             /* competing/best individual */

  assert(pop && (tmsize > 0)); /* check the function arguments */
  best = pop->inds[(int)(pop->size *drand())];
  while (--tmsize > 0) {       /* randomly select tmsize individuals */
    ind = pop->inds[(int)(pop->size *drand())];
    if (ind->fitness > best->fitness) best = ind;
  }                            /* det. individual with best fitness */
  return best;                 /* and return this individual */
}  /* pop_tmsel() */

/*--------------------------------------------------------------------*/

void pop_select (POP *pop, int tmsize, int elitist)
{                              /* --- select individuals */
  int i;                       /* loop variables */
  IND **p;                     /* exchange buffer */

  assert(pop && (tmsize > 0)); /* check the function arguments */
  i = pop->size;               /* select 'popsize' individuals */
  if (elitist)                 /* preserve the best individual */
    ind_copy(pop->buf[--i], pop->best);
  while (--i >= 0)             /* select (other) individuals */
    ind_copy(pop->buf[i], pop_tmsel(pop, tmsize));
  p = pop->inds; pop->inds = pop->buf;
  pop->buf = p;                /* set selected individuals */
  pop->best = NULL;            /* best individual is not known yet */
}  /* pop_select() */

/*--------------------------------------------------------------------*/

void pop_cross (POP *pop, double frac)
{                              /* --- crossover in a population */
  int i, k;                    /* loop variables */

  assert(pop                   /* check the function arguments */
      && (frac >= 0) && (frac <= 1));
  k = (int)((pop->size -1) *frac) & ~1;
  for (i = 0; i < k; i += 2)   /* crossover of pairs of individuals */
    ind_cross(pop->inds[i], pop->inds[i+1]);
}  /* pop_cross() */

/*--------------------------------------------------------------------*/

void pop_mutate (POP *pop, double prob)
{                              /* --- mutate a population */
  int i;                       /* loop variable */

  assert(pop                   /* check the function arguments */
      && (prob >= 0) && (prob <= 1));
  for (i = pop->size -1; --i >= 0; )
    ind_mutate(pop->inds[i], prob);
}  /* pop_mutate() */          /* mutate individuals */

/*--------------------------------------------------------------------*/

#define pop_best(p) ((p)->best)   /* --- get best individual */

/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print an error message */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print the error message */
    va_end(args);               /* end argument evaluation */
  }
  exit(code);                   /* abort the program */
}  /* error() */

/*--------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  int    i, k = 0;              /* loop variables, counters */
  char   *s;                    /* to traverse the options */
  int    n       =    8;        /* size of chessboard */
  int    popsize =  100;        /* size of population */
  int    gencnt  = 1000;        /* number of generations */
  double frac    =    0.5;      /* fraction to create by combining */
  double prob    =    0.1;      /* mutation probability */
  int    tmsize  =    5;        /* tournament size */
  int    elitist =    0;        /* whether to keep best individual */
  int    verb    =    0;        /* flag for verbose output */
  long   seed    = time(NULL);  /* seed for random number generator */
  POP    *pop;                  /* population */
  IND    *ind;                  /* individual */

  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print startup/usage message --- */
  if (argc > 1) {               /* if arguments are given */
    fprintf(stderr, "%s - %s\n", argv[0], DESCRIPTION);
    fprintf(stderr, VERSION); } /* print a startup message */
  else {                        /* if no argument is given */
    printf("usage: %s [options] n\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-p#    size of population (default: %d)\n", popsize);
    printf("-g#    number of generations (default: %d)\n", gencnt);
    printf("-m#    mutation probability (default: %g)\n", prob);
    printf("-f#    fraction of crossover individuals "
                  "(default: %g)\n", frac);
    printf("-t#    tournament size (default: %d)\n", tmsize);
    printf("-e     elitist (always keep best individual)\n");
    printf("-s#    seed for random number generator "
                  "(default: time)\n");
    printf("-v     be verbose (show best fitness in each step)\n");
    printf("n      number of queens/size of the chessboard\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */

  /* --- evaluate arguments --- */
  for (i = 1; i < argc; i++) {  /* traverse arguments */
    s = argv[i];                /* get option argument */
    if ((*s == '-') && *++s) {  /* -- if argument is an option */
      while (*s) {              /* traverse characters */
        switch (*s++) {         /* evaluate option */
          case 'p': popsize = (int)strtol(s, &s, 0); break;
          case 'g': gencnt  = (int)strtol(s, &s, 0); break;
          case 'm': prob    =      strtod(s, &s);    break;
          case 'f': frac    =      strtod(s, &s);    break;
          case 't': tmsize  = (int)strtol(s, &s, 0); break;
          case 'e': elitist = 1;                     break;
          case 's': seed    =      strtol(s, &s, 0); break;
          case 'v': verb    = 1;                     break;
          default : error(E_OPTION, *--s);           break;
        }                       /* set option variables */
      } }
    else {                      /* -- if argument is no option */
      switch (k++) {            /* evaluate non-option */
        case  0: n = atoi(s);     break;
        default: error(E_ARGCNT); break;
      }                         /* note fixed arguments */
    }
  }
  if (k != 1) error(E_ARGCNT);  /* check number of arguments */
  if (n <= 0) error(E_SIZE, n); /* and the argument values */
  if (popsize <= 0)                error(E_POPSIZE, popsize);
  if (gencnt  <= 0)                error(E_GENCNT,  gencnt);
  if ((prob   <  0) || (prob > 1)) error(E_PROB,    prob);
  if ((frac   <  0) || (frac > 1)) error(E_FRAC,    frac);
  if (tmsize  <= 0)                error(E_TMSIZE,  tmsize);
  fprintf(stderr, "\n");        /* terminate the startup message */

  /* --- create populations --- */
  srand((unsigned)seed);        /* init. random number generator */
  pop = pop_create(popsize, n); /* create a population */
  if (!pop) error(E_NOMEM);     /* of candidate solutions */

  /* --- genetic algorithm --- */
  pop_init(pop);                /* initialize the population */
  while ((pop_eval(pop) < 0)    /* while no solution found and */
  &&     (--gencnt >= 0)) {     /* not all generations computed */
    if (verb)                   /* if verbose message output */
      fprintf(stderr, "%8d\b\b\b\b\b\b\b\b", -ind_eval(pop_best(pop)));
    pop_select(pop, tmsize, elitist);
    pop_cross (pop, frac);      /* select individuals, */
    pop_mutate(pop, prob);      /* do crossover, and */
  }                             /* mutate individuals */

  /* --- show solution --- */
  ind = pop_best(pop);          /* get the best individual and */
  ind_show(ind);                /* show the positions of the queens */
  k = ind_eval(ind);            /* get the fitness and print it */
  printf("\nfitness: %d (%ssolution)\n", k, (k >= 0) ? "" : "no ");

  return 0;                     /* return 'ok' */
}  /* main() */