stage2: Extensively comment the source code

[gaul-genprog.git] / stage2.c

/* GAUL Genetic Programming Tutorial - stage 2 */

/* 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 (+,-,*,/). */

/* Stage2: Loop, parser code non-evolved, chromosome is genetic program taking (number, character, number) as its input */

#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 is a program in the form of evaluation tree. Nodes
 * of the tree are functions, with children (in-order) being their
 * parameters; leaves may be integer constants or reference program
 * variables. The program is evaluated left to right, recursively
 * from the root downwards.
 *
 * Functions: ADD, SUB, MUL, DIV, IFEQ
 *
 * Variables: X (first operand), Y (second operand) and Z
 * (operator letter - can be also thought of as its ASCII value). */


/*** PROGRAM TREE STRUCTURE DEFINITIONS */


/* Common header for all nodes. This is contained by actual node
 * structures specific to each type of function. */
struct program_node {
        enum program_node_type {
                PNT_FUNCTION,
                PNT_CONSTANT,
                PNT_VARIABLE,
                PNT__MAX
        } type;
        struct program_node *child; /* Children in tree. */
        struct program_node *sibling; /* Sibling in tree. */
};

struct program_function; /* See below for function classes. */

struct program_node_function {
        struct program_node pn;
        const struct program_function *funct;
};

struct program_node_constant {
        struct program_node pn;
        int value;
};

struct program_node_variable {
        struct program_node pn;
        char name; // X, Y or Z
};


/*** PROGRAM BUILTIN FUNCTIONS DEFINITIONS */


/* The way the program tree itself is called. This describes
 * the parameters of the program, i.e. the values of the variables. */
struct program_call {
        int X, Y, Z;
};


/* Available functions are described by the program_function structure. */
typedef int (*program_function_eval)(struct program_call *pc, int params[]);
struct program_function {
        char *name; /* String description for printing. */
        int n_params; /* Number of parameters. */
        program_function_eval eval; /* Evaluation function - takes parameters and produces value. */
};

/* ADD function */
static int
pf_add_eval(struct program_call *pc, int params[])
{
        return params[0] + params[1];
}
static const struct program_function pf_add = {
        .name = "ADD",
        .n_params = 2,
        .eval = pf_add_eval,
};

/* SUB function */
static int
pf_sub_eval(struct program_call *pc, int params[])
{
        return params[0] - params[1];
}
static const struct program_function pf_sub = {
        .name = "SUB",
        .n_params = 2,
        .eval = pf_sub_eval,
};

/* MUL function */
static int
pf_mul_eval(struct program_call *pc, int params[])
{
        return params[0] * params[1];
}
static const struct program_function pf_mul = {
        .name = "MUL",
        .n_params = 2,
        .eval = pf_mul_eval,
};

/* DIV function */
static int
pf_div_eval(struct program_call *pc, int params[])
{
        if (params[1] == 0)
                return -100000; /* A normally impossible value. */
        return params[0] / params[1];
}
static const struct program_function pf_div = {
        .name = "DIV",
        .n_params = 2,
        .eval = pf_div_eval,
};

/* IFEQ function */
/* The parameter order here is a bit unusual:
 * IFEQ(A, B, C, D) means if (C == D) then B else A */
static int
pf_ifeq_eval(struct program_call *pc, int params[])
{
        /* The parameters are in this order so that the first
         * two parameters (and particularly the != case) have
         * highest chance of having the largest subtrees
         * (when not using the hinting logic). */
        return params[2] == params[3] ? params[1] : params[0];
}
static const struct program_function pf_ifeq = {
        .name = "IFEQ",
        .n_params = 4,
        .eval = pf_ifeq_eval,
};

/* List of all program functions, for randomly picking one. */
static const struct program_function *program_functions[] = {
        &pf_add, &pf_sub, &pf_mul, &pf_div, &pf_ifeq
};
static const int program_functions_n = sizeof(program_functions) / sizeof(program_functions[0]);


/*** PROGRAM EVALUATION ROUTINES */


static int program_node_eval(struct program_call *pc, struct program_node *node);

