This work explores Liquid Time-Constant Networks (LTCs) and Closed-form Continuous-time Networks (CfCs) for modeling retinal ganglion cell activity in tiger salamanders across three datasets. Compared to a convolutional baseline and an LSTM, both architectures achieved lower MAE, faster convergence, smaller model sizes, and favorable query times, though with slightly lower Pearson correlation. Their efficiency and adaptability make them well suited for scenarios with limited data and frequent retraining, such as edge deployments in vision prosthetics.

This study introduces a neurosymbolic approach that performs iterative graph expansion guided by a graph neural network to solve symbolic regression problems. Empirical evaluation demonstrates superior performance of the method compared to baseline algorithms. We also integrate the method with an evolutionary algorithm, which results in further performance improvements.

This study presents and investigates abstract compositional transformers (ACTs), a class of deep learning (DL) architectures based on the transformer blueprint, designed to handle abstract reasoning tasks that require completing spatial visual patterns. We combine ACTs with choice-making modules and apply them to Raven progressive matrices (RPMs), logical puzzles that require selecting the correct image from the available answers. We devise a number of ACT variants, train them in several modes and with additional augmentations, subject them to ablations, demonstrate their data scalability, and analyze their behavior and latent representations that emerged in the process. Using self-supervision allows us to successfully train ACTs on relatively small training sets, mitigate several biases identified in RPMs in past studies, and achieve SotA results on the two most popular RPM benchmarks.

In symbolic regression with formal constraints, the conventional formulation of regression problem is extended with desired properties of the target model, like symmetry, monotonicity, or convexity. We present a genetic programming algorithm that solves such problems using a satisfiability modulo theories solver to formally verify the candidate solutions. The essence of the method consists in collecting the counterexamples resulting from model verification and using them to improve search guidance. The method is exact upon successful termination, the produced model is guaranteed to meet the specified constraints. We compare the effectiveness of the proposed method with standard constraint-agnostic machine learning regression algorithms on a range of benchmarks and demonstrate that it outperforms them on several performance indicators.

In optimization and machine learning, the divide between discrete and continuous problems and methods is deep and persistent. We attempt to remove this distinction by training neural network autoencoders that embed discrete candidate solutions in continuous latent spaces. This allows us to take advantage of state-of-the-art continuous optimization methods for solving discrete optimization problems, and mitigates certain challenges in discrete optimization, such as design of bias-free search operators. In the experimental part, we consider program synthesis as the special case of combinatorial optimization. We train an autoencoder network on a large sample of programs in a problem-agnostic, unsupervised manner, and then use it with an evolutionary continuous optimization algorithm (CMA-ES) to map the points from the latent space to programs. We propose also a variant in which semantically similar programs are more likely to have similar embeddings. Assessment on a range of benchmarks in two domains indicates the viability of this approach and the usefulness of involving program semantics.

In many applications of symbolic regression, domain knowledge constrains the space of admissible models by requiring them to have certain properties, like monotonicity, convexity, or symmetry. As only a handful of variants of genetic programming methods proposed to date can take such properties into account, we introduce a principled approach capable of synthesizing models that simultaneously match the provided training data (tests) and meet user-specified formal properties. To this end, we formalize the task of symbolic regression with formal constraints and present a range of formal properties that are common in practice. We also conduct a comparative experiment that confirms the feasibility of the proposed approach on a suite of realistic symbolic regression benchmarks extended with various formal properties. The study is summarized with discussion of results, properties of the method, and implications for symbolic regression.

Mathematical programming (MP) models are common in optimization of real-world processes. Models are usually built by optimization experts in an iterative manner: an imperfect model is continuously improved until it approximates the reality well-enough and meets all technical requirements (e.g., linearity). To facilitate this task, we propose a genetic one-class constraint synthesis method (GOCCS). Given a set of exemplary states of normal operation of a business process, GOCCS synthesizes constraints in linear programming or nonlinear programming form. The synthesized constraints can be then paired with an arbitrary objective function and supplied to an off-the-shelf solver to find optimal parameters of the process. We assess GOCCS on three families of MP benchmarks and conclude promising results. We also apply it to a real-world process of wine production and optimize that process.

