From ab1fe89bc1730777d9b233a6116dcd2a1a01c27d Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sat, 3 Oct 2009 03:59:51 +0000 Subject: change algorithm --- Makefile | 1 + weasel.c | 187 +++++++++++++++++++++++++++++++++++++++------------------------ 2 files changed, 116 insertions(+), 72 deletions(-) diff --git a/Makefile b/Makefile index c00627d..3ed81cd 100644 --- a/Makefile +++ b/Makefile @@ -2,6 +2,7 @@ PROG= weasel NOMAN= +DEBUG+= -Wall -ggdb LDADD+= -lcurses . include diff --git a/weasel.c b/weasel.c index ca70e32..2a3a196 100644 --- a/weasel.c +++ b/weasel.c @@ -22,12 +22,15 @@ #include #include #include +#include -/* const char aim[] = "METHINKS IT IS LIKE A WEASEL"; */ +#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{|}~"; -extern int LINES; -int mutationrate = 100; /* 1/n */ +#endif TAILQ_HEAD(creatures, creature) generation; struct creature { @@ -43,6 +46,19 @@ 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); - cp->length = length; for (i = 0; i < length; i++) cp->genom[i] = rndchar(); cp->genom[i] = '\0'; - cp->fitness = 0.0; + cp->length = length; + cp->fitness = calculatefitness(cp->genom, cp->length); TAILQ_INSERT_HEAD(&generation, cp, link); } } void -sortfitness() +printcreature(struct creature *c) { - struct creature *next; - - for (cp = TAILQ_FIRST(&generation); cp; cp = next) { - next = TAILQ_NEXT(cp, link); - if (next && next->fitness > cp->fitness) { - TAILQ_REMOVE(&generation, next, link); - TAILQ_INSERT_BEFORE(cp, next, link); - next = TAILQ_NEXT(cp, link); - sortfitness(); /* FIXME */ - } - } + printw("%1.3f\t%s\n", c->fitness, c->genom); } void -calculatefitness() +printpopulation(int maximal) { - int i, good; - + printw("%1.3f\t%s\n\n", 1.0, aim); TAILQ_FOREACH(cp, &generation, link) { - good = 0; - for (i = 0; i < cp->length; i++) - if (aim[i] == cp->genom[i]) - good++; - cp->fitness = good / (float)cp->length; + 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 probability) +intercourse(int population, int mutationsrate) { + struct creature *c[3], *child; int i, length; - struct creature *parent[2], *child, *next; - parent[0] = TAILQ_FIRST(&generation); - parent[1] = TAILQ_NEXT(parent[0], link); - length = strlen(parent[0]->genom); - - /* produce children */ - TAILQ_FOREACH(cp, &generation, link) { - child = malloc(sizeof(struct creature)); - assert(child); - child->genom = malloc(length + 1); - assert(child->genom); - child->length = length; - - /* recombine and mutate */ - for (i = 0; i < length; i++) { - if (arc4random() % probability == 0) { - child->genom[i] = rndchar(); - } else { - child->genom[i] = parent[arc4random() % 2]->genom[i]; - } - } - child->genom[i] = '\0'; - TAILQ_INSERT_HEAD(&generation, child, link); + for (i = 0; i < 3; i++) { + c[i] = pickrandom(population); + assert(c[i]); } - - /* remove old generation */ - for (cp = parent[0]; cp; cp = next) { - next = TAILQ_NEXT(cp, link); - TAILQ_REMOVE(&generation, cp, link); - free(cp->genom); - free(cp); + 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]); } -void -printpopulation() +int +success() { - move(0, 0); - printw("%1.3f\t%s\n\n", 1.0, aim); + struct creature *best = NULL; + float fittest = 0; + + /* find best */ TAILQ_FOREACH(cp, &generation, link) - printw("%1.3f\t%s\n", cp->fitness, cp->genom); - refresh(); + 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; - struct creature *first; initscr(); setterm("vt220"); - initpopulation(strlen(aim), LINES - 5); + initpopulation(strlen(aim), population); for (i = 0;; i++) { - intercourse(mutationrate); - calculatefitness(); - sortfitness(); - first = TAILQ_FIRST(&generation); - printpopulation(); - if (strcmp(first->genom, aim) == 0) + move(0, 0); + intercourse(population, mutationrate); + printpopulation(LINES - 8); + if (success()) break; + refresh(); } - printw("\nhalted after %d generations\n", i); + printw("halted after %d generations\n", i / population); refresh(); endwin(); -- cgit v1.2.3