2 #define _POSIX_C_SOURCE 200112L
17 #include "sn_network.h"
18 #include "sn_population.h"
20 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
22 char *strdup (const char *s);
24 static uint64_t iteration_counter = 0;
25 static int inputs_num = 16;
27 static char *initial_input_file = NULL;
28 static char *best_output_file = NULL;
30 static int stats_interval = 0;
32 static int max_population_size = 128;
33 static sn_population_t *population;
35 static int do_loop = 0;
37 static void sigint_handler (int signal)
40 } /* void sigint_handler */
42 static int init_random (void)
47 fd = open ("/dev/random", O_RDONLY);
54 read (fd, (void *) &r, sizeof (r));
60 } /* int init_random */
62 static int bounded_random (int upper_bound)
64 double r = ((double) rand ()) / ((double) RAND_MAX);
65 return ((int) (r * upper_bound));
68 static void exit_usage (const char *name)
70 printf ("Usage: %s [options]\n"
72 "Valid options are:\n"
73 " -i <file> Initial input file (REQUIRED)\n"
74 " -o <file> Write the current best solution to <file>\n"
75 " -p <num> Size of the population (default: 128)\n"
79 } /* void exit_usage */
81 int read_options (int argc, char **argv)
85 while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1)
91 if (initial_input_file != NULL)
92 free (initial_input_file);
93 initial_input_file = strdup (optarg);
99 if (best_output_file != NULL)
100 free (best_output_file);
101 best_output_file = strdup (optarg);
107 int tmp = atoi (optarg);
109 max_population_size = tmp;
115 int tmp = atoi (optarg);
117 stats_interval = tmp;
123 exit_usage (argv[0]);
128 } /* int read_options */
131 static int rate_network (const sn_network_t *n)
136 rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
137 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
139 sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
140 rate += SN_STAGE_COMP_NUM (s);
144 } /* int rate_network */
148 static int population_print_stats (int iterations)
154 for (i = 0; i < population_size; i++)
156 if ((best == -1) || (best > population[i].rating))
157 best = population[i].rating;
158 total += population[i].rating;
161 printf ("Iterations: %6i; Best: %i; Average: %.2f;\n",
162 iterations, best, ((double) total) / ((double) population_size));
165 } /* int population_print_stats */
169 static int insert_into_population (sn_network_t *n)
178 rating = rate_network (n);
180 if (population_size < max_population_size)
182 population[population_size].network = n;
183 population[population_size].rating = rating;
191 for (i = 0; i < olymp_size; i++)
193 if (population[i].rating > worst_rating)
195 worst_rating = population[i].rating;
198 if ((population[i].rating < best_rating)
199 || (best_rating == -1))
200 best_rating = population[i].rating;
203 if (rating < best_rating)
205 if (best_output_file != NULL)
207 printf ("Writing network with rating %i to %s\n",
208 rating, best_output_file);
209 sn_network_write_file (n, best_output_file);
213 printf ("New best solution has rating %i\n",
218 nmemb = max_population_size - (worst_index + 1);
220 sn_network_destroy (population[worst_index].network);
221 population[worst_index].network = NULL;
223 memmove (population + worst_index,
224 population + (worst_index + 1),
225 nmemb * sizeof (population_entry_t));
227 population[max_population_size - 1].network = n;
228 population[max_population_size - 1].rating = rating;
231 } /* int insert_into_population */
234 static int create_offspring (void)
240 p0 = sn_population_pop (population);
241 p1 = sn_population_pop (population);
246 /* combine the two parents */
247 n = sn_network_combine (p0, p1);
249 sn_network_destroy (p0);
250 sn_network_destroy (p1);
252 /* randomly chose an input and do a min- or max-cut. */
253 while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
256 enum sn_network_cut_dir_e dir;
258 pos = bounded_random (SN_NETWORK_INPUT_NUM (n));
259 dir = (bounded_random (2) == 0) ? DIR_MIN : DIR_MAX;
261 assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
263 sn_network_cut_at (n, pos, dir);
266 /* compress the network to get a compact representation */
267 sn_network_compress (n);
269 assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
271 sn_population_push (population, n);
273 sn_network_destroy (n);
276 } /* int create_offspring */
278 static int start_evolution (void)
287 i = iteration_counter;
290 if ((stats_interval > 0) && ((i % stats_interval) == 0))
291 population_print_stats (i);
296 } /* int start_evolution */
298 int main (int argc, char **argv)
300 struct sigaction sigint_action;
302 read_options (argc, argv);
303 if (initial_input_file == NULL)
304 exit_usage (argv[0]);
308 memset (&sigint_action, '\0', sizeof (sigint_action));
309 sigint_action.sa_handler = sigint_handler;
310 sigaction (SIGINT, &sigint_action, NULL);
312 population = sn_population_create (max_population_size);
313 if (population == NULL)
315 fprintf (stderr, "sn_population_create failed.\n");
322 n = sn_network_read_file (initial_input_file);
325 printf ("n == NULL\n");
329 inputs_num = SN_NETWORK_INPUT_NUM(n);
331 sn_population_push (population, n);
332 sn_network_destroy (n);
335 printf ("Current configuration:\n"
336 " Initial network: %s\n"
337 " Number of inputs: %3i\n"
338 " Population size: %3i\n"
339 "=======================\n",
340 initial_input_file, inputs_num, max_population_size);
344 printf ("Exiting after %llu iterations.\n", iteration_counter);
346 if (best_output_file == NULL)
350 n = sn_population_best (population);
354 sn_network_destroy (n);
358 sn_population_destroy (population);
363 /* vim: set shiftwidth=2 softtabstop=2 : */