Posts In: genetic algorithms

ChromoRhythm: Mediocre Results

November 28, 2009 General News, Plugins 0 Comments

Though I haven't fully fleshed out the ChromoRhythm data structure, I'm already getting the unfortunate feeling that the drum module simply isn't going to be able to stand up to GGrewve.  It's too unstructured to bring any coherence to a drum channel without extensive use of a complicated fitness function and a large population of randomly mutated DNA strands, which results in unnecessarily high run times.

In short, Chromo's genetic algorithm engine isn't looking like a good choice for drum beats.  The engine, even in early stages, consumes too much time and produces mediocre results.

I'm not yet ready to give up on finding a superior alternative to GGrewve.  I may abandon this particular genetic algorithm approach for the moment and focus on a flexible stochastic system implemented on top of a grammar foundation.

As I like to remind myself, one of the greatest benefits of my style of research lies in my ability to immediately turn around when I sense a dead end.  Without a concrete aim or hypothesis, other than the overall goal of creating an infinite music system, I am completely free to try whatever methods I choose, creating and abandoning modules as necessary for maximum productivity.  Killing a module within two days of creating it isn't a bad thing.  It means more experience, more knowledge of what doesn't work, and more opportunity to find out what does work.

ChromoRhythm

November 26, 2009 General News, Plugins 0 Comments

ChromoRhythm is a new generative drum module that combines many of the recent ideas I've had surrounding percussive generation.  One of the main features of ChromoRhythm will be the genetic (chromosome-based) configuration storage system, which will facilitate some degree of dynamic mutation of the drum styles.  Though I have yet to decide how the evolutionary fitness function will be implemented and whether it will be subjective or objective, I believe that the ability to convert information between chromosome-like data structures and configuration variables will enable a degree of variability unknown to previous drum modules.

Naturally, ChromoRhythm will be measured against GGrewve, since GGrewve is the current standard in drum pattern generation (and an excellent standard, at that).  Though I doubt that ChromoRhythm will ever be able to surpass GGrewve in human-feeling beats, the new data paradigm employed by the engine should allow it to trump GGrewve in terms of dynamic playing and variability of style.

Many of the details of Chromo are still being worked out.  Here are a few things that are already coded or conceptually established:

  • DNA data structure consists of a long string of numbers
  • Internal function converts between DNA strings (for use with the generalized XIAS evolutionary engine) and global configuration variable states
  • Engine uses a "base style" for each individual drum, as specified by the DNA
  • Engine layers "variations" on top of the base style for each individual drum, as specified by the DNA
  • Engine adjusts playing dynamics based on movement intensity as well as coordination accenting instructions; DNA specifies the degree and exact parameters of the dynamics

One of the main questions upon which the development of ChromoRhythm is hinging concerns the fitness function.  I see two ways of doing it:

Objective Fitness Function - ChromoRhythm takes a drummer, randomly mutates the DNA of the drummer, then runs a fitness function on the mutations.  The fitness function is the first-ever "ear module" employed in the development of mGen, and mimics a user that listens to the beat.  The fitness function assigns points based on how well the drummer lines up with the coordination instructions, how effectively the dynamics change the style, and how pleasing the beat is in general.  The XIAS evolutionary engine then evolves the drummer mutations to the next generation and repeats the process for a set number of generations (or, alternatively, until the population reaches a specified mean fitness value).

Subjective Fitness Function - ChromoRhythm creates a pool of potential drummers to begin with.  The user selects an option in the interface that makes Chromo generate a channel for each potential drummer during the composition of a single piece.  The user then listens to the piece, muting all but one channel, and assigning points to the drummers based on how much he or she likes the style.  The XIAS evolutionary engine then evolves the drummer pool, as detailed above.

One may see that these two methods have very little in common - in fact, the first details a method of evolving substyles of a single drummer configuration, while the second involves evolving overarching drummer configurations.  Perhaps, then, both of these methods can be combined.

Needless to say, the logistics of implementing a genetic algorithm aren't at all simple.  Conceptualizing the process takes far longer than actually implementing it.  Determining what exactly should be evolved, how populations should be treated, which individual should be played, and how fitness points should be assigned will all heavily affect the output of ChromoRhythm.

Genetic Algorithm Performance Testing II

October 27, 2009 General News 0 Comments

With the superiority of mutation mode 1 at least tentatively established, I have started conducting more thorough optimization tests on the genetic algorithm engine. So far I have only completed two full tests, since the method I am using takes about half a day for a single run.

