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.