When search operators in genetic programming (GP) insert new instructions into programs, they usually draw them uniformly from the available instruction set. Prefering some instructions to others would require additional domain knowledge, which is typically unavailable. However, it has been recently demonstrated that the likelihoods of instructions' occurrence in a program can be reasonably well estimated from its input-output behavior using a neural network. We exploit this idea to bias the choice of instructions used by search operators in GP. Given a large sample of programs and their input-output behaviors, a neural network is trained to predict the presence of individual instructions. When applied to a new program synthesis task, the network is first queried on the set of examples that define the task, and the obtained probabilities determine the frequencies of using instructions in initialization and mutation operators. This priming leads to significant improvements of the odds of successful synthesis on a range of benchmarks.

We propose Neural Estimation of Interaction Outcomes (NEIO), a method that reduces the number of required interactions between candidate solutions and tests in test-based problems. Given the outcomes of a random sample of all solution-test interactions, NEIO uses a neural network to predict the outcomes of remaining interactions and so estimate the fitness of programs. We apply NEIO to genetic programming (GP) problems, i.e. test-based problems in which candidate solutions are programs, while tests are examples of the desired input-output program behavior. In an empirical comparison to several reference methods on categorical GP benchmarks, NEIO attains the highest rank on the success rate of synthesizing correct programs.

Genetic programming is an effective technique for inductive synthesis of programs from tests, i.e. training examples of desired input-output behavior. Programs synthesized in this way are not guaranteed to generalize beyond the training set, which is unacceptable in many applications. We present Counterexample-Driven Genetic Programming (CDGP) that employs evolutionary search to synthesize provably correct programs from formal specifications. CDGP employs a Satisfiability Modulo Theories (SMT) solver to formally verify programs in the evaluation phase. A failed verification produces counterexamples that are in turn used to calculate fitness and thereby drive the search process. When compared with a range of approaches on a suite of state-of-the-art specification-based synthesis benchmarks, CDGP systematically outperforms them, typically synthesizing correct programs faster and using fewer tests.

Conventional genetic programming (GP) can guarantee only that synthesized programs pass tests given by the provided input-output examples. The alternative to such a test-based approach is synthesizing programs by formal specification, typically realized with exact, nonheuristic algorithms. In this article, we build on our earlier study on Counterexample-Based Genetic Programming (CDGP), an evolutionary heuristic that synthesizes programs from formal specifications. The candidate programs in CDGP undergo formal verification with a Satisfiability Modulo Theory (SMT) solver, which results in counterexamples that are subsequently turned into tests and used to calculate fitness. The original CDGP is extended here with a fitness threshold parameter that decides which programs should be verified, a more rigorous mechanism for turning counterexamples into tests, and other conceptual and technical improvements. We apply it to 24 benchmarks representing two domains: the linear integer arithmetic (LIA) and the string manipulation (SLIA) problems, showing that CDGP can reliably synthesize provably correct programs in both domains. We also confront it with two state-of-the art exact program synthesis methods and demonstrate that CDGP effectively trades longer synthesis time for smaller program size.

Program semantics is a promising recent research thread in Genetic Programming (GP). Over a dozen semantic-aware search, selection, and initialization operators for GP have been proposed to date. Some of these operators are designed to exploit the geometric properties of semantic space, while others focus on making offspring effective, that is, semantically different from their parents. Only a small fraction of previous works aimed at addressing both of these features simultaneously. In this article, we propose a suite of competent operators that combine effectiveness with geometry for population initialization, mate selection, mutation, and crossover. We present a theoretical rationale behind these operators and compare them experimentally to operators known from literature on symbolic regression and Boolean function synthesis benchmarks. We analyze each operator in isolation as well as verify how they fare together in an evolutionary run, concluding that the competent operators are superior on a wide range of performance indicators, including best-of-run fitness, test-set fitness, and program size.

