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