Project link: https://github.com/bgrassy/keyboard-layout-generator
The QWERTY keyboard layout is something most people take for granted; it is a safe bet that nearly any given computer or keyboard in America comes with that layout as the default. However, its ingrained nature in our culture certainly does not mean that it is "good" by any measure. Numerous studies have found that QWERTY is inferior to other alternative layouts such as Dvorak or Colemak in practically every measure, such as ergonomics and typing speed. Those other layouts have a rather niche following; however, QWERTY still reigns supreme in most of the world.
Last year, when I first discovered Dvorak, the idea seemed interesting to me. An additional boost to typing speed and decreased risk of stress injuries from typing seemed like a fair price to pay for the decreased amount of resources surrounding the layout. However, my mind soon wandered to a different question: do keyboard layouts exist that are better than Dvorak? Similarly, what metrics can we use to concretely formulate an idea of what a "better" keyboard is?
My initial programmatic attempt at solving the program was rather simplistic, resorting to generating layouts through brute force and comparing them based on their distance traveled, finger alternation, and other metrics. Unfortunately, I lost the code which I used to write it, which contained my basic formula for calculating how good the keyboard is. However, I wrote this paper which described my overall methodology. After this initial paper, due to school and various other commitments I was unable to follow up on it. However, after I took my first quarter of CSE at UW and wrote a genetic algorithm to generate an game-playing "critter" for my final assignment (which I hope to write a writeup on eventually), I realized that this same idea could be applicable to the keyboard problem. First, a little bit of background is necessary on the basic learning algorithm which I use to improve my keyboard layouts. For this project, I am using what is called a genetic algorithm, an algorithm which attempts to emulate the process which drives biological evolution. The three main steps to the recursive process are as follows:
- Initialization. Constructs an initial population of objects, in this case keyboard layouts, in order to use them in later steps. This phase is only completed once, and the next two steps act as continuations of this process.
- Selection. The basic methodology for this is to choose the objects with the highest "fitness score" from the last part, in order to cull the population to a more reasonable size. For my project, I took the initial 100 objects and cut them to the top 15, with the "fitness score" being given by the scoring algorithm which I describe in more detail below.
- Genetic operators. This section of the genetic algorithm does the bulk of the work. The first step is to choose parent objects. There are many different ways to do so. In this case, I chose rank-based selection, which ranks the objects by their fitness scores with 1 being the lowest up to 15 for the highest. I then chose a random number between 1 and the sum from 1 to 15, and saw where it fell in the range of cumulative sums. This results in it being highly likely to choose the ones with highest fitness, while being less likely to choose the ones with lower fitness. Now comes the operators which are performed on the two randomly selected parents (which are not necessarily unique). In the case of my program, there are two main steps: crossover and mutation. The mutation operator is the simpler of the two. In some random proportion of the objects which result from crossover, two of the keys' spots are simply swapped. The crossover algorithm which I chose is called ordered crossover, which retains the uniqueness of each of the "genes", or in this case keys. I randomly chose a starting and ending point within one of the two parents, and followed the process here: http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperatoraspx. From this point on, you take the resulting children genes to be the new starting set for step 2, and continue from there. Eventually, after a hopefully small number of iterations the algorithm will converge to some sort of local maximum. I have the program set so that it automatically stops if there is no change in local maximum after 20 generations of 100 new "children" keyboards; however, this can easily be tweaked within the program.
Now, I will expand a little bit on the process for defining a fitness function for the keyboards. I settled on four equally weighted categories: finger distance moved, alternation of fingers, alternation of hands, and closeness to the ideal ratio of finger percentages. The first three categories are rather self-explanatory, as they simply reward or take away points based on the respective quantities. The last part is a little bit more complex, as it required me to make a judgement decision on what the "ideal" ratio of finger usage should be. The exact numbers can be seen and changed within the program; I followed the basic rule that index fingers are the most desirable to type with, with the fingers to the outside increasingly less so.
Finally, I have one quick example of what the program does. I decided to test the program on one of the most famous speeches of all time: Abraham Lincoln's Gettysburg Address. I decided to go all-in on functionality, ignoring any possible restrictions imposed on the command keys changing or whatnot. As I result, the program outputted the following rudimentary sketch of the layout:
Examining the letter frequencies for the Gettysburg Address, we can see that the top five letters in terms of frequency are e, t, a, o, and h. Notice that all of these are on the home row of the keyboard, and do not require any movement to press. Notice that four of those are on the right side, and only h is on the left out of those. This is because h is the one that is in pairs most frequently with all the other letters; it makes sense to put vowels on the same side, as they are comparatively rarely pressed consecutively.
Eventually, I hope to expand this project to make it much cleaner and eventually add a web interface for it. The code is currently rather messy for it, so my next step is to clean it up. However, I will work on some other projects before doing so. Hopefully the ideas behind the project are interesting; if anyone sees any mistakes or has any questions, feel free to let me know. Thanks for reading!