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.

Co-optimization test-based problems is a class of tasks approached typically with coevolutionary algorithms. It was recently shown that such problems exhibit underlying objectives that form internal problem structure, which can be extracted and analyzed in order to drive the search or design better algorithms. The number of underlying objectives is the dimension of the problem, which is of great importance, since it may be a predictor of problem's difficulty. In this paper, we estimate the number of dimensions for Tic Tac Toe and the Density Classification Task.

Hybridization of global and local search techniques has already produced promising results in the fields of optimization and machine learning. It is commonly presumed that approaches employing this idea, like memetic algorithms that combine evolutionary algorithms with local search, benefit from complementary characteristics of constituent methods and maintain the right balance between exploration and exploitation of the search space. While such extensions of evolutionary algorithms have been intensively studied, hybrids of local search with coevolutionary algorithms have not received much attention yet. In this paper we attempt to fill this gap by presenting Coevolutionary Temporal Difference Learning (CTDL) that works by interlacing global search provided by competitive coevolution and local search by means of temporal difference learning. We verify CTDL by applying it to the board game of Othello, where it learns board evaluation functions represented by a linear architecture of weighted piece counter. The results of a computational experiment show CTDL’s superiority when compared to coevolutionary algorithm and temporal difference learning alone, both in terms of performance of elaborated strategies and computational cost. In order to further exploit CTDL’s potential, we also extend it by an archive that keeps track of selected well-performing solutions found so far and uses them to improve search convergence. The overall conclusion is that the fusion of various forms of coevolution with a gradient-based local search can be highly beneficial and deserves further research.

We apply Coevolutionary Temporal Difference Learning (CTDL) to learn small-board Go strategies represented as weighted piece counters. CTDL is a randomized learning technique which interleaves two search processes that operate in intra-game and inter-game mode. The intra-game learning is driven by gradient-descent Temporal Difference Learning (TDL), a reinforcement learning method that updates the board evaluation function according to differences observed between its values for consecutively visited game states. For the inter-game learning component, we provide coevolutionary algorithm that maintains a sample of strategies and uses the outcomes of games played between them to iteratively modify the probability distribution, according to which new strategies are generated and added to the sample. We analyze CTDL’s sensitivity to all important parameters, including the trace decay constant that controls the lookahead horizon of TDL, and the relative intensity of intra-game and inter-game learning. We investigate also how the presence of memory (an archive) affects the search performance, and find out that the archived approach is superior to other techniques considered here, and produces strategies that outperform a handcrafted weighted piece counter strategy and a simple liberty-based heuristics. This encouraging result can be potentially generalized not only to other strategy representations used for small-board Go, but also to different games and a broader class of problems, because CTDL is generic and does not rely on any problem-specific knowledge.

Problems in which some 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 test-based problem. In test-based problems, candidate solutions are evaluated on a number of test cases (agents, opponents, examples). It has been recently shown that at least some of such problems posses underlying problem structure, which can be formalized in a notion of coordinate system, which spatially arranges candidate solutions and tests in a multidimensional space. Such a coordinate system can be extracted to reveal underlying objectives of the problem, which can be then further exploited to help coevolutionary algorithm make progress. In this study, we propose a novel coevolutionary archive method, called Coordinate System Archive (COSA) that is based on these concepts. In the experimental part, we compare COSA 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 problems (compare-on-one).

We apply gene expression programing to evolve a player for a real-time strategy (RTS) video game. The paper describes the game, evolutionary encoding of strategies and the technical implementation of experimental framework. In the experimental part, we compare two setups that differ with respect to the used approach of task decomposition. One of the setups turns out to be able to evolve an effective strategy, while the other leads to more sophisticated yet inferior solutions. We discuss both the quantitative results and the behavioral patterns observed in the evolved strategies.

This paper presents Coevolutionary Temporal Difference Learning (CTDL), a novel way of hybridizing coevolutionary search with reinforcement learning that works by interlacing one-population competitive coevolution with temporal difference learning. The coevolutionary part of the algorithm provides for exploration of the solution space, while the temporal difference learning performs its exploitation by local search. We apply CTDL to the board game of Othello, using weighted piece counter for representing players’ strategies. The results of an extensive computational experiment demonstrate CTDL’s superiority when compared to coevolution and reinforcement learning alone, particularly when coevolution maintains an archive to provide historical progress. The paper investigates the role of the relative intensity of coevolutionary search and temporal difference search, which turns out to be an essential parameter. The formulation of CTDL leads also to the introduction of Lamarckian form of coevolution, which we discuss in detail.

