• 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
Leszek said:

SpeedMorph, I see you spent many hours on the subject. I will try your code but an interesting idea came to my mind, I should have also start with logging my keyboard. I have been throught many injuries as a youngster so maybe it counts to the rolls effort.

You should definitely get some data first. I didn't.

Offline
  • 0
  • Reputation: 0
  • Registered: 14-May-2008
  • Posts: 103
DreymaR said:

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.

I have to agree about the 20-25ms resolution.  Just based on my personal timing data, I can tell you that anything sampled over 25ms will create quite a bit of "missing data" for the upper speed range.

On my modified colemak layout, I typed an average of 75 wpm, with bursts of 90wpm, but my timing data caught quite a few keypresses separated by only 20ms.

On dvorak, I hit quite a few keypresses within 10ms of eachother. A good majority of those were from hand-switching keypresses.

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

I have to agree about the 20-25ms resolution.  Just based on my personal timing data, I can tell you that anything sampled over 25ms will create quite a bit of "missing data" for the upper speed range.

On my modified colemak layout, I typed an average of 75 wpm, with bursts of 90wpm, but my timing data caught quite a few keypresses separated by only 20ms.

On dvorak, I hit quite a few keypresses within 10ms of eachother. A good majority of those were from hand-switching keypresses.

How did you get your data? ETA: Never mind.

Last edited by SpeedMorph (29-Aug-2008 15:56:30)
Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

