<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Creating a chord progression with a genetic algorithm
This work is the result of an experiment done some months ago. I used a simple genetic algorithm to find a solution to a classic exercise of harmony
Step1:  Will be rempresented as
Step2:  The file lily_template has the template to create the lilypond file and to give it format I used the string.Template class.
Then I set some global variables that I'm going to use
Step3:  Initialization
In the initialization part, you have to create the initial population with all the individuals. In this example an individual will be a chord progression, with all the chords beeing of four notes each. I represented each individual as a list of chords, and each chord a list of notes, for example
Step5:  This individual would be represented as
[[48, 64, 67, 79], [53, 59, 65, 74], [55, 59, 62, 74], [48, 55, 67, 76]] 
To do anything I need the tonality of the exercise, so I defined a function to find it given the bass voice and the key signature, it just looks at the key signature and it looks if the voice has any sight of being a minor key
Step7:  The function returns a tuple with the tonality represented as a number from 0 to 11 (C to B) and a 'M' if the tonality is major or 'm' if it's minor.
Then I wrote a function to create a single chord given the name of the chord and the fundamental note. The interesting part of this is that a chord of four notes can have multiple permutations, different set of notes and it can have a close or open harmony.
For example all these chords are D major and have the same bass
Step9:  After this function, I only need to select a chord for each of the notes in the bass. This process use the midi representation of the notes and making arithmetic operation with them and with a random choice between the possible options. At the end we have a complete chord progression.
Step11:  Now, DEAP requires a generator to create the individuals, so I just create a simple generator that yields each chord of the progression.
Step13:  Selection
From Wikipedia
Step15:  Also between two chords, you have to avoid the consecutive fifths and octaves, and a normal person tends to make the intervals in a voice more "natural" making jumps not bigger than a fifth that often.
Step17:  And for the evaluation of an individual I used this generator to access an element and the two neighbors
Step19:  The actual evaluation function
Step21:  Crossover
In the crossover section I used a simple One point crossover provided by DEAP in its set of tools.
Mutation
In the mutation section I just create a new chord for each one of the lasts chords that randomly pass a threshold.
Step23:  The next function is just to create a lilypond file using the chords in the individual to see a nice sheet.
Step24:  In the main function is where the actual algorithm's running, it's a simple evolutionary algorithm with a hall of fame where the best individuals will be saved. The little while loop is just if you want to run multiple times the algorithm until an individual gets an evaluation lower than, in this case, 15.
Step25:  And at the end set up all the functions and the form of the individual in the toolbox that way DEAP can use them in the algorithm.
The program verbose each of the generations showing the number of individuals evaluated, the average evaluation value, the standard deviation, the minimum and the maximum. At the end it shows the three best individuals in all the evolution process, and it creates a lilypond file with the best of all.
Step26:  And just to show the result I made a little script to trim the pdf that lilypond generate.
<ASSISTANT_TASK:>
Python Code:
from IPython import display
display.Image('img/simple.jpg', width=400)
Explanation: Creating a chord progression with a genetic algorithm
This work is the result of an experiment done some months ago. I used a simple genetic algorithm to find a solution to a classic exercise of harmony: given a certain voice (normally the bass) create the other three voices to make a chord progression. I know that the aproach to solve a progression with a genetic algorithm may not be the best I just wanted to play with this algorithms making somthing fun, the code isn't perfect and the algorithm can be improved adding more options in the chord selection, but for simplicity I didn't use seventh chords.
Working with music
The first part of this challenge is to find a way to easily represent the notes in the melody, luckily for us many years ago MIDI was created, so I used the numbers in MIDI to match every single note being, for example, 60 the central C. And at the beginning of the sequence of notes I set the key signature with the number of sharps or flats.
So an example like this:
End of explanation
import random
import math
import numpy
from string import Template
from deap import base
from deap import creator
from deap import tools
from deap import algorithms
from lily_template import TEMPLATE
Explanation: Will be rempresented as: 0# 57 59 60 62
Lilypond
Going from music notation to this MIDI number representation with just one voice is quite easy (although I might work a hack for that also), but once I generate all the notes that form the chords the process ends up being a pain in the ass. Therefore, at the end I take the output and pass it through a little script that transform the numbers to Lilypond, generate a .ly file and an .jpg of the sheet.
The genetic algorithm
A genetic algorithm works pretty much like a species evolution in real life. You take a group of individuals, called population, in this population there are a few individuals that have the best attributes, those are the ones that will survive and carry on the genes to the next generation. This process continues generation over generation until there is an individual with the perfect attributes, or at least with the best so far. You can read more in Wikipedia.
The process can be structured in this steps:
- Initialization
- Selection
- Crossover
- Mutation
- Termination
Let's tackle them one by one. But first let me explain the framework that I used.
Working enviroment
I used a library called DEAP, Distributed Evolutionary Algorithms in Python, it is a novel evolutionary computation framework for rapid prototyping and testing of ideas. It has all the basic tools to work with genetic algorithms you only have to create the functions to create, select, mate and mutate the individuals.
End of explanation
# Global Variables
OPTIONS_M = ((0,-3,5), (0,-3,5), (0,-4,5), (0,-3,6), (0,-3,5), (0,-4,5), (0,-4,5))
OPTIONS_m = ((0,-4,5), (0,-4,5), (0,-3,5), (0,-3,5), (0,-4,5), (0,-3,6), (0,5))
MOD_M = ('M','m','m','M','M','m','d')
MOD_m = ('m','d','M','m','M','M','M')
Explanation: The file lily_template has the template to create the lilypond file and to give it format I used the string.Template class.
Then I set some global variables that I'm going to use:
OPTIONS_* are the different roles that a note can have in a chord: The first note in the scale of the tonality can be the first note in the tonic chord, the third degree in the 6° chord or the fifth degree in the subdominant. So I represented this options as differences between the fundamental note of the possible chords and the note degree in the scale.
This diferences change a little bit in a minor tonality.
MOD_* are just the grades of the chords in a major and a minor tonality.
End of explanation
display.Image('img/ex_prog.jpg', width=400)
Explanation: Initialization
In the initialization part, you have to create the initial population with all the individuals. In this example an individual will be a chord progression, with all the chords beeing of four notes each. I represented each individual as a list of chords, and each chord a list of notes, for example:
End of explanation
def setTon(line):
    Return the tonality of the exercise and the bass notes of it
    ton = line[:2]
    notes = list(map(int, line[3:].split(' ')))
    if ton[1] == '#':
        ton = (int(ton[0])*7)%12
    else:
        ton = (int(ton[0])*5)%12
    for note in notes:
        if (ton+6)%12 == note%12:
            ton = str((ton-3)%12)+'m'
            break
    else:
        if ton-3 == notes[-1]%12:
            ton = str((ton-3)%12)+'m'
        else:
            ton = str(ton)+'M'
    return ton, notes
