• You are not logged in.
  • Index
  • General
  • Keyboard Optimizer Genetic Algorithm

Keyboard Optimizer Genetic Algorithm

  • Started by SpeedMorph
  • 97 Replies:
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
Shai said:

It looks like a good layout. The only major problem I see is that there is too much work on the pinky corner positions. You'd also want to try to avoid same-finger row jumping, such as with BL digraph.

I noticed that BL problem because it's exactly the same on my Nisa layout (which I designed first). Switching B and K would make it easier to type, but that would hurt finger travel distance, and BL isn't very common to begin with. That's why I decided against it with Nisa. That other layout wasn't designed by me, my program made it. Since my program thinks that the current position of B is better than if you switch B and L, I am considering changing the program so that multiple problems at the same time increase the penalty. For instance, if row jumping costs 30 and finger use costs 40, both might cost 90 instead of 70. Thanks for the feedback, it's very helpful to me.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I changed the program a bit to find the best home row, independent of the other parts. I ran it three times using the following criteria.

In order to simplify things, I limited the home row to ETAOINSRHD. (It was going to be L instead of D because L is more common by most counts, but D works better because it goes well with T, plus I think L can do better off the home row.)

Each position has a value:

9 2 0 0 40 || 40 0 0 2 9

-Using the index finger twice adds 80 to the score.
-Using the same hand more than twice adds 1 for each time it's happened so far.
-Going to the center without changing hands before or after costs 6.
-Rolling inward subtracts 5.
-Rolling outward subtracts 3.

The inroll-outroll values may be a bit high, but I did this on purpose because I don't think it will hurt the layout, and rolls are fun.

All three times I ran it, I got the same result:

s o a t d h n e r i

In terms of just home rows, according to my criteria this is the best possible.

The advantages:
-3 of the 4 most common keys, ETA, are on the strongest 4 fingers
-the pinkies have a pretty small load
-there are some good rolling digraphs: at, en, er, re, so, ne

I thought it was interesting how, when there are only 10 factorial (about 3 million) combinations, it very quickly comes up with the best possible result.

I am working on a way to add in the top row, then mutate that until it is the best, then add in the bottom row. This way it will already be very good before it adds another layer. This is proving to be harder than it sounds.

Offline
  • 0
  • Reputation: 176
  • From: Viken, Norway
  • Registered: 13-Dec-2006
  • Posts: 5,226

I think that with this approach it'll be very easy to "paint yourself into a corner", or in more scientific terms, find local maxima instead of global ones.

The main reason for this would be the digraphs as I see it. I believe the rows have to be seen together to best evaluate the interactions between letters.

*** Learn Colemak in 2–5 steps with Tarmak! ***
*** Check out my Big Bag of Keyboard Tricks for Win/Linux/TMK... ***

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
DreymaR said:

I think that with this approach it'll be very easy to "paint yourself into a corner", or in more scientific terms, find local maxima instead of global ones.

The main reason for this would be the digraphs as I see it. I believe the rows have to be seen together to best evaluate the interactions between letters.

That is true. I'm not saying that the home row it generates is the best when added to a full layout. But it is still better than a layout that is made through completely random generation; I switched just 2 keys on the home row it generated and made myself a layout which ended up being the best one I've made by hand so far. It's the same idea with the genetic algorithm. It starts with something that is already good (if not the best) so it then has to do less work to improve it.

When creating the best layout, the key is really in the home row. Everything is based around that: once you have the home row, you basically have the layout. There are only a few decisions left to make, because there are a lot of givens: Y goes with I, U goes with E, W goes with R, punctuation goes with vowels, try to keep ZXCV in the corner. (On my current best layout I have JXZV in the corner, and C is on the top of the left pinky.) All that's left is the placement of a few letters such as m, g, p, f, and even those can't go anywhere. GR, PR and FR are all too common for them to go with R, SM is too common, etc.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I tested the some layouts on the most important characteristics: effort (i.e. finger travel distance), same finger, same hand, inward rolls, and jumping over the home row. I tested 7 layouts: Capewell's evolved, Dvorak with U and I switched, Colemak, Klausler's evolved, Arensito, Nisa (one that I made), Soit (one that I made with the home row generated by my home row generator program), and my evolved.

