Online Discovery of Search Objectives for Test-Based Problems
- 1 September 2017
- journal article
- Published by MIT Press in Evolutionary Computation
- Vol. 25 (3) , 375-406
Abstract
In test-based problems, commonly approached with competitive coevolutionary algorithms, the fitness of a candidate solution is determined by the outcomes of its interactions with multiple tests. Usually, fitness is a scalar aggregate of interaction outcomes, and as such imposes a complete order on the candidate solutions. However, passing different tests may require unrelated “skills,” and candidate solutions may vary with respect to such capabilities. In this study, we provide theoretical evidence that scalar fitness, inherently incapable of capturing such differences, is likely to lead to premature convergence. To mitigate this problem, we propose disco, a method that automatically identifies the groups of tests for which the candidate solutions behave similarly and define the above skills. Each such group gives rise to a derived objective, and these objectives together guide the search algorithm in multi-objective fashion. When applied to several well-known test-based problems, the proposed approach significantly outperforms the conventional two-population coevolution. This opens the door to efficient and generic countermeasures to premature convergence for both coevolutionary and evolutionary algorithms applied to problems featuring aggregating fitness functions.Keywords
This publication has 48 references indexed in Scilit:
- A Monotonic Archive for Pareto-CoevolutionEvolutionary Computation, 2007
- Nonlinear System Identification Using Coevolution of Models and TestsIEEE Transactions on Evolutionary Computation, 2005
- Ideal Evaluation from CoevolutionEvolutionary Computation, 2004
- Evolving an expert checkers playing program without using human expertiseIEEE Transactions on Evolutionary Computation, 2001
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Learning and the Theory of GamesJournal of Theoretical Biology, 2000
- Evaluation of a simple host-parasite genetic algorithm1998
- The Evolution of Degrees of CooperationJournal of Theoretical Biology, 1996
- Survey Article: Cooperate or Defect? Russian and American Students in a Prisoner's DilemmaComparative Economic Studies, 1994
- Searching for Diverse, Cooperative Populations with Genetic AlgorithmsEvolutionary Computation, 1993