Free Lunches in Pareto Coevolution
Recent work in test based coevolution has focused on employing ideas from multi-objective optimization in coevolutionary domains. So called Pareto coevolution treats the coevolving set of test cases as objectives to be optimized in the sense of multi-objective optimization. Pareto coevolution can be seen as a relaxation of traditional multi-objective evolutionary optimization. Rather than being forced to determine the outcome of a particular individual on every objective, pareto coevolution allows the examination of an individual's outcome on a particular objective. By introducing the notion of certifying pareto dominance and mutual non-dominance, this paper proves for the first time that free lunches exist for the class of pareto coevolutionary optimization problems. This theoretical result is of particular interest because we explicitly provide an algorithm for pareto coevolution which has better performance, on average, than all traditional multi-objective algorithms in the relaxed setting of pareto coevolution. The notion of certificates of preference/non-preference has potential implications for coevolutionary algorithm design in many classes of coevolution as well as for general multi-objective optimization in the relaxed setting of pareto coevolution.
T. C. Service and D. R. Tauritz, "Free Lunches in Pareto Coevolution," Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, pp. 1721-1727, Association for Computing Machinery (ACM), Jan 2009.
The definitive version is available at http://dx.doi.org/10.1145/1569901.1570132
11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009 (2009: Jul. 8-12, Montreal, Quebec, Canada)
Keywords and Phrases
Multi-Objective Optimization; No Free Lunch; Pareto Coevolution
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2009 Association for Computing Machinery (ACM), All rights reserved.