The no free lunch theorem states that, the performance of any two search algorithms are equivalent when averaged across all possible problems. This fails to hol

The no free lunch theorem states that, the performance of any two search algorithms are equivalent when averaged across all possible problems. This fails to hold in coevolutionary settings - selecting a champion through self play. In such cases there will be pairs of algorithms where one is demonstrably better than the other for all possible problems; a free lunch by criteria of the NFL theorem [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.2425&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100... ; also worth checking out: http://www.santafe.edu/media/workingpapers/12-10-017.pdf http://www.santafe.edu/media/workingpapers/12-10-017.pdf]. The No Free Lunch Theorem is also one of those limit statements that rarely impinges on reality. We are not interested in all possible functions - the majority of which will be of such complexity as to be indistinguishable from random - only those with exploitable structure. It's much the same reason for why, although kmeans is NP-hard, failing to find a good clustering is very often suggestive of an ill-posed problem with no interesting structure. If kmeans didn't find a good cluster, very possibly a good one does not exist (e.g. Clustering is difficult only when it does not matter; http://arxiv.org/abs/1205.4891 http://arxiv.org/abs/1205.4891)