Musical Trees – Student Specification

Money doesn't grow on trees... but music does :D

Introduction

In this project, you will create a program that generates musical melodies using a tree structure and a genetic algorithm.

Accessibility Note: This project can be completed without needing to hear any sounds. It also does not require any background in music theory or knowledge of genetic algorithms.

Starting Melody and Tree

The program starts with a series of plain notes:

Diagram of the starting tree structure with a single root node. Piano sound played, [node] {MIDI pitch, duration}: [1] {50, 0.5} {50, 0.5} {50, 0.5} {50, 0.5} {50, 0.5}

Evolved Melody and Tree

After evolving through 1,000 generations, the tree structure and melody sounded like this!

Diagram of the evolved tree structure with 5 unique nodes. Piano sound played, [node] {MIDI pitch, duration}: [1] {67, 0.7} {60, 0.8} {53, 0.7} {60, 0.6} {53, 0.2} [2] {67, 0.6} {72, 0.5} {65, 0.8} {69, 0.1} {62, 0.1} [4] {65, 0.4} {69, 0.4} {65, 0.6} {69, 0.6} {65, 0.2} [2] {67, 0.6} {72, 0.5} {65, 0.8} {69, 0.1} {62, 0.1} [5] {64, 0.5} {69, 0.4} {62, 0.6} {67, 0.1} {60, 0.5} [2] {67, 0.6} {72, 0.5} {65, 0.8} {69, 0.1} {62, 0.1} [1] {67, 0.7} {60, 0.8} {53, 0.7} {60, 0.6} {53, 0.2} [3] {60, 0.1} {67, 0.1} {60, 0.6} {67, 0.1} {62, 0.3} [1] {67, 0.7} {60, 0.8} {53, 0.7} {60, 0.6} {53, 0.2}

Learning Goals

• Practice implementing and manipulating tree-based data structures.
• Gain experience with object-oriented design in C++, including classes, encapsulation, and dynamic memory.
• Strengthen debugging skills by working with pointer-based structures and invariants.

Getting Started/Logistics

Start up the docker container from the docker app.

We recommend creating a folder to keep all assignments for this semester. Download the starter files onto your computer by visiting this link, Starter Code (link). Unzip the folder with the starter files in your folder you created. Open up a new window of VS Code. Click "Open..." and navigate to the folder called "student-musical-trees". Click "open".

See setup instructions for more help (link).

For each part, submit via the autograder (link).

Background Information and Definitions

• Pitch: How low or high a note sounds.
• Motif: A musical fragment. In our case, a series of 5 notes, where each note has a pitch [30-100] and duration [0.1–0.9 seconds].
• Melody: A combination of motifs.

Genetic Algorithm

A computational algorithm inspired by natural selection. It runs for many iterations, called generations, and in each generation the following steps occur:

1. Selection: Items are selected based on a fitness score. Items with a higher score are more likely to be chosen.
2. Reproduction: Selected items reproduce, creating new variants. These children are based on their parents, but with mutations/variation.
3. Pruning: Items with a low fitness score are removed.

Over time, this process should yield new items with higher fitness scores. In this project our items are musical motifs.

Overview

In this project, you will implement a tree where each node in the tree holds a motif, the motif's fitness score, a list of children pointers, and a pointer to its parent. The tree will start with just a root node, whose motif forms the starting melody. The genetic algorithm will generate new nodes and prune others. After many iterations of this process, there will be about 5 motifs left, which will make up the end melody.

To help with time management, this project is broken in two parts. You will have a week to complete each part.

Part 1

In Part 1, you will be implementing the MotifNode class, MusicalTree's constructor, the destructor, the copy constructor, the assignment operator, and the MusicalTree::PruneNodes() function.

MotifNode

MotifNode stores the following member variables:

• A motif, aka a vector of notes (motif_).
• The fitness score of the motif (fitness_score_).
• A vector of pointers to its children (children_).
• A pointer to its parent MotifNode, or nullptr if it is the root node (parent_).

All of motif_node is required for part 1. It is your job to fill in the member functions in motif_node.cc as they are specified in motif_node.hpp. CalculateFitnessScore() and CalculateHarmonicScore() are already implemented. Once you finish the project, as an optional extension, feel free to edit these functions to produce different ending melodies!

Note: The MotifNode class was intentionally designed to help you avoid difficult-to-detect bugs in your tree structure. You will be submitting motif_node.cc only and may not make changes to motif_node.hpp.

MotifNode Invariant

Make sure the invariant below is true at the end of every MotifNode member function. Note: you can use this to access your own address inside a member function.

• Every child of a MotifNode must have its parent pointer set to point back to that MotifNode. In other words, if node A lists node B as a child, then B’s parent pointer must point to A.

MusicalTree

A MusicalTree maintains MotifNodes on the heap. It is responsible for managing the overall tree structure and supporting the genetic algorithm.

MusicalTree stores the following member variables:

• A pointer to the root MotifNode of the tree (root_).
• The current number of connected MotifNodes in the tree (size_).
• A boolean that controls whether the program should print output for grading or stay quiet during execution (verbose_).

The MusicalTree constructor, the destructor, the copy constructor, the assignment operator, and PruneNodes() member function are all required for part 1. Please follow the specification given in musical_tree.hpp.

MusicalTree Invariants

All MotifNodes added to the tree should be allocated on the heap. The MusicalTree is responsible for correctly maintaining the structure and enforcing all invariants described below.