static int
program_node_function_eval(struct program_call *pc, struct program_node_function *node)
{
        /* Visit all children in order and evaluate them, storing the values
         * in a params[] array. */
        int params[node->funct->n_params];
        int i = 0;
        for (struct program_node *param_node = node->pn.child; param_node; param_node = param_node->sibling) {
                assert(i < node->funct->n_params);
                params[i] = program_node_eval(pc, param_node);
                i++;
        }
        assert(i == node->funct->n_params);

        /* Then, evaluate the function itself with the given parameters. */
        return node->funct->eval(pc, params);
}

static int
program_node_constant_eval(struct program_call *pc, struct program_node_constant *node)
{
        return node->value;
}

static int
program_node_variable_eval(struct program_call *pc, struct program_node_variable *node)
{
        switch (node->name) {
                case 'X': return pc->X;
                case 'Y': return pc->Y;
                case 'Z': return pc->Z;
                default: return -100000; /* A normally impossible value. */
        }
}

/* Evaluate a given program, returning the resulting return
 * value of the function at the root of the tree. */
static int
program_node_eval(struct program_call *pc, struct program_node *node)
{
        switch (node->type) {
                case PNT_FUNCTION:
                        return program_node_function_eval(pc, (struct program_node_function *) node);
                case PNT_CONSTANT:
                        return program_node_constant_eval(pc, (struct program_node_constant *) node);
                case PNT_VARIABLE:
                        return program_node_variable_eval(pc, (struct program_node_variable *) node);
        }
        return -100000;
}


/*** PROGRAM PRETTY-PRINTING ROUTINES */


static void program_node_print(FILE *f, struct program_node *node);

static void
program_node_function_print(FILE *f, struct program_node_function *node)
{
        fprintf(f, "%s(", node->funct->name);
        /* Visit all children in order and print them. */
        for (struct program_node *param_node = node->pn.child; param_node; param_node = param_node->sibling) {
                program_node_print(f, param_node);
                if (param_node->sibling)
                        fputs(", ", f);
        }
        fputs(")", f);
}

static void
program_node_constant_print(FILE *f, struct program_node_constant *node)
{
        fprintf(f, "%d:%c", node->value, node->value);
}

static void
program_node_variable_print(FILE *f, struct program_node_variable *node)
{
        fprintf(f, "%c", node->name);
}

/* Print a given program in human-readable format. */
static void
program_node_print(FILE *f, struct program_node *node)
{
        switch (node->type) {
                case PNT_FUNCTION:
                        program_node_function_print(f, (struct program_node_function *) node);
                        break;
                case PNT_CONSTANT:
                        program_node_constant_print(f, (struct program_node_constant *) node);
                        break;
                case PNT_VARIABLE:
                        program_node_variable_print(f, (struct program_node_variable *) node);
                        break;
        }
}


/*** PROGRAM NODE COPY ROUTINES */


static struct program_node *program_node_copy(struct program_node *node);

static struct program_node *
program_node_function_copy(struct program_node_function *node)
{
        struct program_node_function *newnode = malloc(sizeof(*newnode));
        newnode->pn.type = PNT_FUNCTION;
        newnode->pn.child = newnode->pn.sibling = NULL;
        newnode->funct = node->funct;

        struct program_node *lastchild = NULL;
        for (struct program_node *param_node = node->pn.child; param_node; param_node = param_node->sibling) {
                struct program_node *child = program_node_copy(param_node);
                /* Link the children to the program tree. */
                if (!lastchild)
                        newnode->pn.child = child;
                else
                        lastchild->sibling = child;
                lastchild = child;
        }

        return (struct program_node *) newnode;
}

static struct program_node *
program_node_constant_copy(struct program_node_constant *node)
{
        struct program_node_constant *newnode = malloc(sizeof(*newnode));
        newnode->pn.type = PNT_CONSTANT;
        newnode->pn.child = newnode->pn.sibling = NULL;
        newnode->value = node->value;
        return (struct program_node *) newnode;
}

static struct program_node *
program_node_variable_copy(struct program_node_variable *node)
{
        struct program_node_variable *newnode = malloc(sizeof(*newnode));
        newnode->pn.type = PNT_VARIABLE;
        newnode->pn.child = newnode->pn.sibling = NULL;
        newnode->name = node->name;
        return (struct program_node *) newnode;
}

