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.
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.