Achieving a superhuman playing level by AlphaGo corroborated the capabilities of convolutional neural network (CNN) architectures for capturing complex spatial patterns. This result was, to a great extent, due to several analogies between Go board states and 2-D images that CNNs have been designed for, in particular, translational invariance and a relatively large board. In this paper, we verify whether CNN-based move predictors prove effective for Othello, a game with significantly different characteristics, including a much smaller board size and complete lack of translational invariance. We compare several CNN architectures and board encodings, augment them with state-of-the-art extensions, train on an extensive database of experts' moves, and examine them with respect to move prediction accuracy and playing strength. The empirical evaluation confirms high capabilities of neural move predictors and suggests a strong correlation between prediction accuracy and playing strength. The best CNNs not only surpass all other 1-ply Othello players proposed to date but defeat (2 ply) Edax, the best open-source Othello player.

Genetic programming is an effective technique for inductive synthesis of programs from training examples of desired input-output behavior (tests). Programs synthesized in this way are not guaranteed to generalize beyond the training set, which is unacceptable in many applications. We present Counterexample-Driven Genetic Programming (CDGP) that employs evolutionary search to synthesize provably correct programs from formal specifications. CDGP employs a Satisfiability Modulo Theories (SMT) solver to formally verify programs in the evaluation phase. A failed verification produces counterexamples that are in turn used to calculate fitness and so drive the search process. When compared against a range of approaches on a suite of state-of-the-art specification-based synthesis benchmarks, CDGP systematically outperforms them, typically synthesizing correct programs faster and using fewer tests.

In genetic programming (GP), the outcomes of the evaluation phase can be represented as an interaction matrix, with rows corresponding to programs in a population and columns corresponding to tests that define a program synthesis task. Recent contributions on Discovery of Objectives via Clustering (DOC) and Discovery of Objectives by Factorization of interaction matrix (DOF) show that informative characterizations of programs can be automatically derived from interaction matrices in discrete domains and used as search objectives in multidimensional setting. In this paper, we propose analogous methods for continuous domains and compare them with conventional GP that uses tournament selection, Age-Fitness Pareto Optimization, and GP with epsilon-lexicase selection. Experiments show that the proposed methods are effective for symbolic regression, systematically producing better-fitting models than the two former baselines, and surpassing epsilon-lexicase selection on some problems. We also investigate the hybrids of the proposed approach with the baselines, concluding that hybridization of DOC with epsilon-lexicase leads to the best overall results.

Geometric Semantic Genetic Programming (GSGP) induces a unimodal fitness landscape for any problem that consists in finding a function fitting given input/output examples. Most of the work around GSGP to date has focused on real-world applications and on improving the originally proposed search operators, rather than on broadening its theoretical framework to new domains. We extend GSGP to recursive programs, a notoriously challenging domain with highly discontinuous fitness landscapes. We focus on programs that map variable-length Boolean lists to Boolean values, and design search operators that are provably efficient in the training phase and attain perfect generalization. Computational experiments complement the theory and demonstrate the superiority of the new operators to the conventional ones. This work provides new insights into the relations between program syntax and semantics, search operators and fitness landscapes, also for more general recursive domains.

In test-based problems, commonly approached with competitive coevolutionary algorithms, the fitness of a candidate solution is determined by the outcomes of its interactions with multiple tests. Usually, fitness is a scalar aggregate of interaction outcomes, and as such imposes a complete order on the candidate solutions. However, passing different tests may require unrelated "skills," and candidate solutions may vary with respect to such capabilities. In this study, we provide theoretical evidence that scalar fitness, inherently incapable of capturing such differences, is likely to lead to premature convergence. To mitigate this problem, we propose disco, a method that automatically identifies the groups of tests for which the candidate solutions behave similarly and define the above skills. Each such group gives rise to a derived objective, and these objectives together guide the search algorithm in multi-objective fashion. When applied to several well-known test-based problems, the proposed approach significantly outperforms the conventional two-population coevolution. This opens the door to efficient and generic countermeasures to premature convergence for both coevolutionary and evolutionary algorithms applied to problems featuring aggregating fitness functions.

