From 0cc18c4c506a345facbaaa7a3ad41671e4e4fb78 Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Sun, 16 Sep 2012 23:22:20 +0200 Subject: [PATCH] stage2: Extensively comment the source code --- stage2.c | 117 +++++++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 96 insertions(+), 21 deletions(-) diff --git a/stage2.c b/stage2.c index 90b19f1..b5b4f4a 100644 --- a/stage2.c +++ b/stage2.c @@ -54,7 +54,7 @@ load_reference_results(void) * Functions: ADD, SUB, MUL, DIV, IFEQ * * Variables: X (first operand), Y (second operand) and Z - * (operator - ASCII value). */ + * (operator letter - can be also thought of as its ASCII value). */ /*** PROGRAM TREE STRUCTURE DEFINITIONS */ @@ -73,7 +73,7 @@ struct program_node { struct program_node *sibling; /* Sibling in tree. */ }; -struct program_function; +struct program_function; /* See below for function classes. */ struct program_node_function { struct program_node pn; @@ -90,16 +90,17 @@ struct program_node_variable { char name; // X, Y or Z }; -/* The way the program is called. This describes mainly - * the program parameters. */ + +/*** 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; }; -/*** PROGRAM BUILTIN FUNCTIONS DEFINITIONS */ - - /* Available functions are described by the program_function structure. */ typedef int (*program_function_eval)(struct program_call *pc, int params[]); struct program_function { @@ -108,6 +109,7 @@ struct program_function { program_function_eval eval; /* Evaluation function - takes parameters and produces value. */ }; +/* ADD function */ static int pf_add_eval(struct program_call *pc, int params[]) { @@ -119,6 +121,7 @@ static const struct program_function pf_add = { .eval = pf_add_eval, }; +/* SUB function */ static int pf_sub_eval(struct program_call *pc, int params[]) { @@ -130,6 +133,7 @@ static const struct program_function pf_sub = { .eval = pf_sub_eval, }; +/* MUL function */ static int pf_mul_eval(struct program_call *pc, int params[]) { @@ -141,6 +145,7 @@ static const struct program_function pf_mul = { .eval = pf_mul_eval, }; +/* DIV function */ static int pf_div_eval(struct program_call *pc, int params[]) { @@ -154,12 +159,16 @@ static const struct program_function pf_div = { .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. */ + * 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 = { @@ -168,6 +177,7 @@ static const struct program_function pf_ifeq = { .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 }; @@ -193,6 +203,7 @@ program_node_function_eval(struct program_call *pc, struct program_node_function } assert(i == node->funct->n_params); + /* Then, evaluate the function itself with the given parameters. */ return node->funct->eval(pc, params); } @@ -213,7 +224,8 @@ program_node_variable_eval(struct program_call *pc, struct program_node_variable } } -/* Evaluate a given program. */ +/* 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) { @@ -293,7 +305,7 @@ program_node_function_copy(struct program_node_function *node) 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 them up. */ + /* Link the children to the program tree. */ if (!lastchild) newnode->pn.child = child; else @@ -324,6 +336,7 @@ program_node_variable_copy(struct program_node_variable *node) 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) { @@ -357,19 +370,25 @@ program_node_random(int energy, struct program_node *parent) * 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 0 /* Hint importance: low (small improvement) */ +#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; @@ -380,7 +399,9 @@ program_node_random(int energy, struct program_node *parent) 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; @@ -398,10 +419,12 @@ program_node_random(int energy, struct program_node *parent) } } + /* Generate a function node. */ + /* Pick a random function. */ const struct program_function *f = program_functions[random_int(program_functions_n)]; - /* Create function node. */ + /* Create the function node. */ struct program_node_function *node = malloc(sizeof(*node)); node->pn.type = PNT_FUNCTION; node->pn.child = node->pn.sibling = NULL; @@ -439,8 +462,9 @@ program_node_random(int energy, struct program_node *parent) 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 them up. */ + /* Link the children to the program tree. */ if (!lastchild) node->pn.child = child; else @@ -453,11 +477,17 @@ program_node_random(int energy, struct program_node *parent) } +/* 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; @@ -470,6 +500,7 @@ program_node_done(struct program_node *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) { @@ -488,6 +519,8 @@ program_node_subtree_size(struct program_node *node) 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[]) { @@ -506,27 +539,45 @@ program_node_subtree_list(struct program_node *node, struct program_node *nodes[ 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]; - // printf("pick %d/%d\n", i, size); 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) { @@ -543,6 +594,8 @@ program_chromosome_constructor(population *pop, entity *embryo) 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) { @@ -557,6 +610,8 @@ program_chromosome_destructor(population *pop, entity *corpse) 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) { @@ -588,15 +643,27 @@ 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 subtree gets replaced - * by a random different subtree. */ - struct program_node *newnode = program_node_random(random_boolean() ? 1 : 8 * random_double_1() + 2, mnode_father); + /* 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) @@ -605,6 +672,7 @@ mutate_entity(population *pop, entity *father, entity *son) son->chromosome[0] = newnode; newnode->sibling = mnode->sibling; + /* Release the original node. */ program_node_done(mnode); } @@ -615,9 +683,13 @@ crossover_entity(population *pop, entity *mother, entity *father, entity *daught { // 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; @@ -645,8 +717,9 @@ crossover_entity(population *pop, entity *mother, entity *father, entity *daught cdnode->sibling = csnode_sibling; } -/* Execute a single entity, interpreting its chromosome. - * Saves the results to a number array. */ +/* 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]) { @@ -682,6 +755,7 @@ execute_entity(entity *entity, int results[EQNO]) fclose(f); } +/* Assign fitness to an entity. */ static boolean evaluate_entity(population *pop, entity *entity) { @@ -704,12 +778,13 @@ evaluate_entity(population *pop, entity *entity) entity->fitness = 1.0 - (double) diffcount / EQNO; /* In addition, we encourage the simplest programs by - * subtracting a tree size based term. */ + * 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 -= log(1 + size / typical_size) * typical_weight; 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; } -- 2.11.4.GIT