Philosophical Multicore

Sometimes controversial, sometimes fallacious, sometimes thought-provoking, and always fun.

Optimized Evolutionary Algorithm for Keyboard Design Part 2

Posted by Michael Dickens on August 11, 2009

Warning: Math-heavy post ahead. Read at your own risk.

In part 1, we looked at appropriate iteration numbers and mutation rates for when there is only one keyboard per pool. Let’s look at our algorithm:

Step 1: Create a pool containing p randomly-generated keyboard layouts.
Step 2: Score each keyboard according to a fitness function and sort the keyboards by score.
Step 3: Randomly delete half of the pool (giving preference to keyboards with lower fitness) and create a copy of each remaining keyboard.
Step 4: Mutate the copies by randomly swapping the positions of two keys m times.
Step 5: Repeat steps 2-4 until the best keyboard in the pool has not changed for b rounds.
Step 6: Place this best keyboard in pool O and sort each keyboard in O by score.
Step 7: Repeat steps 2-6 until the best keyboard in pool O has not changed for o rounds.
Step 8: Repeat steps 2-4 using pool O until the best keyboard in the pool has not changed for q rounds.

In this post, we will discuss the optimal value for b; that is, the number of rounds it iterates before it stops. Remember that it only stops if the best layout has not changed for b rounds. I will also discuss what happens when a keyboard gets “stuck”; that is, it is not yet optimal but there is no possible improvement.

Let’s look at when a layout will usually get stuck. Say every key is at its 2nd best possible position. The only way a mutation could improve the layout is if, when two keys are swapped, they both improve. Every key only has one possible better position (1 out of 29) so the chance of both keys improving is (1/29) * (1/29), or 1/841. Since the swap could go in either direction, we multiply the chance by two and get 1/420. So the chance of any particular mutation being an improvement is 1 out of 420. But there are 435 possible mutations. So the chance of at least one of them being an improvement is 1 - (419/420)^435, or ~0.65. Worst-case, the chance of finding this improvement is 1/435. So about 2000 rounds (1 - (434/435)^2000 ~ 0.99) are necessary to ensure that the improvement happens. But we can get away with a good deal less, since it’s likely that there will be more than one possible improvement.

But what if we’re satisfied with something worse? Then even fewer rounds are necessary. The chance of improvement is even higher if we are satisfied with every key being in the 3rd best position. Or the 4th.

Let’s assume that every key is in the 3rd best position. The chance of there being one possible improvement is ~0.67. We’d have to take about 2000 iterations to be 99% sure that we’ve found it. After only 500 iterations, we could be about 70% sure. But what if there are two possible improvements? Assuming that every key is in its 3rd best position, there is a 43% chance that there are two possible improvements. If there are two possible improvements, we can be 99% sure that we’ve found one of them after only 1000 rounds. So assuming that every key is in its best possible position, a reasonable value for b is around 500 to 1000.

But there is another factor to take into account: the size of the pool. Assume that the pool has 1000 keyboards in it. It is possible that one of these keyboards is better than all the others. Through the selection process, its “genes” will slowly take over the whole pool. So it’s entirely possible that every single keyboard is close “relative” to just one original keyboard. If they are all so similar, then the chance of improvement is higher since not just one layout could improve, but any layout could improve. So if there are 1000 keyboards then b doesn’t need to be so large. Just what b should be is harder to calculate.

Advertisements

4 Responses to “Optimized Evolutionary Algorithm for Keyboard Design Part 2”

  1. phynnboi said

    Let’s look at when a layout will usually get stuck. Say every key is at its 2nd best possible position. The only way a mutation could improve the layout is if, when two keys are swapped, they both improve.

    Ah, but our evaluation functions do not score every key equally! Putting E in a better position will almost always gain us more than we lose by putting Z in a worse position, for instance. So, it’s possible that a swap could move one key from 2nd best to 1st best and another key from 2nd best to 10th best, yet the overall fitness of the layout still improves!

    • True. But it’s just as probable to happen in the same way in the other direction, so I figure that it averages out. Maybe it doesn’t, but it would require some really complex probability calculations to figure it out.

  2. phynnboi said

    Bah! I used “quote” instead of “blockquote”. Oh well.

  3. […] Posted by Michael Dickens on August 18, 2009 See part 1 and part 2. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: