- author = "Wojciech Jaskowski",
- title = "Algorithms for Test-Based Problems",
- school = "Institute of Computing Science, Poznan University of Technology",
- year = "2011",
- address = "Poznan, Poland",
- month = may,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.put.poznan.pl/wjaskowski/pub/papers/jaskowski11algorithms.pdf",
- size = "193 pages",
-
abstract = "Problems in which some elementary entities interact
with each other are common in computational
intelligence. This scenario, typical for coevolving
artificial-life agents, learning strategies for games,
and machine learning from examples, can be formalised
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 such as agents, opponents or
examples. Although coevolutionary algorithms proved
successful in some applications, they also turned out
to have hard to predict dynamics and fail to sustain
progress during a run, thus being unable to obtain
competitive solutions for many test-based problems.
It has been recently shown that one of the reasons why coevolutionary algorithms demonstrate such undesired behaviour is the aggregation of results of interactions between individuals representing candidate solutions and tests, which typically leads to characterising the performance of an individual by a single scalar value. In order to remedy this situation, in the thesis, we make an attempt to get around the problem of aggregation using two methods.
First, we introduce Fitnessless Coevolution, a method for symmetrical test-based problems. Fitness-less Coevolution plays games between individuals to settle tournaments in the selection phase and skips the typical phase of evaluation and the aggregation of results connected with it. The selection operator applies a single-elimination tournament to a randomly drawn group of individuals, and the winner of the final round becomes the result of selection. Therefore, Fitnessless Coevolution does not involve explicit fitness measure and no aggregation of interaction results is required. We prove that, under a condition of transitivity of the payoff matrix, the dynamics of Fitnessless Coevolution is identical to that of the traditional evolutionary algorithm. The experimental results, obtained on a diversified group of problems, demonstrate that Fitnessless Coevolution is able to produce solutions that are equally good or better than solutions obtained using fitness-based one-population coevolution with different selection methods. In a case study, we provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. We detail the coevolutionary setup that lead to BrilliAnt's emergence, assess its direct and indirect human-competitiveness, and describe the behavioural patterns observed in its strategy.",
-
abstract = "Second, we study the consequences of the fact that the
problem of aggregation of interaction results may be
got around by regarding every test of a test-based
problem as a separate objective, and the whole problem
as a multi-objective optimisation task. 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 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 test-based problem, is of particular interest.
We investigate in-depth the formalism of coordinate
system and its properties, relate them to the
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 several benchmark problems to demonstrate
that the dimension of a problem is typically much lower
than the number of tests. Our work suggest that for at
least some classes of test-based problems, the
dimension of a problem may be proportional to the
logarithm of number of tests.
Based on the above-described theoretical results, we propose a novel coevolutionary archive method founded on the concept of coordinate systems, called Coordinate System Archive (COSA), and compare it to two state-of-the-art archive methods, IPCA and LAPCA. Using two different objective performance measures, we find out that COSA is superior to these methods on a class of artificial test-based problems.",
- notes = "Adviser: Krzysztof Krawiec",
