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