/*---------------------------------------------------------------------- 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 #include #include #include #include #include /*---------------------------------------------------------------------- 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; } 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() */