Hacker News new | ask | show | jobs
by ScottBurson 3176 days ago
> 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.
1 comments
dwringer 3176 days ago
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.

link
ScottBurson 3176 days ago
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

link