2 * libsortnetwork - 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 200809L
29 # define _XOPEN_SOURCE 700
37 #include <sys/types.h>
49 #include <population.h>
51 #include "sn_network.h"
52 #include "sn_random.h"
54 #define SNE_MIN(a,b) ((a) < (b) ? (a) : (b))
55 #define SNE_MAX(a,b) ((a) > (b) ? (a) : (b))
57 #if !defined(__GNUC__) || !__GNUC__
58 # define __attribute__(x) /**/
61 static int inputs_left = 0;
62 static int inputs_right = 0;
63 static int comparators_num = -1;
65 static uint64_t iteration_counter = 0;
67 static char *initial_input_file = NULL;
68 static char *best_output_file = NULL;
70 static int stats_interval = 0;
72 static int max_population_size = 128;
73 static population_t *population;
75 static int evolution_threads_num = 4;
77 static int do_loop = 0;
78 static int weight_overall = 250;
79 static int weight_fails = 10;
80 static int weight_stages = 1;
81 static int weight_comparators = 2;
83 static void sigint_handler (__attribute__((unused)) int signal)
86 } /* void sigint_handler */
87 static void exit_usage (const char *name) /* {{{ */
89 printf ("Usage: %s [options]\n"
91 "Valid options are:\n"
92 " -i <inputs>[:<inputs>] Number of inputs (left and right)\n"
93 " -c <comparators> Number of comparators\n"
94 " -I <file> Initial input file\n"
95 " -o <file> Write the current best solution to <file>\n"
96 " -p <num> Size of the population (default: 128)\n"
97 " -P <peer> Send individuals to <peer> (may be repeated)\n"
98 " -t <num> Number of threads (default: 4)\n"
102 } /* }}} void exit_usage */
104 int read_options (int argc, char **argv) /* {{{ */
108 while ((option = getopt (argc, argv, "i:c:I:o:p:P:s:t:h")) != -1)
119 tmp_str = strchr (optarg, ':');
124 tmp_right = atoi (tmp_str);
131 tmp_left = atoi (optarg);
134 exit_usage (argv[0]);
137 tmp_right = tmp_left;
139 inputs_left = tmp_left;
140 inputs_right = tmp_right;
150 comparators_num = tmp;
156 if (initial_input_file != NULL)
157 free (initial_input_file);
158 initial_input_file = strdup (optarg);
164 if (best_output_file != NULL)
165 free (best_output_file);
166 best_output_file = strdup (optarg);
172 int tmp = atoi (optarg);
175 max_population_size = tmp;
176 population_set_size (population, (size_t) max_population_size);
185 status = population_add_peer (population, optarg, /* port = */ NULL);
188 fprintf (stderr, "population_add_peer failed with status %i.\n",
196 int tmp = atoi (optarg);
198 stats_interval = tmp;
204 int tmp = atoi (optarg);
206 evolution_threads_num = tmp;
212 exit_usage (argv[0]);
217 } /* }}} int read_options */
219 static int rate_network (sn_network_t *n) /* {{{ */
221 int test_pattern[n->inputs_num];
222 int values[n->inputs_num];
224 int patterns_failed = 0;
231 assert (n->inputs_num == (inputs_left + inputs_right));
233 memset (test_pattern, 0, sizeof (test_pattern));
234 for (i = 0; i < inputs_left; i++)
237 for (zeros_left = 0; zeros_left <= inputs_left; zeros_left++)
243 test_pattern[zeros_left - 1] = 0;
245 for (i = 0; i < inputs_right; i++)
246 test_pattern[inputs_left + i] = 1;
248 for (zeros_right = 0; zeros_right <= inputs_right; zeros_right++)
251 test_pattern[inputs_left + zeros_right - 1] = 0;
253 /* Copy the current pattern and let the network sort it */
254 memcpy (values, test_pattern, sizeof (values));
255 status = sn_network_sort (n, values);
259 /* Check if the array is now sorted. */
260 previous = values[0];
262 for (i = 1; i < n->inputs_num; i++)
264 if (previous > values[i])
270 previous = values[i];
272 } /* for (zeros_right) */
273 } /* for (zeros_left) */
275 /* All tests successfull */
276 return (weight_overall
277 + (weight_comparators * sn_network_get_comparator_num (n))
278 + (weight_stages * SN_NETWORK_STAGE_NUM (n))
279 + (weight_fails * patterns_failed));
280 } /* }}} int rate_network */
282 static sn_comparator_t get_random_comparator (void) /* {{{ */
286 c.min = sn_bounded_random (0, inputs_left + inputs_right - 1);
288 while (c.max == c.min)
289 c.max = sn_bounded_random (0, inputs_left + inputs_right - 1);
301 } /* }}} sn_comparator_t get_random_comparator */
303 static int mutate_network (sn_comparator_t *comparators, /* {{{ */
306 static int old_comparators_num = -1;
307 static double mutate_probability = 0.0;
311 if (old_comparators_num != comparators_num)
313 /* Probability that NO mutation takes place: 1/8 */
314 mutate_probability = powl (1.0 / 8.0, (1.0 / ((double) comparators_num)));
315 old_comparators_num = comparators_num;
318 /* `mutate_probability' actually holds 1-p, i. e. it is close to one */
319 for (i = 0; i < comparators_num; i++)
320 if (sn_double_random () >= mutate_probability)
321 comparators[i] = get_random_comparator ();
324 } /* }}} int mutate_network */
326 static int create_offspring (void) /* {{{ */
329 sn_comparator_t p0_comparators[comparators_num];
330 int p0_comparators_num;
333 sn_comparator_t p1_comparators[comparators_num];
334 int p1_comparators_num;
337 sn_comparator_t n_comparators[comparators_num];
338 int n_comparators_num;
342 p0 = population_get_random (population);
343 p1 = population_get_random (population);
348 p0_comparators_num = 0;
349 for (i = 0; i < SN_NETWORK_STAGE_NUM (p0); i++)
354 s = SN_NETWORK_STAGE_GET (p0, i);
356 for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
360 c = SN_STAGE_COMP_GET (s, j);
361 p0_comparators[p0_comparators_num] = *c;
362 p0_comparators_num++;
365 while (p0_comparators_num < comparators_num)
367 p0_comparators[p0_comparators_num] = get_random_comparator ();
368 p0_comparators_num++;
370 sn_network_destroy (p0);
373 p1_comparators_num = 0;
374 for (i = 0; i < SN_NETWORK_STAGE_NUM (p1); i++)
379 s = SN_NETWORK_STAGE_GET (p1, i);
381 for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
385 c = SN_STAGE_COMP_GET (s, j);
386 p1_comparators[p1_comparators_num] = *c;
387 p1_comparators_num++;
390 while (p1_comparators_num < comparators_num)
392 p1_comparators[p1_comparators_num] = get_random_comparator ();
393 p1_comparators_num++;
395 sn_network_destroy (p1);
398 n_comparators_num = sn_bounded_random (SNE_MIN (p0_comparators_num, p1_comparators_num),
399 SNE_MAX (p0_comparators_num, p1_comparators_num));
401 for (i = 0; i < n_comparators_num; i++)
403 if (i >= p0_comparators_num)
404 n_comparators[i] = p1_comparators[i];
405 else if (i >= p1_comparators_num)
406 n_comparators[i] = p0_comparators[i];
407 else if (sn_bounded_random (0, 1) == 0)
408 n_comparators[i] = p1_comparators[i];
410 n_comparators[i] = p0_comparators[i];
414 mutate_network (n_comparators, n_comparators_num);
416 n = sn_network_create (inputs_left + inputs_right);
417 for (i = 0; i < n_comparators_num; i++)
418 sn_network_comparator_add (n, &n_comparators[i]);
420 /* compress the network to get a compact representation */
421 sn_network_compress (n);
423 assert (SN_NETWORK_INPUT_NUM (n) == (inputs_left + inputs_right));
425 population_insert (population, n);
427 sn_network_destroy (n);
430 } /* }}} int create_offspring */
432 static void *evolution_thread (__attribute__((unused)) void *arg)
437 /* XXX: Not synchronized! */
442 } /* int start_evolution */
444 static int evolution_start (int threads_num)
446 pthread_t threads[threads_num]; /* C99 ftw! */
449 for (i = 0; i < threads_num; i++)
453 status = pthread_create (&threads[i], /* attr = */ NULL,
454 evolution_thread, /* arg = */ NULL);
457 fprintf (stderr, "evolution_start: pthread_create[%i] failed "
477 iter = iteration_counter;
479 n = population_get_fittest (population);
481 rating = rate_network (n);
483 stages_num = SN_NETWORK_STAGE_NUM (n);
485 for (i = 0; i < stages_num; i++)
489 s = SN_NETWORK_STAGE_GET (n, i);
490 comparators_num += SN_STAGE_COMP_NUM (s);
493 sn_network_destroy (n);
495 printf ("Best after approximately %i iterations: "
496 "%i comparators in %i stages. Rating: %i (%i not sorted).\n",
497 iter, comparators_num, stages_num, rating,
498 (rating - (weight_overall + (weight_stages * stages_num) + (weight_comparators * comparators_num))) / weight_fails);
502 for (i = 0; i < threads_num; i++)
506 pthread_join (threads[i], /* value_ptr = */ NULL);
510 } /* int evolution_start */
512 int main (int argc, char **argv)
514 struct sigaction sigint_action;
515 struct sigaction sigterm_action;
517 population = population_create ((pi_rate_f) rate_network,
518 (pi_copy_f) sn_network_clone,
519 (pi_free_f) sn_network_destroy);
520 if (population == NULL)
522 fprintf (stderr, "population_create failed.\n");
526 population_set_serialization (population,
527 (pi_serialize_f) sn_network_serialize,
528 (pi_unserialize_f) sn_network_unserialize);
530 read_options (argc, argv);
532 if ((inputs_left <= 0) || (inputs_right <= 0) || (comparators_num <= 0))
533 exit_usage (argv[0]);
535 memset (&sigint_action, '\0', sizeof (sigint_action));
536 sigint_action.sa_handler = sigint_handler;
537 sigaction (SIGINT, &sigint_action, NULL);
539 memset (&sigterm_action, '\0', sizeof (sigterm_action));
540 sigterm_action.sa_handler = sigint_handler;
541 sigaction (SIGTERM, &sigterm_action, NULL);
543 population_start_listen_thread (population, NULL, NULL);
545 if (initial_input_file != NULL)
549 n = sn_network_read_file (initial_input_file);
552 fprintf (stderr, "Cannot read network from `%s'.\n",
557 if (n->inputs_num != (inputs_left + inputs_right))
559 fprintf (stderr, "Network `%s' has %i inputs, but %i were configured "
560 "on the command line.\n",
561 initial_input_file, n->inputs_num,
562 inputs_left + inputs_right);
566 population_insert (population, n);
567 sn_network_destroy (n);
569 else /* if (initial_input_file == NULL) */
574 n = sn_network_create (inputs_left + inputs_right);
575 for (i = 0; i < comparators_num; i++)
579 c = get_random_comparator ();
580 sn_network_comparator_add (n, &c);
583 population_insert (population, n);
584 sn_network_destroy (n);
587 printf ("Current configuration:\n"
588 " Number of inputs: %3i\n"
589 " Number of comparators: %3i\n"
590 " Population size: %3i\n"
591 "=======================\n",
592 inputs_left + inputs_right, comparators_num, max_population_size);
594 evolution_start (evolution_threads_num);
596 printf ("Exiting after %llu iterations.\n",
597 (unsigned long long) iteration_counter);
602 n = population_get_fittest (population);
605 if (best_output_file != NULL)
606 sn_network_write_file (n, best_output_file);
608 sn_network_destroy (n);
612 population_destroy (population);
617 /* vim: set sw=2 sts=2 et fdm=marker : */