/* $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 #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; TAILQ_HEAD(creatures, creature) generation; struct creature { char *genom; int length; float fitness; TAILQ_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); TAILQ_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); TAILQ_FOREACH(cp, &generation, link) { printcreature(cp); if (maximal-- <= 0) break; } printw("\n"); } struct creature * pickrandom(int population) { int n = arc4random() % population; cp = TAILQ_FIRST(&generation); while (n-- && cp) cp = TAILQ_NEXT(cp, link); 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); } int success() { struct creature *best = NULL; float fittest = 0; /* find best */ TAILQ_FOREACH(cp, &generation, link) if (cp->fitness > fittest) { fittest = cp->fitness; best = cp; } assert(best); printcreature(best); printw("\n"); return !strcmp(best->genom, aim); } int main(int argc, char **argv) { extern int LINES; int population = 1000; int mutationrate = 100; /* 1/n */ int i, c; 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); for (i = 0;; i++) { move(0, 0); intercourse(population, mutationrate); printpopulation(LINES - 8); if (success()) break; refresh(); } printw("halted after %d generations\n", i / population); refresh(); endwin(); return 0; }