I created a new scoring system, and got surprising results. I calculated each attribute for Colemak, Dvorak, and my layout, and then found a good average for each attribute that I thought was fair. I then changed the scores for each so that (# of occurrences of that attribute)*(score)=(score from "effort", a.k.a. finger travel distance). I couldn't change the costs for effort, a) because I need a baseline cost and b) because each individual position has different effort. So here's the stuff I got.

          roll = 200.0
          samefinger = 2200.0
          samehand = 611.0
          jumphome = 11000.0
          jumphomeindex = 4000.0 // this is how much jump home is reduced by if the index finger is on the bottom row
          rowchange = 110.0
          tocenter = 110.0

I then ran the program. The result I got was surprisingly good. I looked to see if I might have accidentally ran the algorithm using the wrong scorer, but I found no such problems. Here's the result.

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

It could be better, but it's good. Very good. I expected the effort to be a lot higher, because it was relatively less important. But that didn't happen. I don't see why the result was so good.

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

I have a question for you guys. Which of these layouts do you think is better?

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

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

I think the first one is better, but my program thinks the second one is better. #1 has much better same finger, but higher travel distance. #1 is my improved version of #2, an attempt to reduce same finger, which the computer doesn't like. So I want a third opinion.

Offline
  • 0
  • Reputation: 0
  • Registered: 17-Mar-2008
  • Posts: 192

When designing a good heuristic for a keyboard layout, one tries to make the scoring system reflect as closely as possible the subjective qualities of comfort and speed. In other words, if a layout scores higher, it should be more comfortable and faster. If you find a layout that you think is more comfortable but with a lower score, I would say that the heuristic is not right rather than say that the layout is worse. I.e. subjectivity is more important than the metric that is supposed to accurately reflect subjectivity. That is why it is important to test a layout subjectively at every step and not rely too much on the computer. If you feel the first layout is better, pick that.

To truly evaluate a layout subjectively, I submit you need to use it for at least a month. I experimented a bit when I first started out with Colemak, but found that whatever improvements I could make were so small that I decided to largely stick with Colemak. I have heard the same thing from other Colemak users. For me it is a small added benefit to actually use an existing layout in the hope that it will gain a more widespread adoption (realistically on par with Dvorak).

I understand you are eager for speed. I would say that spending a year to find a better layout will not help you as much as practicing with any layout for a year in that department. If you want to attain master speeds expect it to take several years.

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

When designing a good heuristic for a keyboard layout, one tries to make the scoring system reflect as closely as possible the subjective qualities of comfort and speed. In other words, if a layout scores higher, it should be more comfortable and faster. If you find a layout that you think is more comfortable but with a lower score, I would say that the heuristic is not right rather than say that the layout is worse. I.e. subjectivity is more important than the metric that is supposed to accurately reflect subjectivity. That is why it is important to test a layout subjectively at every step and not rely too much on the computer. If you feel the first layout is better, pick that.

To truly evaluate a layout subjectively, I submit you need to use it for at least a month. I experimented a bit when I first started out with Colemak, but found that whatever improvements I could make were so small that I decided to largely stick with Colemak. I have heard the same thing from other Colemak users. For me it is a small added benefit to actually use an existing layout in the hope that it will gain a more widespread adoption (realistically on par with Dvorak).

I understand you are eager for speed. I would say that spending a year to find a better layout will not help you as much as practicing with any layout for a year in that department. If you want to attain master speeds expect it to take several years.

1. Sometimes my program comes up with things I don't think of. But yeah, you have a point. Thanks for that. I think the difference between the two is almost too small to be noticeable, though.

2. I am not so eager for speed, I'm mostly doing this because I find it fun.

Offline
  • 0
  • Reputation: 0
  • Registered: 17-Mar-2008
  • Posts: 192

1. Sometimes my program comes up with things I don't think of. But yeah, you have a point. Thanks for that. I think the difference between the two is almost too small to be noticeable, though.

It's nice to use a program as a starting point just as you say. And it's important to check back with the program if you make subjective modifications to make sure you haven't accidentally introduced egregious same-finger problems or the like.

2. I am not so eager for speed, I'm mostly doing this because I find it fun.

It is fun, isn't it? Knock yourself out! :)

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

I ran my program, tweaking it, and got my new Hand Alternation layout. This isn't exactly the version my computer has, but I'm trying to get my program to get the result I want.

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

Modified version:

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

The second one puts more stress on the ring finger, but the ring finger has less same finger, which could make things easier. I think I like the first one better, because on my current layout I have AF on the ring finger and it hasn't caused any problems. What do you think?

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

Not sure if this should be a separate thread...oh well.

In life, sexual reproduction allows for faster mutation that asexual.  So maybe there is some way to do that with a genetic algorithm. But how?

A person gets half their DNA from each parent. But it's a different half. I'm not completely sure how it works. Maybe the same thing could work for keyboards. I got the idea of doing this:
-choose two random keyboards
-any keys that they both have in the same place will stay there
-other keys have a probability of being in the same place as one of those layouts
-the remaining keys are placed randomly in the remaining spots

Modifying my algorithm to do this would be hard, and I don't really need to improve my mutation process right now. But for the purpose of speculation, what do you think of this?

Offline
  • 0
  • Reputation: 23
  • From: Belgium
  • Registered: 26-Feb-2008
  • Posts: 480

I don't think this "breeding" approach makes much sense.  Take a qwerty/colemak breed for example: this would leave in place (mostly) the least-frequent keys (q, w, z, x, ...) and randomly move around the more often used ones.  Other layout pairs may have keys in common but perhaps for entirely different reasons (eg. digragh rolls with other keys that may be moved away), again resulting in little reason to keep those keys in the same place in their "offspring".

I think you better start from just one keyboard layout instead, and try to improve on that with random moves.  This is how you could derive a colemak from a qwerty layout.

Last edited by ghen (22-Sep-2008 10:18:18)
Offline
  • 0
  • Reputation: 210
  • From: Viken, Norway
  • Registered: 13-Dec-2006
  • Posts: 5,343

You should breed an army of keyboards and send them to the Arena to battle to the death with each other!  ;)

The Son Of Colemak Arises!  :o

*** 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 could make a new thread, but I don't want to fill up the forum with my personal projects.)

