src/sn-evolution-cut.c

   1 /**
   2  * libsortnetwork - src/sn-evolution-cut.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 #include "config.h"
  23
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include <stdint.h>
  27 #include <inttypes.h>
  28 #include <string.h>
  29
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <fcntl.h>
  33 #include <unistd.h>
  34 #include <signal.h>
  35 #include <assert.h>
  36 #include <limits.h>
  37 #include <errno.h>
  38
  39 #include <pthread.h>
  40
  41 #include <population.h>
  42
  43 #include "sn_network.h"
  44 #include "sn_random.h"
  45
  46 #if !defined(__GNUC__) || !__GNUC__
  47 # define __attribute__(x) /**/
  48 #endif
  49
  50 typedef int individuum_t;
  51
  52 static int inputs_num = 0;
  53 static int outputs_num = 0;
  54 static int cuts_num = 0;
  55
  56 static char *initial_input_file = NULL;
  57 static const sn_network_t *initial_network = NULL;
  58 static char *best_output_file = NULL;
  59
  60 static int stats_interval = 0;
  61
  62 static int max_population_size = 128;
  63 static population_t *population = NULL;
  64
  65 static int evolution_threads_num = 4;
  66
  67 static int do_loop = 0;
  68 static uint64_t iteration_counter = 0;
  69 static uint64_t max_iterations = 0;
  70
  71 static int target_rating = 0;
  72
  73 static void sigint_handler (int signal __attribute__((unused)))
  74 {
  75   do_loop++;
  76 } /* void sigint_handler */
  77
  78 static void exit_usage (const char *name)
  79 {
  80   printf ("Usage: %s [options]\n"
  81       "\n"
  82       "Valid options are:\n"
  83       "  -i <file>     Initial input file (REQUIRED)\n"
  84       "  -o <file>     Write the current best solution to <file>\n"
  85       "  -O <num>      Number of outputs (default: inputs / 2)\n"
  86       "  -p <num>      Size of the population (default: 128)\n"
  87       "  -P <peer>     Send individuals to <peer> (may be repeated)\n"
  88       "  -t <num>      Number of threads (default: 4)\n"
  89       "  -n <num>      Maximum number of steps (iterations) to perform\n"
  90       "  -r <num>      Target rating: Stop loop when rating is less then or equal\n"
  91       "                to this number.\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:o:O:p:P:s:t:n:r:h")) != -1)
 102   {
 103     switch (option)
 104     {
 105       case 'i':
 106       {
 107         if (initial_input_file != NULL)
 108           free (initial_input_file);
 109         initial_input_file = strdup (optarg);
 110         break;
 111       }
 112
 113       case 'o':
 114       {
 115         if (best_output_file != NULL)
 116           free (best_output_file);
 117         best_output_file = strdup (optarg);
 118         break;
 119       }
 120
 121       case 'O':
 122       {
 123         int tmp = atoi (optarg);
 124         if (tmp > 0)
 125           outputs_num = tmp;
 126         break;
 127       }
 128
 129       case 'p':
 130       {
 131         int tmp = atoi (optarg);
 132         if (tmp > 0)
 133         {
 134           max_population_size = tmp;
 135           population_set_size (population, (size_t) max_population_size);
 136         }
 137         break;
 138       }
 139
 140       case 'P':
 141       {
 142         int status;
 143
 144         status = population_add_peer (population, optarg, /* port = */ NULL);
 145         if (status != 0)
 146         {
 147           fprintf (stderr, "population_add_peer failed with status %i.\n",
 148               status);
 149         }
 150         break;
 151       }
 152
 153       case 's':
 154       {
 155         int tmp = atoi (optarg);
 156         if (tmp > 0)
 157           stats_interval = tmp;
 158         break;
 159       }
 160
 161       case 't':
 162       {
 163         int tmp = atoi (optarg);
 164         if (tmp >= 1)
 165           evolution_threads_num = tmp;
 166         break;
 167       }
 168
 169       case 'n':
 170       {
 171         errno = 0;
 172         max_iterations = (uint64_t) strtoull (optarg,
 173             /* endptr = */ NULL,
 174             /* base   = */ 0);
 175         if (errno != 0)
 176         {
 177           fprintf (stderr, "Parsing integer argument failed: %s\n",
 178               strerror (errno));
 179           exit_usage (argv[0]);
 180         }
 181         break;
 182       }
 183
 184       case 'r':
 185       {
 186         int tmp = atoi (optarg);
 187         if (tmp > 0)
 188           target_rating = tmp;
 189         break;
 190       }
 191
 192       case 'h':
 193       default:
 194         exit_usage (argv[0]);
 195     }
 196   }
 197
 198   return (0);
 199 } /* }}} int read_options */
 200
 201 static int rate_network (const sn_network_t *n) /* {{{ */
 202 {
 203   int rate;
 204
 205   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n)
 206     + sn_network_get_comparator_num (n);
 207
 208   return (rate);
 209 } /* }}} int rate_network */
 210
 211 static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */
 212 {
 213   sn_network_t *n;
 214   int mask[SN_NETWORK_INPUT_NUM (initial_network)];
 215
 216   memcpy (mask, ind, sizeof (mask));
 217
 218   n = sn_network_clone (initial_network);
 219   if (n == NULL)
 220     return (NULL);
 221
 222   sn_network_cut (n, mask);
 223
 224   sn_network_normalize (n);
 225   sn_network_compress (n);
 226
 227   return (n);
 228 } /* }}} sn_network_t *individuum_to_network */
 229
 230 static int ind_rate (const void *arg) /* {{{ */
 231 {
 232   sn_network_t *n;
 233   int status;
 234
 235   n = individuum_to_network (arg);
 236   if (n == NULL)
 237     return (-1);
 238
 239   status = rate_network (n);
 240   sn_network_destroy (n);
 241
 242   return (status);
 243 } /* }}} int ind_rate */
 244
 245 static void *ind_copy (const void *in) /* {{{ */
 246 {
 247   size_t s = sizeof (individuum_t) * inputs_num;
 248   void *out;
 249
 250   out = malloc (s);
 251   if (out == NULL)
 252     return (NULL);
 253
 254   memcpy (out, in, s);
 255   return (out);
 256 } /* }}} void *ind_copy */
 257
 258 static void ind_free (void *ind) /* {{{ */
 259 {
 260   if (ind != NULL)
 261     free (ind);
 262 } /* }}} void ind_free */
 263
 264 static void ind_print (const individuum_t *ind) /* {{{ */
 265 {
 266   int i;
 267
 268   for (i = 0; i < inputs_num; i++)
 269   {
 270     printf ("%3i: %s\n", i, (ind[i] == 0) ? "-" :
 271         (ind[i] < 0) ? "MIN" : "MAX");
 272   }
 273
 274   printf ("# sn-cut");
 275   for (i = 0; i < inputs_num; i++)
 276   {
 277     if (ind[i] == 0)
 278       continue;
 279     printf (" %i:%s", i, (ind[i] < 0) ? "MIN" : "MAX");
 280   }
 281   printf ("\n");
 282 } /* }}} void ind_print */
 283
 284 /* Simply makes sure the right amount of cutting positions exist. */
 285 static void mutate (individuum_t *ind, int this_cuts_num) /* {{{ */
 286 {
 287   int i;
 288
 289   if (this_cuts_num < 0)
 290   {
 291     this_cuts_num = 0;
 292     for (i = 0; i < inputs_num; i++)
 293       if (ind[i] != 0)
 294         this_cuts_num++;
 295   }
 296
 297   while (this_cuts_num != cuts_num)
 298   {
 299     i = sn_bounded_random (0, inputs_num - 1);
 300
 301     if ((this_cuts_num < cuts_num)
 302         && (ind[i] == 0))
 303     {
 304       ind[i] = (sn_bounded_random (0, 1) * 2) - 1;
 305       assert (ind[i] != 0);
 306       this_cuts_num++;
 307     }
 308     else if ((this_cuts_num > cuts_num)
 309         && (ind[i] != 0))
 310     {
 311       ind[i] = 0;
 312       this_cuts_num--;
 313     }
 314   }
 315 } /* }}} void mutate */
 316
 317 static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */
 318 {
 319   individuum_t *offspring;
 320   int this_cuts_num;
 321   int i;
 322
 323   if ((i0 == NULL) || (i1 == NULL))
 324     return (NULL);
 325
 326   offspring = malloc (sizeof (*offspring) * inputs_num);
 327   if (offspring == NULL)
 328     return (NULL);
 329   memset (offspring, 0, sizeof (*offspring) * inputs_num);
 330
 331   this_cuts_num = 0;
 332   for (i = 0; i < this_cuts_num; i++)
 333   {
 334     if (sn_bounded_random (0, 1) == 0)
 335       offspring[i] = i0[i];
 336     else
 337       offspring[i] = i1[i];
 338
 339     if (offspring[i] != 0)
 340       this_cuts_num++;
 341   }
 342
 343   mutate (offspring, this_cuts_num);
 344
 345   return (offspring);
 346 } /* }}} individuum_t *recombine */
 347
 348 static int create_offspring (void) /* {{{ */
 349 {
 350   individuum_t *i0;
 351   individuum_t *i1;
 352   individuum_t *i2;
 353
 354   i0 = population_get_random (population);
 355   i1 = population_get_random (population);
 356
 357   i2 = recombine (i0, i1);
 358
 359   population_insert (population, i2);
 360
 361   free (i0);
 362   free (i1);
 363   free (i2);
 364
 365   return (0);
 366 } /* }}} int create_offspring */
 367
 368 static void *evolution_thread (void *arg __attribute__((unused))) /* {{{ */
 369 {
 370   while (do_loop == 0)
 371   {
 372     create_offspring ();
 373     /* XXX: Not synchronized! */
 374     iteration_counter++;
 375   }
 376
 377   return ((void *) 0);
 378 } /* }}} int start_evolution */
 379
 380 static int evolution_start (int threads_num) /* {{{ */
 381 {
 382   pthread_t threads[threads_num]; /* C99 ftw! */
 383   int i;
 384
 385   for (i = 0; i < threads_num; i++)
 386   {
 387     int status;
 388
 389     status = pthread_create (&threads[i], /* attr = */ NULL,
 390         evolution_thread, /* arg = */ NULL);
 391     if (status != 0)
 392     {
 393       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 394           "with status %i.\n",
 395           i, status);
 396       threads[i] = 0;
 397     }
 398   }
 399
 400   while (do_loop == 0)
 401   {
 402     int status;
 403
 404     status = sleep (1);
 405     if (status == 0)
 406     {
 407       individuum_t *ind;
 408       sn_network_t *n;
 409       int stages_num;
 410       int comparators_num;
 411       int rating;
 412       int iter;
 413
 414       iter = iteration_counter;
 415
 416       ind = population_get_fittest (population);
 417       n = individuum_to_network (ind);
 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       ind_free (ind);
 433
 434       printf ("Best after approximately %i iterations: "
 435           "%i comparators in %i stages. Rating: %i.\n",
 436           iter, comparators_num, stages_num, rating);
 437
 438       if ((target_rating > 0) && (rating <= target_rating))
 439         do_loop++;
 440     }
 441
 442     if ((max_iterations > 0) && (iteration_counter >= max_iterations))
 443       do_loop++;
 444   }
 445
 446   for (i = 0; i < threads_num; i++)
 447   {
 448     if (threads[i] == 0)
 449       continue;
 450     pthread_join (threads[i], /* value_ptr = */ NULL);
 451   }
 452
 453   return (0);
 454 } /* }}} int evolution_start */
 455
 456 int main (int argc, char **argv) /* {{{ */
 457 {
 458   struct sigaction sigint_action;
 459   struct sigaction sigterm_action;
 460   int i;
 461
 462   population = population_create (ind_rate, ind_copy, ind_free);
 463   if (population == NULL)
 464   {
 465     fprintf (stderr, "population_create failed.\n");
 466     return (1);
 467   }
 468
 469 #if 0
 470   population_set_serialization (population,
 471       (pi_serialize_f) sn_network_serialize,
 472       (pi_unserialize_f) sn_network_unserialize);
 473 #endif
 474
 475   read_options (argc, argv);
 476   if (initial_input_file == NULL)
 477     exit_usage (argv[0]);
 478
 479   memset (&sigint_action, '\0', sizeof (sigint_action));
 480   sigint_action.sa_handler = sigint_handler;
 481   sigaction (SIGINT, &sigint_action, NULL);
 482
 483   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 484   sigterm_action.sa_handler = sigint_handler;
 485   sigaction (SIGTERM, &sigterm_action, NULL);
 486
 487   /* population_start_listen_thread (population, NULL, NULL); */
 488
 489   initial_network = sn_network_read_file (initial_input_file);
 490   if (initial_network == NULL)
 491   {
 492     fprintf (stderr, "Reading input file failed.\n");
 493     exit (EXIT_FAILURE);
 494   }
 495
 496   inputs_num = SN_NETWORK_INPUT_NUM(initial_network);
 497   if (outputs_num == 0)
 498     outputs_num = inputs_num / 2;
 499
 500   if (outputs_num >= inputs_num)
 501   {
 502     fprintf (stderr, "Number of inputs (%i) is smaller than "
 503         "(or equal to) the number of outputs (%i).\n",
 504         inputs_num, outputs_num);
 505     exit (EXIT_FAILURE);
 506   }
 507
 508   cuts_num = inputs_num - outputs_num;
 509   assert (cuts_num >= 1);
 510
 511   for (i = 0; i < max_population_size; i++)
 512   { /* create a random initial individuum */
 513     individuum_t *ind;
 514
 515     ind = calloc (inputs_num, sizeof (*ind));
 516     if (ind == NULL)
 517     {
 518       fprintf (stderr, "calloc failed.\n");
 519       exit (EXIT_FAILURE);
 520     }
 521     mutate (ind, /* num cuts = */ 0);
 522
 523     population_insert (population, ind);
 524     ind_free (ind);
 525   }
 526
 527   printf ("Current configuration:\n"
 528       "  Initial network:   %s\n"
 529       "  Number of inputs:  %3i\n"
 530       "  Number of outputs: %3i\n"
 531       "  Population size:   %3i\n"
 532       "=======================\n",
 533       initial_input_file, inputs_num, outputs_num, max_population_size);
 534
 535   evolution_start (evolution_threads_num);
 536
 537   printf ("Exiting after %"PRIu64" iterations.\n",
 538       iteration_counter);
 539
 540   {
 541     individuum_t *ind;
 542     sn_network_t *n;
 543
 544     ind = population_get_fittest (population);
 545     if (ind != NULL)
 546     {
 547       n = individuum_to_network (ind);
 548       if (best_output_file != NULL)
 549         sn_network_write_file (n, best_output_file);
 550       sn_network_show (n);
 551       sn_network_destroy (n);
 552
 553       ind_print (ind);
 554       free (ind);
 555     }
 556   }
 557
 558   population_destroy (population);
 559
 560   return (0);
 561 } /* }}} int main */
 562
 563 /* vim: set shiftwidth=2 softtabstop=2 et fdm=marker : */