Modeling real-world phenomena is a focus of many science and engineering efforts, from ecological modeling to financial forecasting. Building an accurate model for complex and dynamic systems improves understanding of underlying processes and leads to resource efficiency. Knowledge-driven modeling builds a model based on human expertise, yet is often suboptimal. At the opposite extreme, data-driven modeling learns a model directly from data, requiring extensive data and potentially generating overfitting. We focus on an intermediate approach, model revision, in which prior knowledge and data are combined to achieve the best of both worlds. We propose a genetic model revision framework based on tree-adjoining grammar (TAG) guided genetic programming (GP), using the TAG formalism and GP operators in an effective mechanism making data-driven revisions while incorporating prior knowledge. Our framework is designed to address the high computational cost of evolutionary modeling of complex systems. Via a case study on the challenging problem of river water quality modeling, we show that the framework efficiently learns an interpretable model, with higher modeling accuracy than existing methods.

Symbolic regression has been one of the main learning domains for Genetic Programming. However, most work so far on using genetic programming for symbolic regression only focus on point prediction. The problem of symbolic interval regression is for each input to find a prediction interval containing the output with a given statistical confidence. This problem is important for many risk-sensitive domains (such as in medical and financial applications). In this paper, we propose the combination of conformal prediction and genetic programming for solving the problem of symbolic interval regression. We study two approaches called black-box conformal prediction genetic programming (black-box CPGP) and white-box conformal prediction genetic programming (white-box CPGP) on a number of benchmarks and previously used problems. We compare the performance of these approaches with two popular interval regressors in statistic and machine learning domains, namely, the linear quantile regression and quantile random forrest. The experimental results show that, on the two performance metrics, black-box CPGP is comparable to the linear quantile regression and not much worse than the quantile random forrest on validity and much better than them on efficiency.

The estimation of distribution algorithms (EDAs) applied to genetic programming (GP) have been studied by a number of authors. Like all EDAs, they suffer from biases induced by the model building and sampling process. However, the biases are amplified in the algorithms for GP. In particular, many systems use stochastic grammars as their model representation, but biases arise due to grammar recursion. We define and estimate the bias due to recursion in grammar-based EDAs in GP, using methods derived from computational linguistics. We confirm the extent of bias in some simple experimental examples. We then propose some methods to repair this bias. We apply the estimation of bias, and its repair, to some more practical applications. We experimentally demonstrate the extent of bias arising from recursion, and the performance improvements that can result from correcting it.

In this paper, we propose a Genetic Algorithm (GA) for solving the problem of dimensional ordering in Radial Visualization (Radviz) systems. The Radviz is a non-linear projection of high-dimensional data set onto two dimensional space. The order of dimension anchors in the Radviz system is crucial for the visualization quality. We conducted experiments on five common data sets and compare the quality of solutions found by GA and those found by the other well-known methods. The experimental results show that the solutions found by GA for these tested data sets are very competitive having better cost values than almost all solutions found by other methods. This suggests that GA could be a good approach to solve the problem of dimensional ordering in Radviz.

Malware is any software aiming to disrupt computer operation. Malware is also used to gather sensitive information or gain access to private computer systems. This is widely seen as one of the major threats to computer systems nowadays. Traditionally, anti-malware software is based on a signature detection system which keeps updating from the Internet malware database and thus keeping track of known malwares. While this method may be very accurate to detect previously known malwares, it is unable to detect unknown malicious codes. Recently, several machine learning methods have been used for malware detection, achieving remarkable success. In this paper, we propose a method in this strand by using Genetic Programming for detecting malwares. The experiments were conducted with the malwares collected from an updated malware database on the Internet and the results show that Genetic Programming, compared to some other well-known machine learning methods, can produce the best results on both balanced and imbalanced datasets.