Explanation: This individual would be represented as
[[48, 64, 67, 79], [53, 59, 65, 74], [55, 59, 62, 74], [48, 55, 67, 76]] 
To do anything I need the tonality of the exercise, so I defined a function to find it given the bass voice and the key signature, it just looks at the key signature and it looks if the voice has any sight of being a minor key:
End of explanation
display.Image('img/all_same.jpg', width=400)
def creatChord(nameC, noteF):
    Create one chord given the name of the chord and the fundamental note
    num_funda = int(nameC[:-1])
    if nameC[-1] == 'M':
        val_notes = [num_funda, (num_funda+4)%12, (num_funda+7)%12]
    elif nameC[-1] == 'm':
        val_notes = [num_funda, (num_funda+3)%12, (num_funda+7)%12]
    elif nameC[-1] == 'd':
        val_notes = [num_funda, (num_funda+3)%12, (num_funda+6)%12]
    
    # Tessitura of each voice
    tenorR = list(range(48, 69))
    contR = list(range(52, 77))
    sopR = list(range(60, 86))
    
    # Depending in the bass note this are the options for the others voices
    if noteF%12 == val_notes[0]:
        opc = [[1,1,1], [2,1,0], [0,1,2]]
    elif noteF%12 == val_notes[1]:
        opc = [[1,0,2], [3,0,0], [2,0,1]]
    elif noteF%12 == val_notes[2]:
        opc = [[1,1,1], [2,1,0]]
    
    opc = random.choice(opc)
    chordN = list()
    for num, val in zip(opc, val_notes):
        chordN += [val]*num
    
    random.shuffle(chordN)
    
    chord = [noteF,]
    for nte, voce in zip(chordN, [tenorR, contR, sopR]):
        posible_n = [x for x in voce if x%12 == nte]
        chord.append(random.choice(posible_n))
    
    return chord