Here's the ratios for highest to lowest on each characteristic.

Hand Count
Most: Capewell
Least: Dvorak
5:1
This makes sense because the Capewell layout was completely ignoring same hand, and even rewarding it, while Dvorak is based on reducing it.

In Rolls (more is better, unlike all others)
Most: Arensito
Least: Dvorak
4.5:1
Most layouts don't really try very hard to get a lot of these, but Arensito has the most. It's a bit odd that Dvorak has the least, because it's the only one with TH. Of course, other than TH and NT, it doesn't really have any.

Home Row Jumping
Most: Evolved
Least: Capewell
3.5:1
I don't know why my evolved layout has so many row jumps because I made it cost a lot. Capewell penalized row jumps highly, though.

Same Finger
Most: Dvorak
Least: Soit
2.5:1
Everyone basically thinks same finger is bad. If you don't count Dvorak, the worst is Capewell, which would make it 1.7:1. Everything besides Dvorak is pretty close.

Effort
Most: Arensito
Least: Nisa
1.07:1
Now this is interesting. Everyone pretty much agrees that finger travel distance is the most important factor, so they all have very similar effort. Arensito probably has the highest because my scoring program is meant for normal keyboards, and Arensito is meant for Kinesis. My 3 layouts are the best 3 at this, which is probably because different people value different spots differently. Even so, they are only a tiny bit better than the 4th best, Colemak.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I have done another interesting experiment. I locked ETAOINSR into the home row, and eliminated all costs other than same finger. The objective was to determine the best possible arrangement where the keys were in groups of very low same finger. I got this result: (well not really, I rearranged it to be a bit more logical but kept all the groupings the same)

. w u l p q f d ' x
a r i n h c s t e o
, ; y m k v b g j z

Capewell same finger: 98320.0
Colemak same finger: 97928.0
This layout same finger: 89190.0

I have also determined through this that S and N are better* to have on the index fingers than T, which is good because having T on the index finger might cause over stress of that finger.

*marginally

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I know that some of you guys like Colemak. So you will be glad to know that I ran some layouts through the mutator and Colemak was hardly touched. My program changed Arensito and Capewell layouts a lot, and the Klausler layout is hardly recognizable! But it only made one change on Colemak: switch period and semicolon. (Unfortunately this increases same finger a bit with shift, but my program doesn't count shift, plus I mostly use the left shift so that doesn't really matter for me.)

Offline
  • 0
  • Reputation: 176
  • From: Viken, Norway
  • Registered: 13-Dec-2006
  • Posts: 5,226
SpeedMorph said:

I know that some of you guys like Colemak.

Gee, whiz, ya think so? Thanks for the laugh.  ;)

I'm wondering: Does this mean primarily that you've developed a Colemak-friendly test algorithm, or that Colemak has really good placements? If only I could think of a good way to test your test, as it were.

Quis custodet ipsos custodes?  --  Juvenal

*** Learn Colemak in 2–5 steps with Tarmak! ***
*** Check out my Big Bag of Keyboard Tricks for Win/Linux/TMK... ***

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
DreymaR said:
SpeedMorph said:

I know that some of you guys like Colemak.

Gee, whiz, ya think so? Thanks for the laugh.  ;)

I'm wondering: Does this mean primarily that you've developed a Colemak-friendly test algorithm, or that Colemak has really good placements? If only I could think of a good way to test your test, as it were.

Quis custodet ipsos custodes?  --  Juvenal

Well I based my algorithm on the values of mainly the Capewell layout, the Arensito layout, Colemak, Dvorak, and my own opinions on what's hardest to type. I think it is Colemak friendly, meaning that it has values that are good, and Colemak also has values that are good, so many of them are the same.

