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