  Current layouts for alphabetic input on mobile phone keypads are very
inefficient. We propose a genetic algorithm (GA) to find a suitable keypad
layout for each user, based on their personal text history. It incorporates
codes for frequent multigrams, which may be directly input. This greatly
reduces the average number of strokes required for typing. We optimize for
two-handed use, the left thumb covering the leftmost rows and vice versa. The
GA mini- mizes the number of strokes, consecutive use of the same key, and
consecutive use of the same hand. Using these criteria, the algorithm
re-arranges the 26 alphabetic characters, plus 14 additional multigrams, on the
10-key pad. We demonstrate that this arrangement can generate a more effective
layout, especially for SMS-style messages. Substantial savings are verified by
both computational analysis and human evaluation.