Also, I finally implemented the thing that keeps ETAOIN on the home row. I also made it so that when the layouts are first generated, ETAOINSRHL are put on the home row, DCUMFGYWPB are put on the top row, and VKXJQZ,.;' are put on the bottom row. Before these modifications, it would usually go through about 150 cycles before stopping. Now it only does about 40.

Last edited by SpeedMorph (29-May-2008 16:55:13)
Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I decided to use a formula to determine the cost of each key, and after a little tweaking, it turned out really well. I measured the horizontal and vertical distance between each key, and applied the following formula to each location:

V = vertical distance from home
H = horizontal distance from home
P = pinky
R = ring
M = middle
I = index

P = h(v+2)*2
R = h^2(v+2)*1.2
M = h^2(v+2)*1
I = h(v+2)*1

Ring and middle finger have horizontal distance squared because it's harder for them to move sideways. That extra number at the end is the relative strength of the finger. M and I are both strong, R isn't quite as strong, and P is a good deal weaker. Here's my results, with everything multiplied by 10 and rounded to the nearest 1:

66 35 29 33 60  91 33 29 35 66
20 12 10 10 40  40 10 10 12 20
96 72 60 48 109 48 48 60 72 96

This is very close to my idea of an ideal cost system. However, a few things were unexpected that I didn't originally implement. It has a much wider spectrum than my original design, where the lowest (that's not 0) is 20 and the highest is 48. I also noticed that the center of the home row ended up costing more than ring, index, AND pinky on the top row. I can understand how this would work; index finger stretches are a bit uncomfortable, and actually have to move slightly farther than reaching to the top row (2 cm vs 1.8 cm). I am going to implement this new system, and will have to tweak the other values to work along with it.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I ran the algorithm twice, and got practically the same result. I've been unable to improve on this layout, so it will probably be the final version for a standard (non-ergonomic) keyboard with shortcuts in place.

 k g l d b j h u f .
 r o t s w m n e a i
 z x v c q y p , ' ;

It has about 10% better finger travel distance than Colemak, a little less than twice as high same finger (which I think is okay because Colemak has remarkably low same finger), about half as much row jumping as Colemak, less inward rolls, and more outward rolls. It has better same hand; notice that four of the five vowels are on one hand.

Do you see any problems with this layout? I could name a couple things that are a bit weird. G and F are on the same finger as vowels. But I rearranged things a bit and that only made it worse. I think it's just that GO/OG and FA/AF are rare digraphs. Also period is on the right pinky, and that might hurt the same finger due to the period-return digraph.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

Okay, this is probably the last time I post three times in a row. http://mtgap.bilfo.com/ Here I talk about the four layouts I've designed. I will be updating it fairly regularly for a while.

Offline
  • 0
  • Reputation: 0
  • Registered: 17-Jun-2008
  • Posts: 7

Any chance you can send me you program so I can try out my own ideas for a layout focused solely on real-world typing speed? I use both Linux and Windows but I'm a noob when it comes to programming so maybe I'll have to start learning C or something

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
slowpoke said:

Any chance you can send me you program so I can try out my own ideas for a layout focused solely on real-world typing speed? I use both Linux and Windows but I'm a noob when it comes to programming so maybe I'll have to start learning C or something

I could, but it's in Ruby which runs on Mac. I think it will run on Windows but you have to download Ruby, i think at ruby-lang.org. I could upload my files onto my website probably.

What ideas did you have in mind? Maybe I could implement them.

http://mtgap.bilfo.com/keyboards.zip

Go to the above website and you can download it. It will download as soon as you navigate there. Right here http://mtgap.bilfo.com/keyboard.html near the bottom of the page it tells you how to use it.

I am working on ways to make it more user-friendly right now, so what's up there right now isn't the final version.

Last edited by SpeedMorph (17-Jun-2008 22:55:29)
Offline
  • 0
  • Reputation: 0
  • Registered: 17-Jun-2008
  • Posts: 7

