src/sn-evolution.c

   1 /**
   2  * collectd - src/sn-evolution.c
   3  * Copyright (C) 2008  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; only version 2 of the License is applicable.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  17  *
  18  * Authors:
  19  *   Florian octo Forster <octo at verplant.org>
  20  **/
  21
  22 #define _ISOC99_SOURCE
  23 #define _POSIX_C_SOURCE 200112L
  24
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <stdint.h>
  28 #include <string.h>
  29
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <fcntl.h>
  33 #include <unistd.h>
  34 #include <signal.h>
  35 #include <assert.h>
  36 #include <limits.h>
  37
  38 #include <pthread.h>
  39
  40 #include "sn_network.h"
  41 #include "sn_population.h"
  42 #include "sn_random.h"
  43
  44 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
  45  * */
  46 char *strdup (const char *s);
  47
  48 static uint64_t iteration_counter = 0;
  49 static int inputs_num = 16;
  50
  51 static char *initial_input_file = NULL;
  52 static char *best_output_file = NULL;
  53
  54 static int stats_interval = 0;
  55
  56 static int max_population_size = 128;
  57 static sn_population_t *population;
  58
  59 static int do_loop = 0;
  60
  61 static void sigint_handler (int signal)
  62 {
  63   do_loop++;
  64 } /* void sigint_handler */
  65
  66 static void exit_usage (const char *name)
  67 {
  68   printf ("Usage: %s [options]\n"
  69       "\n"
  70       "Valid options are:\n"
  71       "  -i <file>     Initial input file (REQUIRED)\n"
  72       "  -o <file>     Write the current best solution to <file>\n"
  73       "  -p <num>      Size of the population (default: 128)\n"
  74       "\n",
  75       name);
  76   exit (1);
  77 } /* void exit_usage */
  78
  79 int read_options (int argc, char **argv)
  80 {
  81   int option;
  82
  83   while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1)
  84   {
  85     switch (option)
  86     {
  87       case 'i':
  88       {
  89         if (initial_input_file != NULL)
  90           free (initial_input_file);
  91         initial_input_file = strdup (optarg);
  92         break;
  93       }
  94
  95       case 'o':
  96       {
  97         if (best_output_file != NULL)
  98           free (best_output_file);
  99         best_output_file = strdup (optarg);
 100         break;
 101       }
 102
 103       case 'p':
 104       {
 105         int tmp = atoi (optarg);
 106         if (tmp > 0)
 107           max_population_size = tmp;
 108         break;
 109       }
 110
 111       case 's':
 112       {
 113         int tmp = atoi (optarg);
 114         if (tmp > 0)
 115           stats_interval = tmp;
 116         break;
 117       }
 118
 119       case 'h':
 120       default:
 121         exit_usage (argv[0]);
 122     }
 123   }
 124
 125   return (0);
 126 } /* int read_options */
 127
 128 #if 0
 129 static int rate_network (const sn_network_t *n)
 130 {
 131   int rate;
 132   int i;
 133
 134   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 135   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 136   {
 137     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 138     rate += SN_STAGE_COMP_NUM (s);
 139   }
 140
 141   return (rate);
 142 } /* int rate_network */
 143 #endif
 144
 145 #if 0
 146 static int population_print_stats (int iterations)
 147 {
 148   int best = -1;
 149   int total = 0;
 150   int i;
 151
 152   for (i = 0; i < population_size; i++)
 153   {
 154     if ((best == -1) || (best > population[i].rating))
 155       best = population[i].rating;
 156     total += population[i].rating;
 157   }
 158
 159   printf ("Iterations: %6i; Best: %i; Average: %.2f;\n",
 160       iterations, best, ((double) total) / ((double) population_size));
 161
 162   return (0);
 163 } /* int population_print_stats */
 164 #endif
 165
 166 #if 0
 167 static int insert_into_population (sn_network_t *n)
 168 {
 169   int rating;
 170   int worst_rating;
 171   int worst_index;
 172   int best_rating;
 173   int nmemb;
 174   int i;
 175
 176   rating = rate_network (n);
 177
 178   if (population_size < max_population_size)
 179   {
 180     population[population_size].network = n;
 181     population[population_size].rating  = rating;
 182     population_size++;
 183     return (0);
 184   }
 185
 186   worst_rating = -1;
 187   worst_index  = -1;
 188   best_rating  = -1;
 189   for (i = 0; i < olymp_size; i++)
 190   {
 191     if (population[i].rating > worst_rating)
 192     {
 193       worst_rating = population[i].rating;
 194       worst_index  = i;
 195     }
 196     if ((population[i].rating < best_rating)
 197         || (best_rating == -1))
 198       best_rating = population[i].rating;
 199   }
 200
 201   if (rating < best_rating)
 202   {
 203     if (best_output_file != NULL)
 204     {
 205       printf ("Writing network with rating %i to %s\n",
 206           rating, best_output_file);
 207       sn_network_write_file (n, best_output_file);
 208     }
 209     else
 210     {
 211       printf ("New best solution has rating %i\n",
 212           rating);
 213     }
 214   }
 215
 216   nmemb = max_population_size - (worst_index + 1);
 217
 218   sn_network_destroy (population[worst_index].network);
 219   population[worst_index].network = NULL;
 220
 221   memmove (population + worst_index,
 222       population + (worst_index + 1),
 223       nmemb * sizeof (population_entry_t));
 224
 225   population[max_population_size - 1].network = n;
 226   population[max_population_size - 1].rating  = rating;
 227
 228   return (0);
 229 } /* int insert_into_population */
 230 #endif
 231
 232 static int create_offspring (void)
 233 {
 234   sn_network_t *p0;
 235   sn_network_t *p1;
 236   sn_network_t *n;
 237
 238   p0 = sn_population_pop (population);
 239   p1 = sn_population_pop (population);
 240
 241   assert (p0 != NULL);
 242   assert (p1 != NULL);
 243
 244   /* combine the two parents */
 245   n = sn_network_combine (p0, p1);
 246
 247   sn_network_destroy (p0);
 248   sn_network_destroy (p1);
 249
 250   /* randomly chose an input and do a min- or max-cut. */
 251   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 252   {
 253     int pos;
 254     enum sn_network_cut_dir_e dir;
 255
 256     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 257     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 258
 259     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 260
 261     sn_network_cut_at (n, pos, dir);
 262   }
 263
 264   /* compress the network to get a compact representation */
 265   sn_network_compress (n);
 266
 267   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 268
 269   sn_population_push (population, n);
 270
 271   sn_network_destroy (n);
 272
 273   return (0);
 274 } /* int create_offspring */
 275
 276 static void *evolution_thread (void *arg)
 277 {
 278   while (do_loop == 0)
 279   {
 280     create_offspring ();
 281     /* XXX: Not synchronized! */
 282     iteration_counter++;
 283   }
 284
 285   return ((void *) 0);
 286 } /* int start_evolution */
 287
 288 static int evolution_start (int threads_num)
 289 {
 290   pthread_t threads[threads_num]; /* C99 ftw! */
 291   int i;
 292
 293   for (i = 0; i < threads_num; i++)
 294   {
 295     int status;
 296
 297     status = pthread_create (&threads[i], /* attr = */ NULL,
 298         evolution_thread, /* arg = */ NULL);
 299     if (status != 0)
 300     {
 301       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 302           "with status %i.\n",
 303           i, status);
 304       threads[i] = 0;
 305     }
 306   }
 307
 308   while (do_loop == 0)
 309   {
 310     int status;
 311
 312     status = sleep (1);
 313     if (status == 0)
 314     {
 315       int best_rating;
 316       i = iteration_counter;
 317
 318       best_rating = sn_population_best_rating (population);
 319       printf ("After approximately %i iterations: Currently best rating: %i\n", i, best_rating);
 320     }
 321   }
 322
 323   for (i = 0; i < threads_num; i++)
 324   {
 325     if (threads[i] == 0)
 326       continue;
 327     pthread_join (threads[i], /* value_ptr = */ NULL);
 328   }
 329
 330   return (0);
 331 } /* int evolution_start */
 332
 333 int main (int argc, char **argv)
 334 {
 335   struct sigaction sigint_action;
 336
 337   read_options (argc, argv);
 338   if (initial_input_file == NULL)
 339     exit_usage (argv[0]);
 340
 341   memset (&sigint_action, '\0', sizeof (sigint_action));
 342   sigint_action.sa_handler = sigint_handler;
 343   sigaction (SIGINT, &sigint_action, NULL);
 344
 345   population = sn_population_create (max_population_size);
 346   if (population == NULL)
 347   {
 348     fprintf (stderr, "sn_population_create failed.\n");
 349     return (1);
 350   }
 351
 352   {
 353     sn_network_t *n;
 354
 355     n = sn_network_read_file (initial_input_file);
 356     if (n == NULL)
 357     {
 358       printf ("n == NULL\n");
 359       return (1);
 360     }
 361
 362     inputs_num = SN_NETWORK_INPUT_NUM(n);
 363
 364     sn_population_push (population, n);
 365     sn_network_destroy (n);
 366   }
 367
 368   printf ("Current configuration:\n"
 369       "  Initial network:  %s\n"
 370       "  Number of inputs: %3i\n"
 371       "  Population size:  %3i\n"
 372       "=======================\n",
 373       initial_input_file, inputs_num, max_population_size);
 374
 375   evolution_start (3);
 376
 377   printf ("Exiting after %llu iterations.\n",
 378       (unsigned long long) iteration_counter);
 379
 380   {
 381     sn_network_t *n;
 382
 383     n = sn_population_best (population);
 384     if (n != NULL)
 385     {
 386       if (best_output_file != NULL)
 387         sn_network_write_file (n, best_output_file);
 388       else
 389         sn_network_show (n);
 390       sn_network_destroy (n);
 391     }
 392   }
 393
 394   sn_population_destroy (population);
 395
 396   return (0);
 397 } /* int main */
 398
 399 /* vim: set shiftwidth=2 softtabstop=2 : */