[Cacti]

Yep. The original wave of genetic algorithms largely depended on some hand-wavy "building block" ideas that no one could really prove. It turned out that it was because proving them is impossible in the general sense, as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all.

So I was surprised to see them make a return about a decade later. Hopefully there is a little more rigor this time around.

[sampo]

> as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all.

NFL theorems are, should I say, purely theoretical and provide no insight on real-world problems. Say we try to find a function that is an optimal solution to something. NFL theorems consider the space of all possible functions, the overwhelming majority of which are discontinuous. Whereas real life problems tend to have functions that are at least more or less continuous.

[letitgo12345]

Not just discontinuous but have high Kolmogorov complexity (effectively meaning that the value of the objective function is random and has no real relation to the input arguments) so not a surprise that you can't do better than random!

Honestly, there's no justification to be using NFL theorems to explain why we can't optimize well on real world tasks.

Edit: And such high Kolmogorov complexity function constitute most possible objective functions -- i.e. exponentially more than the number of objective functions that don't have high Kolmogorov complexity. And all real world objective functions have comparatively low Kolmogorov complexity.

[sampo]

Good notion, pointing the Kolmogorov complexity.

Yeah. You have a function, so basically a long array of numbers, and you want to find the maximum. If the data in the array has some structure, like it's sampled from a sine wave or something, you can use some strategies to find the maximum. Like gradient descent, or binary search. Something.

But if the array is filled with random numbers, looking at other arrays elements give absolutely no hint on what might be in an array element you haven't yet looked at. So there doesn't exist any more efficient strategies to find the maximum number, than linear or random search.

And the space of all possible functions mostly consists of discontinuous functions that are, for all purposes, just samples of random noise.

This is all NFL theorems say. I really don't understand how they got be such a big deal.

[dorgo]

>So there doesn't exist any more efficient strategies to find the maximum number, than linear or random search.

For classic old school computers yes. I'm not so sure about quantum computers. Consider: https://en.wikipedia.org/wiki/Grover%27s_algorithm

[guest12268]

I don't think Grover ("the other GA") helps us here. https://qbnets.wordpress.com/2010/01/06/grovers-algorithm-fo...

[Cacti]

I hear this sentiment a lot lately, and I do not agree with it at all, you're basically just hand-waving the issue away and retroactively deciding what is a real world, practical problem or not after we've already found a solution to those problems. The NFL theorems are not inherently worthless, you are making them worthless because you are throwing away nearly all of the possible problem space, under the assumption that space is not relevant, but that is just a guess, you don't actually know.

I mean, yeah, sure, not knowing if we've hit the global minimum on some optimization problem may not matter as humans, because no one gives a damn, but that is a completely arbitrary line, not a mathematical one. Too often I hear people say "well, NFL is irrelevant" as an argument for why they are mathematically correct, or why their results are mathematically significant, and that's simply a load of crap. Maybe you're right, maybe you're wrong, but you're basically just throwing darts at a dartboard.

[jmmcd]

> make a return about a decade later.

Maybe that is how it looked from the outside. But the field continued as normal with no major problems, solving lots of industry problems with little hype.