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 rate_network (const sn_network_t *n) /* {{{ */
176 rate = SN_NETWORK_STAGE_NUM (n);
177 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
179 sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
180 rate += 2 * SN_STAGE_COMP_NUM (s);
184 } /* }}} int rate_network */
186 static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */
189 int mask[SN_NETWORK_INPUT_NUM (initial_network)];
191 memcpy (mask, ind, sizeof (mask));
193 n = sn_network_clone (initial_network);
197 sn_network_cut (n, mask);
199 sn_network_normalize (n);
200 sn_network_compress (n);
203 } /* }}} sn_network_t *individuum_to_network */
205 static int ind_rate (const void *arg) /* {{{ */
210 n = individuum_to_network (arg);
214 status = rate_network (n);
215 sn_network_destroy (n);
218 } /* }}} int ind_rate */
220 static void *ind_copy (const void *in) /* {{{ */
222 size_t s = sizeof (individuum_t) * inputs_num;
231 } /* }}} void *ind_copy */
233 static void ind_free (void *ind) /* {{{ */
237 } /* }}} void ind_free */
239 static void ind_print (const individuum_t *ind) /* {{{ */
243 for (i = 0; i < inputs_num; i++)
245 printf ("%3i: %s\n", i, (ind[i] == 0) ? "-" :
246 (ind[i] < 0) ? "MIN" : "MAX");
250 for (i = 0; i < inputs_num; i++)
254 printf (" %i:%s", i, (ind[i] < 0) ? "MIN" : "MAX");
257 } /* }}} void ind_print */
259 /* Simply makes sure the right amount of cutting positions exist. */
260 static void mutate (individuum_t *ind, int this_cuts_num) /* {{{ */
264 if (this_cuts_num < 0)
267 for (i = 0; i < inputs_num; i++)
272 while (this_cuts_num != cuts_num)
274 i = sn_bounded_random (0, inputs_num - 1);
276 if ((this_cuts_num < cuts_num)
279 ind[i] = (sn_bounded_random (0, 1) * 2) - 1;
280 assert (ind[i] != 0);
283 else if ((this_cuts_num > cuts_num)
290 } /* }}} void mutate */
292 static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */
294 individuum_t *offspring;
298 if ((i0 == NULL) || (i1 == NULL))
301 offspring = malloc (sizeof (*offspring) * inputs_num);
302 if (offspring == NULL)
304 memset (offspring, 0, sizeof (*offspring) * inputs_num);
307 for (i = 0; i < this_cuts_num; i++)
309 if (sn_bounded_random (0, 1) == 0)
310 offspring[i] = i0[i];
312 offspring[i] = i1[i];
314 if (offspring[i] != 0)
318 mutate (offspring, this_cuts_num);
321 } /* }}} individuum_t *recombine */
323 static int create_offspring (void) /* {{{ */
329 i0 = population_get_random (population);
330 i1 = population_get_random (population);
332 i2 = recombine (i0, i1);
334 population_insert (population, i2);
341 } /* }}} int create_offspring */
343 static void *evolution_thread (void *arg __attribute__((unused))) /* {{{ */
348 /* XXX: Not synchronized! */
353 } /* }}} int start_evolution */
355 static int evolution_start (int threads_num) /* {{{ */
357 pthread_t threads[threads_num]; /* C99 ftw! */
360 for (i = 0; i < threads_num; i++)
364 status = pthread_create (&threads[i], /* attr = */ NULL,
365 evolution_thread, /* arg = */ NULL);
368 fprintf (stderr, "evolution_start: pthread_create[%i] failed "
389 iter = iteration_counter;
391 ind = population_get_fittest (population);
392 n = individuum_to_network (ind);
394 rating = rate_network (n);
396 stages_num = SN_NETWORK_STAGE_NUM (n);
398 for (i = 0; i < stages_num; i++)
402 s = SN_NETWORK_STAGE_GET (n, i);
403 comparators_num += SN_STAGE_COMP_NUM (s);
406 sn_network_destroy (n);
409 printf ("Best after approximately %i iterations: "
410 "%i comparators in %i stages. Rating: %i.\n",
411 iter, comparators_num, stages_num, rating);
415 for (i = 0; i < threads_num; i++)
419 pthread_join (threads[i], /* value_ptr = */ NULL);
423 } /* }}} int evolution_start */
425 int main (int argc, char **argv) /* {{{ */
427 struct sigaction sigint_action;
428 struct sigaction sigterm_action;
431 population = population_create (ind_rate, ind_copy, ind_free);
432 if (population == NULL)
434 fprintf (stderr, "population_create failed.\n");
439 population_set_serialization (population,
440 (pi_serialize_f) sn_network_serialize,
441 (pi_unserialize_f) sn_network_unserialize);
444 read_options (argc, argv);
445 if (initial_input_file == NULL)
446 exit_usage (argv[0]);
448 memset (&sigint_action, '\0', sizeof (sigint_action));
449 sigint_action.sa_handler = sigint_handler;
450 sigaction (SIGINT, &sigint_action, NULL);
452 memset (&sigterm_action, '\0', sizeof (sigterm_action));
453 sigterm_action.sa_handler = sigint_handler;
454 sigaction (SIGTERM, &sigterm_action, NULL);
456 /* population_start_listen_thread (population, NULL, NULL); */
458 initial_network = sn_network_read_file (initial_input_file);
459 if (initial_network == NULL)
461 fprintf (stderr, "Reading input file failed.\n");
465 inputs_num = SN_NETWORK_INPUT_NUM(initial_network);
466 if (outputs_num == 0)
467 outputs_num = inputs_num / 2;
469 if (outputs_num >= inputs_num)
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);
477 cuts_num = inputs_num - outputs_num;
478 assert (cuts_num >= 1);
480 for (i = 0; i < max_population_size; i++)
481 { /* create a random initial individuum */
484 ind = calloc (inputs_num, sizeof (*ind));
487 fprintf (stderr, "calloc failed.\n");
490 mutate (ind, /* num cuts = */ 0);
492 population_insert (population, ind);
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);
504 evolution_start (evolution_threads_num);
506 printf ("Exiting after %"PRIu64" iterations.\n",
513 ind = population_get_fittest (population);
516 n = individuum_to_network (ind);
517 if (best_output_file != NULL)
518 sn_network_write_file (n, best_output_file);
520 sn_network_destroy (n);
527 population_destroy (population);
532 /* vim: set shiftwidth=2 softtabstop=2 et fdm=marker : */