Thanks Speed. I'm going to see how far I can get with your code. I also downloaded the programs from the other projects mentioned earlier it this thread.

My main idea was to replace some of the punctuation with duplicate letters and have the keyboard designed for the most common words and phrases in English. 95% of my typing centers around E-Mail, IM, and Blogs so I want my keyboard optimized for that, and not some obscure corpus of outdated and specialized books.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
slowpoke said:

Thanks Speed. I'm going to see how far I can get with your code. I also downloaded the programs from the other projects mentioned earlier it this thread.

My main idea was to replace some of the punctuation with duplicate letters and have the keyboard designed for the most common words and phrases in English. 95% of my typing centers around E-Mail, IM, and Blogs so I want my keyboard optimized for that, and not some obscure corpus of outdated and specialized books.

Well I put the trigraphs program in the package so you can get trigraph frequency from whatever file you want, but it has to be plain text. But to have more than one key of one type would mess things up. When I tried making 2 Es, one of them completely disappeared. Plus, using the home keys and not pinkies subtracts from the score, so having something more common there actually would reduce the score. It's still exactly the same as if the home keys costed 0, but I made it negative because of how it was working in relation to the rest of the keyboard. So if the home keys are all Es, that would reduce the score. Hmm, that's a bit of a problem. You could just add 10 to every position. The place where it's scored is right here, in scorer6.rb:

          @key_score = {
              [0,0] => 66,
              [0,1] => 35,
              [0,2] => 29,
              [0,3] => 33,
              [0,4] => 60,
                        ....

I found out why it can't have 2 of the same letter. It could if you could somehow distinguish between those two letters. How do I know which E I'm going to press this time? The program doesn't, which is why it doesn't work. I can think of 3 ways, and I could probably implement any of them.

1. it's random
2. 50% of the time hit E1, 50% of the time hit E2
3. If the key is followed or preceded by this letter(s), use this key. Else, use the other key. But how do you know how to divide it up?
     3a. If the key is to the left or right of E1, use E1. Otherwise, use E2
     3b. If the key is on the same hand as E1, use E1. Otherwise, use E2

I think 3a would be better, but it depends on context of course.

Last edited by SpeedMorph (18-Jun-2008 17:59:21)
Offline
  • 0
  • Reputation: 176
  • From: Viken, Norway
  • Registered: 13-Dec-2006
  • Posts: 5,226

I'm taking this topic "back home" from the non-staggered thread, I hope.  ;)

SpeedMorph - I don't remember whether you've done this already so forgive me if I'm being forgetful, but: Did you try weighting a bit for whether a key is moved from QWERTY? And then a little extra penalty if the key is a common shortcut key (such as ZXCVASQW and maybe BFI?)? I guess you don't care so much whether the Ctrl-ZXCV block is shot up, but I'd be very interested in seeing what your optimizer would make out of such constraints. Also, instead of adamantly demanding that certain keys stay in place this tack would just place a value on keeping them where they were. It'd be an interesting exercise I believe, even if you yourself is perfectly willing to learn any new layout you create no matter how complex it may be.

Last edited by DreymaR (25-Jun-2008 08:28:23)

*** Learn Colemak in 2–5 steps with Tarmak! ***
*** Check out my Big Bag of Keyboard Tricks for Win/Linux/TMK... ***

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
DreymaR said:

I'm taking this topic "back home" from the non-staggered thread, I hope.  ;)

SpeedMorph - I don't remember whether you've done this already so forgive me if I'm being forgetful, but: Did you try weighting a bit for whether a key is moved from QWERTY? And then a little extra penalty if the key is a common shortcut key (such as ZXCVASQW and maybe BFI?)? I guess you don't care so much whether the Ctrl-ZXCV block is shot up, but I'd be very interested in seeing what your optimizer would make out of such constraints. Also, instead of adamantly demanding that certain keys stay in place this tack would just place a value on keeping them where they were. It'd be an interesting exercise I believe, even if you yourself is perfectly willing to learn any new layout you create no matter how complex it may be.

Yes, that is interesting. The way you can do that is have it add to the final score.  (It divides the score by the number of characters at the end.) What it does is adds to the score for every key that isn't on the same hand as its QWERTY position, and subtracts for every key in the QWERTY position. Depending on how much you make the penalty, you get different results.

this tack would just place a value on keeping them where they were

Exactly.  I can use a similar penalty for shortcuts. The shortcuts I have are X, Z, C, V, with Q at half value and W at one quarter value.

Here's my favorite:

q w l d b j f u k p
a s r t g h n e o i
z x c v ; y m , . /

I was a bit surprised to find that it moved B, but I can see why. It does not have an added penalty for less frequent keys moving off their QWERTY positions.

It has better finger travel than Colemak, worse same finger and same hand, and better row jumping. In terms of score, they are pretty close. However:

-It keeps 14 keys in their Qwerty positions, to Colemak's 12
-6 other keys are on the same finger
-4 keys change hands: E L F ;

I am not planning on learning this layout. Maintaining 3 keyboards (mine, Colemak, Qwerty) is hard enough. If you want to learn it, be my guest.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

UPDATE:

I am currently learning Objective-C. I still want to improve my program and would love to hear any new ideas, but I won't be making any new layouts until I have re-created the algorithm in Objective C, which could take a while.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303
DreymaR said:

Your evolved layout can only be as good as the correlation between your axioms and actual typing efficiency. It will be a fun and interesting exercise for sure, but will it actually reflect layout quality for most users - or even for yourself?

That gave me a great idea: make an evolutionary algorithm to optimize a scoring system! It would use already known layouts, and work backwards. It would try to find the scoring system that gets these layouts as close as possible to this order:

Colemak
Capewell
MTGAP's Layout 2.0
Arensito
Nisa (by me, you can find it in this thread I believe)
Maltron
Seruxie's Layout
Amuseum's layout
OSTNREAI
Peter Klausler's layout
Asset
Dvorak
Plum
XPeRT
QWERTY

I think that is the order of how good each of these layouts are. Are there any layouts I should add, or do you think I should change this order?

So what it will do is create some copies of the Scorer class. (This is when object-oriented programming comes in handy.) Each Scorer class has random values for each aspect. They score all of these layouts. The half that are farthest from this order are killed, and the other half are duplicated. The duplications change one of their aspects slightly. Repeat. It ends when one of the scorers scores the layouts in this order.

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

For the purpose of research, I just did some finger weightlifting exercises. I tied a string to a 5 pound weight, and tied the other end to my finger. Then I held my hand flat and out (like if your hands are resting on a keyboard), with my fingers hanging down, and lifted the one with the weight until it was level with my hand. Then I did it until I got tired. This is of course very inaccurate; a better test would be to see how much I can lift with a finger, but I only had big weights. I got 6 lifts with my pinky, 2 with my ring finger, 9 with my middle finger, 8 with my index finger, and over 30 with my thumb. I wasn't tired but I stopped at 30.

This is obviously very inaccurate. Does anyone know of a better method?

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I have a great idea! I was having a lot of trouble balancing my scoring system. Then I realized that instead of trying to find the scoring system that would create the perfect ratio between travel distance, same hand, etc., I could use the ratio itself! I am not completely sure how it would work, but the idea is that it would try to find the layout with the closest to the optimal ratio, while each attribute is as low as possible. I calculated the ratios for travel distance, same finger, same hand, rolls, and row jumping, respectively, on my 2 best layouts, Colemak, Capewell, and Dvorak. I used these 5 because a) it's hard to do and I didn't want to do many and b) they cover a good range: mine 2.0 and Capewell's have low same hand, Colemak and mine 1.0 have medium, Dvorak has high; plus I wanted to do both my main layouts.

