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