src/sn-evolution.c

   1 #define _ISOC99_SOURCE
   2 #define _POSIX_C_SOURCE 200112L
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7
   8 #include <sys/types.h>
   9 #include <sys/stat.h>
  10 #include <fcntl.h>
  11 #include <unistd.h>
  12 #include <signal.h>
  13 #include <assert.h>
  14 #include <limits.h>
  15
  16 #include "sn_network.h"
  17
  18 struct population_entry_s
  19 {
  20   sn_network_t *network;
  21   int rating;
  22 };
  23 typedef struct population_entry_s population_entry_t;
  24
  25 static int iterations_num  = INT_MAX;
  26 static int max_population_size = 128;
  27 static int olymp_size = 96;
  28 static int inputs_num      = 16;
  29
  30 static population_entry_t *population = NULL;
  31 int population_size = 0;
  32
  33 static void sigint_handler (int signal)
  34 {
  35   iterations_num = 0;
  36 } /* void sigint_handler */
  37
  38 static int init_random (void)
  39 {
  40   int fd;
  41   unsigned int r;
  42
  43   fd = open ("/dev/random", O_RDONLY);
  44   if (fd < 0)
  45   {
  46     perror ("open");
  47     return (-1);
  48   }
  49
  50   read (fd, (void *) &r, sizeof (r));
  51   close (fd);
  52
  53   srand (r);
  54
  55   return (0);
  56 } /* int init_random */
  57
  58 static int bounded_random (int upper_bound)
  59 {
  60   double r = ((double) rand ()) / ((double) RAND_MAX);
  61   return ((int) (r * upper_bound));
  62 }
  63
  64 static void exit_usage (const char *name)
  65 {
  66   printf ("%s <file0>\n", name);
  67   exit (1);
  68 } /* void exit_usage */
  69
  70 static int rate_network (const sn_network_t *n)
  71 {
  72   int rate;
  73   int i;
  74
  75   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
  76   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
  77   {
  78     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
  79     rate += SN_STAGE_COMP_NUM (s);
  80   }
  81
  82   return (rate);
  83 } /* int rate_network */
  84
  85 static int population_print_stats (int iterations)
  86 {
  87   int best = -1;
  88   int total = 0;
  89   int i;
  90
  91   for (i = 0; i < population_size; i++)
  92   {
  93     if ((best == -1) || (best > population[i].rating))
  94       best = population[i].rating;
  95     total += population[i].rating;
  96   }
  97
  98   printf ("Iterations: %6i; Best: %i; Average: %.2f;\n",
  99       iterations, best, ((double) total) / ((double) population_size));
 100
 101   return (0);
 102 } /* int population_print_stats */
 103
 104 static int insert_into_population (sn_network_t *n)
 105 {
 106   int rating;
 107   int worst_rating;
 108   int worst_index;
 109   int nmemb;
 110   int i;
 111
 112   rating = rate_network (n);
 113
 114   if (population_size < max_population_size)
 115   {
 116     population[population_size].network = n;
 117     population[population_size].rating  = rating;
 118     population_size++;
 119     return (0);
 120   }
 121
 122   worst_rating = -1;
 123   worst_index  = -1;
 124   for (i = 0; i < olymp_size; i++)
 125     if (population[i].rating > worst_rating)
 126     {
 127       worst_rating = population[i].rating;
 128       worst_index  = i;
 129     }
 130
 131   nmemb = max_population_size - (worst_index + 1);
 132
 133   sn_network_destroy (population[worst_index].network);
 134   population[worst_index].network = NULL;
 135
 136   memmove (population + worst_index,
 137       population + (worst_index + 1),
 138       nmemb * sizeof (population_entry_t));
 139
 140   population[max_population_size - 1].network = n;
 141   population[max_population_size - 1].rating  = rating;
 142
 143   return (0);
 144 } /* int insert_into_population */
 145
 146 static int create_offspring (void)
 147 {
 148   int p0;
 149   int p1;
 150   sn_network_t *n;
 151
 152   p0 = bounded_random (population_size);
 153   p1 = bounded_random (population_size);
 154
 155   n = sn_network_combine (population[p0].network, population[p1].network);
 156
 157   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 158   {
 159     int pos;
 160     enum sn_network_cut_dir_e dir;
 161
 162     pos = bounded_random (SN_NETWORK_INPUT_NUM (n));
 163     dir = (bounded_random (2) == 0) ? DIR_MIN : DIR_MAX;
 164
 165     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 166
 167     sn_network_cut_at (n, pos, dir);
 168   }
 169
 170   sn_network_compress (n);
 171
 172   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 173
 174   insert_into_population (n);
 175
 176   return (0);
 177 } /* int create_offspring */
 178
 179 static int start_evolution (void)
 180 {
 181   int i;
 182
 183   for (i = 0; i < iterations_num; i++)
 184   {
 185     if ((i % 1000) == 0)
 186       population_print_stats (i);
 187
 188     create_offspring ();
 189   }
 190
 191   return (0);
 192 } /* int start_evolution */
 193
 194 int main (int argc, char **argv)
 195 {
 196   struct sigaction sigint_action;
 197
 198   if (argc != 2)
 199     exit_usage (argv[0]);
 200
 201   init_random ();
 202
 203   memset (&sigint_action, '\0', sizeof (sigint_action));
 204   sigint_action.sa_handler = sigint_handler;
 205   sigaction (SIGINT, &sigint_action, NULL);
 206
 207   population = (population_entry_t *) malloc (max_population_size
 208       * sizeof (population_entry_t));
 209   if (population == NULL)
 210   {
 211     printf ("Malloc failed.\n");
 212     return (-1);
 213   }
 214   memset (population, '\0', max_population_size
 215       * sizeof (population_entry_t));
 216
 217   {
 218     sn_network_t *n = sn_network_read_file (argv[1]);
 219     if (n == NULL)
 220     {
 221       printf ("n == NULL\n");
 222       return (1);
 223     }
 224     population[0].network = n;
 225     population[0].rating  = rate_network (n);
 226     population_size++;
 227   }
 228
 229   start_evolution ();
 230
 231   {
 232     int i;
 233     int best_rate = -1;
 234     int best_index = -1;
 235
 236     for (i = 0; i < population_size; i++)
 237     {
 238       if ((best_rate == -1) || (best_rate > population[i].rating))
 239       {
 240         best_rate = population[i].rating;
 241         best_index = i;
 242       }
 243     }
 244
 245     sn_network_show (population[best_index].network);
 246   }
 247
 248   {
 249     int i;
 250
 251     for (i = 0; i < population_size; i++)
 252     {
 253       sn_network_destroy (population[i].network);
 254       population[i].network = NULL;
 255     }
 256
 257     free (population);
 258     population = 0;
 259   }
 260
 261   return (0);
 262 } /* int main */
 263
 264 /* vim: set shiftwidth=2 softtabstop=2 : */