I am writing a program that, given a set of inputs and outputs, figures out what the equation is. The way the program works is by randomly generating binary trees and putting them through a genetic algorithm to see which is the best.
All the functions I have written work individually, but there is either one or two that do not.
In the program I use two structs, one for a node in the binary tree and the other to keep track of how accurate each tree is given the data (its fitness):
struct node {
char value;
struct node *left, *right;
};
struct individual {
struct node *genome;
double fitness;
};
One function I use to randomly create trees is a subtree crossover function, which randomly merges two trees, returning two trees that are sort of a mixture of each other. The function is as follows:
struct node **subtree_crossover(struct node parent1, struct node parent2) {
struct node *xo_nodes[2];
for (int i = 0; i < 2; i++) {
struct node *parent = (i ? &parent2 : &parent1);
// Find the subtree at the crossover point
xo_nodes[i] = get_node_at_index(&parent, random_index);
}
else {
// Swap the nodes
struct node tmp = *xo_nodes[0];
*xo_nodes[0] = *xo_nodes[1];
*xo_nodes[1] = tmp;
}
struct node **parents = malloc(sizeof(struct node *) * 2);
parents[0] = &parent1;
parents[1] = &parent2;
return parents;
}
Another function used one that takes two populations (list of individuals) and selects the best from both, returning the next population. It is as follows:
struct individual *generational_replacement(struct individual *new_population,
int size, struct individual *old_population) {
int elite_size = 3;
struct individual *population = malloc(sizeof(struct individual) * (elite_size + size));
int i;
for (i = 0; i < size; i++) {
population[i] = new_population[i];
}
for (i; i < elite_size; i++) {
population[i] = old_population[i];
}
sort_population(population);
population = realloc(population, sizeof(struct individual) * size);
return population;
}
Then there is the function that essentially is the main part of the program. This functions loops through a population, randomly modifies them and chooses the best among them across multiple generations. From this, it selects the best individual (the highest fitness) and returns it. It is as follows:
struct individual *search_loop(struct individual *population) {
int pop_size = 10;
int tourn_size = 3;
int new_pop_i = 0;
int generation = 1
struct individual *new_population = malloc(sizeof(struct individual) * pop_size);
while (generation < 10) {
while (new_pop_i < pop_size) {
// Insert code where random subtrees are chosen
struct node **nodes = subtree_crossover(random_subtree_1, random_subtree_2);
// Insert code to add the trees to new_population
}
population = generational_replacement(new_population, pop_size, population);
// Insert code to sort population by fitness value
}
return &population[0];
}
The issue I am having is that the search_loop function returns a pointer to an individual that is filled with garbage values. To narrow down the causes, I began to comment out code. By commenting out either subtree_crossover() or generational_replacement() the function returns a valid individual. Based on this, my guess is that the error is caused by either subtree_crossover() or generational_replacement().
Obviously, this is a heavily reduced version of the code I am using, but I believe it still will show the error that I am getting. If you would like to view the full source code, look in the development branch of this project: https://github.com/dyingpie1/pony_gp_c/tree/Development
Any help would be greatly appreciated. I have been trying to figure this out for multiple days.
Your subtree_crossover() function is taking two nodes as values. The function will receive copies, which will then live on the stack until the function exits, at which point they will become invalid. Unfortunately, the function later sticks their addresses into an array that it returns. Therefore, the result of subtree_crossover() is going to contain two invalid pointers to garbage data.
You could initialize parents as a struct node * instead of a struct node **, and make it twice the size of a struct node. Then, you could just copy the nodes into the array. This would avoid the issue. Alternatively, you could copy the nodes onto the heap, so that you could return a struct node **. You'd then have to remember to eventually free the copies, though.