Conservation of Information in Coevolutionary Searches

A number of papers show that the No Free Lunch theorem does not apply to coevolutionary search. This has been interpreted as meaning that, unlike classical full query searches, coevolutionary searches do not require extensive a priori knowledge about the domain. Alternately, coevolutionary searches can be viewed as providing incomplete information about fitness and differ from standard evolutionary searches where queries provide full fitness information. Knowing the full value of a fitness is better than knowing partial subjacent fitness information. Consequently, coevolution can be viewed as a degradation of search performance in this sense. We demonstrate this in a number of examples drawn from free lunch proofs in the literature. This observation does not diminish the power or utility of the coevolutionary search. Coevolutionary subjacent queries are often required due to the unavailability or expense of a full query. Nevertheless, coevolution does not allow an escape from the necessity of exploiting prior information in search processes and remains bounded by conservation of information in general and the No Free Lunch theorem in particular.