/* $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_attr_t attr; int population = 1000; int mutationrate = 100; /* 1/n */ 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; struct creature { char *genom; int length; float fitness; int locked; } *cp, **generation; 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; } 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(struct creature *)); assert(generation); for (n = 0; n < population; n++) { 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); generation[n] = cp; cp->locked = 0; } } void printcreature(struct 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(struct 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"); printcreature(best); clrtobot(); refresh(); } struct creature * pickrandom() { int hasone = 0; while (!hasone) { cp = generation[random() % population]; if (!cp->locked) { cp->locked = 1; hasone = 1; } } 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() { struct creature *c[3]; int i; pthread_mutex_lock(&mutexsum); for (i = 0; i < 3; i++) { c[i] = pickrandom(population); assert(c[i]); } pthread_mutex_unlock(&mutexsum); qsort(c, 3, sizeof(struct 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); c[0]->locked = 0; c[1]->locked = 0; c[2]->locked = 0; pthread_exit(NULL); } int success(struct 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); } void switchcase(char *s, int *uflag) { size_t len; int (*f)(int); if (*uflag) { f = tolower; *uflag = 0; } else { f = toupper; *uflag = 1; } for (len = strlen(s); len--; s++) *s = f(*s); } int main(int argc, char **argv) { struct creature *best; pthread_t *threads; int i, c, n, nthreads; int display = 1; int dontstop = 0; int uflag = 1; float threshold = 0.90; int dieflag = 0; alphabet = defalpha; nthreads = ncpu(); 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 's': dontstop = 1; break; case 'S': dontstop = 1; threshold = atof(optarg); 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); threads = calloc(nthreads, sizeof(pthread_t)); assert(threads); initscr(); srandom(time(NULL)); initpopulation(strlen(aim)); pthread_mutex_init(&mutexsum, NULL); pthread_attr_init(&attr); // pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED); for (i = 0; !dieflag || dontstop; i++) { dieflag = success(&best); if (dontstop && average > threshold) switchcase(aim, &uflag); for (n = 0; n < nthreads; n++) pthread_create(&threads[n], &attr, intercourse, NULL); for (n = 0; n < nthreads; n++) pthread_join(threads[n], NULL); if (display) printpopulation(best); } pthread_attr_destroy(&attr); pthread_mutex_destroy(&mutexsum); if (display) { printpopulation(best); printw("\nhalted after %d generations with population of %d\n", nthreads * i / population, population); refresh(); } endwin(); return 0; }