X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fsn-evolution.c;h=ffe5c34e591a9cbfd6f60bc402f3367a4afc8ac6;hb=f408d1dd2f79bc8c7e765af56c8b023e95e21046;hp=8e37cb322e62f4a2ff9ab60a1f2d4bc80d2bf9c9;hpb=f70ce78fe7c255789636ddfbf57d2fb8fede9576;p=sort-networks.git diff --git a/src/sn-evolution.c b/src/sn-evolution.c index 8e37cb3..ffe5c34 100644 --- a/src/sn-evolution.c +++ b/src/sn-evolution.c @@ -1,8 +1,34 @@ -#define _ISOC99_SOURCE -#define _POSIX_C_SOURCE 200112L +/** + * collectd - src/sn-evolution.c + * Copyright (C) 2008 Florian octo Forster + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; only version 2 of the License is applicable. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + **/ + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200112L +#endif #include #include +#include #include #include @@ -11,239 +37,314 @@ #include #include #include +#include -#include "sn_network.h" - -struct population_entry_s -{ - sn_network_t *network; - int rating; -}; -typedef struct population_entry_s population_entry_t; - -static int iterations_num = 1000000; -static int max_population_size = 128; -static int olymp_size = 96; -static int inputs_num = 16; +#include -static population_entry_t *population = NULL; -int population_size = 0; +#include "sn_network.h" +#include "sn_population.h" +#include "sn_random.h" -static void sigint_handler (int signal) -{ - iterations_num = 0; -} /* void sigint_handler */ +/* Yes, this is ugly, but the GNU libc doesn't export it with the above flags. + * */ +char *strdup (const char *s); -static int init_random (void) -{ - int fd; - unsigned int r; +static uint64_t iteration_counter = 0; +static int inputs_num = 16; - fd = open ("/dev/random", O_RDONLY); - if (fd < 0) - { - perror ("open"); - return (-1); - } +static char *initial_input_file = NULL; +static char *best_output_file = NULL; - read (fd, (void *) &r, sizeof (r)); - close (fd); +static int stats_interval = 0; - srand (r); +static int max_population_size = 128; +static sn_population_t *population; - return (0); -} /* int init_random */ +static int do_loop = 0; -static int bounded_random (int upper_bound) +static void sigint_handler (int signal) { - double r = ((double) rand ()) / ((double) RAND_MAX); - return ((int) (r * upper_bound)); -} + do_loop++; +} /* void sigint_handler */ static void exit_usage (const char *name) { - printf ("%s \n", name); + printf ("Usage: %s [options]\n" + "\n" + "Valid options are:\n" + " -i Initial input file (REQUIRED)\n" + " -o Write the current best solution to \n" + " -p Size of the population (default: 128)\n" + "\n", + name); exit (1); } /* void exit_usage */ -static int rate_network (const sn_network_t *n) +int read_options (int argc, char **argv) { - int rate; - int i; + int option; - rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n); - for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) + while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1) { - sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i); - rate += SN_STAGE_COMP_NUM (s); - } + switch (option) + { + case 'i': + { + if (initial_input_file != NULL) + free (initial_input_file); + initial_input_file = strdup (optarg); + break; + } - return (rate); -} /* int rate_network */ + case 'o': + { + if (best_output_file != NULL) + free (best_output_file); + best_output_file = strdup (optarg); + break; + } -static int population_print_stats (int iterations) -{ - int best = -1; - int total = 0; - int i; + case 'p': + { + int tmp = atoi (optarg); + if (tmp > 0) + max_population_size = tmp; + break; + } - for (i = 0; i < population_size; i++) - { - if ((best == -1) || (best > population[i].rating)) - best = population[i].rating; - total += population[i].rating; - } + case 's': + { + int tmp = atoi (optarg); + if (tmp > 0) + stats_interval = tmp; + break; + } - printf ("Iterations: %6i; Best: %i; Average: %.2f;\n", - iterations, best, ((double) total) / ((double) population_size)); + case 'h': + default: + exit_usage (argv[0]); + } + } return (0); -} /* int population_print_stats */ +} /* int read_options */ -static int insert_into_population (sn_network_t *n) +static int mutate_network (sn_network_t *n) { - int rating; - int worst_rating; - int worst_index; - int nmemb; - int i; - - rating = rate_network (n); - - if (population_size < max_population_size) + sn_network_t *n_copy; + int stage_index; + sn_stage_t *s; + int comparator_index; + int status; + + n_copy = sn_network_clone (n); + if (n_copy == NULL) { - population[population_size].network = n; - population[population_size].rating = rating; - population_size++; - return (0); + fprintf (stderr, "mutate_network: sn_network_clone failed.\n"); + return (-1); } - worst_rating = -1; - worst_index = -1; - for (i = 0; i < olymp_size; i++) - if (population[i].rating > worst_rating) - { - worst_rating = population[i].rating; - worst_index = i; - } + stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1); + s = SN_NETWORK_STAGE_GET (n_copy, stage_index); - nmemb = max_population_size - (worst_index + 1); + comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1); + sn_stage_comparator_remove (s, comparator_index); - sn_network_destroy (population[worst_index].network); - population[worst_index].network = NULL; + status = sn_network_brute_force_check (n_copy); + + sn_network_destroy (n_copy); - memmove (population + worst_index, - population + (worst_index + 1), - nmemb * sizeof (population_entry_t)); + if (status < 0) + return (-1); + else if (status > 0) /* Mutated network does not sort anymore. */ + return (1); - population[max_population_size - 1].network = n; - population[max_population_size - 1].rating = rating; + /* We saved one comparator \o/ Let's do the same change on the original + * network. */ + s = SN_NETWORK_STAGE_GET (n, stage_index); + sn_stage_comparator_remove (s, comparator_index); return (0); -} /* int insert_into_population */ +} /* int mutate_network */ static int create_offspring (void) { - int p0; - int p1; + sn_network_t *p0; + sn_network_t *p1; sn_network_t *n; - p0 = bounded_random (population_size); - p1 = bounded_random (population_size); + p0 = sn_population_pop (population); + p1 = sn_population_pop (population); + + assert (p0 != NULL); + assert (p1 != NULL); + + /* combine the two parents */ + n = sn_network_combine (p0, p1); - n = sn_network_combine (population[p0].network, population[p1].network); + sn_network_destroy (p0); + sn_network_destroy (p1); + /* randomly chose an input and do a min- or max-cut. */ while (SN_NETWORK_INPUT_NUM (n) > inputs_num) { int pos; enum sn_network_cut_dir_e dir; - pos = bounded_random (SN_NETWORK_INPUT_NUM (n)); - dir = (bounded_random (2) == 0) ? DIR_MIN : DIR_MAX; + pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1); + dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX; assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n))); sn_network_cut_at (n, pos, dir); } + /* compress the network to get a compact representation */ sn_network_compress (n); assert (SN_NETWORK_INPUT_NUM (n) == inputs_num); - insert_into_population (n); + if (sn_bounded_random (0, 100) <= 1) + { + int status; + + status = mutate_network (n); + if (status == 0) + printf ("Debug: Mutation successfull.\n"); + } + + sn_population_push (population, n); + + sn_network_destroy (n); return (0); } /* int create_offspring */ -static int start_evolution (void) +static void *evolution_thread (void *arg) +{ + while (do_loop == 0) + { + create_offspring (); + /* XXX: Not synchronized! */ + iteration_counter++; + } + + return ((void *) 0); +} /* int start_evolution */ + +static int evolution_start (int threads_num) { + pthread_t threads[threads_num]; /* C99 ftw! */ int i; - for (i = 0; i < iterations_num; i++) + for (i = 0; i < threads_num; i++) { - if ((i % 1000) == 0) - population_print_stats (i); + int status; - create_offspring (); + status = pthread_create (&threads[i], /* attr = */ NULL, + evolution_thread, /* arg = */ NULL); + if (status != 0) + { + fprintf (stderr, "evolution_start: pthread_create[%i] failed " + "with status %i.\n", + i, status); + threads[i] = 0; + } + } + + while (do_loop == 0) + { + int status; + + status = sleep (1); + if (status == 0) + { + int best_rating; + i = iteration_counter; + + best_rating = sn_population_best_rating (population); + printf ("After approximately %i iterations: Currently best rating: %i\n", i, best_rating); + } + } + + for (i = 0; i < threads_num; i++) + { + if (threads[i] == 0) + continue; + pthread_join (threads[i], /* value_ptr = */ NULL); } return (0); -} /* int start_evolution */ +} /* int evolution_start */ int main (int argc, char **argv) { struct sigaction sigint_action; + struct sigaction sigterm_action; - if (argc != 2) + read_options (argc, argv); + if (initial_input_file == NULL) exit_usage (argv[0]); - init_random (); - memset (&sigint_action, '\0', sizeof (sigint_action)); sigint_action.sa_handler = sigint_handler; sigaction (SIGINT, &sigint_action, NULL); - population = (population_entry_t *) malloc (max_population_size - * sizeof (population_entry_t)); + memset (&sigterm_action, '\0', sizeof (sigterm_action)); + sigterm_action.sa_handler = sigint_handler; + sigaction (SIGTERM, &sigterm_action, NULL); + + population = sn_population_create (max_population_size); if (population == NULL) { - printf ("Malloc failed.\n"); - return (-1); + fprintf (stderr, "sn_population_create failed.\n"); + return (1); } - memset (population, '\0', max_population_size - * sizeof (population_entry_t)); { - sn_network_t *n = sn_network_read_file (argv[1]); + sn_network_t *n; + + n = sn_network_read_file (initial_input_file); if (n == NULL) { printf ("n == NULL\n"); return (1); } - population[0].network = n; - population[0].rating = rate_network (n); - population_size++; + + inputs_num = SN_NETWORK_INPUT_NUM(n); + + sn_population_push (population, n); + sn_network_destroy (n); } - start_evolution (); + printf ("Current configuration:\n" + " Initial network: %s\n" + " Number of inputs: %3i\n" + " Population size: %3i\n" + "=======================\n", + initial_input_file, inputs_num, max_population_size); + + evolution_start (3); + + printf ("Exiting after %llu iterations.\n", + (unsigned long long) iteration_counter); { - int i; - int best_rate = -1; - int best_index = -1; + sn_network_t *n; - for (i = 0; i < population_size; i++) + n = sn_population_best (population); + if (n != NULL) { - if ((best_rate == -1) || (best_rate > population[i].rating)) - { - best_rate = population[i].rating; - best_index = i; - } + if (best_output_file != NULL) + sn_network_write_file (n, best_output_file); + else + sn_network_show (n); + sn_network_destroy (n); } - - sn_network_show (population[best_index].network); } + sn_population_destroy (population); + return (0); } /* int main */