Eliezer: "Anyone who can't distinguish between 1s gained in a bitstring, and negentropy gained in allele frequencies, is politely invited not to try to solve this particular problem."

Ok, here's the argument translated into allele frequencies. With sexual selection, mutations spread rapidly through the population, so we assume that each individual gets a random sample from the set of alleles for each gene. This means that some poor bastards will get more than their share of the bad ones and few of the good ones (for the current environment), while luckier individuals gets lots of good ones and few bad ones. When the unlucky individuals fail to reproduce, they're going to eliminate bad genes at a higher-than-average rate, and good genes at a lower-than-average rate.

"On average, one detrimental mutation leads to one death" does not hold with sexual selection.

Also, just in case I'm giving the wrong impression--I'm not trying to argue that genetic algorithms are some kind of secret sauce that has special relevance for AI. They just aren't as slow as you keep saying.