Note 1: When I say same hand, I actually mean reversing direction on one hand.
Note 2: Travel distance is way higher than everything else. It's in centimeters I think.

MTGAP 2.0-- 12 million: 1: 3.3: 21: 0.18

MTGAP 1.0-- 10 million: 1: 2.1: 8: 0.45

Colemak-- 13 million: 1: 3.5: 11: 0.45

Capewell-- 11.5 million: 1: 4.5: 16: 0.2

Dvorak-- 8.4 million: 1: 0.45: 3: 0.25 (Finger travel is low because same finger is high, so it gets reduced instead of increased.)

My idea of a good ratio-- 11 million: 1: 2: 15: 0.3

This ratio is sort of an average of the 5 above. I can create a scorer that gives points for being close to this ratio, and also gives points for the numbers being smaller.

Offline
  • 0
  • Reputation: 176
  • From: Viken, Norway
  • Registered: 13-Dec-2006
  • Posts: 5,226

Hmmm. On a slightly related note, I just realized what I'd probably use: Measured delay times for the different letters from different layouts. As mentioned elsewhere, get an app that provides a load of nice typing statistics and run that on a lot of typing on different layouts. If you want YOUR best layout, you'll be fine with yourself typing. If you want THE best layout, you'll have to have a lot of different users of the different layouts.

