I just ran some tests, and actually, mutation and selection probabilities of near 100% are optimal, as is a very small population size, at least if you use the mutation and selection policies as given in this article (multiply two numbers on 0->1, multiply by population size, floor the result and select the candidate out of a fitness sorted array that has that index). When I say "optimal", you have to be sure to evaluate the population size multiplied by the number of generations to estimate how well the algorithm is doing, because a bigger population takes more work to evaluate even if it requires fewer gens.

Honestly, I'm not sure why the OP's algorithm seems to take so long - with population of 20, and both crossover and mutation set at 100%, I'm seeing an average of about 190 generations needed to evolve a perfect "Hello, World" when started randomly (character codes between 32 and 127). This should be exactly the same setup as the OP has, though I haven't checked his code against mine in serious detail (mine is in JS). I just wrote my code up in a couple hours, so it's quite possible there's a mistake, but it seems unlikely that I coded a bug that made it perform better than it should...

One difference I note is that the way he does crossover is actually two point crossover, in that he selects a start and end point randomly from a uniform distribution over the length. That's a little odd, but probably not a major problem: even when I disable crossover altogether in my code, and roll with mutation-only, I still end up with an average of 342 gens to reach the target, which is an order of magnitude under the 3100 that the OP claims it took for him.

It's worth noting that the OP's first, "naive" algorithm, with a single member in the population, performed at roughly the same number of generations as the one with pop size of 20, mutation, selection, and crossover, according to his report. That's disturbing...I checked, and in my code the "naive" algo (mutate, then either accept or reject the mutation based on whether it's beneficial or not) performs at somewhere around 3000 generations to completion, which makes me suspicious that somewhere in OP's code there's a bug that's somehow missing out on the benefits (measured by gen count - see below) of having a higher population and crossover.

FWIW, for this problem, at least the way the OP set it up, the "naive" algorithm is actually a very good way to go - when I increase the population size to 20, and set the mutation/selection/crossover policies OP used, I find that the average number of fitness checks required to hit "Hello, World" (about 3510) is actually higher than the number in the naive version (in the neighborhood of 3k, usually a bit under). Also, the real time taken is larger. Which means that adding "genetic" to the algorithm has actually hurt us...

In fact, even with my full GA codebase in hand (not a substantial one, I wrote it in response to this post, but it's more flexible than the OP's), I couldn't find any situation where having a population size more than a few members helped - single member mutation (which is accepted/rejected if better/worse) always won. This is a good indication that this type of problem is vastly better suited to gradient descent than it is to a genetic algorithm.

Of course, the reason for this is that the fitness landscape is very smooth, and the local gradient very accurately tells you where to go - an decent hill climber that knew how to work with integer parameters could solve this in probably ten or fifteen steps, max.

Which reminds me, I keep meaning to write up an article on how to pick out problems where GAs are actually of some use. There are a few, but you almost never see them, and almost every demo I've seen on HN over the past few years would be better solved by gradient descent.