2 * collectd - src/sn-evolution.c
3 * Copyright (C) 2008 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 <octo at verplant.org>
22 #ifndef _ISOC99_SOURCE
23 # define _ISOC99_SOURCE
25 #ifndef _POSIX_C_SOURCE
26 # define _POSIX_C_SOURCE 200112L
34 #include <sys/types.h>
44 #include "sn_network.h"
45 #include "sn_population.h"
46 #include "sn_random.h"
48 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
50 char *strdup (const char *s);
52 static uint64_t iteration_counter = 0;
53 static int inputs_num = 16;
55 static char *initial_input_file = NULL;
56 static char *best_output_file = NULL;
58 static int stats_interval = 0;
60 static int max_population_size = 128;
61 static sn_population_t *population;
63 static int do_loop = 0;
65 static void sigint_handler (int signal)
68 } /* void sigint_handler */
70 static void exit_usage (const char *name)
72 printf ("Usage: %s [options]\n"
74 "Valid options are:\n"
75 " -i <file> Initial input file (REQUIRED)\n"
76 " -o <file> Write the current best solution to <file>\n"
77 " -p <num> Size of the population (default: 128)\n"
81 } /* void exit_usage */
83 int read_options (int argc, char **argv)
87 while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1)
93 if (initial_input_file != NULL)
94 free (initial_input_file);
95 initial_input_file = strdup (optarg);
101 if (best_output_file != NULL)
102 free (best_output_file);
103 best_output_file = strdup (optarg);
109 int tmp = atoi (optarg);
111 max_population_size = tmp;
117 int tmp = atoi (optarg);
119 stats_interval = tmp;
125 exit_usage (argv[0]);
130 } /* int read_options */
132 static int mutate_network (sn_network_t *n)
134 sn_network_t *n_copy;
137 int comparator_index;
140 n_copy = sn_network_clone (n);
143 fprintf (stderr, "mutate_network: sn_network_clone failed.\n");
147 stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1);
148 s = SN_NETWORK_STAGE_GET (n_copy, stage_index);
150 comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1);
151 sn_stage_comparator_remove (s, comparator_index);
153 status = sn_network_brute_force_check (n_copy);
155 sn_network_destroy (n_copy);
159 else if (status > 0) /* Mutated network does not sort anymore. */
162 /* We saved one comparator \o/ Let's do the same change on the original
164 s = SN_NETWORK_STAGE_GET (n, stage_index);
165 sn_stage_comparator_remove (s, comparator_index);
168 } /* int mutate_network */
170 static int create_offspring (void)
176 p0 = sn_population_pop (population);
177 p1 = sn_population_pop (population);
182 /* combine the two parents */
183 n = sn_network_combine (p0, p1);
185 sn_network_destroy (p0);
186 sn_network_destroy (p1);
188 /* randomly chose an input and do a min- or max-cut. */
189 while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
192 enum sn_network_cut_dir_e dir;
194 pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
195 dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
197 assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
199 sn_network_cut_at (n, pos, dir);
202 /* compress the network to get a compact representation */
203 sn_network_compress (n);
205 assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
207 if (sn_bounded_random (0, 100) <= 1)
210 sn_population_push (population, n);
212 sn_network_destroy (n);
215 } /* int create_offspring */
217 static void *evolution_thread (void *arg)
222 /* XXX: Not synchronized! */
227 } /* int start_evolution */
229 static int evolution_start (int threads_num)
231 pthread_t threads[threads_num]; /* C99 ftw! */
234 for (i = 0; i < threads_num; i++)
238 status = pthread_create (&threads[i], /* attr = */ NULL,
239 evolution_thread, /* arg = */ NULL);
242 fprintf (stderr, "evolution_start: pthread_create[%i] failed "
257 i = iteration_counter;
259 best_rating = sn_population_best_rating (population);
260 printf ("After approximately %i iterations: Currently best rating: %i\n", i, best_rating);
264 for (i = 0; i < threads_num; i++)
268 pthread_join (threads[i], /* value_ptr = */ NULL);
272 } /* int evolution_start */
274 int main (int argc, char **argv)
276 struct sigaction sigint_action;
277 struct sigaction sigterm_action;
279 read_options (argc, argv);
280 if (initial_input_file == NULL)
281 exit_usage (argv[0]);
283 memset (&sigint_action, '\0', sizeof (sigint_action));
284 sigint_action.sa_handler = sigint_handler;
285 sigaction (SIGINT, &sigint_action, NULL);
287 memset (&sigterm_action, '\0', sizeof (sigterm_action));
288 sigterm_action.sa_handler = sigint_handler;
289 sigaction (SIGTERM, &sigterm_action, NULL);
291 population = sn_population_create (max_population_size);
292 if (population == NULL)
294 fprintf (stderr, "sn_population_create failed.\n");
301 n = sn_network_read_file (initial_input_file);
304 printf ("n == NULL\n");
308 inputs_num = SN_NETWORK_INPUT_NUM(n);
310 sn_population_push (population, n);
311 sn_network_destroy (n);
314 printf ("Current configuration:\n"
315 " Initial network: %s\n"
316 " Number of inputs: %3i\n"
317 " Population size: %3i\n"
318 "=======================\n",
319 initial_input_file, inputs_num, max_population_size);
323 printf ("Exiting after %llu iterations.\n",
324 (unsigned long long) iteration_counter);
329 n = sn_population_best (population);
332 if (best_output_file != NULL)
333 sn_network_write_file (n, best_output_file);
336 sn_network_destroy (n);
340 sn_population_destroy (population);
345 /* vim: set shiftwidth=2 softtabstop=2 : */