In genetic programming (GP), the outcomes of the evaluation phase in an evolutionary loop can be represented as an interaction matrix, with rows corresponding to programs in a population, columns corresponding to tests that define a program synthesis task, and ones and zeroes signaling respectively passing a test and failing to do so. The conventional fitness, equivalent to a row sum in that matrix, only crudely reflects program's compliance with desired output, and recent contributions in semantic and behavioral GP point to alternative, multifaceted characterizations that facilitate navigation in the search space. In this paper, we propose DOF, a method that uses the popular machine learning technique of non-negative matrix factorization to heuristically derive a low number of underlying objectives from an interaction matrix. The resulting objectives redefine the original single-objective synthesis problem as a multiobjective optimization problem, and we posit that such characterization fosters diversification of search directions while maintaining useful search gradient. The comparative experiment conducted on 15 problems from discrete domains confirms this claim: DOF outperforms the conventional GP and GP equipped with an alternative method of derivation of search objectives on success rate and convergence speed.

The condition of the vascular network of human eye is an important diagnostic factor in ophthalmology. Its segmentation in fundus imaging is a nontrivial task due to variable size of vessels, relatively low contrast, and potential presence of pathologies like microaneurysms and hemorrhages. Many algorithms, both unsupervised and supervised, have been proposed for this purpose in the past. We propose a supervised segmentation technique that uses a deep neural network trained on a large (up to 400[Formula: see text]000) sample of examples preprocessed with global contrast normalization, zero-phase whitening, and augmented using geometric transformations and gamma corrections. Several variants of the method are considered, including structured prediction, where a network classifies multiple pixels simultaneously. When applied to standard benchmarks of fundus imaging, the DRIVE, STARE, and CHASE databases, the networks significantly outperform the previous algorithms on the area under ROC curve measure (up to > 0.99) and accuracy of classification (up to > 0.97 ). The method is also resistant to the phenomenon of central vessel reflex, sensitive in detection of fine vessels ( sensitivity > 0.87 ), and fares well on pathological cases.

We present an automated, end-to-end approach for Stage~1 breast cancer detection. The first phase of our proposed work-flow takes individual digital mammograms as input and outputs several smaller sub-images from which the background has been removed. Next, we extract a set of features which capture textural information from the segmented images.

SZ-Tetris, a restricted version of Tetris, is a difficult reinforcement learning task. Previous research showed that, similarly to the original Tetris, value function-based methods such as temporal difference learning, do not work well for SZ-Tetris. The best performance in this game was achieved by employing direct policy search techniques, in particular the cross-entropy method in combination with handcrafted features. Nonetheless, a simple heuristic hand-coded player scores even higher. Here we show that it is possible to equal its performance with CMA-ES (Covariance Matrix Adaptation Evolution Strategy). We demonstrate that further improvement is possible by employing systematic n-tuple network, a knowledge-free function approximator, and VD-CMA-ES, a linear variant of CMA-ES for high dimension optimization. Last but not least, we show that a large systematic n-tuple network (involving more than 4 million parameters) allows the classical temporal difference learning algorithm to obtain similar average performance to VD-CMA-ES, but at 20 times lower computational expense, leading to the best policy for SZ-Tetris known to date. These results enrich the current understanding of difficulty of SZ-Tetris, and shed new light on the capabilities of particular search paradigms when applied to representations of various characteristics and dimensionality.

The Earth surface and atmosphere exchange heat via turbulent fluxes. An accurate description of the heat exchange is essential in modelling the weather and climate. In these models the heat fluxes are described applying the Monin-Obukhov similarity theory, where the flux depends on the air-surface temperature difference and wind speed. The theory makes idealized assumptions and the resulting estimates often have large errors. This is the case particularly in conditions when the air is warmer than the Earth surface, i.e., the atmospheric boundary layer is stably stratified, and turbulence is therefore weak. This is a common situation over snow and ice in the Arctic and Antarctic. In this paper, we present alternative models for heat flux estimation evolved by means of genetic programming (GP). To this aim, we utilize the best heat flux data collected in the Arctic and Antarctic sea ice zones. We obtain GP models that are more accurate, robust, and conceptually novel from the viewpoint of meteorology. Contrary to the Monin-Obukhov theory, the GP equations are not solely based on the air-surface temperature difference and wind speed, but include also radiative fluxes that improve the performance of the method. These results open the door to a new class of approaches to heat flux prediction with potential applications in weather and climate models.

