Discovery of Implicit Objectives by Compression of Interaction Matrix in Test-Based Problems
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
2014
paper
english
- test-based problems
- coevolution
- iterated prisoner dilemma
- multiobjective evolutionary algorithms
EN In test-based problems, commonly solved with competitive coevolution algorithms, candidate solutions (e.g., game strategies) are evaluated by interacting with tests (e.g., opponents). As the number of tests is typically large, it is expensive to calculate the exact value of objective function, and one has to elicit a useful training signal (search gradient) from the outcomes of a limited number of interactions between these coevolving entities. Averaging of interaction outcomes, typically used to that aim, ignores the fact that solutions often have to master different and unrelated skills, which form underlying objectives of the problem. We propose a method for on-line discovery of such objectives via heuristic compression of interaction outcomes. The compressed matrix implicitly defines derived search objectives that can be used by traditional multiobjective search techniques (NSGA-II in this study). When applied to the challenging variant of multi-choice Iterated Prisoner’s Dilemma problem, the proposed approach outperforms conventional two-population coevolution in a statistically significant way.
611 - 620
WoS (15)