Much recent research in Estimation of Distribution Algorithms (EDA) applied to Genetic Programming has adopted a Stochastic Context Free Grammar(SCFG)-based model formalism. However these methods generate biases which may be indistinguishable from selection bias, resulting in sub-optimal performance. The primary factor generating this bias is the combined effect of recursion in the grammars and depth limitation removing some sample trees from the distribution. Here, we demonstrate the bias and provide exact estimates of its scale (assuming infinite populations and simple recursions). We define a quantity h which determines both whether bias occurs (h >; 1) and its scale. We apply this analysis to a number of simple illustrative grammars, and to a range of practically-used GP grammars, showing that this bias is both real and important.

The Gaussian Q-function is of great importance in the field of communications, where the noise is often characterized by the Gaussian distribution. However, no simple exact closed form of the Q-function is known. Consequently, a number of approximations have been proposed over the past several decades. In this paper, we use Genetic Programming with semantic based crossover to approximate the Q-function in two forms: the free and the exponential forms. Using this form, we found approximations in both forms that are more accurate than all previous approximations designed by human experts.

The Gaussian Q-function is the integral of the tail of the Gaussian distribution; as such, it is important across a vast range of fields requiring stochastic analysis. No elementary closed form is possible, so a number of approximations have been proposed. We use a Genetic Programming (GP) system, Tree Adjoining Grammar Guided GP (TAG3P) with local search operators to evolve approximations of the Q-function in the form given by Benitez [1]. We found more accurate approximations than any previously published. This confirms the practical importance of local search in TAG3P.

In this paper, we investigate the impact of a layered learning approach with incremental sampling on Genetic Programming (GP). The new system, called GPLL, is tested and compared with standard GP on twelve symbolic regression problems. While GPLL does not differ from standard GP on univariate target functions, it has better training efficiency on problems with bivariate targets. This indicates the potential usefulness of layered learning with incremental sampling in improving the efficiency of GP evolutionary learning.

This paper examines how the semantic locality of a search operator affects the fitness landscape of Genetic Programming (GP). We compare the fitness landscapes of GP search when standard subtree mutation and arecently proposed semantic-based mutation, Semantic Similarity-based Mutation (SSM), are used. The comparison is based on two well-studied fitness landscape measures, namely, the autocorrelation function and information content. The experiments were conducted on a family of symbolic regression problems with increasing degrees of difficulty. The results show that SSM helps to significantly smooth out the fitness landscape of GP compared to standard subtree mutation. This gives an explanation for the better performance of SSM over standard subtree mutation operator.

We investigate interactions between evolution, development and lifelong layered learning in a combination we call evolutionary developmental evaluation (EDE), using a specific implementation, developmental tree-adjoining grammar guided genetic programming (GP). The approach is consistent with the process of biological evolution and development in higher animals and plants, and is justifiable from the perspective of learning theory. In experiments, the combination is synergistic, outperforming algorithms using only some of these mechanisms. It is able to solve GP problems that lie well beyond the scaling capabilities of standard GP. The solutions it finds are simple, succinct, and highly structured. We conclude this paper with a number of proposals for further extension of EDE systems.

Water quality is an important global issue, requiring effective management, which needs good predictive tools. While good methods for lake water quality prediction have previously been developed, accurate prediction of river water quality has hitherto been difficult. This project combines process-model and data mining approaches through evolutionary methods, resulting in tools for more effective water management. Although the work is still in its preliminary stages, error rates of the predictive models are already around half those resulting from representative applications of either pure process-based or pure data mining approaches.

This paper presents two methods for self-adapting the semantic sensitivities in a recently proposed semantics-based crossover: Semantic Similarity based Crossover (SSC). The first self-adaptation method is inspired by a self-adaptive method for controlling mutation step size in Evolutionary Strategies (1/5 rule). The design of the second takes into account more of our previous experimental observations, that SSC works well only when a certain portion of events successfully exchange semantically similar subtrees. These two proposed methods are then tested on a number of real-valued symbolic regression problems, their performance being compared with SSC using predetermined sensitivities and with standard crossover. The results confirm the benefits of the second self-adaption method.

