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 <stdint.h>
   7 #include <string.h>
   8
   9 #include <sys/types.h>
  10 #include <sys/stat.h>
  11 #include <fcntl.h>
  12 #include <unistd.h>
  13 #include <signal.h>
  14 #include <assert.h>
  15 #include <limits.h>
  16
  17 #include "sn_network.h"
  18
  19 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
  20  * */
  21 char *strdup (const char *s);
  22
  23 struct population_entry_s
  24 {
  25   sn_network_t *network;
  26   int rating;
  27 };
  28 typedef struct population_entry_s population_entry_t;
  29
  30 static uint64_t iteration_counter = 0;
  31 static int max_population_size = 128;
  32 static int olymp_size = 96;
  33 static int inputs_num      = 16;
  34
  35 static char *initial_input_file = NULL;
  36 static char *best_output_file = NULL;
  37
  38 static int stats_interval = 0;
  39
  40 static population_entry_t *population = NULL;
  41 static int population_size = 0;
  42
  43 static int do_loop = 0;
  44
  45 static void sigint_handler (int signal)
  46 {
  47   do_loop++;
  48 } /* void sigint_handler */
  49
  50 static int init_random (void)
  51 {
  52   int fd;
  53   unsigned int r;
  54
  55   fd = open ("/dev/random", O_RDONLY);
  56   if (fd < 0)
  57   {
  58     perror ("open");
  59     return (-1);
  60   }
  61
  62   read (fd, (void *) &r, sizeof (r));
  63   close (fd);
  64
  65   srand (r);
  66
  67   return (0);
  68 } /* int init_random */
  69
  70 static int bounded_random (int upper_bound)
  71 {
  72   double r = ((double) rand ()) / ((double) RAND_MAX);
  73   return ((int) (r * upper_bound));
  74 }
  75
  76 static void exit_usage (const char *name)
  77 {
  78   printf ("Usage: %s [options]\n"
  79       "\n"
  80       "Valid options are:\n"
  81       "  -i <file>     Initial input file (REQUIRED)\n"
  82       "  -o <file>     Write the current best solution to <file>\n"
  83       "  -p <num>      Size of the population (default: 128)\n"
  84       "  -P <num>      Size of the \"olymp\" (default: 96)\n"
  85       "\n",
  86       name);
  87   exit (1);
  88 } /* void exit_usage */
  89
  90 int read_options (int argc, char **argv)
  91 {
  92   int option;
  93
  94   while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1)
  95   {
  96     switch (option)
  97     {
  98       case 'i':
  99       {
 100         if (initial_input_file != NULL)
 101           free (initial_input_file);
 102         initial_input_file = strdup (optarg);
 103         break;
 104       }
 105
 106       case 'o':
 107       {
 108         if (best_output_file != NULL)
 109           free (best_output_file);
 110         best_output_file = strdup (optarg);
 111         break;
 112       }
 113
 114       case 'p':
 115       {
 116         int tmp = atoi (optarg);
 117         if (tmp > 0)
 118           max_population_size = tmp;
 119         break;
 120       }
 121
 122       case 'P':
 123       {
 124         int tmp = atoi (optarg);
 125         if (tmp > 0)
 126           olymp_size = tmp;
 127         break;
 128       }
 129
 130       case 's':
 131       {
 132         int tmp = atoi (optarg);
 133         if (tmp > 0)
 134           stats_interval = tmp;
 135         break;
 136       }
 137
 138       case 'h':
 139       default:
 140         exit_usage (argv[0]);
 141     }
 142   }
 143
 144   return (0);
 145 } /* int read_options */
 146
 147 static int rate_network (const sn_network_t *n)
 148 {
 149   int rate;
 150   int i;
 151
 152   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 153   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 154   {
 155     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 156     rate += SN_STAGE_COMP_NUM (s);
 157   }
 158
 159   return (rate);
 160 } /* int rate_network */
 161
 162 static int population_print_stats (int iterations)
 163 {
 164   int best = -1;
 165   int total = 0;
 166   int i;
 167
 168   for (i = 0; i < population_size; i++)
 169   {
 170     if ((best == -1) || (best > population[i].rating))
 171       best = population[i].rating;
 172     total += population[i].rating;
 173   }
 174
 175   printf ("Iterations: %6i; Best: %i; Average: %.2f;\n",
 176       iterations, best, ((double) total) / ((double) population_size));
 177
 178   return (0);
 179 } /* int population_print_stats */
 180
 181 static int insert_into_population (sn_network_t *n)
 182 {
 183   int rating;
 184   int worst_rating;
 185   int worst_index;
 186   int best_rating;
 187   int nmemb;
 188   int i;
 189
 190   rating = rate_network (n);
 191
 192   if (population_size < max_population_size)
 193   {
 194     population[population_size].network = n;
 195     population[population_size].rating  = rating;
 196     population_size++;
 197     return (0);
 198   }
 199
 200   worst_rating = -1;
 201   worst_index  = -1;
 202   best_rating  = -1;
 203   for (i = 0; i < olymp_size; i++)
 204   {
 205     if (population[i].rating > worst_rating)
 206     {
 207       worst_rating = population[i].rating;
 208       worst_index  = i;
 209     }
 210     if ((population[i].rating < best_rating)
 211         || (best_rating == -1))
 212       best_rating = population[i].rating;
 213   }
 214
 215   if (rating < best_rating)
 216   {
 217     if (best_output_file != NULL)
 218     {
 219       printf ("Writing network with rating %i to %s\n",
 220           rating, best_output_file);
 221       sn_network_write_file (n, best_output_file);
 222     }
 223     else
 224     {
 225       printf ("New best solution has rating %i\n",
 226           rating);
 227     }
 228   }
 229
 230   nmemb = max_population_size - (worst_index + 1);
 231
 232   sn_network_destroy (population[worst_index].network);
 233   population[worst_index].network = NULL;
 234
 235   memmove (population + worst_index,
 236       population + (worst_index + 1),
 237       nmemb * sizeof (population_entry_t));
 238
 239   population[max_population_size - 1].network = n;
 240   population[max_population_size - 1].rating  = rating;
 241
 242   return (0);
 243 } /* int insert_into_population */
 244
 245 static int create_offspring (void)
 246 {
 247   int p0;
 248   int p1;
 249   sn_network_t *n;
 250
 251   p0 = bounded_random (population_size);
 252   p1 = bounded_random (population_size);
 253
 254   n = sn_network_combine (population[p0].network, population[p1].network);
 255
 256   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 257   {
 258     int pos;
 259     enum sn_network_cut_dir_e dir;
 260
 261     pos = bounded_random (SN_NETWORK_INPUT_NUM (n));
 262     dir = (bounded_random (2) == 0) ? DIR_MIN : DIR_MAX;
 263
 264     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 265
 266     sn_network_cut_at (n, pos, dir);
 267   }
 268
 269   sn_network_compress (n);
 270
 271   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 272
 273   insert_into_population (n);
 274
 275   return (0);
 276 } /* int create_offspring */
 277
 278 static int start_evolution (void)
 279 {
 280   uint64_t i;
 281
 282   while (do_loop == 0)
 283   {
 284     create_offspring ();
 285
 286     iteration_counter++;
 287     i = iteration_counter;
 288
 289     if ((stats_interval > 0) && ((i % stats_interval) == 0))
 290       population_print_stats (i);
 291   }
 292
 293   return (0);
 294 } /* int start_evolution */
 295
 296 int main (int argc, char **argv)
 297 {
 298   struct sigaction sigint_action;
 299
 300   read_options (argc, argv);
 301   if (initial_input_file == NULL)
 302     exit_usage (argv[0]);
 303
 304   init_random ();
 305
 306   memset (&sigint_action, '\0', sizeof (sigint_action));
 307   sigint_action.sa_handler = sigint_handler;
 308   sigaction (SIGINT, &sigint_action, NULL);
 309
 310   population = (population_entry_t *) malloc (max_population_size
 311       * sizeof (population_entry_t));
 312   if (population == NULL)
 313   {
 314     printf ("Malloc failed.\n");
 315     return (-1);
 316   }
 317   memset (population, '\0', max_population_size
 318       * sizeof (population_entry_t));
 319
 320   {
 321     sn_network_t *n = sn_network_read_file (initial_input_file);
 322     if (n == NULL)
 323     {
 324       printf ("n == NULL\n");
 325       return (1);
 326     }
 327     population[0].network = n;
 328     population[0].rating  = rate_network (n);
 329     population_size++;
 330
 331     inputs_num = SN_NETWORK_INPUT_NUM(n);
 332   }
 333
 334   printf ("Current configuration:\n"
 335       "  Initial network:  %s\n"
 336       "  Number of inputs: %3i\n"
 337       "  Population size:  %3i\n"
 338       "  Olymp size:       %3i\n"
 339       "=======================\n",
 340       initial_input_file, inputs_num, max_population_size, olymp_size);
 341
 342   start_evolution ();
 343
 344   printf ("Exiting after %llu iterations.\n", iteration_counter);
 345
 346   if (best_output_file == NULL)
 347   {
 348     int i;
 349     int best_rate = -1;
 350     int best_index = -1;
 351
 352     for (i = 0; i < population_size; i++)
 353     {
 354       if ((best_rate == -1) || (best_rate > population[i].rating))
 355       {
 356         best_rate = population[i].rating;
 357         best_index = i;
 358       }
 359     }
 360
 361     sn_network_show (population[best_index].network);
 362   }
 363
 364   {
 365     int i;
 366
 367     for (i = 0; i < population_size; i++)
 368     {
 369       sn_network_destroy (population[i].network);
 370       population[i].network = NULL;
 371     }
 372
 373     free (population);
 374     population = 0;
 375   }
 376
 377   return (0);
 378 } /* int main */
 379
 380 /* vim: set shiftwidth=2 softtabstop=2 : */