src/sn-evolution.c

   1 #define _ISOC99_SOURCE
   2 #define _POSIX_C_SOURCE 200112L
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7
   8 #include <sys/types.h>
   9 #include <sys/stat.h>
  10 #include <fcntl.h>
  11 #include <unistd.h>
  12 #include <signal.h>
  13 #include <assert.h>
  14
  15 #include "sn_network.h"
  16
  17 struct population_entry_s
  18 {
  19   sn_network_t *network;
  20   int rating;
  21 };
  22 typedef struct population_entry_s population_entry_t;
  23
  24 static int iterations_num  = 1000000;
  25 static int max_population_size = 128;
  26 static int olymp_size = 96;
  27 static int inputs_num      = 16;
  28
  29 static population_entry_t *population = NULL;
  30 int population_size = 0;
  31
  32 static void sigint_handler (int signal)
  33 {
  34   iterations_num = 0;
  35 } /* void sigint_handler */
  36
  37 static int init_random (void)
  38 {
  39   int fd;
  40   unsigned int r;
  41
  42   fd = open ("/dev/random", O_RDONLY);
  43   if (fd < 0)
  44   {
  45     perror ("open");
  46     return (-1);
  47   }
  48
  49   read (fd, (void *) &r, sizeof (r));
  50   close (fd);
  51
  52   srand (r);
  53
  54   return (0);
  55 } /* int init_random */
  56
  57 static int bounded_random (int upper_bound)
  58 {
  59   double r = ((double) rand ()) / ((double) RAND_MAX);
  60   return ((int) (r * upper_bound));
  61 }
  62
  63 static void exit_usage (const char *name)
  64 {
  65   printf ("%s <file0>\n", name);
  66   exit (1);
  67 } /* void exit_usage */
  68
  69 static int rate_network (const sn_network_t *n)
  70 {
  71   int rate;
  72   int i;
  73
  74   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
  75   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
  76   {
  77     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
  78     rate += SN_STAGE_COMP_NUM (s);
  79   }
  80
  81   return (rate);
  82 } /* int rate_network */
  83
  84 static int population_print_stats (int iterations)
  85 {
  86   int best = -1;
  87   int total = 0;
  88   int i;
  89
  90   for (i = 0; i < population_size; i++)
  91   {
  92     if ((best == -1) || (best > population[i].rating))
  93       best = population[i].rating;
  94     total += population[i].rating;
  95   }
  96
  97   printf ("Iterations: %6i; Best: %i; Average: %.2f;\n",
  98       iterations, best, ((double) total) / ((double) population_size));
  99
 100   return (0);
 101 } /* int population_print_stats */
 102
 103 static int insert_into_population (sn_network_t *n)
 104 {
 105   int rating;
 106   int worst_rating;
 107   int worst_index;
 108   int nmemb;
 109   int i;
 110
 111   rating = rate_network (n);
 112
 113   if (population_size < max_population_size)
 114   {
 115     population[population_size].network = n;
 116     population[population_size].rating  = rating;
 117     population_size++;
 118     return (0);
 119   }
 120
 121   worst_rating = -1;
 122   worst_index  = -1;
 123   for (i = 0; i < olymp_size; i++)
 124     if (population[i].rating > worst_rating)
 125     {
 126       worst_rating = population[i].rating;
 127       worst_index  = i;
 128     }
 129
 130   nmemb = max_population_size - (worst_index + 1);
 131
 132   sn_network_destroy (population[worst_index].network);
 133   population[worst_index].network = NULL;
 134
 135   memmove (population + worst_index,
 136       population + (worst_index + 1),
 137       nmemb * sizeof (population_entry_t));
 138
 139   population[max_population_size - 1].network = n;
 140   population[max_population_size - 1].rating  = rating;
 141
 142   return (0);
 143 } /* int insert_into_population */
 144
 145 static int create_offspring (void)
 146 {
 147   int p0;
 148   int p1;
 149   sn_network_t *n;
 150
 151   p0 = bounded_random (population_size);
 152   p1 = bounded_random (population_size);
 153
 154   n = sn_network_combine (population[p0].network, population[p1].network);
 155
 156   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 157   {
 158     int pos;
 159     enum sn_network_cut_dir_e dir;
 160
 161     pos = bounded_random (SN_NETWORK_INPUT_NUM (n));
 162     dir = (bounded_random (2) == 0) ? DIR_MIN : DIR_MAX;
 163
 164     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 165
 166     sn_network_cut_at (n, pos, dir);
 167   }
 168
 169   sn_network_compress (n);
 170
 171   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 172
 173   insert_into_population (n);
 174
 175   return (0);
 176 } /* int create_offspring */
 177
 178 static int start_evolution (void)
 179 {
 180   int i;
 181
 182   for (i = 0; i < iterations_num; i++)
 183   {
 184     if ((i % 1000) == 0)
 185       population_print_stats (i);
 186
 187     create_offspring ();
 188   }
 189
 190   return (0);
 191 } /* int start_evolution */
 192
 193 int main (int argc, char **argv)
 194 {
 195   struct sigaction sigint_action;
 196
 197   if (argc != 2)
 198     exit_usage (argv[0]);
 199
 200   init_random ();
 201
 202   memset (&sigint_action, '\0', sizeof (sigint_action));
 203   sigint_action.sa_handler = sigint_handler;
 204   sigaction (SIGINT, &sigint_action, NULL);
 205
 206   population = (population_entry_t *) malloc (max_population_size
 207       * sizeof (population_entry_t));
 208   if (population == NULL)
 209   {
 210     printf ("Malloc failed.\n");
 211     return (-1);
 212   }
 213   memset (population, '\0', max_population_size
 214       * sizeof (population_entry_t));
 215
 216   {
 217     sn_network_t *n = sn_network_read_file (argv[1]);
 218     if (n == NULL)
 219     {
 220       printf ("n == NULL\n");
 221       return (1);
 222     }
 223     population[0].network = n;
 224     population[0].rating  = rate_network (n);
 225     population_size++;
 226   }
 227
 228   start_evolution ();
 229
 230   {
 231     int i;
 232     int best_rate = -1;
 233     int best_index = -1;
 234
 235     for (i = 0; i < population_size; i++)
 236     {
 237       if ((best_rate == -1) || (best_rate > population[i].rating))
 238       {
 239         best_rate = population[i].rating;
 240         best_index = i;
 241       }
 242     }
 243
 244     sn_network_show (population[best_index].network);
 245   }
 246
 247   return (0);
 248 } /* int main */
 249
 250 /* vim: set shiftwidth=2 softtabstop=2 : */