This paper investigates the role of semantic diversity and locality of crossover operators in. Genetic Programming (GP) for Boolean problems. We propose methods for measuring and storing semantics of subtrees in Boolean domains using Trace Semantics, and design several new crossovers on this basis. They can be categorised into two classes depending on their purposes: promoting semantic diversity or improving semantic locality. We test the operators on several well-known Boolean problems, comparing them with Standard GP Crossovers and with the Semantic Driven Crossover of Beadle and Johnson. The experimental results show the positive effects both of promoting semantic diversity, and of improving semantic locality, in crossover operators. They also show that the latter has a greater positive effect on GP performance than the former.

In this paper, we propose a new heuristic, called Center-Based Recursive Clustering - CBRC, for solving the bounded diameter minimum spanning tree (BDMST) problem. Our proposed hybrid genetic algorithm [12] is also extended to include the new heuristic and a multi-parent crossover operator. We test the new heuristic and genetic algorithm on two sets of benchmark problem instances for the Euclidean and Non-Euclidean cases. Experimental results show the effectiveness of the proposed heuristic and genetic algorithm.

In this paper, a new genetic algorithm (GA) for solving the path planning in dynamic environments is proposed. The new genetic algorithm uses local maps, therefore, does not require the knowledge of exact or estimated position of the destination point as other approaches in the literature. Consequently, the new GA could be used to solve the problem of dynamic path planning under an assumption that makes the problem more restrictive but more close to reality (in searching tasks).

In this paper, we investigate the value of a new selection mechanism that is inspired from biochemistry, namely, vesicular selection. We test its effectiveness when used in evolutionary algorithms on a number of benchmark problems in both static and dynamic environments. The results suggest beneficial attributes for the new selection mechanism.

Shin et al [19] and McKay et al [15] previously applied tree compression and semantics-based simplification to study the distribution of building blocks in evolving Genetic Programming populations. However their method could only give static estimates of the degree of repetition of building blocks in one generation at a time, supplying no information about the flow of building blocks between generations. Here, we use a state-of-the-art tree compression algorithm, xmlppm, to estimate the extent to which frequent building blocks from one generation are still in use in a later generation. While they compared the behaviour of different GP algorithms on one specific problem -- a simple symbolic regression problem -- we extend the analysis to a more complex problem, a symbolic regression problem to find a Fourier approximation to a sawtooth wave, and to a Boolean domain, odd parity.

In this paper, a new hybrid genetic algorithm - known as HGA - is proposed for solving the Bounded Diameter Minimum Spanning Tree (BDMST) problem. We experiment with HGA on two sets of benchmark problem instances, both Euclidean and Non-Euclidean. On the Euclidean problem instances, HGA is shown to outperform the previous best two Genetic Algorithms (GAs) reported in the BDMST literature, while on the Non-Euclidean problem instance, HGA performs comparably with these two GAs.

Compression algorithms generate a predictive model of data, using the model to reduce the number of bits required to transmit the data (in effect, transmitting only the differences from the model). As a consequence, the degree of compression achieved provides an estimate of the level of regularity in the data. Previous work has investigated the use of these estimates to understand the replication of building blocks within genetic programming (GP) individuals, and hence to understand how different GP algorithms promote the evolution of repeated common structure within individuals. Here, we extend this work to the population level, and use it to understand the extent of similarity between sub-structures within individuals in GP populations.

In this paper, we investigate the use of some wel-known randomised low-discrepancy sequences (Halton, Sobol, and Faure sequences) for initialising particle swarms. We experimented with the standard global-best particle swarm algorithm for function optimization on some benchmark problems, using randomised low-discrepancy sequences for initialisation, and the results were compared with the same particle swarm algorithm using uniform initialisation with a pseudo-random generator. The results show that, the former initialisation method could help the particle swarm algorithm improve its performance over the latter on the problems tried. Furthermore the comparisons also indicate that the use of different randomised low-discrepancy sequences in the initialisation phase could bring different effects on the performance of PSO.

