2 * collectd - src/sn-evolution.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>
22 #ifndef _ISOC99_SOURCE
23 # define _ISOC99_SOURCE
25 #ifndef _POSIX_C_SOURCE
26 # define _POSIX_C_SOURCE 200112L
34 #include <sys/types.h>
46 #include <population.h>
48 #include "sn_network.h"
49 #include "sn_random.h"
51 #define SNE_MIN(a,b) ((a) < (b) ? (a) : (b))
52 #define SNE_MAX(a,b) ((a) > (b) ? (a) : (b))
54 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
56 char *strdup (const char *s);
58 static uint64_t iteration_counter = 0;
59 static int inputs_num = -1;
61 static int comparators_num = -1;
63 static char *initial_input_file = NULL;
64 static char *best_output_file = NULL;
66 static int stats_interval = 0;
68 static int max_population_size = 128;
69 static population_t *population;
71 static int evolution_threads_num = 4;
73 static int do_loop = 0;
75 static int weight_overall = 50;
76 static int weight_fails = 2;
77 static int weight_stages = 1;
79 static void sigint_handler (int signal)
82 } /* void sigint_handler */
84 static void exit_usage (const char *name)
86 printf ("Usage: %s [options]\n"
88 "Valid options are:\n"
89 " -i <inputs> Number of inputs\n"
90 " -c <comparators> Number of comparators\n"
91 " -I <file> Initial input file\n"
92 " -o <file> Write the current best solution to <file>\n"
93 " -p <num> Size of the population (default: 128)\n"
94 " -P <peer> Send individuals to <peer> (may be repeated)\n"
95 " -t <num> Number of threads (default: 4)\n"
99 } /* void exit_usage */
101 int read_options (int argc, char **argv)
105 while ((option = getopt (argc, argv, "i:c:I:o:p:P:s:t:h")) != -1)
123 comparators_num = tmp;
129 if (initial_input_file != NULL)
130 free (initial_input_file);
131 initial_input_file = strdup (optarg);
137 if (best_output_file != NULL)
138 free (best_output_file);
139 best_output_file = strdup (optarg);
145 int tmp = atoi (optarg);
148 max_population_size = tmp;
149 population_set_size (population, (size_t) max_population_size);
158 status = population_add_peer (population, optarg, /* port = */ NULL);
161 fprintf (stderr, "population_add_peer failed with status %i.\n",
169 int tmp = atoi (optarg);
171 stats_interval = tmp;
177 int tmp = atoi (optarg);
179 evolution_threads_num = tmp;
185 exit_usage (argv[0]);
190 } /* int read_options */
192 static int rate_network (sn_network_t *n) /* {{{ */
194 int test_pattern[n->inputs_num];
195 int values[n->inputs_num];
197 int patterns_sorted = 0;
198 int patterns_failed = 0;
200 memset (test_pattern, 0, sizeof (test_pattern));
208 /* Copy the current pattern and let the network sort it */
209 memcpy (values, test_pattern, sizeof (values));
210 status = sn_network_sort (n, values);
214 /* Check if the array is now sorted. */
215 previous = values[0];
217 for (i = 1; i < n->inputs_num; i++)
219 if (previous > values[i])
225 previous = values[i];
231 /* Generate the next test pattern */
233 for (i = 0; i < n->inputs_num; i++)
235 if (test_pattern[i] == 0)
248 /* Break out of the while loop if we tested all possible patterns */
253 /* All tests successfull */
254 return (weight_overall + (weight_stages * SN_NETWORK_STAGE_NUM (n)) + (weight_fails * patterns_failed));
255 } /* }}} int rate_network */
257 static sn_comparator_t get_random_comparator (void) /* {{{ */
261 c.min = sn_bounded_random (0, inputs_num - 1);
263 while (c.max == c.min)
264 c.max = sn_bounded_random (0, inputs_num - 1);
267 } /* }}} sn_comparator_t get_random_comparator */
269 static int mutate_network (sn_comparator_t *comparators, int comparators_num)
271 static int old_comparators_num = -1;
272 static double mutate_probability = 0.0;
276 if (old_comparators_num != comparators_num)
278 /* Probability that NO mutation takes place: 1/3 */
279 mutate_probability = powl (1.0 / 3.0, (1.0 / ((double) comparators_num)));
280 old_comparators_num = comparators_num;
283 /* `mutate_probability' actually holds 1-p, i. e. it is close to one */
284 for (i = 0; i < comparators_num; i++)
285 if (sn_double_random () >= mutate_probability)
286 comparators[i] = get_random_comparator ();
289 } /* int mutate_network */
291 static int create_offspring (void)
294 sn_comparator_t p0_comparators[comparators_num];
295 int p0_comparators_num;
298 sn_comparator_t p1_comparators[comparators_num];
299 int p1_comparators_num;
302 sn_comparator_t n_comparators[comparators_num];
303 int n_comparators_num;
307 p0 = population_get_random (population);
308 p1 = population_get_random (population);
313 p0_comparators_num = 0;
314 for (i = 0; i < SN_NETWORK_STAGE_NUM (p0); i++)
319 s = SN_NETWORK_STAGE_GET (p0, i);
321 for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
325 c = SN_STAGE_COMP_GET (s, j);
326 p0_comparators[p0_comparators_num] = *c;
327 p0_comparators_num++;
330 while (p0_comparators_num < comparators_num)
332 p0_comparators[p0_comparators_num] = get_random_comparator ();
333 p0_comparators_num++;
335 sn_network_destroy (p0);
338 p1_comparators_num = 0;
339 for (i = 0; i < SN_NETWORK_STAGE_NUM (p1); i++)
344 s = SN_NETWORK_STAGE_GET (p1, i);
346 for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
350 c = SN_STAGE_COMP_GET (s, j);
351 p1_comparators[p1_comparators_num] = *c;
352 p1_comparators_num++;
355 while (p1_comparators_num < comparators_num)
357 p1_comparators[p1_comparators_num] = get_random_comparator ();
358 p1_comparators_num++;
360 sn_network_destroy (p1);
363 n_comparators_num = sn_bounded_random (SNE_MIN (p0_comparators_num, p1_comparators_num),
364 SNE_MAX (p0_comparators_num, p1_comparators_num));
366 for (i = 0; i < n_comparators_num; i++)
368 if (i >= p0_comparators_num)
369 n_comparators[i] = p1_comparators[i];
370 else if (i >= p1_comparators_num)
371 n_comparators[i] = p0_comparators[i];
372 else if (sn_bounded_random (0, 1) == 0)
373 n_comparators[i] = p1_comparators[i];
375 n_comparators[i] = p0_comparators[i];
379 mutate_network (n_comparators, n_comparators_num);
381 n = sn_network_create (inputs_num);
382 for (i = 0; i < n_comparators_num; i++)
383 sn_network_comparator_add (n, &n_comparators[i]);
385 /* compress the network to get a compact representation */
386 sn_network_compress (n);
388 assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
390 population_insert (population, n);
392 sn_network_destroy (n);
395 } /* int create_offspring */
397 static void *evolution_thread (void *arg)
402 /* XXX: Not synchronized! */
407 } /* int start_evolution */
409 static int evolution_start (int threads_num)
411 pthread_t threads[threads_num]; /* C99 ftw! */
414 for (i = 0; i < threads_num; i++)
418 status = pthread_create (&threads[i], /* attr = */ NULL,
419 evolution_thread, /* arg = */ NULL);
422 fprintf (stderr, "evolution_start: pthread_create[%i] failed "
442 iter = iteration_counter;
444 n = population_get_fittest (population);
446 rating = rate_network (n);
448 stages_num = SN_NETWORK_STAGE_NUM (n);
450 for (i = 0; i < stages_num; i++)
454 s = SN_NETWORK_STAGE_GET (n, i);
455 comparators_num += SN_STAGE_COMP_NUM (s);
458 sn_network_destroy (n);
460 printf ("Best after approximately %i iterations: "
461 "%i comparators in %i stages. Rating: %i (%i not sorted).\n",
462 iter, comparators_num, stages_num, rating,
463 (rating - (weight_overall + (weight_stages * stages_num))) / weight_fails);
467 for (i = 0; i < threads_num; i++)
471 pthread_join (threads[i], /* value_ptr = */ NULL);
475 } /* int evolution_start */
477 int main (int argc, char **argv)
479 struct sigaction sigint_action;
480 struct sigaction sigterm_action;
482 population = population_create ((pi_rate_f) rate_network,
483 (pi_copy_f) sn_network_clone,
484 (pi_free_f) sn_network_destroy);
485 if (population == NULL)
487 fprintf (stderr, "population_create failed.\n");
491 population_set_serialization (population,
492 (pi_serialize_f) sn_network_serialize,
493 (pi_unserialize_f) sn_network_unserialize);
495 read_options (argc, argv);
497 if ((inputs_num <= 0) || (comparators_num <= 0))
498 exit_usage (argv[0]);
500 memset (&sigint_action, '\0', sizeof (sigint_action));
501 sigint_action.sa_handler = sigint_handler;
502 sigaction (SIGINT, &sigint_action, NULL);
504 memset (&sigterm_action, '\0', sizeof (sigterm_action));
505 sigterm_action.sa_handler = sigint_handler;
506 sigaction (SIGTERM, &sigterm_action, NULL);
508 population_start_listen_thread (population, NULL, NULL);
510 if (initial_input_file != NULL)
514 n = sn_network_read_file (initial_input_file);
517 fprintf (stderr, "Cannot read network from `%s'.\n",
522 if (n->inputs_num != inputs_num)
524 fprintf (stderr, "Network `%s' has %i inputs, but %i were configured "
525 "on the command line.\n",
526 initial_input_file, n->inputs_num, inputs_num);
530 population_insert (population, n);
531 sn_network_destroy (n);
533 else /* if (initial_input_file == NULL) */
538 n = sn_network_create (inputs_num);
539 for (i = 0; i < comparators_num; i++)
543 c = get_random_comparator ();
544 sn_network_comparator_add (n, &c);
547 population_insert (population, n);
548 sn_network_destroy (n);
551 printf ("Current configuration:\n"
552 " Number of inputs: %3i\n"
553 " Number of comparators: %3i\n"
554 " Population size: %3i\n"
555 "=======================\n",
556 inputs_num, comparators_num, max_population_size);
558 evolution_start (evolution_threads_num);
560 printf ("Exiting after %llu iterations.\n",
561 (unsigned long long) iteration_counter);
566 n = population_get_fittest (population);
569 if (best_output_file != NULL)
570 sn_network_write_file (n, best_output_file);
572 sn_network_destroy (n);
576 population_destroy (population);
581 /* vim: set shiftwidth=2 softtabstop=2 : */