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