Multi-objective optimization of mobile phone keymaps for typing messages using a word list

Most mobile phones today offer the option of using a word list to ease the typing of short messages (SMS). When a word list is used, a word is input as a sequence of digits by pressing the key corresponding to each letter once. The word list is used to look up the word(s) that correspond to this sequence of digits. This paper describes how a mobile phone keyboard layout can be obtained that is better suited for typing such messages. Two objectives are considered: the total cost of typing, and the total cost of word clashes that occur when a certain digit sequence corresponds to two or more words in the word list. A multi-start descent algorithm is developed to obtain a Pareto set of solutions.