A heuristic explores a problem in a specific domain. An algorithm specifies a process at a level suitable for machine implementation. Genetic algorithms are, thus, algorithms, though they are typically applied in heuristics to explore real-world problem spaces.
Nonetheless, I believe there is a real distinction here. As it happens, there is a discussion about algorithms textbooks on HN right now [0]. I contend that GAs are not the kind of thing that would ever be described in a textbook on algorithms, no matter how comprehensive.
> Genetic algorithms can have formally specifiable postconditions, they just aren't definable in terms of the problem space to which they're typically applied.
Actually, I think this would be a pretty good definition of the distinction, if we changed "genetic algorithms" to "heuristics". I think if you look at the procedures described in algorithms textbooks, you'll see they all have postconditions definable in terms of the problem space.
Ah, but it is. What do you get when you run quicksort? You get a sorted list. What do you get when you run a genetic "algorithm"? You get ... the result of performing that procedure. There's no other formally specifiable postcondition. You certainly aren't guaranteed to get a perfect solution to the problem you were trying to solve. That's why it's a heuristic: if you run this procedure a certain number of times, you might get a useful result. Maybe. And the way it works is by searching a space of possibilities in a certain way. That's not an application; that's the whole point.