I do agree that digrams/trigrams turn out to be the most important thing in this kind of layout. The MessagEase layout seems to get a lot of digrams right, even if it's only by accident. I think the real problem is that we don't have a very good model for the relative costs of things like non-alternating thumbs and sliding from the same box after a tap. I think the optimization algorithm would probably not be that hard relative to quantifying the costs of different placements.
I'm not a programmer but there is this open source tool called genkey, which can generate desktop keyboard layouts. Maybe it could be somehow adapted for generating 3x3 layouts.
I'd be willing to give it a try. Have you done any work on the hand movement model, like he shows at 2:06 in the video you posted? Mine would be different from yours, since I type with just one thumb.
The important part is how much time it takes to type key 1 after typing key 2, right? Maybe just logs of people typing with time stamps for every key or something? Then I could make a map to teach the AI with.
Are you particularly attached to the evolutionary algorithm? I might try a few different ones.
MessageEase unfortunately didn't do any optimization after their first 9 letters ( and I don't fully trust what they did there either ). When it came to the swipes, they based it off of whether the letter was curly-shaped or not (curly shaped letters go off the center key)