Solving the popular genetic algorithm problem of getting a cart to optimally center itself at a specific point. MECHTRON 2MD3 Winter 2024 Takehome Midterm Project.
We began with a directory that contains a near-complete implementation of a Genetic Programming experiment to solve the Cart Centering (isotropic rocket) problem. The gp.cpp program will evolve trees for 100 generations and print statistics on the best tree at each generation. It was also expected that we needed to implement a few extra functions to the directory on our own, on top of understanding and testing analytics on the code that was already given.
Finalized results with data collection and answers to any questions to be added to PDF file titled gp.pdf.
void LinkedBinaryTree::printExpression(Node* v),
This function must recursively print the expression tree with parentheses. For example, a tree representing postfix expression “1 2 + 3 *” is printed as “((1+2)*3)”
LinkedBinaryTree createRandExpressionTree(int max_depth, mt19937& rng),
This function should create and return a randomly generated expression tree with a depth no greater than max_depth. (The function currently simply returns the expression tree “a + b” where a and b are the X position and velocity of the cart, respectively.)
void LinkedBinaryTree::deleteSubtreeMutator(mt19937& rng),
This function should delete a randomly selected subtree from the tree.
void LinkedBinaryTree::addSubtreeMutator(mt19937& rng),
This function should add a randomly created subtree to the tree.
Implement a comparator ADT called LexLessThan which performs a lexicographic comparison of two trees TA and TB as follows: If the scores of TA and TB differ by less than 0.01, then TA is “less than” TB if TA has more nodes than TB. Otherwise, compare the trees by their score. The goal of using this comparator is to favour simpler trees only when their scores are similar. Repeat the experiment from part 1 using the new comparator. To do so, you must uncomment the line under “sort using comparator class”. After doing so, does evolution produce simpler trees? Create a line plot comparing the size of the best tree during evolution with and without the LexLessThan comparator
Implement a crossover operator in which you sample two parents and create two children by swapping random subtrees from each parent. Note there is no placeholder code for crossover in the prexisting code from the directory. You must determine where and how to add this feature. When results are ready, add a line to your plot labelled “rand init + crossover + mutation” to show the results of this experiment.
The following finalized code with implemented functions from the section above was to be ran, and results were to be plotted and graphed for each time a new function was added, including the required plots for the LexLessThan and crossover implementations. You should see a significant improvement in the best fitness after implementing createRandExpressionTree, and a further improvement after implementing the mutation operators.
Example terminal output with all functions added:
Best tree:
(((a > a) + (((b > b) * abs(((abs((b / abs(a))) * (((a / b) / a) / b)) > ((abs((a * (b / b))) - (abs(a) /
a)) + a)))) * a)) - (b + a))
Generation: 99
Size: 42
Depth: 11
Fitness: -0.0889936
All plots, graphs, and other figures can be seen on the PDF results sheet - gp.pdf.
In order to get a better understanding of the results, along with genetic programming, there were a few short answer questions to answer to check understanding. These questions relate to tree traversal as the root of the code deals with trees in various forms such as binary trees, and other operations and vocabulary related to them.
The answers can be seen on the PDF results sheet - gp.pdf
What kind of tree traversal (e.g. InOrder, PostOrder, etc.) is used by each function:
- LinkedBinaryTree::printExpression()
- LinkedBinaryTree::evaluateExpression(const Position& p, double a, double b)
- LinkedBinaryTree::depth()
- LinkedBinaryTree::size()
The End.