@PhdThesis{Jaskowski2011algorithms,
  Title                    = {Algorithms for Test-Based Problems},
  Author                   = {Wojciech Jaśkowski},
  School                   = {Institute of Computing Science, Poznan University of Technology},
  Year                     = {2011},

  Address                  = {Poznań, Poland},
  Note                     = {Adviser: Krzysztof Krawiec},

  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 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 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 behavior is the aggregation of results of interactions between individuals representing candidate solutions and tests, which typically leads to characterizing 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. Fitnessless 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 behavioral patterns observed in its strategy. 
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 optimization 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.},
  Url                      = {http://www.cs.put.poznan.pl/wjaskowski/pub/papers/jaskowski11algorithms.pdf}
}