Algorithms for Test-Based Problems
Wojciech Ja±kowski · 2011
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 Bril-