qga.c

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

/*----------------------------------------------------------------------
  File    : qga.c
  Contents: Genetic algorithm solution of the n queens problem
  Author  : Christian Borgelt
  History : 16.10.2001 file created
            18.10.2001 fitness of unmutated inds. no longer invalidated
            23.10.2001 didactical improvements
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <limits.h>
#include <time.h>
#include <assert.h>

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "qga"
#define DESCRIPTION "solve the n queens problem " \
                    "with a genetic algorithm"
#define VERSION     "version 1.2 (23.10.2001)         " \
                    "(c) 2001   Christian Borgelt"

/* --- error codes --- */
#define OK            0         /* no error */
#define E_NONE        0         /* no error */
#define E_NOMEM     (-1)        /* not enough memory */
#define E_OPTION    (-2)        /* unknown option */
#define E_ARGCNT    (-3)        /* wrong number of arguments */
#define E_SIZE      (-4)        /* illegal chessboard size */
#define E_POPSIZE   (-5)        /* illegal population size */
#define E_GENCNT    (-6)        /* illegal number of generations */
#define E_PROB      (-7)        /* illegal mutation probability */
#define E_FRAC      (-8)        /* illegal population fraction */
#define E_TMSIZE    (-9)        /* illegal tournament size */
#define E_UNKNOWN  (-10)        /* unknown error */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {               /* --- an individual --- */
  int fitness;                 /* fitness (number of collisions) */
  int n;                       /* number of genes (number of rows) */
  int genes[1];                /* genes (queen positions in rows) */
} IND;                         /* (individual) */

typedef struct {               /* --- a population --- */
  int size;                    /* number of individuals */
  IND **inds;                  /* vector of individuals */
  IND **buf;                   /* buffer for individuals */
  IND *best;                   /* best individual */
} POP;                         /* (population) */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const char *errmsgs[] = {
  /* E_NONE      0 */  "no error\n",
  /* E_NOMEM    -1 */  "not enough memory\n",
  /* E_OPTION   -2 */  "unknown option -%c\n",
  /* E_ARGCNT   -3 */  "wrong number of arguments\n",
  /* E_SIZE     -4 */  "illegal chessboard size %d\n",
  /* E_POPSIZE  -5 */  "illegal population size %d\n",
  /* E_GENCNT   -6 */  "illegal number of generations %d\n",
  /* E_PROB     -7 */  "illegal mutation probability %g\n",
  /* E_FRAC     -8 */  "illegal population fraction %g\n",
  /* E_TMSIZE   -9 */  "illegal tournament size %d\n",
  /* E_UNKNOWN -10 */  "unknown error\n" };

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
const char *prgname = NULL;     /* program name for error messages */

/*----------------------------------------------------------------------
  Random Number Function
----------------------------------------------------------------------*/

#define drand()  (rand()*(1.0/(RAND_MAX +1.0)))

/*----------------------------------------------------------------------
  Operations on Individuals
----------------------------------------------------------------------*/

#define ind_delete(i) free(i)  /* --- delete an individual */

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

IND* ind_create (int n)
{                              /* --- create an individual */
  IND *ind;                    /* created individual */

  assert(n >= 0);              /* check the function argument */
  ind = (IND*)malloc(sizeof(IND) +(n-1)*sizeof(int));
  if (!ind) return NULL;       /* allocate a memory block and */
  ind->n = n;                  /* note the number of genes */
  return ind;                  /* return the created individual */
}  /* ind_create() */

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

void ind_init (IND *ind)
{                              /* --- initialize an individual */
  int i;                       /* loop variable */

  assert(ind);                 /* check the function argument */
  for (i = ind->n; --i >= 0; ) /* initialize the genes randomly */
    ind->genes[i] = (int)(ind->n *drand());
  ind->fitness = 1;            /* fitness is not known yet */
}  /* ind_init() */

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