I am currently re-writing the algorithm in C. But I was wondering if C would really be the best language. I'm planning on making this one be high quality, and maybe using XCode to make a good user interface. So I want to make sure to do it in the right language. My main considerations are C and Java. C will be faster, but Java is more popular, so more people will be familiar with the code and it will be easier to find help with writing it, if necessary.

What language do you think it should be written in?

If anyone wants to help write it, that would be great. I'm not great at programming, and it would probably take me a couple months to get to where the program is really usable. More people would make it faster. But if no one wants to/is able to help, I can do it on my own.

@ above post: What would that look like?

Offline
  • 0
  • Reputation: 1
  • Registered: 22-Aug-2008
  • Posts: 36

I am interested in such a program for languages with non-Latin letters. I would help if I can, but I'm not great at programming either. I am currently studying C++, and I have used some Java in the past.

Why even consider C? C++ is supposedly no slower than C, only better and object-oriented*, and it's the most popular programming language. The problem with C++ compared to Java is that it does not officially support Unicode (needed for the non-Latin letters) yet (the new standard coming next fall will). And it does not have a standard way to create user interfaces (that would work on different operating systems). Nevertheless, I would recommend C++. :)

* edit: Well, I guess if you use objects that may make the object-oriented C++ program slower.

Last edited by vVv (07-Dec-2008 05:10:08)
Offline
  • 0
  • Reputation: 23
  • From: Belgium
  • Registered: 26-Feb-2008
  • Posts: 480
vVv said:

[C++] does not have a standard way to create user interfaces (that would work on different operating systems).

Qt?

Offline
  • 0
  • Reputation: 1
  • Registered: 22-Aug-2008
  • Posts: 36
ghen said:

Looks like that's what we need. And they have some nice tutorials and documentation at their website.

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

I am interested in such a program for languages with non-Latin letters. I would help if I can, but I'm not great at programming either. I am currently studying C++, and I have used some Java in the past.

Why even consider C? C++ is supposedly no slower than C, only better and object-oriented*, and it's the most popular programming language. The problem with C++ compared to Java is that it does not officially support Unicode (needed for the non-Latin letters) yet (the new standard coming next fall will). And it does not have a standard way to create user interfaces (that would work on different operating systems). Nevertheless, I would recommend C++. :)

* edit: Well, I guess if you use objects that may make the object-oriented C++ program slower.

My programmarial advisor says that using C++ is not as good because Java is best for object-oriented programming, and C is best for speed. He also says that it is very hard to learn C++ without first learning C. C++ is not actually used as much as C, and not nearly as much as Java. Java is good because of its popularity, and C is good because it's low-level, and learning C makes it easy to learn other languages because so many languages are based on C.

Because of Java's popularity, a lot of work has gone into making it as fast as possible. It may actually be faster than C++. https://en.wikipedia.org/wiki/Compariso … nd_C%2B%2B

http://www.tiobe.com/tiobe_index/index.htm (language popularity)

My programmarial advisor recommends either C or Java.

Offline
  • 0
  • Reputation: 1
  • Registered: 22-Aug-2008
  • Posts: 36

SpeedMorph, it seems that according to your programmarial advisor C++ is good for nothing! :)

Of course there are many different opinions. I recommend checking Bjarne Stroustrup's FAQ for the other side of the story. (Stroustrup is the creator of C++).

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

There are many sides to this. The fact that there are so many languages around isn't due entirely to the divisory nature of mankind, but to the many-faceted nature of programming.

This is not the forum for debating the pros and cons of the various flavours available, and I think that many languages would've been very good for your needs. Lua for instance, hasn't been mentioned yet and isn't big (not even mentioned by TIOBE) but it's been used in some large projects such as World Of Warcraft because while it cannot match the C/J languages in speed it isn't far behind and they say it's much easier to develop in it which a gaming industry hard pressed on development time may find convenient.

