ant.c

   1 /*
   2  *  A simple ant-ology of genetic algorithms.
   3  *
   4  *  mj@ucw.cz, Discord YOLD 3166
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 #define NSTATES 16
  12 #define NMARKS 4
  13 #define SENSE_FOOD
  14 #ifdef SENSE_FOOD
  15 #define NTYPES 3
  16 #else
  17 #define NTYPES 8
  18 #endif
  19 #define NWAYS 1
  20 #define NSLOTS (NMARKS*NTYPES*NWAYS)
  21 #define SLOT(m,t,w) (((m)*NTYPES+(t))*NWAYS+(w))
  22
  23 struct slot {
  24   unsigned char op, mark, state;
  25 };
  26
  27 #define OP_NOP 0
  28 #define OP_LEFT 1
  29 #define OP_RIGHT 2
  30 #define OP_UTB 3
  31 #define OP_MAX 4
  32
  33 struct state {
  34   struct slot slots[NSLOTS];
  35 };
  36
  37 struct automaton {
  38   struct state states[NSTATES];
  39   int fitness;
  40 };
  41
  42 #if 0
  43 #define XSIZE 10
  44 #define YSIZE 10
  45 #define XSTART 1
  46 #define YSTART 1
  47
  48 char *maze =
  49 "##########"
  50 "#.#$#....#"
  51 "#.#.#$$$.#"
  52 "#.#.#$$$.#"
  53 "#.#.#$$$.#"
  54 "#.#.####.#"
  55 "#.#...$..#"
  56 "#.##.#####"
  57 "#.$......#"
  58 "##########"
  59 ;
  60 #else
  61 #define XSIZE 34
  62 #define YSIZE 34
  63 #define XSTART 1
  64 #define YSTART 1
  65 char *maze =
  66 "##################################"
  67 "#.$$$............................#"
  68 "#...$............................#"
  69 "#...$.....................$$$....#"
  70 "#...$....................$....$..#"
  71 "#...$....................$....$..#"
  72 "#...$$$$.$$$$$........$$.........#"
  73 "#............$................$..#"
  74 "#............$.......$...........#"
  75 "#............$.......$...........#"
  76 "#............$.......$........$..#"
  77 "#....................$...........#"
  78 "#............$...................#"
  79 "#............$................$..#"
  80 "#............$.......$...........#"
  81 "#............$.......$.....$$$...#"
  82 "#.................$.....$........#"
  83 "#................................#"
  84 "#............$...................#"
  85 "#............$...$.......$.......#"
  86 "#............$...$..........$....#"
  87 "#............$...$...............#"
  88 "#............$...$...............#"
  89 "#............$.............$.....#"
  90 "#............$..........$........#"
  91 "#...$$..$$$$$....$...............#"
  92 "#.$..............$...............#"
  93 "#.$..............$...............#"
  94 "#.$......$$$$$$$.................#"
  95 "#.$.....$........................#"
  96 "#.......$........................#"
  97 "#..$$$$..........................#"
  98 "#................................#"
  99 "##################################"
 100 ;
 101
 102 #endif
 103
 104 #define MI(a,b) ((b)*XSIZE+(a))
 105 char mazec[XSIZE*YSIZE];
 106 char *types = "$#.012345";
 107
 108 #define POPSIZE 100
 109
 110 struct automaton autpool[POPSIZE];
 111 struct automaton *pop[POPSIZE];
 112
 113 void
 114 maze_init(void)
 115 {
 116   int i;
 117
 118   puts("Initializing maze");
 119   for(i=0; i<XSIZE*YSIZE; i++)
 120     {
 121       char *z = strchr(types, maze[i]);
 122       if (!z) { fprintf(stderr, "Maze bug\n"); exit(1); }
 123       mazec[i] = z - types;
 124     }
 125 }
 126
 127 void
 128 aut_gen_random(struct automaton *aut)
 129 {
 130   int i, j;
 131
 132   for(i=0; i<NSTATES; i++)
 133     for(j=0; j<NSLOTS; j++)
 134       {
 135         struct slot *s = &aut->states[i].slots[j];
 136         s->op = random() % OP_MAX;
 137         s->state = random() % NSTATES;
 138         s->mark = random() % NMARKS;
 139       }
 140 }
 141
 142 void
 143 show(char *z)
 144 {
 145   int i, j;
 146   int x = 0;
 147   for(i=0; i<YSIZE; i++)
 148     {
 149       for(j=0; j<XSIZE; j++)
 150         putchar(types[(int)z[x++]]);
 151       putchar('\n');
 152     }
 153 }
 154
 155 int
 156 fitness(struct automaton *aut, int flag)
 157 {
 158   char tmp[XSIZE*YSIZE];
 159   int state = 0;
 160   int x = XSTART;
 161   int y = YSTART;
 162   int d = 0;
 163   static int dx[4] = { 0, -1, 0, 1 };
 164   static int dy[4] = { 1, 0, -1, 0 };
 165   int energy = 50;
 166   int bonus = 1;
 167
 168   memcpy(tmp, mazec, XSIZE*YSIZE);
 169   while (energy > 0)
 170     {
 171       int way = random() % NWAYS;
 172       int here = tmp[MI(x,y)];
 173       int mark = (here < 3) ? 0 : here-3;
 174       int ahead = tmp[MI(x+dx[d],y+dy[d])];
 175       int right = tmp[MI(x+dx[(d+1)%4],y+dy[(d+1)%4])];
 176       int left = tmp[MI(x+dx[(d+3)%4],y+dy[(d+3)%4])];
 177 #ifdef SENSE_FOOD
 178       int view = (ahead >= 2) ? 2 : ahead;
 179 #else
 180       int view = ((ahead==1)?4:0) | ((left==1)?2:0) | ((right==1)?1:0);
 181 #endif
 182       struct slot *s = &aut->states[state].slots[SLOT(mark, view, way)];
 183       tmp[MI(x,y)] = s->mark + 3;
 184       bonus++;
 185       energy--;
 186       switch (s->op)
 187         {
 188         case OP_NOP:    break;
 189         case OP_LEFT:   d = (d+3) % 4; break;
 190         case OP_RIGHT:  d = (d+1) % 4; break;
 191         case OP_UTB:    d = (d+2) % 4; break;
 192         }
 193       ahead = tmp[MI(x+dx[d],y+dy[d])];
 194       switch (ahead)
 195         {
 196         case 0:         energy+=10; bonus+=100; /* food */
 197         default:        x+=dx[d]; y+=dy[d]; break;  /* empty */
 198         case 1:         energy-=5; break; /* wall */
 199         }
 200       state = s->state;
 201     }
 202   if (flag)
 203     show(tmp);
 204   return bonus;
 205 }
 206
 207 void
 208 pop_init(void)
 209 {
 210   int i;
 211
 212   for(i=0; i<POPSIZE; i++)
 213     {
 214       aut_gen_random(&autpool[i]);
 215       pop[i] = &autpool[i];
 216     }
 217 }
 218
 219 int
 220 fcmp(struct automaton **a, struct automaton **b)
 221 {
 222   int fa = (*a)->fitness;
 223   int fb = (*b)->fitness;
 224
 225   return (fa < fb) ? -1 : (fa > fb) ? 1 : 0;
 226 }
 227
 228 void
 229 mutate(struct automaton *a)
 230 {
 231   int state, slot, i;
 232   struct slot *s;
 233
 234   for(i=0; i<40; i++)
 235     {
 236       state = random() % NSTATES;
 237       slot = random() % NSLOTS;
 238       s = &a->states[state].slots[slot];
 239       s->op = random() % OP_MAX;
 240       s->state = random() % NSTATES;
 241       s->mark = random() % NMARKS;
 242     }
 243 }
 244
 245 void
 246 crossover(struct automaton *a, struct automaton *b)
 247 {
 248   int marks[NMARKS], types[NTYPES], ways[NWAYS], slots[NSLOTS];
 249   int i, j, k;
 250
 251   if (a == b)
 252     return;
 253   for(i=0; i<NMARKS; i++)
 254     marks[i] = random() % 2;
 255   for(i=0; i<NTYPES; i++)
 256     types[i] = random() % 2;
 257   for(i=0; i<NWAYS; i++)
 258     ways[i] = random() % 2;
 259   for(i=0; i<NMARKS; i++)
 260     for(j=0; j<NTYPES; j++)
 261       for(k=0; k<NWAYS; k++)
 262         slots[SLOT(i,j,k)] = marks[i] && types[j] && ways[k];
 263   for(i=0; i<NSTATES; i++)
 264     if (random() % 2)
 265       for(j=0; j<NSLOTS; j++)
 266         if (slots[j])
 267           {
 268             struct slot z;
 269             z = a->states[i].slots[j];
 270             a->states[i].slots[j] = b->states[i].slots[j];
 271             b->states[i].slots[j] = z;
 272           }
 273 }
 274
 275 struct automaton *
 276 rgenom(struct automaton **x, int n, int t)
 277 {
 278   int z = random() % t;
 279   int k = 0;
 280   int i = 0;
 281
 282   while (k <= z && n--)
 283     k += x[i++]->fitness;
 284   return x[i-1];
 285 }
 286
 287 void
 288 step(void)
 289 {
 290   int i, total, death;
 291
 292   for(i=0; i<POPSIZE; i++)
 293     {
 294       struct automaton *a = pop[i];
 295       a->fitness = (fitness(a,0) + fitness(a,0) + fitness(a,0)) / 3;
 296     }
 297   qsort(pop, POPSIZE, sizeof(struct automaton *), (int(*)(const void *,const void *)) fcmp);
 298   for(i=0; i<POPSIZE; i++)
 299     {
 300       struct automaton *a = pop[i];
 301       //      printf("%d: %d\n", i, a->fitness);
 302       total += a->fitness;
 303     }
 304   fitness(pop[POPSIZE-1], 1);
 305   printf("best=%d worst=%d\n", pop[POPSIZE-1]->fitness, pop[0]->fitness);
 306
 307   total = 0;
 308   death = POPSIZE/2;
 309   for(i=death; i<POPSIZE; i++)
 310     total += pop[i]->fitness;
 311   for(i=0; i<death; i++)
 312     {
 313       struct automaton *a = pop[i];
 314       struct automaton *x = rgenom(pop+death, POPSIZE-death, total);
 315       memcpy(a, x, sizeof(struct automaton));
 316     }
 317
 318   for(i=0; i<POPSIZE; i++)
 319     {
 320       struct automaton *a = pop[i];
 321       int what = random() % 1024;
 322       //      printf("%d %d\n", i, what);
 323       if (what < 50)
 324         mutate(a);
 325       else if (what < 100)
 326         crossover(a, rgenom(pop+death, POPSIZE-death, total));
 327     }
 328 }
 329
 330 int
 331 main(void)
 332 {
 333   int gen = 0;
 334
 335   maze_init();
 336   pop_init();
 337   for(;;)
 338     {
 339       step();
 340       printf("gen=%d\n", gen++);
 341       //      sleep(1);
 342     }
 343   //  srandom(time(NULL));
 344   return 0;
 345 }