Ideal Evaluation from Coevolution
- 1 June 2004
- journal article
- Published by MIT Press in Evolutionary Computation
- Vol. 12 (2) , 159-192
Abstract
In many problems of interest, performance can be evaluated using tests, such as examples in concept learning, test points in function approximation, and opponents in game-playing. Evaluation on all tests is often infeasible. Identification of an accurate evaluation or fitness function is a difficult problem in itself, and approximations are likely to introduce human biases into the search process. Coevolution evolves the set of tests used for evaluation, but has so far often led to inaccurate evaluation. We show that for any set of learners, a Complete Evaluation Set can be determined that provides ideal evaluation as specified by Evolutionary Multi-Objective Optimization. This provides a principled approach to evaluation in coevolution, and thereby brings automatic ideal evaluation within reach. The Complete Evaluation Set is of manageable size, and progress towards it can be accurately measured. Based on this observation, an algorithm named DELPHI is developed. The algorithm is tested on problems likely to permit progress on only a subset of the underlying objectives. Where all comparison methods result in overspecialization, the proposed method and a variant achieve sustained progress in all underlying objectives. These findings demonstrate that ideal evaluation may be approximated by practical algorithms, and that accurate evaluation for test-based problems is possible even when the underlying objectives of a problem are unknown.Keywords
This publication has 22 references indexed in Scilit:
- Combining Convergence and Diversity in Evolutionary Multiobjective OptimizationEvolutionary Computation, 2002
- Coevolving functions in genetic programmingJournal of Systems Architecture, 2001
- On coevolutionary genetic algorithmsSoft Computing, 2001
- An updated survey of GA-based multiobjective optimization techniquesACM Computing Surveys, 2000
- The coevolution of automata in the repeated Prisoner's DilemmaJournal of Economic Behavior & Organization, 1996
- An Overview of Evolutionary Algorithms in Multiobjective OptimizationEvolutionary Computation, 1995
- Toward an ideal trainerMachine Learning, 1994
- Co-evolving parasites improve simulated evolution as an optimization procedurePhysica D: Nonlinear Phenomena, 1990
- Numerical testing of evolution theoriesActa Biotheoretica, 1963
- Numerical testing of evolution theoriesActa Biotheoretica, 1962