We propose a novel method of evolutionary visual learning that uses a generative approach to assess the learner’s ability to recognize image contents. Each learner, implemented as a genetic programming (GP) individual, processes visual primitives that represent local salient features derived from the input image. The learner analyzes the visual primitives, which involves mostly their grouping and selection, eventually producing a hierarchy of visual primitives build upon the input image. Based on that, it provides partial reproduction of the shapes of the analyzed objects and is evaluated according to the quality of that reproduction. We present the method in detail and verify it experimentally on the real-world task of recognition of hand-drawn shapes. In particular, we show how GP individuals trained on examples from different decision classes can be combined to build a complete multiclass recognition system.We compare such recognition systems to reference methods, showing that our generative learning approach provides similar results. The chapter contains also detailed analysis of processing carried out by an exemplary individual.

A two-player game given in the normal form of payoff matrix may be alternatively viewed as a list of the outcomes of binary interactions between two sets of entities, solutions and tests. The internal structure of such interactions may be characterized by an appropriately constructed coordinate system, which spatially arranges the solutions with respect to coordinates identified with tests, while preserving their mutual relations as given by the matrix. Of particular interest are coordinate systems of minimal size that give rise to the notion of dimension of a game. Following [1], we investigate such coordinate systems and relate their features to properties of partially ordered sets (posets), mostly to poset width and poset dimension. We propose an exact algorithm for constructing a minimal correct coordinate system and prove its correctness. In the experimental part, we compare the exact algorithm to the heuristics proposed in [1] on a sample of random payoff matrices of different sizes to demonstrate that the heuristics heavily overestimates the size of the minimal coordinate system. Finally, we show how the game dimension relate to the a priori dimension of a game.

We propose a method of knowledge reuse between evolutionary processes that solve different optimization tasks. We define the method in the framework of tree-based genetic programming (GP) and implement it as code reuse between GP trees that evolve in parallel in separate populations delegated to particular tasks. The technical means of code reuse is a crossbreeding operator which works very similar to standard tree-swapping crossover. We consider two variants of this operator, which differ in the way they handle the incompatibility of terminals between the considered problems. In the experimental part we demonstrate that such code reuse is usually benefficial and leads to success rate improvements when solving the common boolean benchmarks.

We tell the story of BrilliAnt, the winner of the Ant Wars contest organized within GECCO'2007, Genetic and Evolutionary Computation Conference. The task for the Ant Wars contestants was to evolve a controller for a virtual ant that collects food in a square toroidal grid environment in the presence of a competing ant. BrilliAnt, submitted to the contest by our team, has been evolved through competitive one-population coevolution using genetic programming and a novel fitnessless selection method. In the paper, we detail the evolutionary setup that lead to BrilliAnt's emergence, assess its human-competitiveness, and describe selected behavioral patterns observed in its strategy.

NeuroHunter is the name of an evolved neural network that won the GECCO'2008 Balanced Diet contest, organized within GECCO'2008, Genetic and Evolutionary Computation Conference, in Atlanta, Georgia. The goal was to evolve a controller for a virtual agent that collects two types of food in a 256x256 board, trying to maximize the amount of food collected while minimizing the imbalance between the two types of food. The major difficulty of the task consists in partial observability: the agent cannot see the food pieces. However, the probability of finding a food piece of particular type at a particular location depends on another feature, elevation, which is visible to the agent. Thus, the agent has to learn this dependency, also avoiding revisiting the same locations. Our winner entry used the HyperNEAT by Stanley et al., an evolved structural neural net. The report describes in detail the method, technology, and the results.

We propose a multitask learning method of visual concepts within the genetic programming (GP) framework. Each GP individual is composed of several trees that process visual primitives derived from input images. Two trees solve two different visual tasks and are allowed to share knowledge with each other by commonly calling the remaining GP trees (subfunctions) included in the same individual. The performance of a particular tree is measured by its ability to reproduce the shapes contained in the training images. We apply this method to visual learning tasks of recognizing simple shapes and compare it to a reference method. The experimental verification demonstrates that such multitask learning often leads to performance improvements in one or both solved tasks, without extra computational effort.

Abstract We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence of a competing ant. BrilliAnt has been evolved through a competitive one-population coevolution using genetic programming and fitnessless selection. In this paper, we detail the evolutionary setup that lead to BrilliAnt's emergence, assess its direct and indirect human-competitiveness, and describe the behavioral patterns observed in its strategy.

In evolutionary algorithms, the typical post-processing phase involves selection of the best-of-run individual, which becomes the final outcome of the evolutionary run. Trivial for deterministic problems, this task can get computationally demanding in noisy environments. A typical naive procedure used in practice is to repeat the evaluation of each individual for the fixed number of times and select the one with the highest average. In this paper, we consider several algorithms that can adaptively choose individuals to evaluate basing on the results evaluations which have already been performed. The procedures are designed without any specific assumption about noise distribution. In the experimental part, we compare our algorithms with the naive and optimal procedures, and find out that the performance of typically used naive algorithm is poor even for relatively moderate noise. We also show that one of our algorithms is nearly optimal for most of the examined situations.