The follow chart shows the efficiency of two different populations. The averaged data was taken over the mutation rate interval [1,10] with step size 0.1. Each population ran 3000 times at each mutation rate to ensure very high accuracy in the averages. The first curve, labeled GA Comp 4, represents the efficiency of a population of complexity 4. Similarly, the second curve represents the efficiency of a complexity-5 population. Complexity, for the purposes of this test, is the numerical measure of both the number of individuals in the population as well as the number of alleles available to the engine and the number of alleles in each individual. So, for example, a complexity-4 population comprises 4 individuals, each having 4 alleles, each allele being drawn from a set of 4 unique alleles. Similarly, a complexity-5 population comprises 5 individuals, each having 5 alleles drawn from a set of 5 unique alleles. Obviously, the higher the complexity, the more difficult it is for the engine to reach the "optimal individual."

In the previous post, I estimated that mutation mode 1 runs most efficiently around 4.5%-5.5%. I based that estimation off of a complexity-4 population. The above results confirm that the optimal rate for a complexity-4 population is just shy of 4.5%. This value, however, is not the most efficient for a complexity-5 population, as the red data demonstrates. Rather, as the complexity increases to 5, the optimal mutation rate increases as well - to roughly 5.5%.

It is interesting to note that the efficiency of a complexity-4 population can be approximated quite well by a polynomial of order 3, while the efficiency of a complexity-5 population can be approximated nicely by a polynomial of order 4. These approximation curves are overlaid in the graph above.

Though I'd need several more runs to draw a concrete conclusion, the immediate evidence suggests that, as a rough generalization, the genetic algorithm performs most efficiently when the mutation rate is set to about .5 above the quantitative complexity factor of the population to be optimized.

Now, how does any of this relate to music and algorithmic composition? That I still have to figure out.

Genetic Algorithm Performance Testing

October 25, 2009 General News 0 Comments

Having laid down the foundations of the XIAS genetic algorithm engine, I decided a performance test would be necessary to get the most out of the engine. Genetic algorithms, unlike most of the other methods that I've explored, are highly impacted by small quantitative tweaks to the engine, so performance can be gained by extensive testing of parameters.

Some preliminary tests were run tonight to determine the most effective mutation rate as well as the best mutation mode. I developed two mutation modes for the engine: Mode 1 allows an allele to mutate to any other allele that has been specified as part of the allele set of the engine. Mode 2 allows an allele to mutate only to an allele that already exists on the individual. In order to test these modes, the engine ran through 1000 genetic algorithm populations, keeping track of how many sub-loops it took to optimize the population each time. Each population was allowed a maximum of 100 loops to become perfectly optimized. Obviously, the idea is for the populations to optimize before those 100 loops are up.  The population optimization times are then averaged across the 1000 populations in order to achieve more accurate results.  Note that lower numbers on the graph are better (because the population optimized faster).

A couple of notes about the engine that stem from the graph:

  • Mutation mode 1, in general, optimizes faster than mutation mode 2
  • Mutation mode 1 is most efficient with a mutation rate of around 4.5% to 5.5%
  • Mutation mode 2 is most efficient with a mutation rate of around 6% to 7%
  • Mutation mode 1 provides more consistent optimization (notice that mode 2's curve changes directions several times, whereas mode 1's curve changes direction only once, at the minimum)
  • The optimization time of each mode can be roughly approximated by a cubic curve

Reproduction in Genetic Algorithms

October 19, 2009 Ideas 0 Comments

I've come up with three different ways of performing the reproduction process in the genetic algorithm engine.  Note that all processes start out with ten individuals and, accordingly, perform ten reproductions.  The question is how to optimize the outcome of the reproduction so that the children end up with an optimal gene pool but still retain some diversity.

The first method, which I call "nearest neighbor," simply pairs the individual of rank n with the individual of rank n+1. The last individual pairs with the first.

The second method, "first priority," pairs the top-ranked individual with all other individuals, then pairs the second-ranked individual with the third.

The final method, "multiple neighbor," starts at the top-ranked individual, n, and pairs it with n+1n+2, ..., n+i, then moves on to individual n+1, pairing it with n+2, n+3, ..., n+1+i, continuing this pattern until the number of reproductions matches the number of individuals in the original population.  The integer i should be chosen based on population size.  Note that the "first priority" method is essentially a special case of the multiple neighbor method wherein i is equal to the size of the original population.

I'm betting that multiple neighbor with an i value of about a third of the population size will probably perform the best.  Only tests will tell which of these methods of reproduction (if not all of them) should be implemented in the final engine.

Notes on Implementing Genetic Algorithms

October 18, 2009 Ideas 0 Comments

XIAS (cross-integrated algorithm system) supports the following algorithm types so far:

  • Fractal
  • Grammar
  • L-System

