Genetic Algorithm MELody (GAMEL)

Introduction

A few years ago I completed an Open University Degree; my last course was M366 – Natural and artificial intelligence. One of the subjects was a fascinating one: Genetic Algorithms. Since the end of this course, I have been dreaming of revisiting this topic and “make” something with it.
It happens that I have been a software developer and I decided to refresh my knowledge of a language I love and I did not have the opportunity to use for ten years: Java. So Here we are today in front of an attempt at creating a system that should use Genetic Algorithms (GA) to generate (pleasing) melodies.
This will be fun!

High Level

My aim is to create a system capable of generating the best possible melody. By best, I mean the most pleasing. The first set of melodies will be generated at random and further generations will evolve using the principles of GA.
The melodies will be sequences of chords. The main simplification for this project will be that Human listeners (HL) will be used to establish the fitness of each melody. I do not exclude the possibility of trying to find patterns and attempts to automate this process will be made at a (very) later stage. As far as possible, each run of GAMEL will generate a file allowing an analysis and review of the parameters and processes. This should help the system evolve.
A number of parameters and designs will be used in an iterative process allowing the production of evolving prototypes.

Genetic Algorithm: Quick overview

I do not have the ambition to produce a course about GA here. The following is just a highlight of the principles and issues.
Genetic algorithms is a topic associated to artificial intelligence (AI). The principle is to mimic reproduction and natural selection to produce a solution or a set of solutions to a problem.
This method presents a few challenges:

• Representing the problem you want to solve in the form of a genome, each parameter being treated as a gene.
• Finding a formula that, for each generated solution, looks at the genome and assigns a fitness value. The higher the value, the closer to the best or ideal individual.
• Determining all the parameters associated with the natural selection: Who survives and get the opportunity to transmit the genes.
• The reproduction: Is the “strongest” solution the “dominant male” and will reproduce with all the female (elitism) or do we have the creation of couples.
• Transfer of genes: How do we determine how and what genes are transmitted from the parents to the child.
• Mutations: When genes as copied, there are sometimes, little accidents, spelling mistakes. The result is that new characteristics will appear at random. Natural selection will do the rest by calculating a new fitness and decide, again, who survives to pass on the new “features”. The challenge there is to decide, what can mutate, how much it can mutate and how often we allow this to happen. I guess that if this was not happening in our world, the cats, the dogs, the people and even the tomatoes would have the same colour of eyes – how boring! :-).
• What is the best size for the initial population?

I would recommend you visit the following web site if you want to have a practical and no nonsense introduction to GA.
http://www.obitko.com/tutorials/genetic-algorithms/
There is plenty of material on the net for those who want to go further on the theory.

Definitions/Variables

Melody (Mld)
A melody is a set or array  of chords. An initial number of 12 chords will be used.

Chord (Chrd)
A chord is a set or array of distinct musical notes. An initial number of 3 will be used.

Note (Nt)
A musical note is a sound within a range.  Initially, the range will be between Medium DO and SI, including the # and b.

Human Listener (HL)
Human person who will assess the fitness of a Melody.

Representation of the genome

At this initial stage I will consider that a gene is a Chord.
A note can be represented by an integer between 1 and 11; 1 will be DO, 2: DO#, 3:  RE, etc.
A Chord can therefore be represented by a sequence or array of 3 integers. The representation can use a number of separators such as comma, tab and semi-colon; which separator is used is not important at the moment, I guess the IT side of the project will make any specific requirement more obvious. The representation of a chord will impose that the notes are sorted.
Chord representation specifications

The Genome can be represented by a sequence or array of Genes. Again I can use separator or not. I will chose not to use a comma separator. The convention will therefore be that each note in a position which is a multiple of 3 is the first note of a chord.

Melody Genome
1,3,8,1,2,9, 1,2,8,2,6,9,1,2,5,2,4,10,3,5,8,1,4,5,6,8,10,2,9,10,3,5,9,4,10,11

Next => Coding the first generation