In test-based problems, commonly solved with competitive coevolutionalgorithms, candidate solutions (e.g., game strategies) are evaluatedby interacting with tests (e.g., opponents). As the number of testsis typically large, it is expensive to calculate the exact value ofobjective function, and one has to elicit a useful training signal(search gradient) from the outcomes of a limited number of interactionsbetween these coevolving entities. Averaging of interaction outcomes,typically used to that aim, ignores the fact that solutions oftenhave to master different and unrelated skills, which form underlyingobjectives of the problem. We propose a method for on-line discoveryof such objectives via heuristic compression of interaction outcomes.The compressed matrix implicitly defines derived search objectivesthat can be used by traditional multiobjective search techniques(NSGA-II in this study). When applied to the challenging variant ofmulti-choice Iterated Prisoner's Dilemma problem, the proposed approachoutperforms conventional two-population coevolution in a statisticallysignificant way.

`@INPROCEEDINGS { LNCS86720611,`

EDITOR = { Thomas Bartz-Beielstein and J\"{u}rgen Branke and Bogdan Filipi\v{c} and Jim Smith },

BOOKTITLE = { Parallel Problem Solving from Nature -- PPSN XIII },

PUBLISHER = { Springer },

LOCATION = { Heidelberg },

SERIES = { Lecture Notes in Computer Science },

VOLUME = { 8672 },

YEAR = { 2014 },

ISBN = { 978-3-319-10761-5 },

DOI = { 10.1007/978-3-319-10762-2_60 },

AUTHOR = { Pawe{\l} Liskowski and Krzysztof Krawiec },

TITLE = { Discovery of Implicit Objectives by Compression of Interaction Matrix in Test-Based Problems },

PAGES = { 611--620 },

ABSTRACT = { In test-based problems, commonly solved with competitive coevolutionalgorithms, candidate solutions (e.g., game strategies) are evaluatedby interacting with tests (e.g., opponents). As the number of testsis typically large, it is expensive to calculate the exact value ofobjective function, and one has to elicit a useful training signal(search gradient) from the outcomes of a limited number of interactionsbetween these coevolving entities. Averaging of interaction outcomes,typically used to that aim, ignores the fact that solutions oftenhave to master different and unrelated skills, which form underlyingobjectives of the problem. We propose a method for on-line discoveryof such objectives via heuristic compression of interaction outcomes.The compressed matrix implicitly defines derived search objectivesthat can be used by traditional multiobjective search techniques(NSGA-II in this study). When applied to the challenging variant ofmulti-choice Iterated Prisoner's Dilemma problem, the proposed approachoutperforms conventional two-population coevolution in a statisticallysignificant way. },

}