/* Produce a recursive memory copy of the given node and all its children. */
static struct program_node *
program_node_copy(struct program_node *node)
{
        switch (node->type) {
                case PNT_FUNCTION:
                        return program_node_function_copy((struct program_node_function *) node);
                case PNT_CONSTANT:
                        return program_node_constant_copy((struct program_node_constant *) node);
                case PNT_VARIABLE:
                        return program_node_variable_copy((struct program_node_variable *) node);
        }
        return NULL;
}


/*** PROGRAM LIFETIME ROUTINES */


/* Generate a random node, including possibly a sub-tree. The energy
 * represents desired size of the sub-tree (approximately; it can be
 * slightly more). */
static struct program_node *
program_node_random(int energy, struct program_node *parent)
{
        /* This function includes some hints so that the solution is pushed
         * towards the canonical form of something like:
         *
         *      IFEQ(IFEQ(IFEQ(ADD(Y, X), DIV(X, Y), 47:/, Z), SUB(X, Y), Z, 45:-), MUL(X, Y), Z, 42:*)
         *
         * To enable and disable hints, just flip 0 and 1. Disabling hint
         * will usually need to be accompanied by significantly raising
         * population size and/or the number of generations. */

        /* Prepare information used by the hinting logic. */

        struct program_node_function *parentf = (struct program_node_function *) parent;
        bool allow_constant = true, variable_xy = true;
        if (parent) {
                parentf = (struct program_node_function *) parent;
#if 1 /* Hint importance: low (small improvement) */
                /* XXX: Hinting - allow constants only as parameters of IF. */
                allow_constant = (parentf->funct == &pf_ifeq);
#endif
                variable_xy = (parentf->funct != &pf_ifeq);
        }

        /* If energy is 1, this node will be a "simple" node:
         * a constant or a variable, not function. */

        if (energy == 1) {
                if (allow_constant && random_boolean()) {
                        /* Generate a constant node. */
                        struct program_node_constant *node = malloc(sizeof(*node));
                        node->pn.type = PNT_CONSTANT;
                        node->pn.child = node->pn.sibling = NULL;
#if 1 /* Hint importance: high (large population and many generations will still find solution) */
                        /* XXX: Hinting - only constants that correspond to arithmetic operator characters. */
                        node->value = "+-*/"[random_int(4)];
#else
                        node->value = random_int(256);
#endif
                        return (struct program_node *) node;

                } else {
                        /* Generate a variable node. */
                        struct program_node_variable *node = malloc(sizeof(*node));
                        node->pn.type = PNT_VARIABLE;
                        node->pn.child = node->pn.sibling = NULL;
#if 1 /* Hint importance: high (large population and many generations will still find solution) */
                        /* XXX: Hinting - X, Y anywhere but IFEQ, Z forced there. */
                        if (variable_xy) {
                                node->name = "XY"[random_int(2)];
                        } else {
                                node->name = 'Z';
                        }
#else
                        node->name = "XYZ"[random_int(3)];
#endif
                        return (struct program_node *) node;
                }
        }

        /* Generate a function node. */

        /* Pick a random function. */
        const struct program_function *f = program_functions[random_int(program_functions_n)];

        /* Create the function node. */
        struct program_node_function *node = malloc(sizeof(*node));
        node->pn.type = PNT_FUNCTION;
        node->pn.child = node->pn.sibling = NULL;
        node->funct = f;

        /* Decrease energy by function node. */
        energy--;
        if (energy < f->n_params)
                energy = f->n_params;

        /* Create parameter children. */

#if 1 /* Hint importance: very high (very long time needed to approach correct result) */
        if (node->funct == &pf_ifeq) {
                /* XXX: Hinting: IFEQ children template */
                int children_energy = energy - (f->n_params - 1 - 2);
                int child_energy = random_int(children_energy);
                /* "ELSE" branch - multiple nodes */
                node->pn.child = program_node_random(1 + child_energy, (struct program_node *) node);
                /* "THEN" branch - multiple nodes */
                node->pn.child->sibling = program_node_random(1 + children_energy - child_energy, (struct program_node *) node);
                /* "X in X == Y" branch - simple node */
                node->pn.child->sibling->sibling = program_node_random(1, (struct program_node *) node);
                /* "Y in X == Y" branch - simple node */
                node->pn.child->sibling->sibling->sibling = program_node_random(1, (struct program_node *) node);
        } else {
                /* XXX: Hinting: Simple function template - simple nodes as children only */
                node->pn.child = program_node_random(1, (struct program_node *) node);
                node->pn.child->sibling = program_node_random(1, (struct program_node *) node);
        }

#else
        /* Generic tree-growing code without templates. */
        struct program_node *lastchild = NULL;
        for (int i = 0; i < f->n_params; i++) {
                /* Remaining energy is randomly distributed between children. */
                int child_energy = 1 + random_int(energy - (f->n_params - 1 - i));
                /* Recursively create randomized children. */
                struct program_node *child = program_node_random(child_energy, (struct program_node *) node);
                /* Link the children to the program tree. */
                if (!lastchild)
                        node->pn.child = child;
                else
                        lastchild->sibling = child;
                lastchild = child;
        }
#endif

        return (struct program_node *) node;
}


