[ScottBurson]

Yes, a lot of people use "algorithm" to mean simply "procedure". I'm glad to see someone besides me pointing out the distinction between algorithms, in the strict sense, and heuristics. Complaining about the misuse of technical terms is unlikely to have impact on usage in the popular press ([0]), but I think it's appropriate in a technical discussion.

One of the most egregious misuses of "algorithm", in my opinion, is the term "genetic algorithms". Not only are these not algorithms in the strict sense, but referring to the procedures as "genetic heuristics" or "genetic search" would be much clearer.

[0] https://news.ycombinator.com/item?id=10475884

[dwringer]

Genetic algorithms are algorithms in that they are a description of a specific process or set of processes (which may used in heuristics, or studied in isolation) at an implementation level of abstraction. "Genetic heuristics" suggests heuristic applications, rather than algorithms in isolation, and "genetic search" suggests a specific application, but a "genetic algorithm" can be extremely simple and isn't fundamentally different than an algorithm like quicksort. Either could be used as part of some heuristic, or not.

[ScottBurson]

> a "genetic algorithm" can be extremely simple and isn't fundamentally different than an algorithm like quicksort

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.

[dwringer]

I don't understand what you mean about formally specifiable postconditions. Genetic algorithms can have formally specifiable postconditions, they just aren't definable in terms of the problem space to which they're typically applied. The postconditions can be defined in terms of the state of the genetic system. I also am not able to find, anywhere, a formal definition of algorithm that unambiguously wouldn't include genetic algorithms as I outlined them in the above comment.

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.

[ScottBurson]

Well, I'll grant you that lots of people use the word "algorithm" in a way that doesn't respect the distinction andrewla and I are trying to draw.

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.

[0] https://news.ycombinator.com/item?id=15423045