We initialize a global-best particle swarm with a Halton sequence, comparing it with uniform initialization on a range of benchmark function optimization problems. We see substantial improvements in performance, particularly with high complexity problems /small populations. Halton initialization yields equivalent performance to uniform initialization with substantially smaller populations.

In this paper, we show some experimental results using Incremental Evaluation with Tree Adjoining Grammar Guided Genetic Programming (DEVTAG) on two symbolic regression problems, a benchmark polynomial fitting problem in genetic programming, and a Fourier series problem (sawtooth problem). In our pilot study, we compare results with standard Genetic Programming (GP) and the original Tree Adjoining Grammar Guided Genetic Programming (TAG3P). Our results on the two problems are good, outperforming both standard GP and the original TAG3P.

In this paper, we describe a new test problem for genetic programming (GP), ORDERTREE. We argue that it is a natural analogue of ONEMAX, a popular GA test problem, and that it also avoids some of the known weaknesses of other benchmark problems for Genetic Programming. Through experiments, we show that the difficulty of the problem can be tuned not only by increasing the size of the problem, but also by increasing the non-linearity in the fitness structure.

Standard tree-based genetic programming suffers from a structural difficulty problem in that it is unable to search effectively for solutions requiring very full or very narrow trees. This deficiency has been variously explained as a consequence of restrictions imposed by the tree structure or as a result of the numerical distribution of tree shapes. We show that by using a different tree-based representation and local (insertion and deletion) structural modification operators, that this problem can be almost eliminated even with trivial (stochastic hill-climbing) search methods, thus eliminating the above explanations. We argue, instead, that structural difficulty is a consequence of the large step size of the operators in standard genetic programming, which is itself a consequence of the fixed-arity property embodied in its representation.

We investigate the roles of insertion and deletion as mutation operators and local search operators in a tree adjoining grammar guided genetic programming (TAG3P) system (Nguyen Xuan Hoai et al., 2003). The results show that, on three standard problems, these operators work better as mutation operators than the more standard sub-tree mutation originally used in (Nguyen Xuan Hoai et al., 2003, 2004). Moreover, for some problems, insertion and deletion can act effectively as local search operators, allowing TAG3P to solve problems with very small population sizes.

In evolutionary computation, genetic operators, such as mutation and crossover, are employed to perturb individuals to generate the next population. However these fixed, problem independent genetic operators may destroy the sub-solution, usually called building blocks, instead of discovering and preserving them. One way to overcome this problem is to build a model based on the good individuals, and sample this model to obtain the next population. There is a wide range of such work in genetic algorithms; but because of the complexity of the genetic programming (GP) tree representation, little work of this kind has been done in GP. In this paper, we propose a new method, grammar model-based program evolution (GMPE) to evolved GP program. We replace common GP genetic operators with a probabilistic context-free grammar (SCFG). In each generation, an SCFG is learnt, and a new population is generated by sampling this SCFG model. On two benchmark problems we have studied, GMPE significantly outperforms conventional GP, learning faster and more reliably.

Genetic programming (GP) plays the primary role in the discovery of programs through evolving the program's set of parse trees. We present a new technique for constructing programs through ant colony optimization (ACO) using the tree adjunct grammar (TAG) formalism. We call the method AntTAG and we show that the results are very promising.

In this paper, we show some experimental results of tree-adjunct grammar-guided genetic programming (TAG3P) on the symbolic regression problem, a benchmark problem in genetic programming. We compare the results with genetic programming (GP) and grammar-guided genetic programming (GGGP). The results show that TAG3P significantly outperforms GP and GGGP on the target functions attempted in terms of the probability of success. Moreover, TAG3P still performed well when the structural complexity of the target function was scaled up.