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 rate_network (const sn_network_t *n) /* {{{ */
 172 {
 173   int rate;
 174   int i;
 175
 176   rate = SN_NETWORK_STAGE_NUM (n);
 177   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 178   {
 179     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 180     rate += 2 * SN_STAGE_COMP_NUM (s);
 181   }
 182
 183   return (rate);
 184 } /* }}} int rate_network */
 185
 186 static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */
 187 {
 188   sn_network_t *n;
 189   int mask[SN_NETWORK_INPUT_NUM (initial_network)];
 190
 191   memcpy (mask, ind, sizeof (mask));
 192
 193   n = sn_network_clone (initial_network);
 194   if (n == NULL)
 195     return (NULL);
 196
 197   sn_network_cut (n, mask);
 198
 199   sn_network_normalize (n);
 200   sn_network_compress (n);
 201
 202   return (n);
 203 } /* }}} sn_network_t *individuum_to_network */
 204
 205 static int ind_rate (const void *arg) /* {{{ */
 206 {
 207   sn_network_t *n;
 208   int status;
 209
 210   n = individuum_to_network (arg);
 211   if (n == NULL)
 212     return (-1);
 213
 214   status = rate_network (n);
 215   sn_network_destroy (n);
 216
 217   return (status);
 218 } /* }}} int ind_rate */
 219
 220 static void *ind_copy (const void *in) /* {{{ */
 221 {
 222   size_t s = sizeof (individuum_t) * inputs_num;
 223   void *out;
 224
 225   out = malloc (s);
 226   if (out == NULL)
 227     return (NULL);
 228
 229   memcpy (out, in, s);
 230   return (out);
 231 } /* }}} void *ind_copy */
 232
 233 static void ind_free (void *ind) /* {{{ */
 234 {
 235   if (ind != NULL)
 236     free (ind);
 237 } /* }}} void ind_free */
 238
 239 static void ind_print (const individuum_t *ind) /* {{{ */
 240 {
 241   int i;
 242
 243   for (i = 0; i < inputs_num; i++)
 244   {
 245     printf ("%3i: %s\n", i, (ind[i] == 0) ? "-" :
 246         (ind[i] < 0) ? "MIN" : "MAX");
 247   }
 248
 249   printf ("# sn-cut");
 250   for (i = 0; i < inputs_num; i++)
 251   {
 252     if (ind[i] == 0)
 253       continue;
 254     printf (" %i:%s", i, (ind[i] < 0) ? "MIN" : "MAX");
 255   }
 256   printf ("\n");
 257 } /* }}} void ind_print */
 258
 259 /* Simply makes sure the right amount of cutting positions exist. */
 260 static void mutate (individuum_t *ind, int this_cuts_num) /* {{{ */
 261 {
 262   int i;
 263
 264   if (this_cuts_num < 0)
 265   {
 266     this_cuts_num = 0;
 267     for (i = 0; i < inputs_num; i++)
 268       if (ind[i] != 0)
 269         this_cuts_num++;
 270   }
 271
 272   while (this_cuts_num != cuts_num)
 273   {
 274     i = sn_bounded_random (0, inputs_num - 1);
 275
 276     if ((this_cuts_num < cuts_num)
 277         && (ind[i] == 0))
 278     {
 279       ind[i] = (sn_bounded_random (0, 1) * 2) - 1;
 280       assert (ind[i] != 0);
 281       this_cuts_num++;
 282     }
 283     else if ((this_cuts_num > cuts_num)
 284         && (ind[i] != 0))
 285     {
 286       ind[i] = 0;
 287       this_cuts_num--;
 288     }
 289   }
 290 } /* }}} void mutate */
 291
 292 static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */
 293 {
 294   individuum_t *offspring;
 295   int this_cuts_num;
 296   int i;
 297
 298   if ((i0 == NULL) || (i1 == NULL))
 299     return (NULL);
 300
 301   offspring = malloc (sizeof (*offspring) * inputs_num);
 302   if (offspring == NULL)
 303     return (NULL);
 304   memset (offspring, 0, sizeof (*offspring) * inputs_num);
 305
 306   this_cuts_num = 0;
 307   for (i = 0; i < this_cuts_num; i++)
 308   {
 309     if (sn_bounded_random (0, 1) == 0)
 310       offspring[i] = i0[i];
 311     else
 312       offspring[i] = i1[i];
 313
 314     if (offspring[i] != 0)
 315       this_cuts_num++;
 316   }
 317
 318   mutate (offspring, this_cuts_num);
 319
 320   return (offspring);
 321 } /* }}} individuum_t *recombine */
 322
 323 static int create_offspring (void) /* {{{ */
 324 {
 325   individuum_t *i0;
 326   individuum_t *i1;
 327   individuum_t *i2;
 328
 329   i0 = population_get_random (population);
 330   i1 = population_get_random (population);
 331
 332   i2 = recombine (i0, i1);
 333
 334   population_insert (population, i2);
 335
 336   free (i0);
 337   free (i1);
 338   free (i2);
 339
 340   return (0);
 341 } /* }}} int create_offspring */
 342
 343 static void *evolution_thread (void *arg __attribute__((unused))) /* {{{ */
 344 {
 345   while (do_loop == 0)
 346   {
 347     create_offspring ();
 348     /* XXX: Not synchronized! */
 349     iteration_counter++;
 350   }
 351
 352   return ((void *) 0);
 353 } /* }}} int start_evolution */
 354
 355 static int evolution_start (int threads_num) /* {{{ */
 356 {
 357   pthread_t threads[threads_num]; /* C99 ftw! */
 358   int i;
 359
 360   for (i = 0; i < threads_num; i++)
 361   {
 362     int status;
 363
 364     status = pthread_create (&threads[i], /* attr = */ NULL,
 365         evolution_thread, /* arg = */ NULL);
 366     if (status != 0)
 367     {
 368       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 369           "with status %i.\n",
 370           i, status);
 371       threads[i] = 0;
 372     }
 373   }
 374
 375   while (do_loop == 0)
 376   {
 377     int status;
 378
 379     status = sleep (1);
 380     if (status == 0)
 381     {
 382       individuum_t *ind;
 383       sn_network_t *n;
 384       int stages_num;
 385       int comparators_num;
 386       int rating;
 387       int iter;
 388
 389       iter = iteration_counter;
 390
 391       ind = population_get_fittest (population);
 392       n = individuum_to_network (ind);
 393
 394       rating = rate_network (n);
 395
 396       stages_num = SN_NETWORK_STAGE_NUM (n);
 397       comparators_num = 0;
 398       for (i = 0; i < stages_num; i++)
 399       {
 400         sn_stage_t *s;
 401
 402         s = SN_NETWORK_STAGE_GET (n, i);
 403         comparators_num += SN_STAGE_COMP_NUM (s);
 404       }
 405
 406       sn_network_destroy (n);
 407       ind_free (ind);
 408
 409       printf ("Best after approximately %i iterations: "
 410           "%i comparators in %i stages. Rating: %i.\n",
 411           iter, comparators_num, stages_num, rating);
 412     }
 413   }
 414
 415   for (i = 0; i < threads_num; i++)
 416   {
 417     if (threads[i] == 0)
 418       continue;
 419     pthread_join (threads[i], /* value_ptr = */ NULL);
 420   }
 421
 422   return (0);
 423 } /* }}} int evolution_start */
 424
 425 int main (int argc, char **argv) /* {{{ */
 426 {
 427   struct sigaction sigint_action;
 428   struct sigaction sigterm_action;
 429   int i;
 430
 431   population = population_create (ind_rate, ind_copy, ind_free);
 432   if (population == NULL)
 433   {
 434     fprintf (stderr, "population_create failed.\n");
 435     return (1);
 436   }
 437
 438 #if 0
 439   population_set_serialization (population,
 440       (pi_serialize_f) sn_network_serialize,
 441       (pi_unserialize_f) sn_network_unserialize);
 442 #endif
 443
 444   read_options (argc, argv);
 445   if (initial_input_file == NULL)
 446     exit_usage (argv[0]);
 447
 448   memset (&sigint_action, '\0', sizeof (sigint_action));
 449   sigint_action.sa_handler = sigint_handler;
 450   sigaction (SIGINT, &sigint_action, NULL);
 451
 452   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 453   sigterm_action.sa_handler = sigint_handler;
 454   sigaction (SIGTERM, &sigterm_action, NULL);
 455
 456   /* population_start_listen_thread (population, NULL, NULL); */
 457
 458   initial_network = sn_network_read_file (initial_input_file);
 459   if (initial_network == NULL)
 460   {
 461     fprintf (stderr, "Reading input file failed.\n");
 462     exit (EXIT_FAILURE);
 463   }
 464
 465   inputs_num = SN_NETWORK_INPUT_NUM(initial_network);
 466   if (outputs_num == 0)
 467     outputs_num = inputs_num / 2;
 468
 469   if (outputs_num >= inputs_num)
 470   {
 471     fprintf (stderr, "Number of inputs (%i) is smaller than "
 472         "(or equal to) the number of outputs (%i).\n",
 473         inputs_num, outputs_num);
 474     exit (EXIT_FAILURE);
 475   }
 476
 477   cuts_num = inputs_num - outputs_num;
 478   assert (cuts_num >= 1);
 479
 480   for (i = 0; i < max_population_size; i++)
 481   { /* create a random initial individuum */
 482     individuum_t *ind;
 483
 484     ind = calloc (inputs_num, sizeof (*ind));
 485     if (ind == NULL)
 486     {
 487       fprintf (stderr, "calloc failed.\n");
 488       exit (EXIT_FAILURE);
 489     }
 490     mutate (ind, /* num cuts = */ 0);
 491
 492     population_insert (population, ind);
 493     ind_free (ind);
 494   }
 495
 496   printf ("Current configuration:\n"
 497       "  Initial network:   %s\n"
 498       "  Number of inputs:  %3i\n"
 499       "  Number of outputs: %3i\n"
 500       "  Population size:   %3i\n"
 501       "=======================\n",
 502       initial_input_file, inputs_num, outputs_num, max_population_size);
 503
 504   evolution_start (evolution_threads_num);
 505
 506   printf ("Exiting after %"PRIu64" iterations.\n",
 507       iteration_counter);
 508
 509   {
 510     individuum_t *ind;
 511     sn_network_t *n;
 512
 513     ind = population_get_fittest (population);
 514     if (ind != NULL)
 515     {
 516       n = individuum_to_network (ind);
 517       if (best_output_file != NULL)
 518         sn_network_write_file (n, best_output_file);
 519       sn_network_show (n);
 520       sn_network_destroy (n);
 521
 522       ind_print (ind);
 523       free (ind);
 524     }
 525   }
 526
 527   population_destroy (population);
 528
 529   return (0);
 530 } /* }}} int main */
 531
 532 /* vim: set shiftwidth=2 softtabstop=2 et fdm=marker : */