From: Florian Forster Date: Mon, 10 May 2010 13:04:38 +0000 (+0200) Subject: sn-evolution-cut: Add new evolutionary algorithm for optimizing cuts through networks. X-Git-Tag: v1.0.0~55 X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=commitdiff_plain;h=a0693de016d176c60b9a8c8c377219f7b81fbc60 sn-evolution-cut: Add new evolutionary algorithm for optimizing cuts through networks. --- diff --git a/src/Makefile.am b/src/Makefile.am index 773573a..773906f 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -42,10 +42,15 @@ sn_tex_SOURCES = sn-tex.c sn_tex_LDADD = libsortnetwork.la if BUILD_WITH_LIBPOPULATION -bin_PROGRAMS += sn-evolution +bin_PROGRAMS += sn-evolution sn-evolution-cut sn_evolution_SOURCES = sn-evolution.c sn_evolution_CPPFLAGS = $(AM_CPPFLAGS) $(LIBPOPULATION_CPPFLAGS) sn_evolution_LDFLAGS = $(AM_LDFLAGS) $(LIBPOPULATION_LDFLAGS) sn_evolution_LDADD = libsortnetwork.la $(LIBPOPULATION_LIBS) + +sn_evolution_cut_SOURCES = sn-evolution-cut.c +sn_evolution_cut_CPPFLAGS = $(AM_CPPFLAGS) $(LIBPOPULATION_CPPFLAGS) +sn_evolution_cut_LDFLAGS = $(AM_LDFLAGS) $(LIBPOPULATION_LDFLAGS) +sn_evolution_cut_LDADD = libsortnetwork.la $(LIBPOPULATION_LIBS) endif diff --git a/src/sn-evolution-cut.c b/src/sn-evolution-cut.c new file mode 100644 index 0000000..7adef3d --- /dev/null +++ b/src/sn-evolution-cut.c @@ -0,0 +1,521 @@ +/** + * collectd - src/sn-evolution-cut.c + * Copyright (C) 2008-2010 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 + **/ + +#include "config.h" + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#include + +#include + +#include "sn_network.h" +#include "sn_random.h" + +#if !defined(__GNUC__) || !__GNUC__ +# define __attribute__(x) /**/ +#endif + +typedef int individuum_t; + +static int inputs_num = 0; +static int outputs_num = 0; +static int cuts_num = 0; + +static char *initial_input_file = NULL; +static const sn_network_t *initial_network = NULL; +static char *best_output_file = NULL; + +static int stats_interval = 0; + +static int max_population_size = 128; +static population_t *population = NULL; + +static int evolution_threads_num = 4; + +static int do_loop = 0; +static uint64_t iteration_counter = 0; + +static void sigint_handler (int signal __attribute__((unused))) +{ + do_loop++; +} /* void sigint_handler */ + +static void exit_usage (const char *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" + " -O Number of outputs (default: inputs / 2)\n" + " -p Size of the population (default: 128)\n" + " -P Send individuals to (may be repeated)\n" + " -t Number of threads (default: 4)\n" + "\n", + name); + exit (1); +} /* void exit_usage */ + +int read_options (int argc, char **argv) /* {{{ */ +{ + int option; + + while ((option = getopt (argc, argv, "i:o:O:p:P:s:t:h")) != -1) + { + switch (option) + { + case 'i': + { + if (initial_input_file != NULL) + free (initial_input_file); + initial_input_file = strdup (optarg); + break; + } + + case 'o': + { + if (best_output_file != NULL) + free (best_output_file); + best_output_file = strdup (optarg); + break; + } + + case 'O': + { + int tmp = atoi (optarg); + if (tmp > 0) + outputs_num = tmp; + break; + } + + case 'p': + { + int tmp = atoi (optarg); + if (tmp > 0) + { + max_population_size = tmp; + population_set_size (population, (size_t) max_population_size); + } + break; + } + + case 'P': + { + int status; + + status = population_add_peer (population, optarg, /* port = */ NULL); + if (status != 0) + { + fprintf (stderr, "population_add_peer failed with status %i.\n", + status); + } + break; + } + + case 's': + { + int tmp = atoi (optarg); + if (tmp > 0) + stats_interval = tmp; + break; + } + + case 't': + { + int tmp = atoi (optarg); + if (tmp >= 1) + evolution_threads_num = tmp; + break; + } + + case 'h': + default: + exit_usage (argv[0]); + } + } + + return (0); +} /* }}} int read_options */ + +static int apply_cut (sn_network_t *n, int input) /* {{{ */ +{ + enum sn_network_cut_dir_e dir = DIR_MAX; + + if (input < 0) + { + dir = DIR_MIN; + input *= (-1); + } + input--; + + return (sn_network_cut_at (n, input, dir)); +} /* }}} int apply_cut */ + +static int apply (sn_network_t *n, const individuum_t *ind) /* {{{ */ +{ + int i; + + for (i = 0; i < cuts_num; i++) + apply_cut (n, ind[i]); + + return (0); +} /* }}} int apply */ + +static int rate_network (const sn_network_t *n) /* {{{ */ +{ + int rate; + int i; + + rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n); + for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) + { + sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i); + rate += SN_STAGE_COMP_NUM (s); + } + + return (rate); +} /* }}} int rate_network */ + +static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */ +{ + sn_network_t *n; + + n = sn_network_clone (initial_network); + if (n == NULL) + return (NULL); + + apply (n, ind); + + sn_network_normalize (n); + sn_network_compress (n); + + return (n); +} /* }}} sn_network_t *individuum_to_network */ + +static int ind_rate (const void *arg) /* {{{ */ +{ + sn_network_t *n; + int status; + + n = individuum_to_network (arg); + if (n == NULL) + return (-1); + + status = rate_network (n); + sn_network_destroy (n); + + return (status); +} /* }}} int ind_rate */ + +static void *ind_copy (const void *in) /* {{{ */ +{ + size_t s = sizeof (individuum_t) * cuts_num; + void *out; + + out = malloc (s); + if (out == NULL) + return (NULL); + + memcpy (out, in, s); + return (out); +} /* }}} void *ind_copy */ + +static void ind_free (void *ind) /* {{{ */ +{ + if (ind != NULL) + free (ind); +} /* }}} void ind_free */ + +static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */ +{ + individuum_t *offspring; + int cut_at; + int i; + + if ((i0 == NULL) || (i1 == NULL)) + return (NULL); + + offspring = malloc (sizeof (*offspring) * cuts_num); + if (offspring == NULL) + return (NULL); + memset (offspring, 0, sizeof (*offspring) * cuts_num); + + cut_at = sn_bounded_random (0, cuts_num); + for (i = 0; i < cuts_num; i++) + { + if (i < cut_at) + offspring[i] = i0[i]; + else + offspring[i] = i1[i]; + } + + return (offspring); +} /* }}} individuum_t *recombine */ + +static void random_cut (individuum_t *ind, int index) /* {{{ */ +{ + int max_input = inputs_num - index; + + ind[index] = 0; + while (ind[index] == 0) + ind[index] = sn_bounded_random ((-1) * max_input, max_input); +} /* }}} void random_cut */ + +static void mutate (individuum_t *ind) /* {{{ */ +{ + int reset_input; + int i; + + reset_input = sn_bounded_random (0, 3 * cuts_num); + for (i = 0; i < cuts_num; i++) + { + if (reset_input == i) + random_cut (ind, i); + + if (sn_bounded_random (0, 100)) + ind[i] *= (-1); + } +} /* }}} void mutate */ + +static int create_offspring (void) /* {{{ */ +{ + individuum_t *i0; + individuum_t *i1; + individuum_t *i2; + + i0 = population_get_random (population); + i1 = population_get_random (population); + + i2 = recombine (i0, i1); + mutate (i2); + + population_insert (population, i2); + + free (i0); + free (i1); + free (i2); + + return (0); +} /* }}} int create_offspring */ + +static void *evolution_thread (void *arg __attribute__((unused))) /* {{{ */ +{ + 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 < threads_num; i++) + { + int status; + + 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) + { + individuum_t *ind; + sn_network_t *n; + int stages_num; + int comparators_num; + int rating; + int iter; + + iter = iteration_counter; + + ind = population_get_fittest (population); + n = individuum_to_network (ind); + + rating = rate_network (n); + + stages_num = SN_NETWORK_STAGE_NUM (n); + comparators_num = 0; + for (i = 0; i < stages_num; i++) + { + sn_stage_t *s; + + s = SN_NETWORK_STAGE_GET (n, i); + comparators_num += SN_STAGE_COMP_NUM (s); + } + + sn_network_destroy (n); + ind_free (ind); + + printf ("Best after approximately %i iterations: " + "%i comparators in %i stages. Rating: %i.\n", + iter, comparators_num, stages_num, rating); + } + } + + for (i = 0; i < threads_num; i++) + { + if (threads[i] == 0) + continue; + pthread_join (threads[i], /* value_ptr = */ NULL); + } + + return (0); +} /* }}} int evolution_start */ + +int main (int argc, char **argv) /* {{{ */ +{ + struct sigaction sigint_action; + struct sigaction sigterm_action; + int i; + + population = population_create (ind_rate, ind_copy, ind_free); + if (population == NULL) + { + fprintf (stderr, "population_create failed.\n"); + return (1); + } + +#if 0 + population_set_serialization (population, + (pi_serialize_f) sn_network_serialize, + (pi_unserialize_f) sn_network_unserialize); +#endif + + read_options (argc, argv); + if (initial_input_file == NULL) + exit_usage (argv[0]); + + memset (&sigint_action, '\0', sizeof (sigint_action)); + sigint_action.sa_handler = sigint_handler; + sigaction (SIGINT, &sigint_action, NULL); + + memset (&sigterm_action, '\0', sizeof (sigterm_action)); + sigterm_action.sa_handler = sigint_handler; + sigaction (SIGTERM, &sigterm_action, NULL); + + /* population_start_listen_thread (population, NULL, NULL); */ + + initial_network = sn_network_read_file (initial_input_file); + if (initial_network == NULL) + { + fprintf (stderr, "Reading input file failed.\n"); + exit (EXIT_FAILURE); + } + + inputs_num = SN_NETWORK_INPUT_NUM(initial_network); + if (outputs_num == 0) + outputs_num = inputs_num / 2; + + if (outputs_num >= inputs_num) + { + fprintf (stderr, "Number of inputs (%i) is smaller than " + "(or equal to) the number of outputs (%i).\n", + inputs_num, outputs_num); + exit (EXIT_FAILURE); + } + + cuts_num = inputs_num - outputs_num; + assert (cuts_num >= 1); + + for (i = 0; i < max_population_size; i++) + { /* create a random initial individuum */ + individuum_t *ind; + int i; + + ind = malloc (sizeof (*ind) * cuts_num); + if (ind == NULL) + { + fprintf (stderr, "malloc failed.\n"); + exit (EXIT_FAILURE); + } + + for (i = 0; i < cuts_num; i++) + random_cut (ind, i); + + population_insert (population, ind); + ind_free (ind); + } + + printf ("Current configuration:\n" + " Initial network: %s\n" + " Number of inputs: %3i\n" + " Number of outputs: %3i\n" + " Population size: %3i\n" + "=======================\n", + initial_input_file, inputs_num, outputs_num, max_population_size); + + evolution_start (evolution_threads_num); + + printf ("Exiting after %"PRIu64" iterations.\n", + iteration_counter); + + { + individuum_t *ind; + sn_network_t *n; + + ind = population_get_fittest (population); + if (ind != NULL) + { + n = individuum_to_network (ind); + if (best_output_file != NULL) + sn_network_write_file (n, best_output_file); + sn_network_show (n); + sn_network_destroy (n); + } + } + + population_destroy (population); + + return (0); +} /* }}} int main */ + +/* vim: set shiftwidth=2 softtabstop=2 et fdm=marker : */