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