From 2c6214f745ea35eb29984086175c5fa76f1a484f Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Fri, 10 Aug 2012 18:30:21 +0200 Subject: [PATCH] stage1: Implement --- Makefile | 9 +++ stage1.c | 251 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 260 insertions(+) create mode 100644 stage1.c diff --git a/Makefile b/Makefile index 0eac7e5..8e94777 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,13 @@ CFLAGS=-Wall -O3 -g -std=gnu99 +LIBS=-lgaul -lgaul_util + +all: generator stage1 generator: generator.o $(CC) $(LDFLAGS) -o $@ $^ + +stage1: stage1.o + $(CC) $(LDFLAGS) -o $@ $^ $(LIBS) + +clean: + rm -f *.o stage1 generator diff --git a/stage1.c b/stage1.c new file mode 100644 index 0000000..9b1466c --- /dev/null +++ b/stage1.c @@ -0,0 +1,251 @@ +/* GAUL Genetic Programming Tutorial - stage 1 */ + +/* Evolve a simple four function calculator from 2 text files. Input text file + * is a list of simple math questions (1+1=, 4-1=, 3*3=, 12/2=). output text + * file contains correct answers (2, 3, 9, 6). Each member of the population + * would need to input the text file and produce its own output file. The + * fitness function would need to compare each population output file the + * correct math output file. Input file will only have 2 arguments per question + * and only the four basic functions (+,-,*,/). */ + +/* Stage1: Loop, parser code non-evolved, chromosome is mapping from characters to operations */ + +#include "gaul.h" + + +/* Number of equations in the file. Just to make the code simpler. */ +#define EQNO 100 + +/* Reference results. */ +static int refresults[EQNO]; + +/* Loads reference results. */ +static void +load_reference_results(void) +{ + /* Open file. */ + FILE *f = fopen("eq.out", "r"); + if (!f) { + perror("eq.out"); + exit(EXIT_FAILURE); + } + + int eq = 0; + + /* Read one line at a time. */ + char line[256]; + while (fgets(line, sizeof(line), f)) { + /* Convert line to number and store it + * in the refresults[] array. */ + refresults[eq++] = atoi(line); + } + + /* Close file. */ + fclose(f); +} + + +/* Chromosome format: The chromosome here is a four-item array. The items + * correspond to the: + * 0. '+' operator + * 1. '-' operator + * 2. '*' operator + * 3. '/' operator + * Each item value is a number from 0 to 3. The numbers correspond + * to operations: + * 0. addition + * 1. subtraction + * 2. multiplication + * 3. division + * + * Therefore, the correct chromosome is { 0, 1, 2, 3 }. */ + + +/* Initializes a single entity randomly. */ +static boolean +seed_entity(population *pop, entity *entity) +{ + int *intchromosome = (int *) entity->chromosome[0]; + + for (int i = 0; i < pop->len_chromosomes; i++) + intchromosome[i] = random_int(4); + + return TRUE; +} + +/* Mutates an entity. */ +static void +mutate_entity(population *pop, entity *father, entity *son) +{ + /* Copy genome from father. */ + int *intchromosome_father = (int *) father->chromosome[0]; + int *intchromosome_son = (int *) son->chromosome[0]; + for (int i = 0; i < pop->len_chromosomes; i++) + intchromosome_son[i] = intchromosome_father[i]; + + /* Select mutation locus. */ + int point = random_int(pop->len_chromosomes); + + /* Mutate by tweaking a single allele. */ + intchromosome_son[point] = random_int(4); +} + +/* Execute a single entity, interpreting its chromosome. + * Saves the results to a number array. */ +static void +execute_entity(entity *entity, int results[EQNO]) +{ + /* Open file. */ + FILE *f = fopen("eq.in", "r"); + if (!f) { + perror("eq.in"); + exit(EXIT_FAILURE); + } + + int eq = 0; + + /* Read one line at a time. */ + char line[256]; + while (fgets(line, sizeof(line), f)) { + /* Parse line. We do not handle errors here. */ + int arg1, arg2; + char op; + sscanf(line, "%d%c%d=", &arg1, &op, &arg2); + + /* Parse operator. */ + int item = 0; + switch (op) { + case '+': item = 0; break; + case '-': item = 1; break; + case '*': item = 2; break; + case '/': item = 3; break; + } + + /* Lookup operation. */ + int *intchromosome = (int *) entity->chromosome[0]; + int operation = intchromosome[item]; + + /* Perform operation. */ + int result = 0; + switch (operation) { + case 0: result = arg1 + arg2; break; + case 1: result = arg1 - arg2; break; + case 2: result = arg1 * arg2; break; + case 3: + if (arg2 != 0) { + result = arg1 / arg2; + } else { + /* Division by zero. Set the result + * to a value that we cannot achieve + * otherwise (with default ./generate + * settings). */ + result = -100000; + } + break; + } + + /* Store result. */ + results[eq++] = result; + } + + /* Close file. */ + fclose(f); +} + +static boolean +evaluate_entity(population *pop, entity *entity) +{ + /* Get results computed by our entity. */ + int results[EQNO]; + execute_entity(entity, results); + + /* Count number of differences to reference results. */ + int diffcount = 0; + for (int i = 0; i < EQNO; i++) { + if (results[i] != refresults[i]) + diffcount++; + } + + /* Compute entity fitness. With no differences, fitness + * will be 1; with no match, fitness will be 0. With + * e.g. 75% match, fitness will be 0.75. */ + /* The (double) typecast makes sure / will be floating, + * not integer division. */ + entity->fitness = 1.0 - (double) diffcount / EQNO; + + return TRUE; +} + +int main(int argc, char **argv) +{ + char *beststring = NULL; /* Human readable form of best solution. */ + size_t beststrlen = 0; /* Length of beststring. */ + + /* Load results of equations to compare the entities to. */ + load_reference_results(); + + /* Run the algorithm several times. */ + for (int i = 1; i < 10; i++) { + /* Make sure different random numbers are tried in each + * iteration, but same results are obtained over repeated + * program runs. */ + random_seed(i * 16801); + /* The random number generator in GAUL behaves extraordinarily + * poorly in case it is used to generate numbers 0..2^k-1 where + * k is small. Its behavior improves after some time, + * so this drains its initial state by asking for a random + * number many times. */ + for (int j = 0; j < 10000; j++) + (void) random_rand(); + + /* Set up the initial population and define the genetic + * operators (names of functions for assigning fitness, + * mutation, crossover, etc.). */ + population *pop = ga_genesis_integer( + 4, /* const int population_size */ + 1, /* const int num_chromo */ + 4, /* const int len_chromo */ + NULL, /* GAgeneration_hook generation_hook */ + NULL, /* GAiteration_hook iteration_hook */ + NULL, /* GAdata_destructor data_destructor */ + NULL, /* GAdata_ref_incrementor data_ref_incrementor */ + evaluate_entity, /* GAevaluate evaluate */ + seed_entity, /* GAseed seed */ + NULL, /* GAadapt adapt */ + ga_select_one_sus, /* GAselect_one select_one */ + ga_select_two_sus, /* GAselect_two select_two */ + mutate_entity, /* GAmutate mutate */ + ga_crossover_integer_singlepoints, /* GAcrossover crossover */ + NULL, /* GAreplace replace */ + NULL /* vpointer User data */ + ); + + /* Set parameters of the genetic algorithm. */ + ga_population_set_parameters( + pop, /* population *pop */ + GA_SCHEME_DARWIN, /* const ga_scheme_type scheme */ + GA_ELITISM_PARENTS_DIE, /* const ga_elitism_type elitism */ + 0.9, /* double crossover */ + 0.2, /* double mutation */ + 0.0 /* double migration */ + ); + + /* Run the genetic algorithm for 10 generations. */ + ga_evolution( + pop, /* population *pop */ + 10 /* const int max_generations */ + ); + + /* Print the winner. */ + printf("The solution with seed = %d was:\n", i); + beststring = ga_chromosome_integer_to_string(pop, ga_get_entity_from_rank(pop, 0), beststring, &beststrlen); + printf("%s\n", beststring); + printf("With score = %f\n", ga_entity_get_fitness(ga_get_entity_from_rank(pop, 0))); + + ga_extinction(pop); + } + + s_free(beststring); + + exit(EXIT_SUCCESS); +} -- 2.11.4.GIT