G e n e t i c   A l g o r i t h m s   O n

N e t a d e l i c a

These pages are embryonic - I'm still learning this stuff. In the absence of tutorial material, they assume you're familiar with the basics of GAs (here's an ultra-brief description if you're interested). Right now, these pages contain the results of my comparisons of different parameters for a very simple GA, a "bit counter".

Comparing Different Parameters for Evolving a Bit Counter

Just about the simplest GA is the "bit counter". Each individual in the population ("member") comprises one chromosome, an n-bit string of binary digits ("0"s and "1"s). Each member's fitness is determined as the number of bits within its chromosome that are turned on ("1"). E.g., for a five-bit string:

Table 1: Fitness of Example Bit Counters
Member Chromosome Fitness
1 01111 4
2 10010 2
3 00000 0

This is unlifelike: genes don't code "for" embryonic or any other development; there's no phenotype involved. We've all got to start somewhere, though.

I wrote a program that evolves bit counters using systematically different parameters. For each unique set of parameters, the program perfomed six runs of 30 generations per run. The parameters used were:

Table 2: Parameters Varied for Evolving a Bit Counter
Parameter Value 1 Value 2 Value 3 Value 4
Mutation 0 0.001 0.05 N/A
Crossover rate 0 0.7 1 N/A
Selection method Uniform Fitness-proportionate N/A N/A
Crossover method Single-point Two-point Each-bit uniform Each-bit weighted

The program ignores cases where mutation=0 and crossover rate=0 (i.e. no evolution takes place). There are therefore 64 possible evolution models using the above parameters. The program accepts another parameter, clone rate, which dictates what fittest percentage of the population are not bred but instead are cloned into the next generation, but that parameter was not used for these pages.

In my program, parameters that are not changeable (except by changing the program) include:

Within the program's constraints, quite a lot of variation is possible (well, 64 variations as mentioned above). I did sessions on three population sizes: eight, 20 and 150. Each session went through six runs of 30 generations for each of the 64 different evolution models (11,520 generations simulated for each population size).

For each of the three population sizes I sorted the results of the 64 evolution models by average highest fitness attained per run, then by average generation in which highest fitness was attained. The 64 evolution models end up sorted in order of "goodness", or efficiency, best first.

The graphs below show the values of the variable parameters as they occur in the sorted lists of evolution model. Rather than show graphs of average or highest fitness per generation for each model, this shows which evolution methods were most succesful for each population size.

Graph 1. This shows that for a large population, the most successful crossover methods were those that worked on each bit of the parents' genes, not those that swapped over large chunks of genes. Of the two methods that work in that way, each-bit weighted was most successful.

Graph 2. For a small-medium population, each-bit crossover was most successful, but not as emphatically as it was for a larger population.

Graph 3. For a small population, crossover method seems not to be a significant factor.

Graphs 4-6. Method of selection (whether fit parents are chosen at random or are chosen at random with a bias towards more fit members) seems not to be significant for any population size.

Graph 5.

Graph 6.

Graph 7-9. The larger the population, the more significant crossover is; large populations did well when crossover was always applied and did badly when it was not. The same effect is true of smaller populations, but less emphatically so.

Graph 8.

Graph 9.

Graphs 10-12. Mutation rate (the probability with which each gene changes value in a child) shows the most sensitivity to population size. In large (highly diverse) populations, a low rate of mutation works best. In a small-medium population, mutation rate is not so significant. In small populations (little diversity), a high mutation rate gives best results.

Graph 11.

Graph 12.

Conclusions

None, really - this was only an idle experiment. Evaluating fitness based on the number of 1s in a member's genotype is trivial and nothing like the real world. It's worthwhile to me, though, to show that choosing parameters for a GA has a significant effect on the GA's operation. Here, population size and mutation rate were most obviously influential. I'll be inclined to consider each-bit weighted (is there a proper term for this?) crossover for future experiments more than I would have done had I not gone through this exercise.

There's no copyright on this; take anything you like from above, but I'd appreciate a credit if you use any of it. If you like, mail me.

Back to the Netadelica home page