Explanation: The function returns a tuple with the tonality represented as a number from 0 to 11 (C to B) and a 'M' if the tonality is major or 'm' if it's minor.
Then I wrote a function to create a single chord given the name of the chord and the fundamental note. The interesting part of this is that a chord of four notes can have multiple permutations, different set of notes and it can have a close or open harmony.
For example all these chords are D major and have the same bass:
End of explanation
def selChord(ton, notesBass):
    Select the chords from all the posibilities
    listaOp = OPTIONS_M if ton[-1] == 'M' else OPTIONS_m
    listaMod = MOD_M if ton[-1] == 'M' else MOD_m
    prog = list()
    
    for note in notesBass:
        name = note%12
        grad = name-int(ton[:-1])
        grad = math.ceil(((grad+12)%12) / 2)
        num = (random.choice(listaOp[grad]) + name +12) % 12
        grad = num-int(ton[:-1])
        grad = math.ceil(((grad+12)%12) / 2)
        name = '{}{}'.format(num, listaMod[grad])
        prog.append([creatChord(name, note), grad])
    return prog
Explanation: After this function, I only need to select a chord for each of the notes in the bass. This process use the midi representation of the notes and making arithmetic operation with them and with a random choice between the possible options. At the end we have a complete chord progression.
End of explanation
def newChordProg(ton, notes):
    Create a new individual given the tonality and the base notes
    chords = selChord(ton, notes)
    for c in chords:
        yield c
Explanation: Now, DEAP requires a generator to create the individuals, so I just create a simple generator that yields each chord of the progression.
End of explanation
def check_interval(chord):
    Return the number of mistakes in the distance between the notes.
    res = 0
    if chord[2] - chord[1] > 12 or chord[2]-chord[1] < 0:
        res += 15
    if chord[3] - chord[2] > 12 or chord[3]-chord[2] < 0:
        res += 15
        
    if chord[1] == chord[2] or chord[2] == chord[3]:
        res += 1.4
    return res    
Explanation: Selection
From Wikipedia: "During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected."
So, I created a fitness function based on the classical harmony, it evaluate the progression to find "errors" like a distance between notes greater than an octave, or try to avoid two voices singing the same note:
End of explanation
def check_2_chords(ch1, ch2):
    Return the number of mistakes in the intervals between 2 chords.
    res = 0
    
    # Check for 5° and 8°
    ite1 = map(lambda x,y: y-x, ch1[:-1], ch1[1:])
    ite2 = map(lambda x,y: y-x, ch2[:-1], ch2[1:])
    for inter1, inter2 in zip(ite1, ite2):
        if inter1 == 7 and inter2 == 7:
            res += 15
        elif inter1 == 0 and inter2 == 0:
            res += 15
        elif inter1 == 12 and inter2 == 12:
            res += 15
    
    # Check for big intervals, just to make it more "human" 
    for note1, note2 in zip(ch1[1:], ch2[1:]):
        if abs(note1-note2) >= 7: # 7 equals 5° interval
            res += .7
    
    return res
Explanation: Also between two chords, you have to avoid the consecutive fifths and octaves, and a normal person tends to make the intervals in a voice more "natural" making jumps not bigger than a fifth that often.
End of explanation
def neighborhood(iterable):
    Generator gives the prev actual and next.
    iterator = iter(iterable)
    prev = None
    item = next(iterator)  # throws StopIteration if empty.
    for nex in iterator:
        yield (prev,item,nex)
        prev = item
        item = nex
    yield (prev,item,None)
Explanation: And for the evaluation of an individual I used this generator to access an element and the two neighbors:
End of explanation
def evalNumErr(ton, individual):
    Evaluation function.
    res = 0
    for prev, item, nex in neighborhood(individual):
        res += check_interval(item[0])
        if prev == None:
            if item[1] != 0:
                res += 6
            continue
        else:
            if prev[1] in [4, 6] and item[1] in [3, 1]:
                res += 20
            res += check_2_chords(prev[0], item[0])
        if nex == None:
            if item[1] in [1, 2, 3, 4, 5, 6]:
                res += 6
    return (res,)
            
Explanation: The actual evaluation function:
End of explanation
def mutChangeNotes(ton, individual, indpb):
    Mutant function.
    new_ind = toolbox.clone(individual)
    for x in range(len(individual[0])):
        if random.random() < indpb:
            
            listaOp = OPTIONS_M if ton[-1] == 'M' else OPTIONS_m
            listaMod = MOD_M if ton[-1] == 'M' else MOD_m
            
            note = individual[x][0][0]
            
            name = note%12
            grad = name-int(ton[:-1])
            grad = math.ceil(((grad+12)%12) / 2)
            num = (random.choice(listaOp[grad]) + name +12) % 12
            grad = num-int(ton[:-1])
            grad = math.ceil(((grad+12)%12) / 2)
            name = '{}{}'.format(num, listaMod[grad])
            
            new_ind[x] = [creatChord(name, note), grad]
    
    del new_ind.fitness.values
    return new_ind,
