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 static int mutate_network (sn_network_t *n)
 133 {
 134   sn_network_t *n_copy;
 135   int stage_index;
 136   sn_stage_t *s;
 137   int comparator_index;
 138   int status;
 139
 140   n_copy = sn_network_clone (n);
 141   if (n_copy == NULL)
 142   {
 143     fprintf (stderr, "mutate_network: sn_network_clone failed.\n");
 144     return (-1);
 145   }
 146
 147   stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1);
 148   s = SN_NETWORK_STAGE_GET (n_copy, stage_index);
 149
 150   comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1);
 151   sn_stage_comparator_remove (s, comparator_index);
 152
 153   status = sn_network_brute_force_check (n_copy);
 154
 155   sn_network_destroy (n_copy);
 156
 157   if (status < 0)
 158     return (-1);
 159   else if (status > 0) /* Mutated network does not sort anymore. */
 160     return (1);
 161
 162   /* We saved one comparator \o/ Let's do the same change on the original
 163    * network. */
 164   s = SN_NETWORK_STAGE_GET (n, stage_index);
 165   sn_stage_comparator_remove (s, comparator_index);
 166
 167   return (0);
 168 } /* int mutate_network */
 169
 170 static int create_offspring (void)
 171 {
 172   sn_network_t *p0;
 173   sn_network_t *p1;
 174   sn_network_t *n;
 175
 176   p0 = sn_population_pop (population);
 177   p1 = sn_population_pop (population);
 178
 179   assert (p0 != NULL);
 180   assert (p1 != NULL);
 181
 182   /* combine the two parents */
 183   n = sn_network_combine (p0, p1);
 184
 185   sn_network_destroy (p0);
 186   sn_network_destroy (p1);
 187
 188   /* randomly chose an input and do a min- or max-cut. */
 189   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 190   {
 191     int pos;
 192     enum sn_network_cut_dir_e dir;
 193
 194     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 195     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 196
 197     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 198
 199     sn_network_cut_at (n, pos, dir);
 200   }
 201
 202   /* compress the network to get a compact representation */
 203   sn_network_compress (n);
 204
 205   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 206
 207   if (sn_bounded_random (0, 100) <= 1)
 208     mutate_network (n);
 209
 210   sn_population_push (population, n);
 211
 212   sn_network_destroy (n);
 213
 214   return (0);
 215 } /* int create_offspring */
 216
 217 static void *evolution_thread (void *arg)
 218 {
 219   while (do_loop == 0)
 220   {
 221     create_offspring ();
 222     /* XXX: Not synchronized! */
 223     iteration_counter++;
 224   }
 225
 226   return ((void *) 0);
 227 } /* int start_evolution */
 228
 229 static int evolution_start (int threads_num)
 230 {
 231   pthread_t threads[threads_num]; /* C99 ftw! */
 232   int i;
 233
 234   for (i = 0; i < threads_num; i++)
 235   {
 236     int status;
 237
 238     status = pthread_create (&threads[i], /* attr = */ NULL,
 239         evolution_thread, /* arg = */ NULL);
 240     if (status != 0)
 241     {
 242       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 243           "with status %i.\n",
 244           i, status);
 245       threads[i] = 0;
 246     }
 247   }
 248
 249   while (do_loop == 0)
 250   {
 251     int status;
 252
 253     status = sleep (1);
 254     if (status == 0)
 255     {
 256       int best_rating;
 257       i = iteration_counter;
 258
 259       best_rating = sn_population_best_rating (population);
 260       printf ("After approximately %i iterations: Currently best rating: %i\n", i, best_rating);
 261     }
 262   }
 263
 264   for (i = 0; i < threads_num; i++)
 265   {
 266     if (threads[i] == 0)
 267       continue;
 268     pthread_join (threads[i], /* value_ptr = */ NULL);
 269   }
 270
 271   return (0);
 272 } /* int evolution_start */
 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   evolution_start (3);
 317
 318   printf ("Exiting after %llu iterations.\n",
 319       (unsigned long long) iteration_counter);
 320
 321   {
 322     sn_network_t *n;
 323
 324     n = sn_population_best (population);
 325     if (n != NULL)
 326     {
 327       if (best_output_file != NULL)
 328         sn_network_write_file (n, best_output_file);
 329       else
 330         sn_network_show (n);
 331       sn_network_destroy (n);
 332     }
 333   }
 334
 335   sn_population_destroy (population);
 336
 337   return (0);
 338 } /* int main */
 339
 340 /* vim: set shiftwidth=2 softtabstop=2 : */