We introduce fitnessless coevolution (FC), a novel method of comparative one-population coevolution. FC plays games between individuals to settle tournaments in the selection phase and skips the typical phase of evaluation. 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, FC does not involve explicit fitness measure. We prove that, under a condition of transitivity of the payoff matrix, the dynamics of FC is identical to that of the traditional evolutionary algorithm. The experimental results, obtained on a diversified group of problems, demonstrate that FC is able to produce solutions that are equally good or better than solutions obtained using fitness-based one-population coevolution with different selection methods.

This work introduces a numerical, continuous measure of symmetry for 3D stick creatures and solid 3D objects. Background information about the property of symmetry is provided, and motivations to developing symmetry measure are described. Three approaches are mentioned, and two of them are presented in detail using a formal mathematical language. The best approach is used to sort a set of creatures according to their symmetry. Experiments with a mixed set of 84 individuals originating from both human design and evolution are performed to examine symmetry within these two sources, and to determine if human designers and evolutionary processes prefer symmetry or asymmetry.

We propose a learning algorithm that reuses knowledge acquired in past learning sessions to improve its performance on a new learning task. The method concerns visual learning and uses genetic programming to represent hypotheses, each of them being a procedure that processes visual primitives derived from the training images. The process of recognition is generative, i.e., a procedure is supposed to restore the shape of the processed object by drawing its reproduction on a separate canvas. This basic method is extended with a knowledge reuse mechanism that allows learners to import genetic material from hypotheses that evolved for the other decision classes (object classes). We compare both methods on a task of handwritten character recognition, and conclude that knowledge reuse leads to significant improvement of classification accuracy and reduces the risk of overfitting.

We propose a method of knowledge reuse for an ensemble of genetic programming-based learners solving a visual learning task. First, we introduce a visual learning method that uses genetic programming individuals to represent hypotheses. Individuals-hypotheses process image representation composed of visual primitives derived from the training images that contain objects to be recognized. The process of recognition is generative, i.e., an individual is supposed to restore the shape of the processed object by drawing its reproduction on a separate canvas. This canonical method is extended with a knowledge reuse mechanism that allows a learner to import genetic material from hypotheses that evolved for the other decision classes (object classes). We compare the performance of the extended approach to the basic method on a real-world tasks of handwritten character recognition, and conclude that knowledge reuse leads to significant convergence speedup and, more importantly, significantly reduces the risk of overfitting.

BriliANT is the name of a program that won the GECCO'2007 Ant Wars contest. Ant Wars was one of the competitions organized within GECCO'2007, Genetic and Evolutionary Computation Conference, in London, England, July 7-12, 2007. The goal was to evolve a controller for a virtual ant that collects food in a square toroidal grid environment in the presence of a competing ant. The report describes the method and technology we used to evolve BriliANT.

We consider multitask learning of visual concepts within genetic programming (GP) framework. The proposed method evolves a population of GP individuals, with each of them composed of several GP trees that process visual primitives derived from input images. The two main trees are delegated to solving two different visual tasks and are allowed to share knowledge with each other by calling the remaining GP trees (subfunctions) included in the same individual. The method is applied to the visual learning task of recognizing simple shapes, using generative approach based on visual primitives, introduced in [17]. We compare this approach to a reference method devoid of knowledge sharing, and conclude that in the worst case cross-task learning performs equally well, and in many cases it leads to significant performance improvements in one or both solved tasks.

We propose a method of knowledge reuse for an ensemble of genetic programming-based learners solving a visual learning task. First, we introduce a visual learning method that uses genetic programming individuals to represent hypotheses. Individuals-hypotheses process image representation composed of visual primitives derived from given training images that contain objects to be recognized. The process of recognition is generative, i.e., an individual is supposed to restore the shape of the processed object by drawing its reproduction on a separate canvas. This canonical method is in the following extended with a knowledge reuse mechanism that allows a learner to import genetic material from hypotheses that evolved for other decision classes (object classes). We compare the performance of the extended approach to the basic method on a real-world tasks of handwritten character recognition, and conclude that knowledge reuse leads to significant convergence speedup and reduces the risk of overfitting.

Analysis and prediction of three dimensional (3D) protein structure become one of the crucial task in science nowadays. Unfortunately, it is hard to identify one methodology which gives the best prediction of 3D protein structure for different protein sequences. Trying to solve this problem, the concept of metaserver has been introduced. In this paper, we propose a new metaserver method called 3D-Judge, which uses an artifficial neural network (ANN) to select the best model from among models produced by individual servers. This decision is made basing on the mutual similarities between models produced by the servers and the knowledge obtained during the training. ANN is trained on historical data, e.g.,models from CASP experiment. Here, we compare 3D-Judge with 3D-Jury that is a popular and effective metaserver method. The obtained results indicate that the 3D-Judge is competitive to 3D-Jury and, in some cases, outperformes it.