/* Recursively release memory occupied by this node and all its children. */
static void
program_node_done(struct program_node *node)
{
        struct program_node *cnode = node->child;
        while (cnode) {
                /* cnode_sibling is temporary variable for storing the
                 * pointer of the next sibling. This is necessary since
                 * the moment we want to move on to the sibling, we cannot
                 * look at the pointer in the current node anymore since
                 * we have already free()d the node. */
                struct program_node *cnode_sibling = cnode->sibling;
                program_node_done(cnode);
                cnode = cnode_sibling;
        }

        free(node);
}


/*** PROGRAM TREE WALKING (OTHER) */


/* Measure size of a program sub-tree in term of number of nodes. */
static int
program_node_subtree_size(struct program_node *node)
{
        if (!node)
                return 0;

        int size = 1; /* Self. */

        for (struct program_node *param_node = node->child; param_node; param_node = param_node->sibling) {
                if (param_node->child)
                        size += program_node_subtree_size(param_node);
                else
                        size++;
        }

        return size;
}

/* Store pointers to all nodes in the given subtree (and their corresponding
 * fathers and left (previous) siblings) in a flat array nodes[]. */
static int
program_node_subtree_list(struct program_node *node, struct program_node *nodes[], struct program_node *fathers[], struct program_node *psiblings[])
{
        int i = 0;

        struct program_node *prev_node = NULL;
        for (struct program_node *param_node = node->child; param_node; prev_node = param_node, param_node = param_node->sibling) {
                nodes[i] = param_node;
                fathers[i] = node;
                psiblings[i] = prev_node;
                i++;
                if (param_node->child) {
                        i += program_node_subtree_list(param_node, &nodes[i], &fathers[i], &psiblings[i]);
                }
        }
        return i;
}

/* Randomly pick a node in the program tree rooted at @node. Also give
 * (in *father and *psibling) pointers to its father and left (previous)
 * sibling. */
static struct program_node *
program_node_subtree_random_pick(struct program_node *node, struct program_node **father, struct program_node **psibling)
{
        int size = program_node_subtree_size(node);

        /* Flat array to collect all nodes. */
        struct program_node *nodes[size], *fathers[size], *psiblings[size];
        nodes[0] = node; fathers[0] = NULL; psiblings[0] = NULL;

        /* Collect all the nodes into the flat array. */
        int s = program_node_subtree_list(node, &nodes[1], &fathers[1], &psiblings[1]) + 1;
        assert(s == size);

        /* Randomly pick an element of the array. */
        int i = random_int(size);
        // printf("pick %d/%d\n", i, size);
        *father = fathers[i];
        *psibling = psiblings[i];
        return nodes[i];
}


/*** CHROMOSOME MANAGEMENT */


/* How is the program represented from GAUL view? The GAUL operates
 * in terms of entities (members of the population) which are composed
 * from chromosomes.
 *
 * We use only a single chromosome per entity, i.e. chromosomes are
 * 1:1 with population members for us. The chromosome is then a pointer
 * to the root node of the program tree corresponding to the entity. */