int ind_eval (IND *ind)
{                              /* --- evaluate an individual */
  int i, k;                    /* loop variables */
  int d;                       /* horizontal distance between queens */
  int n;                       /* number of collisions */

  assert(ind);                 /* check the function argument */
  if (ind->fitness <= 0)       /* if the fitness is already known, */
    return ind->fitness;       /* simply return it */
  for (n = 0, i = ind->n; --i > 0; ) {
    for (k = i; --k >= 0; ) {  /* traverse all pairs of queens */
      d = abs(ind->genes[i] -ind->genes[k]);
      if ((d == 0) || (d == i-k)) n++;
    }                          /* count the number of pairs of queens */
  }                            /* in the same column or diagonal */
  return ind->fitness = -n;    /* return the number of collisions */
}  /* ind_eval() */

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

IND* ind_copy (IND *dst, const IND *src)
{                              /* --- copy an individual */
  int i;                       /* loop variable */

  assert(dst && src            /* check the function arguments */
     && (dst->n == src->n));
  for (i = dst->n; --i >= 0; ) /* copy the genes */
    dst->genes[i] = src->genes[i];
  dst->fitness = src->fitness; /* copy the fitness */
  return dst;                  /* return the destination indivdual */
}  /* ind_copy() */

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

void ind_cross (IND *ind1, IND *ind2)
{                              /* --- crossover of two chromosomes */
  int i;                       /* loop variable */
  int k;                       /* gene index of crossover point */
  int t;                       /* exchange buffer */

  assert(ind1 && ind2          /* check the function arguments */
     && (ind1->n == ind2->n));
  k = (int)(drand() *(ind1->n-1)) +1; /* choose a crossover point */
  if (k > (ind1->n >> 1)) { i = ind1->n; }
  else                    { i = k; k = 0; }
  while (--i >= k) {           /* traverse smaller section */
    t              = ind1->genes[i];
    ind1->genes[i] = ind2->genes[i];
    ind2->genes[i] = t;        /* exchange genes */
  }                            /* of the chromosomes */
  ind1->fitness = 1;           /* invalidate the fitness */
  ind2->fitness = 1;           /* of the changed individuals */
}  /* ind_cross() */

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

void ind_mutate (IND *ind, double prob)
{                              /* --- mutate an individual */
  assert(ind                   /* check the function arguments */
      && (prob >= 0) && (prob <= 1));
  if (drand() >= prob) return; /* det. whether to change individual */
  do ind->genes[(int)(ind->n *drand())] = (int)(ind->n *drand());
  while (drand() < prob);      /* randomly change random genes */
  ind->fitness = 1;            /* fitness is no longer known */
}  /* ind_mutate() */

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

void ind_show (const IND *ind)
{                              /* --- show an individual */
  int i, k;                    /* loop variables */

  assert(ind);                 /* check the function argument */
  for (i = ind->n; --i >= 0; ) {
    for (k = 0; k < ind->genes[i]; k++) printf(" .");
    printf(" Q");
    while (++k < ind->n) printf(" .");
    printf("\n");              /* print rows of the chessboard */
  }                            /* (empty fields: '.', Queens: 'Q') */
}  /* ind_show() */

/*----------------------------------------------------------------------
  Operations on Populations
----------------------------------------------------------------------*/

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

  assert(pop);                 /* check the function argument */
  for (i = 2*pop->size; --i >= 0; )
    if (pop->inds[i]) free(pop->inds[i]);
  free(pop->inds);             /* delete all individuals, */
  free(pop);                   /* the vectors, and */
}  /* pop_delete() */          /* the base structure */

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

POP* pop_create (int size, int n)
{                              /* --- create a population */
  POP *pop;                    /* created population */

  assert((size > 0) && (n > 0));  /* check the function arguments */
  pop = (POP*)calloc(1, sizeof(POP));
  if (!pop) return NULL;       /* allocate the base structure */
  pop->inds = malloc(2 *size *sizeof(IND*));
  if (!pop->inds) { free(pop); return NULL; }