A No-free-lunch Framework for Coevolution
Abstract
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.
Recommended Citation
T. Service and D. R. Tauritz, "A No-free-lunch Framework for Coevolution," Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, Association for Computing Machinery (ACM), Jul 2008.
The definitive version is available at https://doi.org/10.1145/1389095.1389163
Department(s)
Computer Science
Keywords and Phrases
No Free Lunch; Solution Concept; Theory; Coevolution
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2008 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
01 Jul 2008
