/* $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 /* const char aim[] = "METHINKS IT IS LIKE A WEASEL"; */ 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 */ 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)]; } void initpopulation(int length, int number) { int i; TAILQ_INIT(&generation); while (number--) { 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; TAILQ_INSERT_HEAD(&generation, cp, link); } } void sortfitness() { 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 */ } } } void calculatefitness() { int i, good; 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; } } void intercourse(int probability) { 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); } /* 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); } } void printpopulation() { move(0, 0); printw("%1.3f\t%s\n\n", 1.0, aim); TAILQ_FOREACH(cp, &generation, link) printw("%1.3f\t%s\n", cp->fitness, cp->genom); refresh(); } int main() { int i; struct creature *first; initscr(); setterm("vt220"); initpopulation(strlen(aim), LINES - 5); for (i = 0;; i++) { intercourse(mutationrate); calculatefitness(); sortfitness(); first = TAILQ_FIRST(&generation); printpopulation(); if (strcmp(first->genom, aim) == 0) break; } printw("\nhalted after %d generations\n", i); refresh(); endwin(); return 0; }