stage1.c

   1 /* GAUL Genetic Programming Tutorial - stage 1 */
   2
   3 /* Evolve a simple four function calculator from 2 text files. Input text file
   4  * is a list of simple math questions (1+1=, 4-1=, 3*3=, 12/2=). output text
   5  * file contains correct answers (2, 3, 9, 6). Each member of the population
   6  * would need to input the text file and produce its own output file. The
   7  * fitness function would need to compare each population output file the
   8  * correct math output file. Input file will only have 2 arguments per question
   9  * and only the four basic functions (+,-,*,/). */
  10
  11 /* Stage1: Loop, parser code non-evolved, chromosome is mapping from characters to operations */
  12
  13 #include "gaul.h"
  14
  15
  16 /* Number of equations in the file. Just to make the code simpler. */
  17 #define EQNO 100
  18
  19 /* Reference results. */
  20 static int refresults[EQNO];
  21
  22 /* Loads reference results. */
  23 static void
  24 load_reference_results(void)
  25 {
  26         /* Open file. */
  27         FILE *f = fopen("eq.out", "r");
  28         if (!f) {
  29                 perror("eq.out");
  30                 exit(EXIT_FAILURE);
  31         }
  32
  33         int eq = 0;
  34
  35         /* Read one line at a time. */
  36         char line[256];
  37         while (fgets(line, sizeof(line), f)) {
  38                 /* Convert line to number and store it
  39                  * in the refresults[] array. */
  40                 refresults[eq++] = atoi(line);
  41         }
  42
  43         /* Close file. */
  44         fclose(f);
  45 }
  46
  47
  48 /* Chromosome format: The chromosome here is a four-item array. The items
  49  * correspond to the:
  50  * 0. '+' operator
  51  * 1. '-' operator
  52  * 2. '*' operator
  53  * 3. '/' operator
  54  * Each item value is a number from 0 to 3. The numbers correspond
  55  * to operations:
  56  * 0. addition
  57  * 1. subtraction
  58  * 2. multiplication
  59  * 3. division
  60  *
  61  * Therefore, the correct chromosome is { 0, 1, 2, 3 }. */
  62
  63
  64 /* Initializes a single entity randomly. */
  65 static boolean
  66 seed_entity(population *pop, entity *entity)
  67 {
  68         int *intchromosome = (int *) entity->chromosome[0];
  69
  70         for (int i = 0; i < pop->len_chromosomes; i++)
  71                 intchromosome[i] = random_int(4);
  72
  73         return TRUE;
  74 }
  75
  76 /* Mutates an entity. */
  77 static void
  78 mutate_entity(population *pop, entity *father, entity *son)
  79 {
  80         /* Copy genome from father. */
  81         int *intchromosome_father = (int *) father->chromosome[0];
  82         int *intchromosome_son = (int *) son->chromosome[0];
  83         for (int i = 0; i < pop->len_chromosomes; i++)
  84                 intchromosome_son[i] = intchromosome_father[i];
  85
  86         /* Select mutation locus. */
  87         int point = random_int(pop->len_chromosomes);
  88
  89         /* Mutate by tweaking a single allele. */
  90         intchromosome_son[point] = random_int(4);
  91 }
  92
  93 /* Execute a single entity, interpreting its chromosome.
  94  * Saves the results to a number array. */
  95 static void
  96 execute_entity(entity *entity, int results[EQNO])
  97 {
  98         /* Open file. */
  99         FILE *f = fopen("eq.in", "r");
 100         if (!f) {
 101                 perror("eq.in");
 102                 exit(EXIT_FAILURE);
 103         }
 104
 105         int eq = 0;
 106
 107         /* Read one line at a time. */
 108         char line[256];
 109         while (fgets(line, sizeof(line), f)) {
 110                 /* Parse line. We do not handle errors here. */
 111                 int arg1, arg2;
 112                 char op;
 113                 sscanf(line, "%d%c%d=", &arg1, &op, &arg2);
 114
 115                 /* Parse operator. */
 116                 int item = 0;
 117                 switch (op) {
 118                         case '+': item = 0; break;
 119                         case '-': item = 1; break;
 120                         case '*': item = 2; break;
 121                         case '/': item = 3; break;
 122                 }
 123
 124                 /* Lookup operation. */
 125                 int *intchromosome = (int *) entity->chromosome[0];
 126                 int operation = intchromosome[item];
 127
 128                 /* Perform operation. */
 129                 int result = 0;
 130                 switch (operation) {
 131                         case 0: result = arg1 + arg2; break;
 132                         case 1: result = arg1 - arg2; break;
 133                         case 2: result = arg1 * arg2; break;
 134                         case 3:
 135                                 if (arg2 != 0) {
 136                                         result = arg1 / arg2;
 137                                 } else {
 138                                         /* Division by zero. Set the result
 139                                          * to a value that we cannot achieve
 140                                          * otherwise (with default ./generate
 141                                          * settings). */
 142                                         result = -100000;
 143                                 }
 144                                 break;
 145                 }
 146
 147                 /* Store result. */
 148                 results[eq++] = result;
 149         }
 150
 151         /* Close file. */
 152         fclose(f);
 153 }
 154
 155 static boolean
 156 evaluate_entity(population *pop, entity *entity)
 157 {
 158         /* Get results computed by our entity. */
 159         int results[EQNO];
 160         execute_entity(entity, results);
 161
 162         /* Count number of differences to reference results. */
 163         int diffcount = 0;
 164         for (int i = 0; i < EQNO; i++) {
 165                 if (results[i] != refresults[i])
 166                         diffcount++;
 167         }
 168
 169         /* Compute entity fitness. With no differences, fitness
 170          * will be 1; with no match, fitness will be 0. With
 171          * e.g. 75% match, fitness will be 0.75. */
 172         /* The (double) typecast makes sure / will be floating,
 173          * not integer division. */
 174         entity->fitness = 1.0 - (double) diffcount / EQNO;
 175
 176         return TRUE;
 177 }
 178
 179 int main(int argc, char **argv)
 180 {
 181         char *beststring = NULL; /* Human readable form of best solution. */
 182         size_t beststrlen = 0;   /* Length of beststring. */
 183
 184         /* Load results of equations to compare the entities to. */
 185         load_reference_results();
 186
 187         /* Run the algorithm several times. */
 188         for (int i = 1; i < 10; i++) {
 189                 /* Make sure different random numbers are tried in each
 190                  * iteration, but same results are obtained over repeated
 191                  * program runs. */
 192                 random_seed(i * 16801);
 193                 /* The random number generator in GAUL behaves extraordinarily
 194                  * poorly in case it is used to generate numbers 0..2^k-1 where
 195                  * k is small. Its behavior improves after some time,
 196                  * so this drains its initial state by asking for a random
 197                  * number many times. */
 198                 for (int j = 0; j < 10000; j++)
 199                         (void) random_rand();
 200
 201                 /* Set up the initial population and define the genetic
 202                  * operators (names of functions for assigning fitness,
 203                  * mutation, crossover, etc.). */
 204                 population *pop = ga_genesis_integer(
 205                         4,                      /* const int              population_size */
 206                         1,                      /* const int              num_chromo */
 207                         4,                      /* const int              len_chromo */
 208                         NULL,                   /* GAgeneration_hook      generation_hook */
 209                         NULL,                   /* GAiteration_hook       iteration_hook */
 210                         NULL,                   /* GAdata_destructor      data_destructor */
 211                         NULL,                   /* GAdata_ref_incrementor data_ref_incrementor */
 212                         evaluate_entity,        /* GAevaluate             evaluate */
 213                         seed_entity,            /* GAseed                 seed */
 214                         NULL,                   /* GAadapt                adapt */
 215                         ga_select_one_sus,      /* GAselect_one           select_one */
 216                         ga_select_two_sus,      /* GAselect_two           select_two */
 217                         mutate_entity,          /* GAmutate               mutate */
 218                         ga_crossover_integer_singlepoints,      /* GAcrossover            crossover */
 219                         NULL,                   /* GAreplace              replace */
 220                         NULL                    /* vpointer               User data */
 221                 );
 222
 223                 /* Set parameters of the genetic algorithm. */
 224                 ga_population_set_parameters(
 225                         pop,                    /* population      *pop */
 226                         GA_SCHEME_DARWIN,       /* const ga_scheme_type     scheme */
 227                         GA_ELITISM_PARENTS_DIE, /* const ga_elitism_type   elitism */
 228                         0.9,                    /* double  crossover */
 229                         0.2,                    /* double  mutation */
 230                         0.0                     /* double  migration */
 231                 );
 232
 233                 /* Run the genetic algorithm for 10 generations. */
 234                 ga_evolution(
 235                         pop,                    /* population      *pop */
 236                         10                      /* const int       max_generations */
 237                 );
 238
 239                 /* Print the winner. */
 240                 printf("The solution with seed = %d was:\n", i);
 241                 beststring = ga_chromosome_integer_to_string(pop, ga_get_entity_from_rank(pop, 0), beststring, &beststrlen);
 242                 printf("%s\n", beststring);
 243                 printf("With score = %f\n", ga_entity_get_fitness(ga_get_entity_from_rank(pop, 0)));
 244
 245                 ga_extinction(pop);
 246         }
 247
 248         s_free(beststring);
 249
 250         exit(EXIT_SUCCESS);
 251 }