In genetic programming, a search algorithm is expected to produce a program that achieves the desired final computation state (desired output). To reach that state, an executing program needs to traverse certain intermediate computation states. An evolutionary search process is expected to autonomously discover such states. This can be difficult for nontrivial tasks that require long programs to be solved. The semantic backpropagation algorithm proposed in this paper heuristically inverts the execution of evolving programs to determine the desired intermediate computation states. Two search operators, random desired operator and approximately geometric semantic crossover, use the intermediate states determined by semantic backpropagation to define subtasks of the original programming task, which are then solved using an exhaustive search. The operators outperform the standard genetic search operators and other semantic-aware operators when compared on a suite of symbolic regression and Boolean benchmarks. This result and additional analysis conducted in this paper indicate that semantic backpropagation helps evolution to identify the desired intermediate computation states and makes the search process more efficient.

We propose a new means of executing a genetic program which improves its output quality. Our approach, called Multiple Regression Genetic Programming (MRGP) decouples and linearly combines a program's subexpressions via multiple regression on the target variable. The regression yields an alternate output: the prediction of the resulting multiple regression model. It is this output, over many fitness cases, that we assess for fitness, rather than the program's execution output. MRGP can be used to improve the fitness of a final evolved solution. On our experimental suite, MRGP consistently generated solutions fitter than the result of competent GP or multiple regression. When integrated into GP, inline MRGP, on the basis of equivalent computational budget, outperforms competent GP while also besting post-run MRGP. Thus MRGP's output method is shown to be superior to the output of program execution and it represents a practical, cost neutral, improvement to GP.

In evolutionary computation, the fitness of a candidate solution conveys sparse feedback. Yet in many cases, candidate solutions can potentially yield more information. In genetic programming (GP), one can easily examine program behavior on particular fitness cases or at intermediate execution states. However, how to exploit it to effectively guide the search remains unclear. In this study we apply machine learning algorithms to features describing the intermediate behavior of the executed program. We then drive the standard evolutionary search with additional objectives reflecting this intermediate behavior. The machine learning functions independent of task-specific knowledge and discovers potentially useful components of solutions (subprograms), which we preserve in an archive and use as building blocks when composing new candidate solutions. In an experimental assessment on a suite of benchmarks, the proposed approach proves more capable of finding optimal and/or well-performing solutions than control methods.

Recent developments cast doubts on the effectiveness of coevolutionary learning in interactive domains. A simple evolution with fitness evaluation based on games with random strategies has been found to generalize better than competitive coevolution. In an attempt to investigate this phenomenon, we analyze the utility of random opponents for one and two-population competitive coevolution applied to learning strategies for the game of Othello. We show that if coevolution uses two-population setup and engages also random opponents, it is capable of producing equally good strategies as evolution with random sampling for the expected utility performance measure. To investigate the differences between analyzed methods, we introduce performance profile, a tool that measures the player's performance against opponents of various strength. The profiles reveal that evolution with random sampling produces players coping well with mediocre opponents, but playing relatively poorly against stronger ones. This finding explains why in the round-robin tournament, evolution with random sampling is one of the worst methods from all those considered in this study.

We propose a novel crossover operator for tree-based genetic programming, that produces approximately geometric offspring. We empirically analyze certain aspects of geometry of crossover operators and verify performance of the new operator on both, training and test fitness cases coming from set of symbolic regression benchmarks. The operator shows superior performance and higher probability of producing geometric offspring than tree-swapping crossover and other semantic-aware control methods.

Online progress in search and optimization is often hindered by neutrality in the fitness landscape, when many genotypes map to the same fitness value. We propose a method for imposing a gradient on the fitness function of a metaheuristic (in this case, Genetic Programming) via a metric (Minimum Description Length) induced from patterns detected in the trajectory of program execution. These patterns are induced via a decision tree classifier. We apply this method to a range of integer and boolean-valued problems, significantly outperforming the standard approach. The method is conceptually straightforward and applicable to virtually any metaheuristic that can be appropriately instrumented.