/* A service routine for creating a chromosome (i.e. a single member
 * of the population. */
boolean
program_chromosome_constructor(population *pop, entity *embryo)
{
        if (!pop) die("Null pointer to population structure passed.");
        if (!embryo) die("Null pointer to entity structure passed.");

        if (embryo->chromosome!=NULL)
                die("This entity already contains chromosomes.");

        embryo->chromosome = s_malloc(sizeof(struct program_node *));
        /* Initialize the chromosome with no program. */
        embryo->chromosome[0] = NULL;

        return TRUE;
}

/* A service routine for releasing a chromosome (i.e. a single member
 * of the population. */
void
program_chromosome_destructor(population *pop, entity *corpse)
{
        if (!pop) die("Null pointer to population structure passed.");
        if (!corpse) die("Null pointer to entity structure passed.");

        if (corpse->chromosome==NULL)
                die("This entity already contains no chromosomes.");

        program_node_done(corpse->chromosome[0]);
        s_free(corpse->chromosome);
        corpse->chromosome = NULL;
}

/* A service routine for replicating a chromosome (i.e. a single member
 * of the population. */
void
program_chromosome_replicate(const population *pop, entity *src, entity *dest, const int chromosomeid)
{
        if (!pop) die("Null pointer to population structure passed.");
        if (!src || !dest) die("Null pointer to entity structure passed.");
        if (!src->chromosome || !dest->chromosome) die("Entity has no chromosomes.");
        if (!src->chromosome[0]) die("Source entity has empty chromosomes.");
        if (dest->chromosome[0]) die("Target entity has empty chromosomes.");
        if (chromosomeid != 0) die("Invalid chromosome index passed.");

        dest->chromosome[0] = program_node_copy((struct program_node *) src->chromosome[0]);
}


/*** GENETIC OPERATORS */


/* Initializes a single entity randomly. */
static boolean
seed_entity(population *pop, entity *entity)
{
        entity->chromosome[0] = program_node_random(4 * 4 + 1, NULL);
        return TRUE;
}


/* Mutates an entity. */
static void
mutate_entity(population *pop, entity *father, entity *son)
{
        // printf("%p (%p) <- %p (%p)\n", son, son->chromosome[0], father, father->chromosome[0]);

        /* A mutated entity starts off as a 1:1 copy of the original entity. */
        son->chromosome[0] = program_node_copy((struct program_node *) father->chromosome[0]);

        /* Randomly pick a node. */
        struct program_node *mnode_father, *mnode_psibling;
        struct program_node *mnode = program_node_subtree_random_pick(son->chromosome[0], &mnode_father, &mnode_psibling);

        /* Mutation means that this node (including a subtree it
         * potentially holds gets replaced by a random new node. */

        /* With 50% probability, the new node is a simple node
         * with energy 1 (variable or constant). Otherwise, it is
         * assigned a random energy in the range of 2 to 10 and
         * therefore becomes a function node holding a small subtree
         * of its own. */
        int energy = random_boolean() ? 1 : 8.0 * random_double_1() + 2;

        struct program_node *newnode = program_node_random(energy, mnode_father);

        /* Link up the new node in stead of the original node. */
        if (mnode_psibling)
                mnode_psibling->sibling = newnode;
        else if (mnode_father)
                mnode_father->child = newnode;
        else
                son->chromosome[0] = newnode;
        newnode->sibling = mnode->sibling;

        /* Release the original node. */
        program_node_done(mnode);
}


