A No-free-lunch Framework for Coevolution

The No-Free-Lunch theorem is a fundamental result in the field of black-box function optimization. Recent work has shown that coevolution can exhibit free lunches. The question as to which classes of coevolution exhibit free lunches is still open. In this paper we present a novel framework for analyzing No-Free-Lunch like results for classes of coevolutionary algorithms. Our framework has the advantage of analyzing No-Free-Lunch like inquiries in terms of solution concepts and isomorphisms on the weak preference relation on solution configurations. This allows coevolutionary algorithms to be naturally classified by the type of solution they seek. Using the weak preference relation also permits us to present a simpler definition of performance metrics than that used in previous coevolutionary No-Free-Lunch work, more akin to the definition used in the original No-Free-Lunch theorem. The framework presented in this paper can be viewed as the combination of the ideas and definitions from two separate theoretical frameworks for analyzing search algorithms and coevolution consistent with the terminology of both. We also present a new instance of free lunches in coevolution which demonstrates the applicability of our framework to analyzing coevolutionary algorithms based upon the solution concept which they implement