In evolutionary learning of game-playing strategies, fitness evaluation is based on playing games with certain opponents. In this paper we investigate how the performance of these opponents and the way they are chosen influence the efficiency of learning. For this purpose we introduce a simple method for shaping the fitness function by sampling the opponents from a biased performance distribution. We compare the shaped function with existing fitness evaluation approaches that sample the opponents from an unbiased performance distribution or from a coevolving population. In an extensive computational experiment we employ these methods to learn Othello strategies and assess both the absolute and relative performance of the elaborated players. The results demonstrate the superiority of the shaping approach, and can be explained by means of performance profiles, an analytical tool that evaluate the evolved strategies using a range of variably skilled opponents.

The instructions used for solving typical genetic programming tasks have strong mathematical properties. In this study, we leverage one of such properties: invertibility. A search operator is proposed that performs an approximate reverse execution of program fragments, trying to determine in this way the desired semantics (partial outcome) at intermediate stages of program execution. The desired semantics determined in this way guides the choice of a subprogram that replaces the old program fragment. An extensive computational experiment on 20 symbolic regression and Boolean domain problems leads to statistically significant evidence that the proposed Random Desired Operator outperforms all typical combinations of conventional mutation and crossover operators.

This study investigates different methods of learning to play the game of Othello. The main questions posed concern scalability of algorithms with respect to the search space size and their capability to generalize and produce players that fare well against various opponents. The considered algorithms represent strategies as n-tuple networks, and employ self-play temporal difference learning (TDL), evolutionary learning (EL) and coevolutionary learning (CEL), and hybrids thereof. To assess the performance, three different measures are used: score against an a priori given opponent (a fixed heuristic strategy), against opponents trained by other methods (round-robin tournament), and against the top-ranked players from the online Othello League. We demonstrate that although evolutionary-based methods yield players that fare best against a fixed heuristic player, it is the coevolutionary temporal difference learning (CTDL), a hybrid of coevolution and TDL, that generalizes better and proves superior when confronted with a pool of previously unseen opponents. Moreover, CTDL scales well with the size of representation, attaining better results for larger n-tuple networks. By showing that a strategy learned in this way wins against the top entries from the Othello League, we conclude that it is one of the best 1-ply Othello players obtained to date without explicit use of human knowledge.

We investigate semantic properties of linear programs, both internally, by analyzing the memory states they produce during execution, and externally, by inspecting program outcomes. The main concept of the formalism we propose is program trace, which reflects the behavior of program in semantic space. It allows us to characterize programming tasks in terms of traces of programs that solve them, and to propose certain measures that reveal their properties. We are primarily interested in measures that quantitatively characterize functional (semantic, behavioral) modularity of programming tasks. The experiments conducted on large samples of linear programs written in Push demonstrate that semantic structure varies from task to task, and reveal patterns of different forms of modularity. In particular, we identify interesting relationships between task modularity, task complexity, and program length, and conclude that a great share of programming tasks are modular.

Genetic programming (GP) is not a field noted for the rigor of its benchmarking. Some of its benchmark problems are popular purely through historical contingency, and they can be criticized as too easy or as providing misleading information concerning real-world performance, but they persist largely because of inertia and the lack of good alternatives. Even where the problems themselves are impeccable, comparisons between studies are made more difficult by the lack of standardization. We argue that the definition of standard benchmarks is an essential step in the maturation of the field. We make several contributions towards this goal. We motivate the development of a benchmark suite and define its goals; we survey existing practice; we enumerate many candidate benchmarks; we report progress on reference implementations; and we set out a concrete plan for gathering feedback from the GP community that would, if adopted, lead to a standard set of benchmarks.

We propose an alternative program representation that relies on automatic semantic-based embedding of programs into discrete multidimensional spaces. An embedding imposes a well-structured hypercube topology on the search space, endows it with a semantic-aware neighborhood, and enables convenient search using Cartesian coordinates. The embedding algorithm consists in locality-driven optimization and operates in abstraction from a specific fitness function, improving locality of all possible fitness landscapes simultaneously. We experimentally validate the approach on a large sample of symbolic regression tasks and show that it provides better search performance than the original program space. We demonstrate also that semantic embedding of small programs can be exploited in a compositional manner to effectively search the space of compound programs.

