New Keyboard Layout Project: Efficient Genetic Algorithm Optimization
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:
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?