The next natural extension of XIAS is an implementation of genetic algorithms.  I have a bit of experience with genetic algorithms from designing the EvoSpeak engine, which basically combined stochastics and genetic algorithms to evolve towards good-sounding melodies.

In keeping with the overall theme of the XIAS project, the designs for this genetic algorithm implementation focus on portability and ease-of-use.  As such, the system may seem a little oversimplified.  Only time will tell whether it will suffice for algorithmic composition needs or whether I will need to extend the features of the genetic algorithms.  For now, here are some notes that I've brainstormed for the implementation of this new system.

Data Structure of the GA Engine

  • Engine
    • Alleles (effectively the algorithm's domain; string)
    • Cumulative point distribution (count; integer)
  • Individuals
    • Data String (genetic data; string)
    • Points (count; integer)

GA Engine Operation

  • Create m individuals with random alleles
  • Rate each of the individuals
    • Pass data string to transform function
    • Feed transformed output to fitness evaluation function
    • Distribute points according to fitness performance
  • Breed the top n individuals according to point distribution with each other to create m new individuals
  • Repeat with the new generation of individuals

Mutation in the GA Engine

  • Deterministic Approach
    • Create a function that takes two parent alleles and returns a third allele different from both (think cross product)
    • Run the function on every qth allele
  • Nondeterministic Approach
    • Replace a child allele with a random allele with a given frequency

Quick Summary of GA Engine Implementation

  • Randomize Individuals
  • Rate
    • Functional Transformation
    • Fitness Evaluation
    • Point Allocation
  • Reproduce
    • Allele Combination
    • Allele Mutation
  • Repeat

The only real problem left to solve is concerning reproduction.  How do we choose which individuals to combine with which individuals in order to produce a population of exactly m members, given that we want the children to have the best possible combinations of genes based on the point distribution of the parents?

Computer Models of Musical Creativity (3)

March 30, 2009 Sources & Notes 0 Comments

Computer Models of Musical Creativity (David Cope)
Chapter 3: Current Models of Musical Creativity

  • Although randomness often competes with creativity in terms of surprise, it is no substitute for a creative process
  • Most random processes are simply too complex to predict
  • Randomness arises from a lack of predictability using logic, not a lack of determinism
  • Good creativity simply requires good algorithms
  • Some models of creativity include cellular automata, mathematical models, fuzzy logic, neural networks, and Markov chains
  • Using Markov chains, one can analyze a piece of music and produce new music in roughly the same style
  • Genetic algorithms operate on the principle of natural selection
  • Genetic algorithms and cellular automata can both generate very complex output
  • In rule-based programs, creativity really belongs to the programmer, not the program
  • Neural networks use "hidden unit" networks to simulate the output of a given situation based on a sample input and output
  • Neural networks simulate the workings of the human brain
  • Mathematical formulas can be used to produce quasi randomness
  • "Randomness is not an engaging mystery, but a simple reflection of ignorance"
  • "Randomness refers to behavior that is either too complex, too patternless, or too irrelevant to make prediction possible"
  • "For those believing that using algorithms to create music somehow removes imagination, inspiration, and intuition from the composing process, know that defining a good algorithm requires as much imagination, inspiration, and intuition as does composing a good melody or harmony"
  • "Neither good algorithms nor good musical ideas grow on trees"
  • "Integrating association-based procedures with data-driven processes increases the creative potential of this approach to music composition"
  • "GAs typically involve DNA-like inheritance of characteristics as well as crossover and mutation techniques to develop new traits"
  • "Neural networks then cycle through a series of forward or back propagations that compare output with input and alter hidden unit values, until the output values match or approximate the relationships of the input and output data upon which they were trained"
  • "Sandwiched between these nodes are variable numbers of layers of hidden units, as well as variable numbers of connections between these inputs, outputs, and hidden units, making the training process extremely complex"
  • "We should not overestimate the abilities of neural networks or let comtivity mask a lack of true creativity"
  • "Mathematical origins for algorithmic music, while occasionally producing interesting results, in no way indicate the presence of creativity"
  • "Computer programs must be sufficiently independent of their programmers and users in order to qualify as truly creative. Most apparently creative algorithmic composing programs either produce enormous output from which users make preferential choices or invoke so many programmer-defined rules that the software only proves the creativity of the programmer"

GenJam

January 12, 2009 Sources & Notes 0 Comments

Found a program today by the name of GenJam. It makes use of evolutionary genetic algorithms to "learn" to play jazz by listening to a human play trumpet. The program is private, but there a few links to sample clips in which you can hear GenJam playing along with the human.

GenJam