Introduction to Artificial Intelligence Assignment 2: Accompaniment Generation

Artem Chernitsa, B20-02, a.chernitsa@innopolis.university

The goal

The most important goal of assignment is to generate accompaniment for the given melody using evolutionary algorithm.

General idea

The most common way is define following most important terms:

1. Population
2. Mating operators
3. Mutating operators
4. Fitness metric
5. Selection strategy

Population – set of individuals, in our case individual is the sequence of chords generated by some rules, described in report below.

Mating operators – crossover, we take two individuals and create child taking different chords from both of them.

Mutating operators – plus some absolute value to the note in child chord, for instance half-tone.

Fitness metric – sum of points calculated for population taking into the consideration every individual in this population.

Selection strategy – taking the individuals with the best fitness value to keep it for the new generation (new population).

Individual

Individual in this implementations is the sequence of chords. Chord is the gene. To generate chord the make_random_chord function is called. It randomly generates three values from 0 to 24, means the half-tones and then add offset in sense of octave to adjust the pitch of sound. Then the make_chord_seq calls previous function as many times as many chords we want to define for our melody. For example if the chord length is quarter, then count of bars multiplied by 4 divided by chord length. So, that is how we can get the yet another individual.

Crossover

When the population is reached limited size the crossover is called on the sorted descending list of individuals. It takes every two consequent individuals and with probability 0.7 takes genes from the first one and with 0.3 from the second one, hence creates new individual.

Mutation

After the every crossover on the every new individual mutation is called. It randomly not adds or adds half-tone or adds tone to every chord in sequence with probability of being mutated 0.1.

Fitness

First of all, for every individual the individual_fitness is called. It contains algorithm to determine what notes are played in the relative time to chord’s one. For instance, melody consists of 5 notes, with the following time stamps in quarters relatively to start: 0.25 0.5 0.75 1 2. We have two chords with the following time stamps in quarters relatively to start: 1 2. This is obvious that all of the notes 0.25, 0.5, 0.75, 1 are played in the moment of the first chord, and the last note is played in the moment of the second chord.

Selection process based on the fitness score. It simply takes individuals with the higher fitness score and manipulate on them.

Detail explanation of fitness function

As was mentioned before, we can extract notes or the rests for every chord we placed. So, there is no fitness bonus over the individual overall, like chord sequence as tonic, subdominant, dominant and tonic. The chord alone is considered only in fitness function. Knowing the notes of melody we can identify the key of this melody. So, using key we can get all notes, like in C#m we have C# D# E F# G# A B. Important remark: in this implementation there is no determining the transition between keys. In the continuation, keeping the key we can see the chord built in the different key levels, for example, on the I level this is C#m, on the IV and V – F#m and G#m respectively.

There is two parameters: f and k. k is the simple coefficient. f is the fitness score. Every good property of the chord will be add some points, every bad one will be lead to less number of points or getting zero points. The following rules have been considered:

1. Is chord is consonant? → plus linear value;
2. Does it contains gaps less than 2 half-tones or more than 12 half-tones? → leads to zero points;
3. How many notes matched notes from the key? → plus quadratic value if exists, 0 if not;
4. Check if the gene matches the best optioned suggested chord for this set of notes. → cubic value if fully matched, k^{2.5} if two values are same, linear if one is matched;
5. Last check if the chord is matched fully with at least one of the key chords. → log{k^2}

Detail explanation of the crossover function

Remark: the mutation is pretty fully has been described before, means there is explanation of the crossover function in general.

Since we have the population sorted with the higher fitness score first we can iterate over population by two neighbours. Take consequently two of them, pull out with probability 0.7 from the parent with higher fitness value and the rest from the second one.

Obtained child is being mutated with probability 0.1. Then, simply counts fitness score for the child and add child to the population.

Overview of the evolution

Theevolution function is the main function that do the following:

1. Generate / Initialize base population with size of 1000.
2. Counts fitness score for every individual in this population.
3. Sort the population by fitness score.
4. Do crossover and mutation correspondingly.
5. Sort the augmented population again.
6. Repeats step 3-5 as many times as many generations we want to get.

There is the turning point number where the fitness score is good enough to be stable and do not be changed significantly. But for the 100 generations (called epoch in the code terminal debug output) it gives decent sound level.

How to run

1. Make sure you use python version 3.9.12
2. Create virtual environment by the following commandpython3 -m venv env
3. Run source env/bin/activate
4. Install packages: pip install requirements.txt
5. Run program ./main.py <input_name.mid> <output_name.mid>