Skip to main content
A No-free-lunch Framework for Coevolution
Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation
  • Travis Service
  • Daniel R. Tauritz, Missouri University of Science and Technology

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.

Computer Science
Keywords and Phrases
  • No Free Lunch,
  • Solution Concept,
  • Theory,
  • Coevolution
Document Type
Article - Conference proceedings
Document Version
File Type
© 2008 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
Citation Information
Travis Service and Daniel R. Tauritz. "A No-free-lunch Framework for Coevolution" Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (2008)
Available at: