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 <population.h>
  45
  46 #include "sn_network.h"
  47 #include "sn_random.h"
  48
  49 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
  50  * */
  51 char *strdup (const char *s);
  52
  53 static uint64_t iteration_counter = 0;
  54 static int inputs_num = 16;
  55
  56 static char *initial_input_file = NULL;
  57 static char *best_output_file = NULL;
  58
  59 static int stats_interval = 0;
  60
  61 static int max_population_size = 128;
  62 static population_t *population;
  63
  64 static int do_loop = 0;
  65
  66 static void sigint_handler (int signal)
  67 {
  68   do_loop++;
  69 } /* void sigint_handler */
  70
  71 static void exit_usage (const char *name)
  72 {
  73   printf ("Usage: %s [options]\n"
  74       "\n"
  75       "Valid options are:\n"
  76       "  -i <file>     Initial input file (REQUIRED)\n"
  77       "  -o <file>     Write the current best solution to <file>\n"
  78       "  -p <num>      Size of the population (default: 128)\n"
  79       "\n",
  80       name);
  81   exit (1);
  82 } /* void exit_usage */
  83
  84 int read_options (int argc, char **argv)
  85 {
  86   int option;
  87
  88   while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1)
  89   {
  90     switch (option)
  91     {
  92       case 'i':
  93       {
  94         if (initial_input_file != NULL)
  95           free (initial_input_file);
  96         initial_input_file = strdup (optarg);
  97         break;
  98       }
  99
 100       case 'o':
 101       {
 102         if (best_output_file != NULL)
 103           free (best_output_file);
 104         best_output_file = strdup (optarg);
 105         break;
 106       }
 107
 108       case 'p':
 109       {
 110         int tmp = atoi (optarg);
 111         if (tmp > 0)
 112           max_population_size = tmp;
 113         break;
 114       }
 115
 116       case 's':
 117       {
 118         int tmp = atoi (optarg);
 119         if (tmp > 0)
 120           stats_interval = tmp;
 121         break;
 122       }
 123
 124       case 'h':
 125       default:
 126         exit_usage (argv[0]);
 127     }
 128   }
 129
 130   return (0);
 131 } /* int read_options */
 132
 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
 148 static int mutate_network (sn_network_t *n)
 149 {
 150   sn_network_t *n_copy;
 151   int stage_index;
 152   sn_stage_t *s;
 153   int comparator_index;
 154   int status;
 155
 156   n_copy = sn_network_clone (n);
 157   if (n_copy == NULL)
 158   {
 159     fprintf (stderr, "mutate_network: sn_network_clone failed.\n");
 160     return (-1);
 161   }
 162
 163   stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1);
 164   s = SN_NETWORK_STAGE_GET (n_copy, stage_index);
 165
 166   comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1);
 167   sn_stage_comparator_remove (s, comparator_index);
 168
 169   status = sn_network_brute_force_check (n_copy);
 170
 171   sn_network_destroy (n_copy);
 172
 173   if (status < 0)
 174     return (-1);
 175   else if (status > 0) /* Mutated network does not sort anymore. */
 176     return (1);
 177
 178   /* We saved one comparator \o/ Let's do the same change on the original
 179    * network. */
 180   s = SN_NETWORK_STAGE_GET (n, stage_index);
 181   sn_stage_comparator_remove (s, comparator_index);
 182
 183   return (0);
 184 } /* int mutate_network */
 185
 186 static int create_offspring (void)
 187 {
 188   sn_network_t *p0;
 189   sn_network_t *p1;
 190   sn_network_t *n;
 191
 192   p0 = population_get_random (population);
 193   p1 = population_get_random (population);
 194
 195   assert (p0 != NULL);
 196   assert (p1 != NULL);
 197
 198   /* combine the two parents */
 199   n = sn_network_combine (p0, p1);
 200
 201   sn_network_destroy (p0);
 202   sn_network_destroy (p1);
 203
 204   /* randomly chose an input and do a min- or max-cut. */
 205   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 206   {
 207     int pos;
 208     enum sn_network_cut_dir_e dir;
 209
 210     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 211     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 212
 213     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 214
 215     sn_network_cut_at (n, pos, dir);
 216   }
 217
 218   /* compress the network to get a compact representation */
 219   sn_network_compress (n);
 220
 221   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 222
 223   if (sn_bounded_random (0, 100) <= 1)
 224     mutate_network (n);
 225
 226   population_insert (population, n);
 227
 228   sn_network_destroy (n);
 229
 230   return (0);
 231 } /* int create_offspring */
 232
 233 static void *evolution_thread (void *arg)
 234 {
 235   while (do_loop == 0)
 236   {
 237     create_offspring ();
 238     /* XXX: Not synchronized! */
 239     iteration_counter++;
 240   }
 241
 242   return ((void *) 0);
 243 } /* int start_evolution */
 244
 245 static int evolution_start (int threads_num)
 246 {
 247   pthread_t threads[threads_num]; /* C99 ftw! */
 248   int i;
 249
 250   for (i = 0; i < threads_num; i++)
 251   {
 252     int status;
 253
 254     status = pthread_create (&threads[i], /* attr = */ NULL,
 255         evolution_thread, /* arg = */ NULL);
 256     if (status != 0)
 257     {
 258       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 259           "with status %i.\n",
 260           i, status);
 261       threads[i] = 0;
 262     }
 263   }
 264
 265   while (do_loop == 0)
 266   {
 267     int status;
 268
 269     status = sleep (1);
 270     if (status == 0)
 271     {
 272       sn_network_t *n;
 273       int rating;
 274
 275       i = iteration_counter;
 276
 277       n = population_get_fittest (population);
 278       rating = rate_network (n);
 279       sn_network_destroy (n);
 280
 281       printf ("After approximately %i iterations: "
 282           "Currently best rating: %i\n",
 283           i, rating);
 284     }
 285   }
 286
 287   for (i = 0; i < threads_num; i++)
 288   {
 289     if (threads[i] == 0)
 290       continue;
 291     pthread_join (threads[i], /* value_ptr = */ NULL);
 292   }
 293
 294   return (0);
 295 } /* int evolution_start */
 296
 297 int main (int argc, char **argv)
 298 {
 299   struct sigaction sigint_action;
 300   struct sigaction sigterm_action;
 301
 302   read_options (argc, argv);
 303   if (initial_input_file == NULL)
 304     exit_usage (argv[0]);
 305
 306   memset (&sigint_action, '\0', sizeof (sigint_action));
 307   sigint_action.sa_handler = sigint_handler;
 308   sigaction (SIGINT, &sigint_action, NULL);
 309
 310   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 311   sigterm_action.sa_handler = sigint_handler;
 312   sigaction (SIGTERM, &sigterm_action, NULL);
 313
 314   population = population_create ((pi_rate_f) rate_network,
 315       (pi_copy_f) sn_network_clone,
 316       (pi_free_f) sn_network_destroy);
 317   if (population == NULL)
 318   {
 319     fprintf (stderr, "population_create failed.\n");
 320     return (1);
 321   }
 322
 323   {
 324     sn_network_t *n;
 325
 326     n = sn_network_read_file (initial_input_file);
 327     if (n == NULL)
 328     {
 329       printf ("n == NULL\n");
 330       return (1);
 331     }
 332
 333     inputs_num = SN_NETWORK_INPUT_NUM(n);
 334
 335     population_insert (population, n);
 336     sn_network_destroy (n);
 337   }
 338
 339   printf ("Current configuration:\n"
 340       "  Initial network:  %s\n"
 341       "  Number of inputs: %3i\n"
 342       "  Population size:  %3i\n"
 343       "=======================\n",
 344       initial_input_file, inputs_num, max_population_size);
 345
 346   evolution_start (3);
 347
 348   printf ("Exiting after %llu iterations.\n",
 349       (unsigned long long) iteration_counter);
 350
 351   {
 352     sn_network_t *n;
 353
 354     n = population_get_fittest (population);
 355     if (n != NULL)
 356     {
 357       if (best_output_file != NULL)
 358         sn_network_write_file (n, best_output_file);
 359       else
 360         sn_network_show (n);
 361       sn_network_destroy (n);
 362     }
 363   }
 364
 365   population_destroy (population);
 366
 367   return (0);
 368 } /* int main */
 369
 370 /* vim: set shiftwidth=2 softtabstop=2 : */