It's also interesting to note that the old C/C++ workhorses are still very strong, and if you look at the change from Dec 2007 you'll see that they are actually gaining on Java. The proclaimed paradigm shift to Java may not take place after all. That said, as SpeedMorph (and his guru) said Java is a nice language for sure. It's probably the best if you want to develop for multiple platforms? But not everybody is interested in that. And while C may be a tad faster than C++, the boilerplate is worse and you may not notice the slight drop in performance where the boost in programming efficiency will probably be noticeable. The same can probably be said for Java. And in the end, they aren't all that different even.

Like with keyboard layouts, people have different preferences and ymmv. Debating C vs C++ vs J (vs the rest of the family) may be harder than debating Dvorak vs. Colemak (on a Dvorak board!).  :)  But they all seem good. Wish I could make up my mind, myself...

*** 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:

There are many sides to this. The fact that there are so many languages around isn't due entirely to the divisory nature of mankind, but to the many-faceted nature of programming.

This is not the forum for debating the pros and cons of the various flavours available, and I think that many languages would've been very good for your needs. Lua for instance, hasn't been mentioned yet and isn't big (not even mentioned by TIOBE) but it's been used in some large projects such as World Of Warcraft because while it cannot match the C/J languages in speed it isn't far behind and they say it's much easier to develop in it which a gaming industry hard pressed on development time may find convenient.

It's also interesting to note that the old C/C++ workhorses are still very strong, and if you look at the change from Dec 2007 you'll see that they are actually gaining on Java. The proclaimed paradigm shift to Java may not take place after all. That said, as SpeedMorph (and his guru) said Java is a nice language for sure. It's probably the best if you want to develop for multiple platforms? But not everybody is interested in that. And while C may be a tad faster than C++, the boilerplate is worse and you may not notice the slight drop in performance where the boost in programming efficiency will probably be noticeable. The same can probably be said for Java. And in the end, they aren't all that different even.

Like with keyboard layouts, people have different preferences and ymmv. Debating C vs C++ vs J (vs the rest of the family) may be harder than debating Dvorak vs. Colemak (on a Dvorak board!).  :)  But they all seem good. Wish I could make up my mind, myself...

You have a point there. We could debate this all day.

I'm doing Java.

I am going to program in C a little bit more because I want to get some theory down. After that I'll start to learn Java. Based on how much I've learned with C, I should have adequate Java knowledge within about a month. Until then, I'll work on the theory of the program.


Actually, I don't want to clutter up colemak.com. So anyone who is interested in helping out should go here:
http://mtgap.bilfo.com/blog/2008/12/09/ … ject-nklp/

Edit: wrong link

Last edited by SpeedMorph (09-Dec-2008 18:37:06)
Offline
  • 0
  • Reputation: 0
  • Registered: 17-Dec-2008
  • Posts: 59

ON TIMING

Getting timing results from one's own typing is the first idea I tried.  One can (reportedly) get sub-millisecond resolution using Java's System.nanoTime(), although I stuck to 1 ms resolution.  Unfortunately, the results were useless.

Part of the problem is, seasoned typists will tend to be depressing the next key even before releasing the current key.  For instance, when typing IN on QWERTY, I'm already most of the way done depressing the N key by the time I'm ready to release the I key.  So, the true cost of pushing N is masked; it looks like the total time fingers spent flying around between I and N is, say, 10 ms, when in reality it's much more.

The only good way around this problem that I could think of was to measure only same-finger transition times, like between D and E on QWERTY.  Sadly, this turned out to be useless as well, at least for the kind of layout I wanted to grow.  Why?  Well, here were my top 10 fastest transitions on QWERTY:

F -> R
S -> X   (!)
F -> V
L -> O   (!)
D -> C
K -> I
; -> P   (!!!)
J -> U
D -> E
H -> U

So, what's wrong with that?  Well, despite my being very right-dominant, somehow the top three fastest transitions are all on the left hand!  On the right hand, the ring and pinky fingers rate faster than the index finger!  (In fact, all fingers on the right hand rate faster than the index finger).  This means that layouts resulting from this timing data will tend to be left-hand heavy (like QWERTY), and that the right index finger will probably end up massively under-used.  In other words, the resultant layout would probably be worse than QWERTY!  Why bother?

