I remember reading this and thinking "That would be so much simpler to do with a breadth first search". Sure 'genetic' sounds cool, but when the search space is as limited as it is in a build order optimization like this, you should use the right tools for the task.
They also didn't use crossover which I thought was the main advantage of genetic algorithms. How would a breadth first search work better? The search space is huge.
If your edges are 'building things' and your nodes are records of some type (current time, number of stuff, stuff currently building), then you can calculate when you will be able to build what next, and generate the descendent states.
Given we are interested in four types of buildings and three types of units, that's maximum 7 descendents per node. Getting to 7 roaches doesn't require more than 20-30 actions. That's 7^30 and too much, but a lot of states are easy to prune, e.g. don't build 2 zergling dens, and on top of that you can add some goal searching heuristics, like a*.