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