/* $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 pthread_t *threads; pthread_mutex_t mutexsum; pthread_attr_t attr; struct intargs { int mutationrate; int population; }; #if 0 const char defaim[] = "METHINKS IT IS LIKE A WEASEL"; const char alphabet[] = " ABCDEEFGHIJKLMNOPQRSTUVWXYZ"; #else const char defaim[] = "THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG'S BACK 1234567890 TIMES."; const char alphabet[] = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEEFGHIJKLMNOPQRSTUVWXYZ[\\]^_abcdefghijklmnopqrstuvwxyz{|}~"; #endif const char *aim; SLIST_HEAD(creatures, creature) generation; struct creature { char *genom; int length; float fitness; int locked; SLIST_ENTRY(creature) link; } *cp; char rndchar() { return alphabet[random() % (sizeof(alphabet) - 1)]; } 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 number) { int i; SLIST_INIT(&generation); while (number-- > 0) { cp = malloc(sizeof(struct 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); cp->locked = 0; SLIST_INSERT_HEAD(&generation, cp, link); } } void printcreature(struct creature *c) { printw("%1.3f\t%s\n", c->fitness, c->genom); } void printpopulation(int maximal) { printw("%1.3f\t%s\n\n", 1.0, aim); SLIST_FOREACH(cp, &generation, link) { printcreature(cp); if (maximal-- <= 0) break; } printw("\n"); } struct creature * pickrandom(int population) { int n; for (;;) { n = random() % population; SLIST_FOREACH(cp, &generation, link) if (n-- <= 0) break; if (cp->locked) continue; pthread_mutex_lock(&mutexsum); assert(!cp->locked); cp->locked = 1; pthread_mutex_unlock(&mutexsum); break; } return cp; } int cmp(const void *u, const void *v) { struct creature * const *a = u; struct creature * const *b = v; if ((*a)->fitness < (*b)->fitness) return 1; if ((*a)->fitness > (*b)->fitness) return -1; return 0; } void intercourse(int population, int mutationsrate) { struct creature *c[3]; int i; for (i = 0; i < 3; i++) { c[i] = pickrandom(population); assert(c[i]); } qsort(c, 3, sizeof(struct creature *), cmp); for (i = 0; i < c[2]->length; i++) { if (random() % mutationsrate) 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); c[0]->locked = 0; c[1]->locked = 0; c[2]->locked = 0; } int success() { struct creature *best = NULL; float fittest = 0; /* find best */ SLIST_FOREACH(cp, &generation, link) if (cp->fitness > fittest) { fittest = cp->fitness; best = cp; } assert(best); printcreature(best); return best->fitness == 1.0; } void * ptintercourse(void *args) { struct intargs *ia = args; intercourse(ia->population, ia->mutationrate); pthread_exit(NULL); } void usage(void) { extern char *__progname; fprintf(stderr, "usage: %s [-m ] [-p ] [-t ] [target string]\n", __progname); exit(1); } int main(int argc, char **argv) { struct intargs args; extern int LINES; int population = 1000; int mutationrate = 100; /* 1/n */ int nthreads = population / 10; int i, c, t; while ((c = getopt(argc, argv, "m:p:t:")) != -1) switch (c) { case 'm': i = atoi(optarg); if (i > 0) mutationrate = i; else usage(); break; case 'p': i = atoi(optarg); if (i >= 3) population = i; else usage(); break; case 't': i = atoi(optarg); if (i >= 1) nthreads = i; else usage(); break; default: usage(); /* NOTREACHED */ } argc -= optind; argv += optind; aim = argc ? strdup(*argv) : defaim; initscr(); srandom(time(NULL)); initpopulation(strlen(aim), population); args.population = population; args.mutationrate = mutationrate; threads = calloc(nthreads, sizeof(pthread_t)); assert(threads); pthread_mutex_init(&mutexsum, NULL); pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED); for (i = 0;; i++) { move(0, 0); for (t = 0; t < nthreads; t++) pthread_create(&threads[t], &attr, ptintercourse, (void *)&args); printpopulation(LINES - 8); if (success()) break; refresh(); } pthread_attr_destroy(&attr); pthread_mutex_destroy(&mutexsum); free(threads); printw("\nhalted after %d generations of %d population (%d births)\n", nthreads * i / population, population, nthreads * i); refresh(); endwin(); return 0; }