Explanation: Crossover
In the crossover section I used a simple One point crossover provided by DEAP in its set of tools.
Mutation
In the mutation section I just create a new chord for each one of the lasts chords that randomly pass a threshold.
End of explanation
def transform_lilypond(ton, indiv, make_file=False):
    Take one list of chords and print the it in lilypond notation.
    note_map = dict()
    if ton[-1] == 'M':
        note_map = {0: 'c',
                    1: 'cis',
                    2: 'd',
                    3: 'dis',
                    4: 'e',
                    5: 'f',
                    6: 'fis',
                    7: 'g',
                    8: 'gis',
                    9: 'a',
                    10:'ais',
                    11:'b'
                    }
        gra = 'major'
    else:
        note_map = {0: 'c',
                    1: 'des',
                    2: 'd',
                    3: 'ees',
                    4: 'e',
                    5: 'f',
                    6: 'ges',
                    7: 'g',
                    8: 'aes',
                    9: 'a',
                    10:'bes',
                    11:'b'
                    }
        gra = 'minor'
    voces = [[], [], [], []]
    
    for chord in indiv:
        for note, voce in zip(chord, voces):
            
            octave = (note // 12)-4
            name_lily = note_map[note % 12]
            if octave < 0:
                name_lily += ',' * (octave * -1)
            elif octave > 0:
                name_lily += "'" * octave
            voce.append(name_lily)
    
    if make_file:
        with open('lily/'+ton+'.ly', 'w') as f:
            key_map = {'0': 'c',
                    '1': 'des',
                    '2': 'd',
                    '3': 'ees',
                    '4': 'e',
                    '5': 'f',
                    '6': 'ges',
                    '7': 'g',
                    '8': 'aes',
                    '9': 'a',
                    '10':'bes',
                    '11':'b'
                    }
            print(ton)
            f.write(Template(TEMPLATE).substitute(key=key_map[ton[:-1]], grade=gra, notes='{}|\n{}|\n{}|\n{}|\n'.format(*(' '.join(voce) for voce in reversed(voces)))))
    
    print('{}|\n{}|\n{}|\n{}|\n'.format(*(' '.join(voce) for voce in reversed(voces))))
Explanation: The next function is just to create a lilypond file using the chords in the individual to see a nice sheet.
End of explanation
def main(ton):
    pop = toolbox.population(n=400)
    hof = tools.HallOfFame(3)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register('avg', numpy.mean)
    stats.register('std', numpy.std)
    stats.register('min', numpy.min)
    stats.register('max', numpy.max)
    
    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.3, ngen=70, stats=stats, halloffame=hof, verbose=True)
    while min(log.select('min')) > 15:
        pop = toolbox.population(n=400)
        pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.3, ngen=70, stats=stats, halloffame=hof, verbose=True)
        
    for best in hof:
        print([x[0] for x in best], end='\n============\n')
    transform_lilypond(ton, [x[0] for x in hof[0]], make_file=True)
Explanation: In the main function is where the actual algorithm's running, it's a simple evolutionary algorithm with a hall of fame where the best individuals will be saved. The little while loop is just if you want to run multiple times the algorithm until an individual gets an evaluation lower than, in this case, 15.
End of explanation
if __name__ == '__main__':
    line = input('n[#b] notas ')
    ton, notes = setTon(line)
    print(ton, notes)
    
    # ========================= GA setup =========================
    creator.create('FitnessMin', base.Fitness, weights=(-1.0,))
    creator.create('Individual', list, fitness=creator.FitnessMin)
    toolbox = base.Toolbox()
    toolbox.register('creat_notes', newChordProg, ton, notes)
    toolbox.register('individual', tools.initIterate, creator.Individual,
                     toolbox.creat_notes)
    toolbox.register('population', tools.initRepeat, list, toolbox.individual)
    toolbox.register('evaluate', evalNumErr, ton)
    toolbox.register('mate', tools.cxOnePoint)
    toolbox.register('mutate', mutChangeNotes, ton, indpb=0.4)
    toolbox.register('select', tools.selTournament, tournsize=3)
    # =============================================================
    
    main(ton)
Explanation: And at the end set up all the functions and the form of the individual in the toolbox that way DEAP can use them in the algorithm.
The program verbose each of the generations showing the number of individuals evaluated, the average evaluation value, the standard deviation, the minimum and the maximum. At the end it shows the three best individuals in all the evolution process, and it creates a lilypond file with the best of all.
End of explanation
import os
os.system('python auto_trim.py {} {}'.format('lily/'+ton+'.ly', 'temp.jpg'))
display.Image('img/temp.jpg', width=600)
Explanation: And just to show the result I made a little script to trim the pdf that lilypond generate.
End of explanation
<END_TASK>