aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2009-10-03 03:59:51 +0000
committerDimitri Sokolyuk <demon@dim13.org>2009-10-03 03:59:51 +0000
commitab1fe89bc1730777d9b233a6116dcd2a1a01c27d (patch)
tree3aa1f842e6c9fcb60e560a0f5372d0dbf81ddcd5
parent364a4bc48dc8680b1e8b947575a81c92256b6f6d (diff)
change algorithm
-rw-r--r--Makefile1
-rw-r--r--weasel.c187
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 <bsd.prog.mk>
diff --git a/weasel.c b/weasel.c
index ca70e32..2a3a196 100644
--- a/weasel.c
+++ b/weasel.c
@@ -22,12 +22,15 @@
#include <stdlib.h>
#include <string.h>
#include <term.h>
+#include <unistd.h>
-/* 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 <length; i++)
+ if (aim[i] == genom[i])
+ good++;
+
+ return good / (float)length;
+}
+
void
initpopulation(int length, int number)
{
@@ -50,120 +66,147 @@ initpopulation(int length, int number)
TAILQ_INIT(&generation);
- while (number--) {
+ while (number-- > 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();