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