2 * collectd - 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 individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */
262 individuum_t *offspring;
266 if ((i0 == NULL) || (i1 == NULL))
269 offspring = malloc (sizeof (*offspring) * cuts_num);
270 if (offspring == NULL)
272 memset (offspring, 0, sizeof (*offspring) * cuts_num);
274 cut_at = sn_bounded_random (0, cuts_num);
275 for (i = 0; i < cuts_num; i++)
278 offspring[i] = i0[i];
280 offspring[i] = i1[i];
284 } /* }}} individuum_t *recombine */
286 static void random_cut (individuum_t *ind, int index) /* {{{ */
288 int max_input = inputs_num - index;
291 while (ind[index] == 0)
292 ind[index] = sn_bounded_random ((-1) * max_input, max_input);
293 } /* }}} void random_cut */
295 static void mutate (individuum_t *ind) /* {{{ */
300 reset_input = sn_bounded_random (0, 3 * cuts_num);
301 for (i = 0; i < cuts_num; i++)
303 if (reset_input == i)
306 if (sn_bounded_random (0, 100))
309 } /* }}} void mutate */
311 static int create_offspring (void) /* {{{ */
317 i0 = population_get_random (population);
318 i1 = population_get_random (population);
320 i2 = recombine (i0, i1);
323 population_insert (population, i2);
330 } /* }}} int create_offspring */
332 static void *evolution_thread (void *arg __attribute__((unused))) /* {{{ */
337 /* XXX: Not synchronized! */
342 } /* }}} int start_evolution */
344 static int evolution_start (int threads_num) /* {{{ */
346 pthread_t threads[threads_num]; /* C99 ftw! */
349 for (i = 0; i < threads_num; i++)
353 status = pthread_create (&threads[i], /* attr = */ NULL,
354 evolution_thread, /* arg = */ NULL);
357 fprintf (stderr, "evolution_start: pthread_create[%i] failed "
378 iter = iteration_counter;
380 ind = population_get_fittest (population);
381 n = individuum_to_network (ind);
383 rating = rate_network (n);
385 stages_num = SN_NETWORK_STAGE_NUM (n);
387 for (i = 0; i < stages_num; i++)
391 s = SN_NETWORK_STAGE_GET (n, i);
392 comparators_num += SN_STAGE_COMP_NUM (s);
395 sn_network_destroy (n);
398 printf ("Best after approximately %i iterations: "
399 "%i comparators in %i stages. Rating: %i.\n",
400 iter, comparators_num, stages_num, rating);
404 for (i = 0; i < threads_num; i++)
408 pthread_join (threads[i], /* value_ptr = */ NULL);
412 } /* }}} int evolution_start */
414 int main (int argc, char **argv) /* {{{ */
416 struct sigaction sigint_action;
417 struct sigaction sigterm_action;
420 population = population_create (ind_rate, ind_copy, ind_free);
421 if (population == NULL)
423 fprintf (stderr, "population_create failed.\n");
428 population_set_serialization (population,
429 (pi_serialize_f) sn_network_serialize,
430 (pi_unserialize_f) sn_network_unserialize);
433 read_options (argc, argv);
434 if (initial_input_file == NULL)
435 exit_usage (argv[0]);
437 memset (&sigint_action, '\0', sizeof (sigint_action));
438 sigint_action.sa_handler = sigint_handler;
439 sigaction (SIGINT, &sigint_action, NULL);
441 memset (&sigterm_action, '\0', sizeof (sigterm_action));
442 sigterm_action.sa_handler = sigint_handler;
443 sigaction (SIGTERM, &sigterm_action, NULL);
445 /* population_start_listen_thread (population, NULL, NULL); */
447 initial_network = sn_network_read_file (initial_input_file);
448 if (initial_network == NULL)
450 fprintf (stderr, "Reading input file failed.\n");
454 inputs_num = SN_NETWORK_INPUT_NUM(initial_network);
455 if (outputs_num == 0)
456 outputs_num = inputs_num / 2;
458 if (outputs_num >= inputs_num)
460 fprintf (stderr, "Number of inputs (%i) is smaller than "
461 "(or equal to) the number of outputs (%i).\n",
462 inputs_num, outputs_num);
466 cuts_num = inputs_num - outputs_num;
467 assert (cuts_num >= 1);
469 for (i = 0; i < max_population_size; i++)
470 { /* create a random initial individuum */
474 ind = malloc (sizeof (*ind) * cuts_num);
477 fprintf (stderr, "malloc failed.\n");
481 for (i = 0; i < cuts_num; i++)
484 population_insert (population, ind);
488 printf ("Current configuration:\n"
489 " Initial network: %s\n"
490 " Number of inputs: %3i\n"
491 " Number of outputs: %3i\n"
492 " Population size: %3i\n"
493 "=======================\n",
494 initial_input_file, inputs_num, outputs_num, max_population_size);
496 evolution_start (evolution_threads_num);
498 printf ("Exiting after %"PRIu64" iterations.\n",
505 ind = population_get_fittest (population);
508 n = individuum_to_network (ind);
509 if (best_output_file != NULL)
510 sn_network_write_file (n, best_output_file);
512 sn_network_destroy (n);
516 population_destroy (population);
521 /* vim: set shiftwidth=2 softtabstop=2 et fdm=marker : */