/* $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 #define NUM_THREADS 10 pthread_t threads[NUM_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[arc4random() % (sizeof(alphabet) - 1)]; } float calculatefitness(char *genom, int length) { int i, good; good = 0; for (i = 0; i 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 = arc4random() % population; cp = SLIST_FIRST(&generation); while (n-- > 0 && cp) cp = SLIST_NEXT(cp, link); if (cp->locked) cp = pickrandom(population); pthread_mutex_lock(&mutexsum); cp->locked = 1; pthread_mutex_unlock(&mutexsum); return cp; } int cmp(const void *u, const void *v) { struct creature * const *a = u; struct creature * const *b = v; return ((*a)->fitness <= (*b)->fitness ? 1 : -1); } 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 (arc4random() % mutationsrate == 0) c[2]->genom[i] = rndchar(); else c[2]->genom[i] = c[arc4random() % 2]->genom[i]; } 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); } int main(int argc, char **argv) { struct intargs args; extern int LINES; int population = 1000; int mutationrate = 100; /* 1/n */ int i, c, t; while ((c = getopt(argc, argv, "m:p:")) != -1) switch (c) { case 'm': mutationrate = atoi(optarg); break; case 'p': population = atoi(optarg); break; default: break; } argc -= optind; argv += optind; aim = argc ? strdup(*argv) : defaim; initscr(); setterm("vt220"); initpopulation(strlen(aim), population); args.population = population; args.mutationrate = mutationrate; 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 < NUM_THREADS; t++) pthread_create(&threads[t], &attr, ptintercourse, (void *)&args); printpopulation(LINES - 8); if (success()) break; refresh(); } pthread_attr_destroy(&attr); pthread_mutex_destroy(&mutexsum); printw("\nhalted after %d generations\n", NUM_THREADS * i / population); refresh(); endwin(); return 0; }