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