2 * libsortnetwork - src/sn-evolution-cut.c
3 * Copyright (C) 2008-2010 Florian octo Forster
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.
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.
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
19 * Florian octo Forster <ff at octo.it>
30 #include <sys/types.h>
40 #include <population.h>
42 #include "sn_network.h"
43 #include "sn_random.h"
45 #if !defined(__GNUC__) || !__GNUC__
46 # define __attribute__(x) /**/
49 typedef int individuum_t;
51 static int inputs_num = 0;
52 static int outputs_num = 0;
53 static int cuts_num = 0;
55 static char *initial_input_file = NULL;
56 static const sn_network_t *initial_network = NULL;
57 static char *best_output_file = NULL;
59 static int stats_interval = 0;
61 static int max_population_size = 128;
62 static population_t *population = NULL;
64 static int evolution_threads_num = 4;
66 static int do_loop = 0;
67 static uint64_t iteration_counter = 0;
69 static void sigint_handler (int signal __attribute__((unused)))
72 } /* void sigint_handler */
74 static void exit_usage (const char *name)
76 printf ("Usage: %s [options]\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"
88 } /* void exit_usage */
90 int read_options (int argc, char **argv) /* {{{ */
94 while ((option = getopt (argc, argv, "i:o:O:p:P:s:t:h")) != -1)
100 if (initial_input_file != NULL)
101 free (initial_input_file);
102 initial_input_file = strdup (optarg);
108 if (best_output_file != NULL)
109 free (best_output_file);
110 best_output_file = strdup (optarg);
116 int tmp = atoi (optarg);
124 int tmp = atoi (optarg);
127 max_population_size = tmp;
128 population_set_size (population, (size_t) max_population_size);
137 status = population_add_peer (population, optarg, /* port = */ NULL);
140 fprintf (stderr, "population_add_peer failed with status %i.\n",
148 int tmp = atoi (optarg);
150 stats_interval = tmp;
156 int tmp = atoi (optarg);
158 evolution_threads_num = tmp;
164 exit_usage (argv[0]);
169 } /* }}} int read_options */
171 static int apply_cut (sn_network_t *n, int input) /* {{{ */
173 enum sn_network_cut_dir_e dir = DIR_MAX;
182 return (sn_network_cut_at (n, input, dir));
183 } /* }}} int apply_cut */
185 static int apply (sn_network_t *n, const individuum_t *ind) /* {{{ */
189 for (i = 0; i < cuts_num; i++)
190 apply_cut (n, ind[i]);
193 } /* }}} int apply */
195 static int rate_network (const sn_network_t *n) /* {{{ */
200 rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
201 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
203 sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
204 rate += SN_STAGE_COMP_NUM (s);
208 } /* }}} int rate_network */
210 static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */
214 n = sn_network_clone (initial_network);
220 sn_network_normalize (n);
221 sn_network_compress (n);
224 } /* }}} sn_network_t *individuum_to_network */
226 static int ind_rate (const void *arg) /* {{{ */
231 n = individuum_to_network (arg);
235 status = rate_network (n);
236 sn_network_destroy (n);
239 } /* }}} int ind_rate */
241 static void *ind_copy (const void *in) /* {{{ */
243 size_t s = sizeof (individuum_t) * cuts_num;
252 } /* }}} void *ind_copy */
254 static void ind_free (void *ind) /* {{{ */
258 } /* }}} void ind_free */
260 static void ind_print (const individuum_t *ind)
264 for (i = 0; i < cuts_num; i++)
276 printf ("%s(%3i)\n", (dir == 0) ? "MAX" : "MIN", input);
278 } /* }}} void ind_print */
280 static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */
282 individuum_t *offspring;
286 if ((i0 == NULL) || (i1 == NULL))
289 offspring = malloc (sizeof (*offspring) * cuts_num);
290 if (offspring == NULL)
292 memset (offspring, 0, sizeof (*offspring) * cuts_num);
294 cut_at = sn_bounded_random (0, cuts_num);
295 for (i = 0; i < cuts_num; i++)
298 offspring[i] = i0[i];
300 offspring[i] = i1[i];
304 } /* }}} individuum_t *recombine */
306 static void random_cut (individuum_t *ind, int index) /* {{{ */
308 int max_input = inputs_num - index;
311 while (ind[index] == 0)
312 ind[index] = sn_bounded_random ((-1) * max_input, max_input);
313 } /* }}} void random_cut */
315 static void mutate (individuum_t *ind) /* {{{ */
320 reset_input = sn_bounded_random (0, 3 * cuts_num);
321 for (i = 0; i < cuts_num; i++)
323 if (reset_input == i)
326 if (sn_bounded_random (0, 100))
329 } /* }}} void mutate */
331 static int create_offspring (void) /* {{{ */
337 i0 = population_get_random (population);
338 i1 = population_get_random (population);
340 i2 = recombine (i0, i1);
343 population_insert (population, i2);
350 } /* }}} int create_offspring */
352 static void *evolution_thread (void *arg __attribute__((unused))) /* {{{ */
357 /* XXX: Not synchronized! */
362 } /* }}} int start_evolution */
364 static int evolution_start (int threads_num) /* {{{ */
366 pthread_t threads[threads_num]; /* C99 ftw! */
369 for (i = 0; i < threads_num; i++)
373 status = pthread_create (&threads[i], /* attr = */ NULL,
374 evolution_thread, /* arg = */ NULL);
377 fprintf (stderr, "evolution_start: pthread_create[%i] failed "
398 iter = iteration_counter;
400 ind = population_get_fittest (population);
401 n = individuum_to_network (ind);
403 rating = rate_network (n);
405 stages_num = SN_NETWORK_STAGE_NUM (n);
407 for (i = 0; i < stages_num; i++)
411 s = SN_NETWORK_STAGE_GET (n, i);
412 comparators_num += SN_STAGE_COMP_NUM (s);
415 sn_network_destroy (n);
418 printf ("Best after approximately %i iterations: "
419 "%i comparators in %i stages. Rating: %i.\n",
420 iter, comparators_num, stages_num, rating);
424 for (i = 0; i < threads_num; i++)
428 pthread_join (threads[i], /* value_ptr = */ NULL);
432 } /* }}} int evolution_start */
434 int main (int argc, char **argv) /* {{{ */
436 struct sigaction sigint_action;
437 struct sigaction sigterm_action;
440 population = population_create (ind_rate, ind_copy, ind_free);
441 if (population == NULL)
443 fprintf (stderr, "population_create failed.\n");
448 population_set_serialization (population,
449 (pi_serialize_f) sn_network_serialize,
450 (pi_unserialize_f) sn_network_unserialize);
453 read_options (argc, argv);
454 if (initial_input_file == NULL)
455 exit_usage (argv[0]);
457 memset (&sigint_action, '\0', sizeof (sigint_action));
458 sigint_action.sa_handler = sigint_handler;
459 sigaction (SIGINT, &sigint_action, NULL);
461 memset (&sigterm_action, '\0', sizeof (sigterm_action));
462 sigterm_action.sa_handler = sigint_handler;
463 sigaction (SIGTERM, &sigterm_action, NULL);
465 /* population_start_listen_thread (population, NULL, NULL); */
467 initial_network = sn_network_read_file (initial_input_file);
468 if (initial_network == NULL)
470 fprintf (stderr, "Reading input file failed.\n");
474 inputs_num = SN_NETWORK_INPUT_NUM(initial_network);
475 if (outputs_num == 0)
476 outputs_num = inputs_num / 2;
478 if (outputs_num >= inputs_num)
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);
486 cuts_num = inputs_num - outputs_num;
487 assert (cuts_num >= 1);
489 for (i = 0; i < max_population_size; i++)
490 { /* create a random initial individuum */
494 ind = malloc (sizeof (*ind) * cuts_num);
497 fprintf (stderr, "malloc failed.\n");
501 for (i = 0; i < cuts_num; i++)
504 population_insert (population, ind);
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);
516 evolution_start (evolution_threads_num);
518 printf ("Exiting after %"PRIu64" iterations.\n",
525 ind = population_get_fittest (population);
528 n = individuum_to_network (ind);
529 if (best_output_file != NULL)
530 sn_network_write_file (n, best_output_file);
532 sn_network_destroy (n);
539 population_destroy (population);
544 /* vim: set shiftwidth=2 softtabstop=2 et fdm=marker : */