Het optimaliseren van een toetsenbord voor een mobiele telefoon

Omdat het veelgebruikte QWERTY-toetsenbord voor een mobiele telefoon, waarop veelal met één vinger getypt wordt, geen optimale typtijd genereert, wordt gezocht naar een nieuwe toetsenbordindeling. Om dit Toetsenbord Layout Probleem op te lossen, worden in de eerste plaats twee nieuwe toetsenroosters gecreëerd, namelijk een met hexagonale toetsen en een met rechthoekige toetsen. Met behulp van WhatsApp gesprekken en de nieuw gevormde toetsenroosters worden twee matrices gemaakt, die gebruikt worden om een kwadratisch toewijzingsprobleem (QAP) op te stellen. Vervolgens wordt met behulp van de eigenvalue bound, Gilmore-Lawler bound en reduced Gilmore-Lawler bound ondergrenzen bepaald voor dit probleem. Ook wordt de gemiddelde waarde van alle mogelijke oplossingen bepaald met de mean objective value. Hierna wordt met twee heuristieken geprobeerd voor beide toetsenrooster een optimale toetsindeling te vinden, namelijk met local search en simulated annealing. Uiteindelijk worden met simulated annealing de twee best gevonden toetsenbordindelingen gevonden. Met de hexagonale layout blijkt iets sneller te kunnen worden getypt dan met de rechthoekige layout, maar voor beide geldt dat ze maximaal 14 procent verbeterd zouden kunnen worden, kijkend naar de onderzochte ondergrenzen