We propose Coevolutionary Gradient Search, a blueprint for a family of iterative learning algorithms that combine elements of local search and population-based search. The approach is applied to learning Othello strategies represented as n-tuple networks, using different search operators and modes of learning. We focus on the interplay between the continuous, directed, gradient-based search in the space of weights, and fitness-driven, combinatorial, coevolutionary search in the space of entire n-tuple networks. In an extensive experiment, we assess both the objective and relative performance of algorithms, concluding that the hybridization of search techniques improves the convergence. The best algorithms not only learn faster than constituent methods alone, but also produce top ranked strategies in the online Othello League.

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 (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 a 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.

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 propose an evolutionary method for detection of vehicles in satellite imagery which involves a large number of simple elementary features and multiple detectors trained by genetic programming. The complete detection system is composed of several detectors that are chained into a cascade and successively filter out the negative examples. Each detector is a committee of genetic programming trees that together vote over the decision concerning vehicle presence, and is trained only on the examples classified as positive by the previous cascade node. The individual trees use typical arithmetic transformations to aggregate features selected from a very large collections of Haar-like features derived from the input image. The paper presents detailed description of the proposed algorithm and reports the results of an extensive computational experiment carried out on real-world satellite images. The evolved detection system exhibits competitive sensitivity and relatively low false positive rate for testing images, despite not making use of domain-specific knowledge.

In this paper we apply Coevolutionary Temporal Difference Learning (CTDL), a hybrid of coevolutionary search and reinforcement learning proposed in our former study, to evolve strategies for playing the game of Go on small boards (5×5). CTDL works by interlacing exploration of the search space provided by one-population competitive coevolution and exploitation by means of temporal difference learning. Despite using simple representation of strategies (weighted piece counter), CTDL proves able to evolve players that defeat solutions found by its constituent methods. The results of the conducted experiments indicate that our algorithm turns out to be superior to pure coevolution and pure temporal difference learning, both in terms of performance of the elaborated strategies and the computational cost. This demonstrates the existence of synergistic interplay between components of CTDL, which we also briefly discuss in this study.

We propose an evolutionary framework that uses the set of instructions provided with a genetic programming (GP) problem to automatically build a repertoire of related problems and subsequently uses them to improve the performance of search. The novel idea is to use the synthesized related problems to simultaneously exert multiple selection pressures on the evolving population(s). For that framework, we design two methods. In the first method, individuals optimizing for particular problems dwell in separate populations and spawn clones which migrate to other populations, similarly to the island model. The second method operates on a single population and ranks the fitness values that individuals receive from particular problems to make them comparable. When applied to six symbolic regression problems of different difficulty, both methods perform better than the standard GP, though sometimes fail to prove superior to certain control setup.

We propose a crossover operator that works with genetic programming trees and is approximately geometric crossover in the semantic space. By defining semantic as program's evaluation profile with respect to a set of fitness cases and constraining to a specific class of metric-based fitness functions, we cause the fitness landscape in the semantic space to have perfect fitness-distance correlation. The proposed approximately geometric semantic crossover exploits this property of the semantic fitness landscape by an appropriate sampling. We demonstrate also how the proposed method may be conveniently combined with hill climbing. We discuss the properties of the methods, and describe an extensive computational experiment concerning logical function synthesis and symbolic regression.

In this paper we introduce, formalize, and experimentally validate a novel concept of functional modularity for Genetic Programming (GP). We rely on module definition that is most natural for GP: a piece of program code (subtree). However, as opposed to syntax-based approaches that abstract from the actual computation performed by a module, we analyze also its semantic using a set of fitness cases. In particular, the central notion of this approach is subgoal, an entity that embodies module's desired semantic and is used to evaluate module candidates. As the cardinality of the space of all subgoals is exponential with respect to the number of fitness cases, we introduce monotonicity to assess subgoals' potential utility for searching for good modules. For a given subgoal and a sample of modules, monotonicity measures the correlation of subgoal's distance from module's semantics and the fitness of the solution the module is part of. In the experimental part we demonstrate how these concepts may be used to describe and quantify the modularity of two simple problems of Boolean function synthesis. In particular, we conclude that monotonicity usefully differentiates two problems with different nature of modularity, allows us to tell apart the useful subgoals from the other ones, and may be potentially used for problem decomposition and enhance the efficiency of evolutionary search.

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.

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.

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. 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 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.

As a learning method support vector machine is regarded as one of the best classifiers with a strong mathematical foundation. On the other hand, evolutionary computational technique is characterized as a soft computing learning method with its roots in the theory of evolution. During the past decade, SVM has been commonly used as a classifier for various applications. The evolutionary computation has also attracted a lot of attention in pattern recognition and has shown significant performance improvement on a variety of applications. However, there has been no comparison of the two methods. In this paper, first we propose an improvement of a coevolutionary computational classification algorithm, called Improved Coevolutionary Feature Synthesized EM (I-CFS-EM) algorithm. It is a hybrid of coevolutionary genetic programming and EM algorithm applied on partially labeled data. It requires less labeled data and it makes the test in a lower dimension, which speeds up the testing. Then, we provide a comprehensive comparison between SVM with different kernel functions and I-CFS-EM on several real datasets. This comparison shows that I-CFS-EM outperforms SVM in the sense of both the classification performance and the computational efficiency in the testing phase. We also give an intensive analysis of the pros and cons of both approaches.

Among the existing feature selection/synthesis approaches, Coevolutionary Feature Synthesis (CFS) based on Coevolutionary Genetic Programming (CGP) has shown good performance on a variety of applications. In this paper, we propose an MDL-based fitness function to help pick a reasonable number of synthesized features which is equal to the number of subpopulations. It naturally balances the feature transformation complexity and classification performance. Experiments on a real image database show that the new fitness function solves the problem quite well.al.

In this paper, we present a novel method for learning complex concepts/hypotheses directly from raw training data. The task addressed here concerns data-driven synthesis of recognition procedures for real-world object recognition. The method uses linear genetic programming to encode potential solutions expressed in terms of elementary operations, and handles the complexity of the learning task by applying cooperative coevolution to decompose the problem automatically at the genotype level. The training coevolves feature extraction procedures, each being a sequence of elementary image processing and computer vision operations applied to input images. Extensive experimental results show that the approach attains competitive performance for three-dimensional object recognition in real synthetic aperture radar imagery.

The paper presents a novel method of evolutionary learning dedicated to acquisition of visual concepts. The learning process takes place in a population of genetic programming-based learners that process attributed visual primitives derived from raw raster images. The approach uses an original evaluation scheme: evolving individuals-learners are rewarded for being able to sketch the input visual stimulus. Recognition proceeds here as an attempt of restoring essential features of the input image. The approach is general by being based mostly on universal vision knowledge; only very limited amount of a priori knowledge about the particular application or target concept to be learned is required. We explain the method in detail and verify it experimentally on acquisition of simple visual concepts (triangle and section) from examples.

In this paper, a novel genetically inspired visual learning method is proposed. Given the training raster images, this general approach induces a sophisticated feature-based recognition system. It employs the paradigm of cooperative coevolution to handle the computational difficulty of this task. To represent the feature extraction agents, the linear genetic programming is used. The paper describes the learning algorithm and provides a firm rationale for its design. Different architectures of recognition systems are considered that employ the proposed feature synthesis method. An extensive experimental evaluation on the demanding real-world task of object recognition in synthetic aperture radar (SAR) imagery shows the ability of the proposed approach to attain high recognition performance in different operating conditions.

This paper presents an empirical study of the use of the rough set approach to reduction of data for a neural network classifying objects described by quantitative and qualitative attributes. Two kinds of reduction are considered: reduction of the set of attributes and reduction of the domains of attributes. Computational tests were performed with five data sets having different character, for original and two reduced representations of data. The learning time acceleration due to data reduction is up to 4.72 times. The resulting increase of misclassification error does not exceed 11.06%. These promising results let us claim that the rough set approach is a useful tool for preprocessing of data for neural networks.