'Course, it's possible you'll get more intuitive data for yourself, but I wouldn't count on it.



ON BREEDING

It's not worth worrying too much about your breeding strategy.  I've dabbled quite a bit in genetic algorithms (mostly with real-number "genes" rather than bit-based "genes") and read a fair number of journal articles on the subject; I've come to the conclusion that generally, adding complexity to one's breeding strategy doesn't help.  With these kinds of algorithms, you generally want to get as close to random as possible while still converging on a "good" solution in a reasonable amount of time.  See the "No Free Lunch Theorems" for more info.

Yes, life does better with sexual reproduction, but that's largely because most tweaks to DNA result in totally non-viable organisms--organisms that, in GA parlance, have the worst possible fitness value because they never even get the chance to live, let alone breed.  Thus, you're a lot more likely to get a viable organism by mixing DNA from two known-viable organisms (crossover) than you are by randomly dinking with the DNA of a single organism (mutation).  For the vast majority of GA applications, all "organisms" are viable (i.e., capable of competing and reproducing); they may not be good, but comparatively few are the worst.



ON LANGUAGES

Java is fine for these kinds of applications.  Modern Java is fast, free, has a great free IDE (Eclipse), and has a massive library.  This goes 10-fold if you're a new programmer--with C and C++, you're going to be spending the bulk of your time fighting with the language rather than your problem.  C++, in particular, has an unholy amount of arcana, and a language standard at least as opaque as any law book.




ON USER INTERFACES

I really wouldn't worry about this at all.  Tweaking the UI will easily steal all your time from improving your GA, and pretty much no one is going go use it, anyway.  Of the tiny fraction of people who want to switch from QWERTY, an even tinier fraction of those people want to switch to a layout of their own design, and of that microscopic group of people, they all probably want to write their own software to do it, because they think they're smarter than everyone else.  :)

Last edited by Phynnboi (18-Dec-2008 02:41:49)
Offline
  • 0
  • Reputation: 0
  • Registered: 08-Mar-2008
  • Posts: 303

Phynnboi: You make some good points there.

Phynnboi said:

ON USER INTERFACES

I really wouldn't worry about this at all.  Tweaking the UI will easily steal all your time from improving your GA, and pretty much no one is going go use it, anyway.  Of the tiny fraction of people who want to switch from QWERTY, an even tinier fraction of those people want to switch to a layout of their own design, and of that microscopic group of people, they all probably want to write their own software to do it, because they think they're smarter than everyone else.  :)

Unfortunately, yes. I kind of just want a UI because that makes it more fun.

I just wish more people would publish their damn stuff. I've found at least three people with genetic algorithms that I didn't know about, because they never published anything. I thought there were just a few of us, but apparently there's a lot more.

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

a lot more.

...for a given value of 'a lot'...   ;)

I wish you coder heads would help me break apart the Windows keyboard manager instead so we could get that portable 'MSKLC' working.  :D

*** 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:

a lot more.

...for a given value of 'a lot'...   ;)

I wish you coder heads would help me break apart the Windows keyboard manager instead so we could get that portable 'MSKLC' working.  :D

1. I don't know nuthin' about Windows.

2. What's MSKLC?

Offline
  • 0
  • Reputation: 0
  • Registered: 17-Dec-2008
  • Posts: 59
DreymaR said:
SpeedMorph said:

a lot more.

I wish you coder heads would help me break apart the Windows keyboard manager instead so we could get that portable 'MSKLC' working.  :D

Portable?  You mean to other operating systems?  That's a pretty tall order, since as I understand it, they all have quite different mechanisms for remapping the keyboard.  Heck, I'd be happy if MSKLC would allow changing virtual keys.  Having to do part of the process in a text editor is pretty annoying.

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