src/sn-evolution2.c

   1 /**
   2  * collectd - src/sn-evolution.c
   3  * Copyright (C) 2008,2009  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 <math.h>
  43
  44 #include <pthread.h>
  45
  46 #include <population.h>
  47
  48 #include "sn_network.h"
  49 #include "sn_random.h"
  50
  51 #define SNE_MIN(a,b) ((a) < (b) ? (a) : (b))
  52 #define SNE_MAX(a,b) ((a) > (b) ? (a) : (b))
  53
  54 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
  55  * */
  56 char *strdup (const char *s);
  57
  58 static uint64_t iteration_counter = 0;
  59 static int inputs_num = -1;
  60
  61 static int comparators_num = -1;
  62
  63 static char *best_output_file = NULL;
  64
  65 static int stats_interval = 0;
  66
  67 static int max_population_size = 128;
  68 static population_t *population;
  69
  70 static int evolution_threads_num = 4;
  71
  72 static int do_loop = 0;
  73
  74 static void sigint_handler (int signal)
  75 {
  76   do_loop++;
  77 } /* void sigint_handler */
  78
  79 static void exit_usage (const char *name)
  80 {
  81   printf ("Usage: %s [options]\n"
  82       "\n"
  83       "Valid options are:\n"
  84       "  -i <inputs>       Number of inputs\n"
  85       "  -c <comparators>  Number of comparators\n"
  86       "  -o <file>         Write the current best solution to <file>\n"
  87       "  -p <num>          Size of the population (default: 128)\n"
  88       "  -P <peer>         Send individuals to <peer> (may be repeated)\n"
  89       "  -t <num>          Number of threads (default: 4)\n"
  90       "\n",
  91       name);
  92   exit (1);
  93 } /* void exit_usage */
  94
  95 int read_options (int argc, char **argv)
  96 {
  97   int option;
  98
  99   while ((option = getopt (argc, argv, "i:c:o:p:P:s:t:h")) != -1)
 100   {
 101     switch (option)
 102     {
 103       case 'i':
 104       {
 105         int tmp;
 106         tmp = atoi (optarg);
 107         if (tmp > 0)
 108           inputs_num = tmp;
 109         break;
 110       }
 111
 112       case 'c':
 113       {
 114         int tmp;
 115         tmp = atoi (optarg);
 116         if (tmp > 0)
 117           comparators_num = tmp;
 118         break;
 119       }
 120
 121       case 'o':
 122       {
 123         if (best_output_file != NULL)
 124           free (best_output_file);
 125         best_output_file = strdup (optarg);
 126         break;
 127       }
 128
 129       case 'p':
 130       {
 131         int tmp = atoi (optarg);
 132         if (tmp > 0)
 133         {
 134           max_population_size = tmp;
 135           population_set_size (population, (size_t) max_population_size);
 136         }
 137         break;
 138       }
 139
 140       case 'P':
 141       {
 142         int status;
 143
 144         status = population_add_peer (population, optarg, /* port = */ NULL);
 145         if (status != 0)
 146         {
 147           fprintf (stderr, "population_add_peer failed with status %i.\n",
 148               status);
 149         }
 150         break;
 151       }
 152
 153       case 's':
 154       {
 155         int tmp = atoi (optarg);
 156         if (tmp > 0)
 157           stats_interval = tmp;
 158         break;
 159       }
 160
 161       case 't':
 162       {
 163         int tmp = atoi (optarg);
 164         if (tmp >= 1)
 165           evolution_threads_num = tmp;
 166         break;
 167       }
 168
 169       case 'h':
 170       default:
 171         exit_usage (argv[0]);
 172     }
 173   }
 174
 175   return (0);
 176 } /* int read_options */
 177
 178 static int rate_network (sn_network_t *n) /* {{{ */
 179 {
 180   int test_pattern[n->inputs_num];
 181   int values[n->inputs_num];
 182
 183   int patterns_sorted = 0;
 184   int patterns_failed = 0;
 185
 186   memset (test_pattern, 0, sizeof (test_pattern));
 187   while (42)
 188   {
 189     int previous;
 190     int overflow;
 191     int status;
 192     int i;
 193
 194     /* Copy the current pattern and let the network sort it */
 195     memcpy (values, test_pattern, sizeof (values));
 196     status = sn_network_sort (n, values);
 197     if (status != 0)
 198       return (status);
 199
 200     /* Check if the array is now sorted. */
 201     previous = values[0];
 202     status = 0;
 203     for (i = 1; i < n->inputs_num; i++)
 204     {
 205       if (previous > values[i])
 206       {
 207         patterns_failed++;
 208         status = -1;
 209         break;
 210       }
 211       previous = values[i];
 212     }
 213
 214     if (status == 0)
 215       patterns_sorted++;
 216
 217     /* Generate the next test pattern */
 218     overflow = 1;
 219     for (i = 0; i < n->inputs_num; i++)
 220     {
 221       if (test_pattern[i] == 0)
 222       {
 223         test_pattern[i] = 1;
 224         overflow = 0;
 225         break;
 226       }
 227       else
 228       {
 229         test_pattern[i] = 0;
 230         overflow = 1;
 231       }
 232     }
 233
 234     /* Break out of the while loop if we tested all possible patterns */
 235     if (overflow == 1)
 236       break;
 237   } /* while (42) */
 238
 239   /* All tests successfull */
 240   return (SN_NETWORK_STAGE_NUM (n) + patterns_failed);
 241 } /* }}} int rate_network */
 242
 243 static sn_comparator_t get_random_comparator (void) /* {{{ */
 244 {
 245   sn_comparator_t c;
 246
 247   c.min = sn_bounded_random (0, inputs_num - 1);
 248   c.max = c.min;
 249   while (c.max == c.min)
 250     c.max = sn_bounded_random (0, inputs_num - 1);
 251
 252   return (c);
 253 } /* }}} sn_comparator_t get_random_comparator */
 254
 255 static int mutate_network (sn_comparator_t *comparators, int comparators_num)
 256 {
 257   static int old_comparators_num = -1;
 258   static int cut_off = 1000000;
 259
 260   int i;
 261
 262   if (old_comparators_num != comparators_num)
 263   {
 264     double p;
 265
 266     p = powl (0.5, (1.0 / ((double) comparators_num)));
 267     cut_off = (int) (((double) 1000000) * p);
 268
 269     old_comparators_num = comparators_num;
 270   }
 271
 272   for (i = 0; i < comparators_num; i++)
 273     if (sn_bounded_random (0, 1000000) >= cut_off)
 274       comparators[i] = get_random_comparator ();
 275
 276   return (0);
 277 } /* int mutate_network */
 278
 279 static int create_offspring (void)
 280 {
 281   sn_network_t *p0;
 282   sn_comparator_t p0_comparators[comparators_num];
 283   int p0_comparators_num;
 284
 285   sn_network_t *p1;
 286   sn_comparator_t p1_comparators[comparators_num];
 287   int p1_comparators_num;
 288
 289   sn_network_t *n;
 290   sn_comparator_t n_comparators[comparators_num];
 291   int n_comparators_num;
 292
 293   int i;
 294
 295   p0 = population_get_random (population);
 296   p1 = population_get_random (population);
 297
 298   assert (p0 != NULL);
 299   assert (p1 != NULL);
 300
 301   p0_comparators_num = 0;
 302   for (i = 0; i < SN_NETWORK_STAGE_NUM (p0); i++)
 303   {
 304     sn_stage_t *s;
 305     int j;
 306
 307     s = SN_NETWORK_STAGE_GET (p0, i);
 308
 309     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 310     {
 311       sn_comparator_t *c;
 312
 313       c = SN_STAGE_COMP_GET (s, j);
 314       p0_comparators[p0_comparators_num] = *c;
 315       p0_comparators_num++;
 316     }
 317   }
 318   while (p0_comparators_num < comparators_num)
 319   {
 320     p0_comparators[p0_comparators_num] = get_random_comparator ();
 321     p0_comparators_num++;
 322   }
 323   sn_network_destroy (p0);
 324   p0 = NULL;
 325
 326   p1_comparators_num = 0;
 327   for (i = 0; i < SN_NETWORK_STAGE_NUM (p1); i++)
 328   {
 329     sn_stage_t *s;
 330     int j;
 331
 332     s = SN_NETWORK_STAGE_GET (p1, i);
 333
 334     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 335     {
 336       sn_comparator_t *c;
 337
 338       c = SN_STAGE_COMP_GET (s, j);
 339       p1_comparators[p1_comparators_num] = *c;
 340       p1_comparators_num++;
 341     }
 342   }
 343   while (p1_comparators_num < comparators_num)
 344   {
 345     p1_comparators[p1_comparators_num] = get_random_comparator ();
 346     p1_comparators_num++;
 347   }
 348   sn_network_destroy (p1);
 349   p1 = NULL;
 350
 351   n_comparators_num = sn_bounded_random (SNE_MIN (p0_comparators_num, p1_comparators_num),
 352       SNE_MAX (p0_comparators_num, p1_comparators_num));
 353
 354   for (i = 0; i < n_comparators_num; i++)
 355   {
 356     if (i >= p0_comparators_num)
 357       n_comparators[i] = p1_comparators[i];
 358     else if (i >= p1_comparators_num)
 359       n_comparators[i] = p0_comparators[i];
 360     else if (sn_bounded_random (0, 1) == 0)
 361       n_comparators[i] = p1_comparators[i];
 362     else
 363       n_comparators[i] = p0_comparators[i];
 364
 365   }
 366
 367   mutate_network (n_comparators, n_comparators_num);
 368
 369   n = sn_network_create (inputs_num);
 370   for (i = 0; i < n_comparators_num; i++)
 371     sn_network_comparator_add (n, &n_comparators[i]);
 372
 373   /* compress the network to get a compact representation */
 374   sn_network_compress (n);
 375
 376   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 377
 378   population_insert (population, n);
 379
 380   sn_network_destroy (n);
 381
 382   return (0);
 383 } /* int create_offspring */
 384
 385 static void *evolution_thread (void *arg)
 386 {
 387   while (do_loop == 0)
 388   {
 389     create_offspring ();
 390     /* XXX: Not synchronized! */
 391     iteration_counter++;
 392   }
 393
 394   return ((void *) 0);
 395 } /* int start_evolution */
 396
 397 static int evolution_start (int threads_num)
 398 {
 399   pthread_t threads[threads_num]; /* C99 ftw! */
 400   int i;
 401
 402   for (i = 0; i < threads_num; i++)
 403   {
 404     int status;
 405
 406     status = pthread_create (&threads[i], /* attr = */ NULL,
 407         evolution_thread, /* arg = */ NULL);
 408     if (status != 0)
 409     {
 410       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 411           "with status %i.\n",
 412           i, status);
 413       threads[i] = 0;
 414     }
 415   }
 416
 417   while (do_loop == 0)
 418   {
 419     int status;
 420
 421     status = sleep (1);
 422     if (status == 0)
 423     {
 424       sn_network_t *n;
 425       int stages_num;
 426       int comparators_num;
 427       int rating;
 428       int iter;
 429
 430       iter = iteration_counter;
 431
 432       n = population_get_fittest (population);
 433
 434       rating = rate_network (n);
 435
 436       stages_num = SN_NETWORK_STAGE_NUM (n);
 437       comparators_num = 0;
 438       for (i = 0; i < stages_num; i++)
 439       {
 440         sn_stage_t *s;
 441
 442         s = SN_NETWORK_STAGE_GET (n, i);
 443         comparators_num += SN_STAGE_COMP_NUM (s);
 444       }
 445
 446       sn_network_destroy (n);
 447
 448       printf ("Best after approximately %i iterations: "
 449           "%i comparators in %i stages. Rating: %i (%i not sorted).\n",
 450           iter, comparators_num, stages_num, rating,
 451           rating - stages_num);
 452     }
 453   }
 454
 455   for (i = 0; i < threads_num; i++)
 456   {
 457     if (threads[i] == 0)
 458       continue;
 459     pthread_join (threads[i], /* value_ptr = */ NULL);
 460   }
 461
 462   return (0);
 463 } /* int evolution_start */
 464
 465 int main (int argc, char **argv)
 466 {
 467   struct sigaction sigint_action;
 468   struct sigaction sigterm_action;
 469
 470   population = population_create ((pi_rate_f) rate_network,
 471       (pi_copy_f) sn_network_clone,
 472       (pi_free_f) sn_network_destroy);
 473   if (population == NULL)
 474   {
 475     fprintf (stderr, "population_create failed.\n");
 476     return (1);
 477   }
 478
 479   population_set_serialization (population,
 480       (pi_serialize_f) sn_network_serialize,
 481       (pi_unserialize_f) sn_network_unserialize);
 482
 483   read_options (argc, argv);
 484
 485   if ((inputs_num <= 0) || (comparators_num <= 0))
 486     exit_usage (argv[0]);
 487
 488   memset (&sigint_action, '\0', sizeof (sigint_action));
 489   sigint_action.sa_handler = sigint_handler;
 490   sigaction (SIGINT, &sigint_action, NULL);
 491
 492   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 493   sigterm_action.sa_handler = sigint_handler;
 494   sigaction (SIGTERM, &sigterm_action, NULL);
 495
 496   population_start_listen_thread (population, NULL, NULL);
 497
 498   {
 499     sn_network_t *n;
 500     int i;
 501
 502     n = sn_network_create (inputs_num);
 503     for (i = 0; i < comparators_num; i++)
 504     {
 505       sn_comparator_t c;
 506
 507       c = get_random_comparator ();
 508       sn_network_comparator_add (n, &c);
 509     }
 510
 511     population_insert (population, n);
 512     sn_network_destroy (n);
 513   }
 514
 515   printf ("Current configuration:\n"
 516       "  Number of inputs:      %3i\n"
 517       "  Number of comparators: %3i\n"
 518       "  Population size:       %3i\n"
 519       "=======================\n",
 520       inputs_num, comparators_num, max_population_size);
 521
 522   evolution_start (evolution_threads_num);
 523
 524   printf ("Exiting after %llu iterations.\n",
 525       (unsigned long long) iteration_counter);
 526
 527   {
 528     sn_network_t *n;
 529
 530     n = population_get_fittest (population);
 531     if (n != NULL)
 532     {
 533       if (best_output_file != NULL)
 534         sn_network_write_file (n, best_output_file);
 535       sn_network_show (n);
 536       sn_network_destroy (n);
 537     }
 538   }
 539
 540   population_destroy (population);
 541
 542   return (0);
 543 } /* int main */
 544
 545 /* vim: set shiftwidth=2 softtabstop=2 : */