| Formal Analysis, Hardness and Algorithms for Extracting Internal Structure of Test-Based Problems. | |
| | |
MedLine Citation:
|
PMID: 21815770 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
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 a 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 multi-objective optimization. Research on reducing the number of such 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 a 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. |
| | |
Authors:
|
Wojciech Jaśkowski; Krzysztof Krawiec |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-8-4 |
Journal Detail:
|
Title: Evolutionary computation Volume: - ISSN: 1530-9304 ISO Abbreviation: - Publication Date: 2011 Aug |
Date Detail:
|
Created Date: 2011-8-5 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9513581 Medline TA: Evol Comput Country: - |
Other Details:
|
Languages: ENG Pagination: - Citation Subset: - |
Affiliation:
|
Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60965 Poznań, Poland. wjaskowski@cs.put.poznan.pl. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Motif Difficulty (MD): A Predictive Measure of Problem Difficulty for Evolutionary Algorithms using ...
Next Document: Dietary Supplementation with an Extract of North American Ginseng in Adult and Juvenile Mice Increas...