Philosophical Multicore

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

New Keyboard Layout Project: Efficient Genetic Algorithm Optimization

Posted by Michael Dickens on August 18, 2009

See part 1 and part 2.

I’m using a slightly modified algorithm, designed for increased performance.

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 k keyboards in pool O and sort each keyboard in O by score.
Step 7: Repeat steps 2-6 until O contains o layouts.
Step 8: Repeat steps 2-4 using pool O until the best keyboard in the pool has not changed for q rounds.

I did some empirical testing and came up with an optimized algorithm. For p = 2048, b = 16, k = 32, o = 4096, q = 2048, it took five hours to come up with a layout with fitness 2304432 (remember that lower is better). But for p = 128, b = 16, k = 1, o = 1024, q = 2048, it took only one hour to come up with a layout with fitness 2304182, which is slightly better. Not only that, but the second set of values optimizes faster. I ran the first version twice, and each time came up with a different layout (one scored 2304432, the other scored worse). But when I ran the second version twice, I came up with the same layout both times. This means that it is probably the best possible layout given the criteria. Here’s the layout:

kcfpb jhuw.
osatd lneri
qv,gz ;myx'

Not bad, eh?

Soon, I will post a comparison of this layout and various other layouts. For now I’ll just say that this layout beats out MTGAP 2.0 on every criterion but one. Impressive, huh?


Leave a Reply

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

You are commenting using your 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: