Algorithms for Test-Based Problems

Created by W.Langdon from gp-bibliography.bib Revision:1.4549

  author =       "Wojciech Jaskowski",
  title =        "Algorithms for Test-Based Problems",
  school =       "Institute of Computing Science, Poznan University of
  year =         "2011",
  address =      "Poznan, Poland",
  month =        may,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  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",

Genetic Programming entries for Wojciech Jaskowski