src/sn-evolution2.c

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