/* Makes a crossover between two entities. */
static void
crossover_entity(population *pop, entity *mother, entity *father, entity *daughter, entity *son)
{
        // printf("%p (%p) xx %p (%p) => %p (%p) xx %p (%p)\n", father, father->chromosome[0], mother, mother->chromosome[0], son, son->chromosome[0], daughter, daughter->chromosome[0]);

        /* The new entities start off as copies of the original entities. */
        daughter->chromosome[0] = program_node_copy((struct program_node *) mother->chromosome[0]);
        son->chromosome[0] = program_node_copy((struct program_node *) father->chromosome[0]);

        /* Randomly pick nodes in the new entities to be swapped together
         * with the subtrees they hold. */

        struct program_node *cdnode_father, *cdnode_psibling;
        struct program_node *cdnode = program_node_subtree_random_pick(daughter->chromosome[0], &cdnode_father, &cdnode_psibling);
        struct program_node *cdnode_sibling = cdnode->sibling;

        struct program_node *csnode_father, *csnode_psibling;
        struct program_node *csnode = program_node_subtree_random_pick(son->chromosome[0], &csnode_father, &csnode_psibling);
        struct program_node *csnode_sibling = csnode->sibling;

        /* Swap cdnode and csnode in their respective trees. */

        if (cdnode_psibling)
                cdnode_psibling->sibling = csnode;
        else if (cdnode_father)
                cdnode_father->child = csnode;
        else
                daughter->chromosome[0] = csnode;
        csnode->sibling = cdnode_sibling;

        if (csnode_psibling)
                csnode_psibling->sibling = cdnode;
        else if (csnode_father)
                csnode_father->child = cdnode;
        else
                son->chromosome[0] = cdnode;
        cdnode->sibling = csnode_sibling;
}

/* Execute a single entity, interpreting its chromosome supplying it with
 * equations from a prepared text file. */
/* The funciton 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);

                struct program_call pc = { .X = arg1, .Y = arg2, .Z = op };
                int result = program_node_eval(&pc, entity->chromosome[0]);

                // printf("X = %d, Y = %d, Z = %d:%c  ", pc.X, pc.Y, pc.Z, pc.Z);
                // program_node_print(stdout, entity->chromosome[0]);
                // printf("\n  -> %d\n", result);

                /* Store result. */
                results[eq++] = result;
        }

        /* Close file. */
        fclose(f);
}

/* Assign fitness to an entity. */
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;

        /* In addition, we encourage the simplest programs by
         * subtracting a tree size based term from the fitness. */
        const int typical_size = 200;
        const double typical_weight = 0.01;
        int size = program_node_subtree_size(entity->chromosome[0]);
        entity->fitness -= size / typical_size * typical_weight;
        /* Alternative idea, does not work as well: */
        //entity->fitness -= log(1 + size / typical_size) * typical_weight;

        return TRUE;
}

int main(int argc, char **argv)
{
        /* 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 + 1239197);
                /* 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 chromosome
                 * routines and genetic operators (names of functions for
                 * assigning fitness, mutation, crossover, etc.). */
                population *pop = ga_population_new(
                        100                     /* const int              population_size */,
                        1,                      /* const int              num_chromo */
                        0                       /* const int              len_chromo */
                );
                pop->chromosome_constructor = program_chromosome_constructor;
                pop->chromosome_destructor = program_chromosome_destructor;
                pop->chromosome_replicate = program_chromosome_replicate;

                pop->evaluate = evaluate_entity;
                pop->seed = seed_entity;
                pop->select_one = ga_select_one_sus;
                pop->select_two = ga_select_two_sus;
                pop->mutate = mutate_entity;
                pop->crossover = crossover_entity;

                /* Set parameters of the genetic algorithm. */
                ga_population_set_parameters(
                        pop,                    /* population      *pop */
                        GA_SCHEME_DARWIN,       /* const ga_scheme_type     scheme */
                        GA_ELITISM_PARENTS_SURVIVE,     /* const ga_elitism_type   elitism */
                        0.9,                    /* double  crossover */
                        0.4,                    /* double  mutation */
                        0.0                     /* double  migration */
                );

                /* Run the genetic algorithm for 10 generations. */
                ga_evolution(
                        pop,                    /* population      *pop */
                        150                     /* const int       max_generations */
                );

                /* Print the winner. */
                entity *winner = ga_get_entity_from_rank(pop, 0);
                printf("The solution with seed = %d was:\n", i);
                program_node_print(stdout, (struct program_node *) winner->chromosome[0]);
                printf("\nWith score = %f\n", ga_entity_get_fitness(winner));

                ga_extinction(pop);
        }

        exit(EXIT_SUCCESS);
}