• There is always a valid root node. In other words, the size of the tree should never be less than 1.
• The root node's parent pointer must be equal to nullptr.
• If a node has children, each child must be a valid MotifNode on the heap (i.e., not deleted)
• The tree’s size should equal the number of valid MotifNodes connected through the root.

To help debug MusicalTree, it is recommended that you write a function to check these invariants and call it at the end of each member function. However, for your final submission and runtime performance, be sure to comment out the invariant-checking calls — they significantly slow down the code.

MusicalTree::PruneNodes()

This function removes nodes from the tree whose motif evaluates below a given fitness threshold. There are a few distinct cases to handle:

• Single-node tree: If the node to prune is the only node in the tree, do nothing.
• Leaf node: If the node to prune has no children, remove it from the tree.
• Internal node with children: If the node to prune has children,
  1. Recursively prune all of its descendants that also fall below the threshold.
  2. If, after pruning, the node still has children, rotate its most recently added child up to take its place.
  • When rotating, merge the child’s children with the current node’s remaining children, and reassign the parent pointers appropriately.

Written Example:
Suppose node A has children [B, C, D] (added in that order), and node D has children [E, F]. If node A is below the threshold, and the others are not, then node D will rotate up to replace A. Node D's new children will be [B, C, E, F], and D's parent pointer will be updated to A’s former parent.

Visual Example:

Image of a valid Musical Tree BEFORE pruning.

Image of a valid Musical Tree AFTER pruning anything below a fitness score of 50 (involved a rotation).

Tip: Draw pictures! Also, make sure the invariants are true at the end of each call to PruneNodes!

Part 1 Next Steps

Start by reviewing the code in motif_node.hpp and musical_tree.hpp. Then begin implementing the functions outlined for Part 1. To test your code run the following commands,

make tests
./bin/tests

Part 2

In Part 2, you will be implementing the rest of the MusicalTree class. This class is used to create and maintain a tree of MotifNodes through a genetic algorithm.

In order to grade your work, please follow the directions in the specifications and in the starter files exactly. Once you have completed the graded version of the project, feel free to adjust the parameters and see if you can create an even better melody!

Your work will be graded with a script that analyzes the output your program produces. The functions in musical_tree.hpp marked required are needed to grade your work, do not change their declarations and implement them per the RMEs. Feel free to add any other functions you would like.

To grade your output, you need to use the exact print statements required. To help, I have included all the cout statements required for you to copy and paste as needed. They can be found in the print_statement_reference.txt file.

For this project, you will NOT submit your driver.cc file. Two driver files are given to you. driver_no_music.cc is similar to what the autograder will run. driver.cc and utilities.cc work to take your code from musical_tree.cc and turn it into an WAV file. This is optional and not graded. To reiterate, the only graded files are musical_tree.hpp, musical_tree.cc, and motif_node.cc. Exact details on how to run each driver file is below.

Printing out a lot of statements is needed to grade your work but it also slows down your program. To help, the MusicalTree class takes in a boolean called verbose. When set to true, your program needs to print all the output required for grading and nothing extra. When set to false your program can print as little or as much as you would like.

Genetic Algorithm

The MusicalTree::GeneticAlgorithm() function should run the following high-level steps:

1. Go through X number of generations — X is a parameter to the function
• Evolve (selection + reproduction) - 3 times
• Prune
2. After all generations, do a final prune to get down to 5ish nodes.

Evolve

Selection Phase

Traverse every node in the tree and select a subset of nodes based on the following rule:

if SP < max(FitnessScore(node) / 100, 0.10) then select node

• SP: Selection Probability — a random value between 0 and 1
• FitnessScore(node): The fitness score of the node

Reproduction Phase

In this phase, the subset of nodes selected in the selection phase each create a new, mutated child.

For each selected node, its motif is mutated to create a new child. Each note is mutated by adding a random value between -2 and 2 to the pitch and a random value of -0.2, -0.1, 0.0, 0.1 or 0.2 to the duration. The pitch cannot be less than 30 or greater than 100. The duration cannot be less than 0.1 and greater than 0.9 seconds. If the new mutated value exceeds these, adjust it to the nearest valid value. For example, if the pitch is mutated to 28, it would be adjusted to 30.

The new child is then added to the selected node's children list.

Pruning

This phase removes nodes from the tree that have a motif with a fitness score below a given threshold.

Start the threshold for pruning at the value 10 and prune all nodes below that threshold if the size is greater than 300. After, if there are still more than 300 nodes in the tree, increase the threshold by 1 and prune again. Repeat. This will help keep the tree at a good size for speed and diversity.

Final Prune

Generating the Melody

Verbose Print Statements

Every generation should start with printing,

Every evolve cycle should start with printing,

Every selection phase should start with,

Then, while selecting, for each node in the tree print,

After the selection phase, for every node that was selected, print

Once all Evolve cycles are done, it's time to prune. Start by always printing,

If you need to prune the tree, using the algorithm described above FIRST prune THEN print,

At the end of all the generations before the final prune always print,

See the file example_output.txt for an example of what correct output could look like.

Part 2 Next Steps

Start by planning out your code in musical_tree.cc. Then begin implementing the functions you need. To test your code and generate the output music file, run the following commands,

make exec
./bin/exec

To test your code WITHOUT the music file, run the following commands,

make exec_no_music
./bin/exec_no_music