A Quick Thought on Genetic Algorithms

I love genetic algorithms (GAs). They are a clever, biologically inspired way to solve a problem. I have programmed a couple of GAs, but I have not actively incorporated them into my research.

Although there is not time here, genetic algorithms encode some traits into a genome (often 1s and 0s). Then particularly "fit" individuals can be selected from the population, and their genomes can be combined to create genetically new -- but related -- offspring. In addition, it is pretty simple to implement mutation and crossover, which more closely approximates our DNA. In addition, crossover and mutation allow completely new genomes, which result in new species, so to speak.

The other day, my colleague, Dr. Ed Palazzolo, passed along an interesting genetic algorithm problem posted to a message board. The question involved a GA that would assign a bunch of tasks to a bunch of individuals. Not every individual need have a task, but each task had to be assigned among the individuals with equal probability. And it should be equally probable that each person have each numbers of tasks (i.e., person 1 should not routinely end up with more tasks, which actually better resembles your actual workplace).

The solution is pretty elegant, although imperfect. If you use binary code
to assign each task, then probabilities are even. The problem is that you
have to a priori define the size of the universe.

000 = person 0 assigned
100 = person 1 assigned
010 = person 2 assigned
110 = person 3 assigned
001 = person 4 assigned
101 = person 5 assigned
011 = person 6 assigned
111 = person 7 assigned

Here there are 8 people, are each has a 12.5% probability of having the task
assigned to them. If you have 4 tasks, you have 4 x 3 genes, or a 12 unit genome. If one "parent" workplace had the genome 000000000000, then person 0 would have all four tasks. Say workplace 2 had the genome 111111111111, then person 7 would have all the tasks.

If we combine these genomes with crossover at the middle, we would get 000000111111 and 111111000000 (if we have 2 offspring, a computational convenience). Thus, in each of the "offspring" workplaces, we would see individuals 0 and 7 each with 2 tasks. Now we throw in some small probability of mutation, and perhaps we see one child become 010000111111. Here, mutation has switched a task to person 2, something that had not happened in the original world.

Perhaps this would allow for a particularly "fit" workplace, and this mutation would proliferate in the population. At any rate, this is what I am thinking about for fun today.