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 evolution_threads_num = 4;
  65
  66 static int do_loop = 0;
  67
  68 static void sigint_handler (int signal)
  69 {
  70   do_loop++;
  71 } /* void sigint_handler */
  72
  73 static void exit_usage (const char *name)
  74 {
  75   printf ("Usage: %s [options]\n"
  76       "\n"
  77       "Valid options are:\n"
  78       "  -i <file>     Initial input file (REQUIRED)\n"
  79       "  -o <file>     Write the current best solution to <file>\n"
  80       "  -p <num>      Size of the population (default: 128)\n"
  81       "  -P <peer>     Send individuals to <peer> (may be repeated)\n"
  82       "  -t <num>      Number of threads (default: 4)\n"
  83       "\n",
  84       name);
  85   exit (1);
  86 } /* void exit_usage */
  87
  88 int read_options (int argc, char **argv)
  89 {
  90   int option;
  91
  92   while ((option = getopt (argc, argv, "i:o:p:P:s:t:h")) != -1)
  93   {
  94     switch (option)
  95     {
  96       case 'i':
  97       {
  98         if (initial_input_file != NULL)
  99           free (initial_input_file);
 100         initial_input_file = strdup (optarg);
 101         break;
 102       }
 103
 104       case 'o':
 105       {
 106         if (best_output_file != NULL)
 107           free (best_output_file);
 108         best_output_file = strdup (optarg);
 109         break;
 110       }
 111
 112       case 'p':
 113       {
 114         int tmp = atoi (optarg);
 115         if (tmp > 0)
 116         {
 117           max_population_size = tmp;
 118           population_set_size (population, (size_t) max_population_size);
 119         }
 120         break;
 121       }
 122
 123       case 'P':
 124       {
 125         int status;
 126
 127         status = population_add_peer (population, optarg, /* port = */ NULL);
 128         if (status != 0)
 129         {
 130           fprintf (stderr, "population_add_peer failed with status %i.\n",
 131               status);
 132         }
 133         break;
 134       }
 135
 136       case 's':
 137       {
 138         int tmp = atoi (optarg);
 139         if (tmp > 0)
 140           stats_interval = tmp;
 141         break;
 142       }
 143
 144       case 't':
 145       {
 146         int tmp = atoi (optarg);
 147         if (tmp >= 1)
 148           evolution_threads_num = tmp;
 149         break;
 150       }
 151
 152       case 'h':
 153       default:
 154         exit_usage (argv[0]);
 155     }
 156   }
 157
 158   return (0);
 159 } /* int read_options */
 160
 161 static int rate_network (const sn_network_t *n)
 162 {
 163   int rate;
 164   int i;
 165
 166   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 167   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 168   {
 169     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 170     rate += SN_STAGE_COMP_NUM (s);
 171   }
 172
 173   return (rate);
 174 } /* int rate_network */
 175
 176 static int mutate_network (sn_network_t *n)
 177 {
 178   sn_network_t *n_copy;
 179   int stage_index;
 180   sn_stage_t *s;
 181   int comparator_index;
 182   int status;
 183
 184   n_copy = sn_network_clone (n);
 185   if (n_copy == NULL)
 186   {
 187     fprintf (stderr, "mutate_network: sn_network_clone failed.\n");
 188     return (-1);
 189   }
 190
 191   stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1);
 192   s = SN_NETWORK_STAGE_GET (n_copy, stage_index);
 193
 194   comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1);
 195   sn_stage_comparator_remove (s, comparator_index);
 196
 197   status = sn_network_brute_force_check (n_copy);
 198
 199   sn_network_destroy (n_copy);
 200
 201   if (status < 0)
 202     return (-1);
 203   else if (status > 0) /* Mutated network does not sort anymore. */
 204     return (1);
 205
 206   /* We saved one comparator \o/ Let's do the same change on the original
 207    * network. */
 208   s = SN_NETWORK_STAGE_GET (n, stage_index);
 209   sn_stage_comparator_remove (s, comparator_index);
 210
 211   return (0);
 212 } /* int mutate_network */
 213
 214 static int create_offspring (void)
 215 {
 216   sn_network_t *p0;
 217   sn_network_t *p1;
 218   sn_network_t *n;
 219
 220   p0 = population_get_random (population);
 221   p1 = population_get_random (population);
 222
 223   assert (p0 != NULL);
 224   assert (p1 != NULL);
 225
 226   /* combine the two parents */
 227   n = sn_network_combine (p0, p1);
 228
 229   sn_network_destroy (p0);
 230   sn_network_destroy (p1);
 231
 232   /* randomly chose an input and do a min- or max-cut. */
 233   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 234   {
 235     int pos;
 236     enum sn_network_cut_dir_e dir;
 237
 238     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 239     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 240
 241     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 242
 243     sn_network_cut_at (n, pos, dir);
 244   }
 245
 246   /* compress the network to get a compact representation */
 247   sn_network_compress (n);
 248
 249   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 250
 251   if (sn_bounded_random (0, 100) <= 1)
 252     mutate_network (n);
 253
 254   population_insert (population, n);
 255
 256   sn_network_destroy (n);
 257
 258   return (0);
 259 } /* int create_offspring */
 260
 261 static void *evolution_thread (void *arg)
 262 {
 263   while (do_loop == 0)
 264   {
 265     create_offspring ();
 266     /* XXX: Not synchronized! */
 267     iteration_counter++;
 268   }
 269
 270   return ((void *) 0);
 271 } /* int start_evolution */
 272
 273 static int evolution_start (int threads_num)
 274 {
 275   pthread_t threads[threads_num]; /* C99 ftw! */
 276   int i;
 277
 278   for (i = 0; i < threads_num; i++)
 279   {
 280     int status;
 281
 282     status = pthread_create (&threads[i], /* attr = */ NULL,
 283         evolution_thread, /* arg = */ NULL);
 284     if (status != 0)
 285     {
 286       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 287           "with status %i.\n",
 288           i, status);
 289       threads[i] = 0;
 290     }
 291   }
 292
 293   while (do_loop == 0)
 294   {
 295     int status;
 296
 297     status = sleep (1);
 298     if (status == 0)
 299     {
 300       sn_network_t *n;
 301       int stages_num;
 302       int comparators_num;
 303       int rating;
 304       int iter;
 305
 306       iter = iteration_counter;
 307
 308       n = population_get_fittest (population);
 309
 310       rating = rate_network (n);
 311
 312       stages_num = SN_NETWORK_STAGE_NUM (n);
 313       comparators_num = 0;
 314       for (i = 0; i < stages_num; i++)
 315       {
 316         sn_stage_t *s;
 317
 318         s = SN_NETWORK_STAGE_GET (n, i);
 319         comparators_num += SN_STAGE_COMP_NUM (s);
 320       }
 321
 322       sn_network_destroy (n);
 323
 324       printf ("Best after approximately %i iterations: "
 325           "%i comparators in %i stages. Rating: %i.\n",
 326           iter, comparators_num, stages_num, rating);
 327     }
 328   }
 329
 330   for (i = 0; i < threads_num; i++)
 331   {
 332     if (threads[i] == 0)
 333       continue;
 334     pthread_join (threads[i], /* value_ptr = */ NULL);
 335   }
 336
 337   return (0);
 338 } /* int evolution_start */
 339
 340 int main (int argc, char **argv)
 341 {
 342   struct sigaction sigint_action;
 343   struct sigaction sigterm_action;
 344
 345   population = population_create ((pi_rate_f) rate_network,
 346       (pi_copy_f) sn_network_clone,
 347       (pi_free_f) sn_network_destroy);
 348   if (population == NULL)
 349   {
 350     fprintf (stderr, "population_create failed.\n");
 351     return (1);
 352   }
 353
 354   population_set_serialization (population,
 355       (pi_serialize_f) sn_network_serialize,
 356       (pi_unserialize_f) sn_network_unserialize);
 357
 358   read_options (argc, argv);
 359   if (initial_input_file == NULL)
 360     exit_usage (argv[0]);
 361
 362   memset (&sigint_action, '\0', sizeof (sigint_action));
 363   sigint_action.sa_handler = sigint_handler;
 364   sigaction (SIGINT, &sigint_action, NULL);
 365
 366   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 367   sigterm_action.sa_handler = sigint_handler;
 368   sigaction (SIGTERM, &sigterm_action, NULL);
 369
 370   population_start_listen_thread (population, NULL, NULL);
 371
 372   {
 373     sn_network_t *n;
 374
 375     n = sn_network_read_file (initial_input_file);
 376     if (n == NULL)
 377     {
 378       printf ("n == NULL\n");
 379       return (1);
 380     }
 381
 382     inputs_num = SN_NETWORK_INPUT_NUM(n);
 383
 384     population_insert (population, n);
 385     sn_network_destroy (n);
 386   }
 387
 388   printf ("Current configuration:\n"
 389       "  Initial network:  %s\n"
 390       "  Number of inputs: %3i\n"
 391       "  Population size:  %3i\n"
 392       "=======================\n",
 393       initial_input_file, inputs_num, max_population_size);
 394
 395   evolution_start (evolution_threads_num);
 396
 397   printf ("Exiting after %llu iterations.\n",
 398       (unsigned long long) iteration_counter);
 399
 400   {
 401     sn_network_t *n;
 402
 403     n = population_get_fittest (population);
 404     if (n != NULL)
 405     {
 406       if (best_output_file != NULL)
 407         sn_network_write_file (n, best_output_file);
 408       sn_network_show (n);
 409       sn_network_destroy (n);
 410     }
 411   }
 412
 413   population_destroy (population);
 414
 415   return (0);
 416 } /* int main */
 417
 418 /* vim: set shiftwidth=2 softtabstop=2 : */