/* $Id$ */ /* * Copyright (c) 2009 Dimitri Sokolyuk * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include #include #include #include #include #include #include #include #include #include #include pthread_mutex_t mutexsum; pthread_mutex_t gen; int population = 1000; int mutationrate = 100; /* 1/n */ int dieflag = 0; int ngeneration = 0; float average; #if 0 char defaim[] = "METHINKS IT IS LIKE A WEASEL"; char defalpha[] = " ABCDEEFGHIJKLMNOPQRSTUVWXYZ"; #else char defaim[] = "THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG'S BACK 1234567890 TIMES."; char defalpha[] = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEEFGHIJKLMNOPQRSTUVWXYZ[\\]^_abcdefghijklmnopqrstuvwxyz{|}~"; #endif char *alphabet; int alphalen; char *aim; typedef struct creature Creature; struct creature { char *genom; int length; float fitness; int locked; } *cp, **generation; #if __openbsd__ int ncpu(void) { int mib[2], n; size_t len; mib[0] = CTL_HW; mib[1] = HW_NCPU; len = sizeof(n); if (sysctl(mib, 2, &n, &len, NULL, 0) == -1) return 1; return n; } #endif static inline char rndchar() { return alphabet[random() % alphalen]; } float calculatefitness(char *genom, int length) { int i, good; good = 0; for (i = 0; i < length; i++) if (aim[i] == genom[i]) good++; return good / (float)length; } void initpopulation(int length) { int i, n; generation = calloc(population, sizeof(Creature *)); assert(generation); for (n = 0; n < population; n++) { cp = malloc(sizeof(Creature)); assert(cp); cp->genom = malloc(length + 1); assert(cp->genom); for (i = 0; i < length; i++) cp->genom[i] = rndchar(); cp->genom[i] = '\0'; cp->length = length; cp->fitness = calculatefitness(cp->genom, cp->length); generation[n] = cp; cp->locked = 0; } } void printcreature(Creature *c) { int attr = A_NORMAL; if (c->locked) attr |= A_REVERSE; if (c->fitness > average) attr |= A_BOLD; attron(attr); printw("%1.3f\t%s\n", c->fitness, c->genom); attroff(attr); } void printpopulation(Creature *best) { extern int LINES; int n; move(0, 0); printw("%1.3f\t%s\n\n", average, aim); for (n = 0; n < population; n++) { printcreature(generation[n]); if (n >= LINES - 8) break; } printw("\n"); if (best) printcreature(best); clrtobot(); refresh(); } Creature * pickrandom() { do cp = generation[random() % population]; while (cp->locked); cp->locked = 1; return cp; } int cmp(const void *u, const void *v) { Creature * const *a = u; Creature * const *b = v; if ((*a)->fitness < (*b)->fitness) return 1; if ((*a)->fitness > (*b)->fitness) return -1; return 0; } void * intercourse() { Creature *c[3]; int i; while (!dieflag) { pthread_mutex_lock(&mutexsum); for (i = 0; i < 3; i++) c[i] = pickrandom(); pthread_mutex_unlock(&mutexsum); qsort(c, 3, sizeof(Creature *), cmp); for (i = 0; i < c[2]->length; i++) { if (random() % mutationrate) c[2]->genom[i] = c[random() % 2]->genom[i]; else c[2]->genom[i] = rndchar(); } c[2]->genom[i] = '\0'; c[2]->fitness = calculatefitness(c[2]->genom, c[2]->length); /* recalculate fitness of parents */ c[0]->fitness = calculatefitness(c[0]->genom, c[0]->length); c[1]->fitness = calculatefitness(c[1]->genom, c[1]->length); c[0]->locked = 0; c[1]->locked = 0; c[2]->locked = 0; pthread_mutex_lock(&gen); ++ngeneration; pthread_mutex_unlock(&gen); usleep(100); // REMOVE to speed up } pthread_exit(NULL); } int success(Creature **best) { float fittest = 0; int n; average = 0; /* find best */ for (n = 0; n < population; n++) { cp = generation[n]; if (cp->fitness > fittest) { fittest = cp->fitness; *best = cp; } average += cp->fitness; } average /= population; return (*best)->fitness == 1.0; } void usage(void) { extern char *__progname; fprintf(stderr, "usage: %s [-ns] [-a ] [-m ] [-p ] target string]\n", __progname); exit(1); } int main(int argc, char **argv) { Creature *best; pthread_t *threads; int i = 0, c, n, nthreads; int display = 1; alphabet = defalpha; #if __openbsd__ nthreads = ncpu(); #else nthreads = 1; #endif while ((c = getopt(argc, argv, "a:m:np:sS:t:")) != -1) switch (c) { case 'a': alphabet = strdup(optarg); break; case 'm': i = atoi(optarg); if (i <= 0) usage(); mutationrate = i; break; case 'n': display = 0; break; case 'p': i = atoi(optarg); if (i < 3) usage(); population = i; break; case 't': i = atoi(optarg); if (i <= 0) usage(); nthreads = i; break; default: usage(); /* NOTREACHED */ } argc -= optind; argv += optind; aim = argc ? strdup(*argv) : defaim; alphalen = strlen(alphabet); initscr(); srandom(time(NULL)); initpopulation(strlen(aim)); pthread_mutex_init(&mutexsum, NULL); threads = calloc(nthreads, sizeof(pthread_t)); assert(threads); for (n = 0; n < nthreads; n++) { pthread_create(&threads[n], NULL, intercourse, NULL); pthread_detach(threads[n]); } best = NULL; do if (display) printpopulation(best); while (!(dieflag = success(&best))); endwin(); fprintf(stderr, "halted after %d generations with population of %d\n", ngeneration, population); pthread_mutex_destroy(&mutexsum); pthread_exit(NULL); }