Problems in which some elementary entities interact with each other are common in computational intelligence. This scenario, typical for co-evolving artificial-life agents, learning strategies for games, and machine learning from examples, can be formalized as test-based problem and conveniently embedded in the common conceptual framework of coevolution. In test-based problems candidate solutions are evaluated on a number of test cases (agents, opponents, examples). It has been recently shown that every test of such problem can be regarded as a separate objective, and the whole problem as a multi-objective optimization. Research on reducing the number of objectives while preserving the relations between candidate solutions and tests led to the notions of underlying objectives and internal problem structure, which can be formalized as coordinate system that spatially arranges candidate solutions and tests. The coordinate system that spans the minimal number of axes determines the so-called dimension of a problem and, being an inherent property of every problem, is of particular interest. In this study, we investigate in-depth the formalism of coordinate system and its properties, relate them to properties of partially ordered sets, and design an exact algorithm for finding a minimal coordinate system. We also prove that this problem is NP-hard and come up with a heuristic which is superior to the best algorithm proposed so far. Finally, we apply the algorithms to three abstract problems and demonstrate that the dimension of the problem is typically much lower than the number of tests, and for some problems converges to the intrinsic parameter of the problem -- its a priori dimension. #2012jaskowskiECJBib
@ARTICLE { 2012jaskowskiECJ,
ABSTRACT = { Problems in which some elementary entities interact with each other are common in computational intelligence. This scenario, typical for co-evolving artificial-life agents, learning strategies for games, and machine learning from examples, can be formalized as test-based problem and conveniently embedded in the common conceptual framework of coevolution. In test-based problems candidate solutions are evaluated on a number of test cases (agents, opponents, examples). It has been recently shown that every test of such problem can be regarded as a separate objective, and the whole problem as a multi-objective optimization. Research on reducing the number of objectives while preserving the relations between candidate solutions and tests led to the notions of underlying objectives and internal problem structure, which can be formalized as coordinate system that spatially arranges candidate solutions and tests. The coordinate system that spans the minimal number of axes determines the so-called dimension of a problem and, being an inherent property of every problem, is of particular interest. In this study, we investigate in-depth the formalism of coordinate system and its properties, relate them to properties of partially ordered sets, and design an exact algorithm for finding a minimal coordinate system. We also prove that this problem is NP-hard and come up with a heuristic which is superior to the best algorithm proposed so far. Finally, we apply the algorithms to three abstract problems and demonstrate that the dimension of the problem is typically much lower than the number of tests, and for some problems converges to the intrinsic parameter of the problem -- its a priori dimension. },
ANNOTE = { doi: 10.1162/EVCO{\_}a{\_}00046 },
AUTHOR = { Ja{\'s}kowski, Wojciech and Krawiec, Krzysztof },
BOOKTITLE = { Evolutionary Computation },
DA = { 2011/12/01 },
DATE = { 2011/08/04 },
ADDED = { 2012-04-02 10:13:47 +0200 },
MODIFIED = { 2012-04-02 10:13:47 +0200 },
DOI = { 10.1162/EVCO{\_}a{\_}00046 },
ISBN = { 1063-6560 },
JOURNAL = { Evolutionary Computation },
JOURNAL1 = { Evolutionary Computation },
M3 = { doi: 10.1162/EVCO{\_}a{\_}00046 },
MONTH = { Apr },
NUMBER = { 4 },
PAGES = { 639--671 },
PUBLISHER = { MIT Press },
TITLE = { Formal Analysis, Hardness, and Algorithms for Extracting Internal Structure of Test-Based Problems },
TY = { JOUR },
URL = { http://dx.doi.org/10.1162/EVCO_a_00046 },
VOLUME = { 19 },
YEAR = { 2011 },
YEAR1 = { 2011 },
1 = { http://dx.doi.org/10.1162/EVCO_a_00046 },
2 = { http://dx.doi.org/10.1162/EVCO%7B%5C_%7Da%7B%5C_%7D00046 },
}