src/sn-evolution.c

   1 /**
   2  * collectd - src/sn-evolution.c
   3  * Copyright (C) 2008  Florian octo Forster
   4  *
   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.
   8  *
   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.
  13  *
  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
  17  *
  18  * Authors:
  19  *   Florian octo Forster <octo at verplant.org>
  20  **/
  21
  22 #define _ISOC99_SOURCE
  23 #define _POSIX_C_SOURCE 200112L
  24
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <stdint.h>
  28 #include <string.h>
  29
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <fcntl.h>
  33 #include <unistd.h>
  34 #include <signal.h>
  35 #include <assert.h>
  36 #include <limits.h>
  37
  38 #include "sn_network.h"
  39 #include "sn_population.h"
  40 #include "sn_random.h"
  41
  42 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
  43  * */
  44 char *strdup (const char *s);
  45
  46 static uint64_t iteration_counter = 0;
  47 static int inputs_num = 16;
  48
  49 static char *initial_input_file = NULL;
  50 static char *best_output_file = NULL;
  51
  52 static int stats_interval = 0;
  53
  54 static int max_population_size = 128;
  55 static sn_population_t *population;
  56
  57 static int do_loop = 0;
  58
  59 static void sigint_handler (int signal)
  60 {
  61   do_loop++;
  62 } /* void sigint_handler */
  63
  64 static void exit_usage (const char *name)
  65 {
  66   printf ("Usage: %s [options]\n"
  67       "\n"
  68       "Valid options are:\n"
  69       "  -i <file>     Initial input file (REQUIRED)\n"
  70       "  -o <file>     Write the current best solution to <file>\n"
  71       "  -p <num>      Size of the population (default: 128)\n"
  72       "\n",
  73       name);
  74   exit (1);
  75 } /* void exit_usage */
  76
  77 int read_options (int argc, char **argv)
  78 {
  79   int option;
  80
  81   while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1)
  82   {
  83     switch (option)
  84     {
  85       case 'i':
  86       {
  87         if (initial_input_file != NULL)
  88           free (initial_input_file);
  89         initial_input_file = strdup (optarg);
  90         break;
  91       }
  92
  93       case 'o':
  94       {
  95         if (best_output_file != NULL)
  96           free (best_output_file);
  97         best_output_file = strdup (optarg);
  98         break;
  99       }
 100
 101       case 'p':
 102       {
 103         int tmp = atoi (optarg);
 104         if (tmp > 0)
 105           max_population_size = tmp;
 106         break;
 107       }
 108
 109       case 's':
 110       {
 111         int tmp = atoi (optarg);
 112         if (tmp > 0)
 113           stats_interval = tmp;
 114         break;
 115       }
 116
 117       case 'h':
 118       default:
 119         exit_usage (argv[0]);
 120     }
 121   }
 122
 123   return (0);
 124 } /* int read_options */
 125
 126 #if 0
 127 static int rate_network (const sn_network_t *n)
 128 {
 129   int rate;
 130   int i;
 131
 132   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 133   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 134   {
 135     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 136     rate += SN_STAGE_COMP_NUM (s);
 137   }
 138
 139   return (rate);
 140 } /* int rate_network */
 141 #endif
 142
 143 #if 0
 144 static int population_print_stats (int iterations)
 145 {
 146   int best = -1;
 147   int total = 0;
 148   int i;
 149
 150   for (i = 0; i < population_size; i++)
 151   {
 152     if ((best == -1) || (best > population[i].rating))
 153       best = population[i].rating;
 154     total += population[i].rating;
 155   }
 156
 157   printf ("Iterations: %6i; Best: %i; Average: %.2f;\n",
 158       iterations, best, ((double) total) / ((double) population_size));
 159
 160   return (0);
 161 } /* int population_print_stats */
 162 #endif
 163
 164 #if 0
 165 static int insert_into_population (sn_network_t *n)
 166 {
 167   int rating;
 168   int worst_rating;
 169   int worst_index;
 170   int best_rating;
 171   int nmemb;
 172   int i;
 173
 174   rating = rate_network (n);
 175
 176   if (population_size < max_population_size)
 177   {
 178     population[population_size].network = n;
 179     population[population_size].rating  = rating;
 180     population_size++;
 181     return (0);
 182   }
 183
 184   worst_rating = -1;
 185   worst_index  = -1;
 186   best_rating  = -1;
 187   for (i = 0; i < olymp_size; i++)
 188   {
 189     if (population[i].rating > worst_rating)
 190     {
 191       worst_rating = population[i].rating;
 192       worst_index  = i;
 193     }
 194     if ((population[i].rating < best_rating)
 195         || (best_rating == -1))
 196       best_rating = population[i].rating;
 197   }
 198
 199   if (rating < best_rating)
 200   {
 201     if (best_output_file != NULL)
 202     {
 203       printf ("Writing network with rating %i to %s\n",
 204           rating, best_output_file);
 205       sn_network_write_file (n, best_output_file);
 206     }
 207     else
 208     {
 209       printf ("New best solution has rating %i\n",
 210           rating);
 211     }
 212   }
 213
 214   nmemb = max_population_size - (worst_index + 1);
 215
 216   sn_network_destroy (population[worst_index].network);
 217   population[worst_index].network = NULL;
 218
 219   memmove (population + worst_index,
 220       population + (worst_index + 1),
 221       nmemb * sizeof (population_entry_t));
 222
 223   population[max_population_size - 1].network = n;
 224   population[max_population_size - 1].rating  = rating;
 225
 226   return (0);
 227 } /* int insert_into_population */
 228 #endif
 229
 230 static int create_offspring (void)
 231 {
 232   sn_network_t *p0;
 233   sn_network_t *p1;
 234   sn_network_t *n;
 235
 236   p0 = sn_population_pop (population);
 237   p1 = sn_population_pop (population);
 238
 239   assert (p0 != NULL);
 240   assert (p1 != NULL);
 241
 242   /* combine the two parents */
 243   n = sn_network_combine (p0, p1);
 244
 245   sn_network_destroy (p0);
 246   sn_network_destroy (p1);
 247
 248   /* randomly chose an input and do a min- or max-cut. */
 249   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 250   {
 251     int pos;
 252     enum sn_network_cut_dir_e dir;
 253
 254     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 255     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 256
 257     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 258
 259     sn_network_cut_at (n, pos, dir);
 260   }
 261
 262   /* compress the network to get a compact representation */
 263   sn_network_compress (n);
 264
 265   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 266
 267   sn_population_push (population, n);
 268
 269   sn_network_destroy (n);
 270
 271   return (0);
 272 } /* int create_offspring */
 273
 274 static int start_evolution (void)
 275 {
 276   uint64_t i;
 277
 278   while (do_loop == 0)
 279   {
 280     create_offspring ();
 281
 282     iteration_counter++;
 283     i = iteration_counter;
 284
 285     if ((i % 1000) == 0)
 286     {
 287       int rating = sn_population_best_rating (population);
 288       printf ("After %10llu iterations: Best rating: %4i\n", i, rating);
 289     }
 290   }
 291
 292   return (0);
 293 } /* int start_evolution */
 294
 295 int main (int argc, char **argv)
 296 {
 297   struct sigaction sigint_action;
 298
 299   read_options (argc, argv);
 300   if (initial_input_file == NULL)
 301     exit_usage (argv[0]);
 302
 303   memset (&sigint_action, '\0', sizeof (sigint_action));
 304   sigint_action.sa_handler = sigint_handler;
 305   sigaction (SIGINT, &sigint_action, NULL);
 306
 307   population = sn_population_create (max_population_size);
 308   if (population == NULL)
 309   {
 310     fprintf (stderr, "sn_population_create failed.\n");
 311     return (1);
 312   }
 313
 314   {
 315     sn_network_t *n;
 316
 317     n = sn_network_read_file (initial_input_file);
 318     if (n == NULL)
 319     {
 320       printf ("n == NULL\n");
 321       return (1);
 322     }
 323
 324     inputs_num = SN_NETWORK_INPUT_NUM(n);
 325
 326     sn_population_push (population, n);
 327     sn_network_destroy (n);
 328   }
 329
 330   printf ("Current configuration:\n"
 331       "  Initial network:  %s\n"
 332       "  Number of inputs: %3i\n"
 333       "  Population size:  %3i\n"
 334       "=======================\n",
 335       initial_input_file, inputs_num, max_population_size);
 336
 337   start_evolution ();
 338
 339   printf ("Exiting after %llu iterations.\n", iteration_counter);
 340
 341   {
 342     sn_network_t *n;
 343
 344     n = sn_population_best (population);
 345     if (n != NULL)
 346     {
 347       if (best_output_file != NULL)
 348         sn_network_write_file (n, best_output_file);
 349       else
 350         sn_network_show (n);
 351       sn_network_destroy (n);
 352     }
 353   }
 354
 355   sn_population_destroy (population);
 356
 357   return (0);
 358 } /* int main */
 359
 360 /* vim: set shiftwidth=2 softtabstop=2 : */