Transcript PPT

Evolving a Faster Keyboard
Christopher P Walker
Overview





Motivation
Algorithm Considerations
Design of the EA
The nonexistent preliminary results
Future Work
Motivation



More efficient work
authors, secretaries, and other people
who depend on typing would be able
to work faster
This project would be done faster.
Algorithm Considerations


Brute force methods will have to check
at least 88! possible key combinations
Evolutionary Algorithms seem natural
for this problem
Inner Workings of the EA



Two populations pools
Rank based reproductive selection
Deterministic proportional generational
selection
Individual Characteristics



Each individual is represented by an
array of keyboard locations.
Indexes into the array correspond to
the key in question.
Allows for efficient key lookup and
quicker evaluation.
Individuals (cont.)


The keyboard is divided into the
following sections: ALPHA,
NUMERIC, SYMBOLIC, and
MODIFIER
Crossover and mutation will not be
allowed to move key locations outside
of their sections.
Keyboard Layout
Individual Evaluation


The layout will be “tested” by typing
out different words from the English
Language.
Individuals will be rewarded for forcing
the user to alternate fingers and
hands, while being penalized for
repetitive characters on the same
finger and hand.
Individual Evaluation (cont.)



A word is randomly selected from a
list, and is “typed” using the keyboard.
The keyboard is then scored based on
how the word is typed, and the score is
normalized over the length of the word.
The score is then averaged into the
total score for the individual.
Individual Evaluation (Phase I)
For Phase I, the scores are computed
according to the following criteria


Three points are given each time two
consecutive letters require a different
hand, one point for different fingers, and
two points for home row.
Two points are deducted if the same
finger is used for a different row, one
point is deducted for the same hand
Individual Evaluation (P II)
Phase II will use values determined
experimentally for the fitness function.
Word Sources



Words will be randomly selected from
various sources
Initially they will be selected from the
1000 most used words in the English
language.
Later the system will be asked to
virtually type sentences from various
sources
Sentence Sources
Sentence Sources Include




The Bible, King James Version
Moby Dick, by Herman Melville
The Dark Tower V, by Stephen King
Dope, by Sax Rohmer
Reproduction - Crossover


Crossover will be based on the
categories/divisions in the keyboard
structure, not on individual key
locations
Will probably be removed in later
iterations.
Reproduction - Mutation



Mutation is accomplished by swapping
the location of keys.
Currently only allowed to swap within
their categorical restrictions.
Will become the only reproductive
operator in future iterations, when the
categories are removed.
Preliminary Results

No.
Future Work



Remove the categorical groupings of
the keys.
Optimize the entire keyboard, not just
the part that’s most commonly used.
Attempt to optimize the keyboard for
other languages as well.
Questions/Comments?