Then compile the lot and hope to make a publishable article out of it.  :)

*** Learn Colemak in 2–5 steps with Tarmak! ***
*** Check out my Big Bag of Keyboard Tricks for Win/Linux/TMK... ***

Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I tried implementing my new idea, and it didn't really work. I couldn't get the overall score to stay low, and when I created a penalty for one of the aspects, I couldn't balance it.

DreymaR: The best thing would be something that also gets digraphs. It's not just individual letters, but also the one that came before it. I want to write a program to count letter and digraph frequency, but I see no way to count hundredths of a second.

Leszek: You have a lot of rolls that you like.

If you're using a Mac, you can use my program. I have a cost for everything I could think of, so all you have to do is change the numbers. You should check out http://mtgap.bilfo.com and colemak.com/Alternative_layouts. I have a bunch of stuff there.

Tuning your weighing algorithms takes a LONG time. I did it for about three months, and then I somehow screwed it up and now I can't get it to work better. There are some very subtle changes that can change a lot. My biggest problem was balancing same finger and travel distance. I put same finger higher, but then it put vowels on the same finger, overloading the finger and increasing travel distance. The solution I found was to give the keys on the home positions a negative score, which isn't perfect, but works.

What do you think of the layouts I've made? You can see them at the "Official keyboards" page on my website.

Edited broken link.

Last edited by SpeedMorph (24-Aug-2008 04:02:00)
Offline
  • 0
  • Reputation: 176
  • From: Viken, Norway
  • Registered: 13-Dec-2006
  • Posts: 5,226

Hundredths? Ah yes, I see how that would be useful but I think you'd get away with tenths. That's out of the league of scripting languages as far as I'm aware of, but should be within reach for the C family.

If one types at a fast-but-doable 100 WPM (=500 CPM), that equals 120 ms per character. Granted, some people are half again as fast but I don't know whether we'd be measuring any of those so let's be comforted to know that most the measurements would be on people half as fast instead. Now, the real question is of course what kind of variation from that mean we're looking at measuring - but if you get your sampling resolution into the 20-25 ms ballpark and use a fairly large data sample I think you should be just fine; my rule-of-thumb is a sampling resolution of 10 times the signal (i.e., 240 ms per char for 50 WPM). (Keep in mind that with only an hour of typing will produce a lot of characters!) That's just a guess though - I don't have the exact calculation in my head to the degree that I'd have to start searching around at work to do it.

To get something like that to work, I'd think it'd have to be a background process ticking away through the day while the keyboardist types away at what he or she usually types away at. I've seen such apps.

Last edited by DreymaR (24-Aug-2008 09:24:09)

*** Learn Colemak in 2–5 steps with Tarmak! ***
*** Check out my Big Bag of Keyboard Tricks for Win/Linux/TMK... ***

Offline
  • 0
  • Index
  • General
  • Keyboard Optimizer Genetic Algorithm