This thesis concentrates in the fields of computer vision, image understanding and machine learning. We present a novel approach for learning visual concepts from raw image data. Our method is able to learn new concepts and, in result, acquire knowledge that can be than used in standard computer vision tasks such as pattern recognition, object identification or object tracking. The acquired knowledge is encoded in a form of individuals/learners which are able to process visual information. The originality of this approach lies also in the fact that individuals do not process raw image data directly. Instead, they operate on a set of attributed visual primitives that are acquired from images in the preliminary stage of the processing. The proposed approach is very general, because it uses the learning principle. For the purpose of learning we use genetic programming. Each individual/learner represents a procedure in a form of a tree of operations on sets of visual primitives. The images from the training set in our approach are not labeled in any way and no information is assigned with them. It means that the knowledge is acquired in totally unsupervised way. The only feedback information that states which individual better represents the target concept from the training set is the measure how the individual is able to reconstruct the input image. The rational standing behind this approach is following. We believe that a visual concept can be proved to be acquired and understood only if it can be reconstructed and successfully compared with original image from it was previously learned. In the thesis we present our methodology in details and describe its exemplary implementation that is based on the concept of segment as visual primitive. The method is verified on several sets of shapes of simple objects such as triangles, sections, Y letters and others. We also elaborate a methodology of cross-task knowledge sharing that is a step towards modularization of knowledge and provide results of massive experiments with cross-task knowledge sharing. Finally, the most important design decisions of software environment that was developed as a platform for computational experiments with our approach are described. A particular emphasis is put on computational performance issues of the developed software.

This work summarizes various approaches to measuring symmetry of static and moving creatures. It outlines some problems with estimating symmetry of moving creatures: determination of the temporal direction of movement, aggregation of changing lifespan symmetry to a single value, and indeterminism of computer simulations.

Regardless of fast development of technology and human knowledge, year by year statistics of accident casualties in sparsely populated areas often visited by hikers, such as national parks and mountainous terrains, remain high. Existing safety precautions are clearly insufficient. Our research showed that there is currently no system operatingover a vast area that improves safety through fast and effective reaction to an emergency situation regardless of the type of the accident and capability of the user to call for help. As of now, lack of feedback from people under threat or those near them makes detecting emergencies virtually impossible. Numerous consultations, brainstorming sessions and a needs analysis led us to the idea of designing the system solving many of these problems - Lifetch. It is based on distributed personal units (we call them ICUs - Intelligent Communication Units - pronounced as "I see you") that we designed and built. They combine modules such as: a GPS receiver, a Radio Frequency (RF) transceiver and sensors that measure temperature, ambient light and acceleration. These lightweight units carried by people under protection of the Lifetch system communicate with each other over RF and exchange information gathered from the sources mentioned above. The ICUs periodically transmit their data to the Command Center using GSM/GPRS/UMTS (later denoted GPRS as the most practical choice) or, should it fail, the message passing system (ad-hoc network) working on a RF. The Command Center is the heart of our system and maintains its global status. It stores the information acquired from the ICUs in the database and processes it through several subsystems. The goal of these activities is to help the operator ensure the safety of the people protected by the system and automatize certain preventive safety-improving actions. In order to find out whether our project is viable, we decided on a real-life approach to establish the benefits that would come from introducing the Lifetch system. Our needs analysis was based on research of the archival materials of the Polish Mountain Rescue Organization. We selected over 200 mountain accident cases from the last 10 years. Over 80 of these cases included fatalities. The outcome of the analysis showed that in 71\% of these cases the effects of accidents could be minimized or even avoided if our system had been deployed. Improvements raising the safety level apply to the following matters: - Any person carrying an ICU can signal an emergency situation and request help even when there is no GSM network coverage. - Our system automatically discovers potentially dangerous situations such as people straying from the safe track and opens more possibilities to react to these situations. - Implementing intelligent position prediction algorithms, the system enables the park rangers to reduce substantially the time of locating a missing person, therefore increasing his/her chances of survival. - The system gives the possibility to monitor and analyze the traffic in national parks or other areas. This can become an important factor while making decisions concerning further safety improvements. It can also be useful for enhancing environment protection. - The system puts a strong emphasis on cooperation of a group of people. Group leader has full information about the status of his/her group, whereas a member can easily locate the group and find the right track even in difficult weather conditions. This can be particularly useful for groups of children on a class trip, tourists hiking with a guide, as well as for a team of rangers performing a rescue operation.