/* $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 aim[] = "METHINKS IT IS LIKE A WEASEL"; const char alphabet[] = " ABCDEEFGHIJKLMNOPQRSTUVWXYZ"; #else const char aim[] = "THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG'S BACK 1234567890 TIMES."; const char alphabet[] = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEEFGHIJKLMNOPQRSTUVWXYZ[\\]^_abcdefghijklmnopqrstuvwxyz{|}~"; #endif 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], *child; int i, length; for (i = 0; i < 3; i++) { c[i] = pickrandom(population); assert(c[i]); } qsort(c, 3, sizeof(struct creature *), cmp); length = c[0]->length; child = malloc(sizeof(struct creature)); assert(child); child->genom = malloc(length); assert(child->genom); for (i = 0; i < length; i++) { if (arc4random() % mutationsrate == 0) child->genom[i] = rndchar(); else child->genom[i] = c[arc4random() % 2]->genom[i]; } child->genom[i] = '\0'; child->length = length; child->fitness = calculatefitness(child->genom, child->length); #if 0 printw("\n"); printcreature(c[0]); printcreature(c[1]); printcreature(c[2]); printw("\n"); printcreature(child); printw("\n"); refresh(); #endif /* insert child & kill weakest */ TAILQ_INSERT_TAIL(&generation, child, link); TAILQ_REMOVE(&generation, c[2], link); free(c[2]->genom); free(c[2]); } 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() { extern int LINES; int population = 1000; int mutationrate = 100; /* 1/n */ int i; 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; }