Bayesian Methods for Efficient Genetic Programming

A Bayesian framework for genetic programming (GP) is presented. This is motivated by the observation that genetic programming iteratively searches populations of fitter programs and thus the information gained in the previous generation can be used in the next generation. The Bayesian GP makes use of Bayes theorem to estimate the posterior distribution of programs from their prior distribution and likelihood for the fitness data observed. Offspring programs are then generated by sampling from the posterior distribution by genetic variation operators. We present two GP algorithms derived from the Bayesian GP framework. One is the genetic programming with the adaptive Occam's razor (AOR) designed to evolve parsimonious programs. The other is the genetic programming with incremental data inheritance (IDI) designed to accelerate evolution by active selection of fitness cases. A multiagent learning task is used to demonstrate the effectiveness of the presented methods. In a series of experiments, AOR reduced solution complexity by 20% and IDI doubled evolution speed, both without loss of solution accuracy.     

Internal reinforcement in a connectionist genetic programming approach

Genetic programming (GP) can learn complex concepts by searching for the target concept through evolution of a population of candidate hypothesis programs. However, unlike some learning techniques, such as Artificial Neural Networks (ANNs), GP does not have a principled procedure for changing parts of a learned structure based on that structure's performance on the training data. GP is missing a clear, locally optimal update procedure, the equivalent of gradient-descent backpropagation for ANNs. This article introduces a new algorithm, “internal reinforcement”, for defining and using performance feedback on program evolution. This internal reinforcement principled mechanism is developed within a new connectionist representation for evolving parameterized programs, namely “neural programming”. We present the algorithms for the generation of credit and blame assignment in the process of learning programs using neural programming and internal reinforcement. The article includes a comprehensive overview of genetic programming and empirical experiments that demonstrate the increased learning rate obtained by using our principled program evolution approach.     

Evolving encapsulated programs as shared grammars

Facilitating the discovery and reuse of modular building blocks is generally regarded as the key to achieving better scalability in genetic programming (GP). A precedent for this exists in biology, where complex designs are the product of developmental processes that can also be abstractly modeled as generative grammars. We introduce shared grammar evolution (SGE), which aligns grammatical development with the common application of grammars in GP as a means of establishing declarative bias. Programs are derived from and represented by a global context-free grammar that is transformed and extended according to another, user-defined grammar. Grammatical productions and the subroutines they encapsulate are shared between programs, which enables their reuse without reevaluation and can significantly reduce total evaluation time for large programs and populations. Several variants of SGE employing different strategies for controlling solution size and diversity are tested on classic GP problems. Results compare favorably against GP and newer techniques, with the best results obtained by promoting diversity between derived programs.     

Genetic programming incorporating biased mutation for evolution and adaptation of Snakebot

In this work we propose an approach for incorporating learning probabilistic context-sensitive grammar (LPCSG) in genetic programming (GP), employed for evolution and adaptation of locomotion gaits of a simulated snake-like robot (Snakebot). Our approach is derived from the original context-free grammar which usually expresses the syntax of genetic programs in canonical GP. Empirically obtained results verify that employing LPCSG contributes to the improvement of computational effort of both (i) the evolution of the fastest possible locomotion gaits for various fitness conditions and (ii) adaptation of these locomotion gaits to challenging environment and degraded mechanical abilities of the Snakebot.     

Probabilistic incremental program evolution

Probabilistic incremental program evolution (PIPE) is a novel technique for automatic program synthesis. We combine probability vector coding of program instructions, population-based incremental learning, and tree-coded programs like those used in some variants of genetic programming (GP). PIPE iteratively generates successive populations of functional programs according to an adaptive probability distribution over all possible programs. Each iteration, it uses the best program to refine the distribution. Thus, it stochastically generates better and better programs. Since distribution refinements depend only on the best program of the current population, PIPE can evaluate program populations efficiently when the goal is to discover a program with minimal runtime. We compare PIPE to GP on a function regression problem and the 6-bit parity problem. We also use PIPE to solve tasks in partially observable mazes, where the best programs have minimal runtime.     

Evolutionary program induction directed by logic grammars

Program induction generates a computer program that can produce the desired behavior for a given set of situations. Two of the approaches in program induction are inductive logic programming (ILP) and genetic programming (GP). Since their formalisms are so different, these two approaches cannot be integrated easily, although they share many common goals and functionalities. A unification will greatly enhance their problem-solving power. Moreover, they are restricted in the computer languages in which programs can be induced. In this paper, we present a flexible system called LOGENPRO (The LOgic gramar-based GENetic PROgramming system) that uses some of the techniques of GP and ILP. It is based on a formalism of logic grammars. The system applies logic grammars to control the evolution of programs in various programming languages and represent context-sensitive information and domain-dependent knowledge. Experiments have been performed to demonstrate that LOGENPRO can emulate GP and GP with automatically defined functions (ADFs). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. The experiments show that LOGENPRO has superior performance to that of GP and GP with ADFs when more domain-dependent knowledge is available. We have applied LOGENPRO to evolve general recursive functions for the even-n-parity problem from noisy training examples. A number of experiments have been performed to determine the impact of domain-specific knowledge and noise in training examples on the speed of learning.     

Learning to control the program evolution process with cultural algorithms

Traditional software engineering dictates the use of modular and structured programming and top-down stepwise refinement techniques that reduce the amount of variability arising in the development process by establishing standard procedures to be followed while writing software. This focusing leads to reduced variability in the resulting products, due to the use of standardized constructs. Genetic programming (GP) performs heuristic search in the space of programs. Programs produced through the GP paradigm emerge as the result of simulated evolution and are built through a bottom-up process, incrementally augmenting their functionality until a satisfactory level of performance is reached. Can we automatically extract knowledge from the GP programming process that can be useful to focus the search and reduce product variability, thus leading to a more effective use of the available resources? An answer to this question is investigated with the aid of cultural algorithms. A new system, cultural algorithms with genetic programming (CAGP), is presented. The system has two levels. The first is the pool of genetic programs (population level), and the second is a knowledge repository (belief set) that is built during the GP run and is used to guide the search process. The microevolution within the population brings about potentially meaningful characteristics of the programs for the achievement of the given task, such as properties exhibited by the best performers in the population. CAGP extracts these features and represents them as the set of the current beliefs. Beliefs correspond to constraints that all the genetic operators and programs must follow. Interaction between the two levels occurs in one direction through the extraction process and, in the other, through the modulation of an individual's program parameters according to which, and how many, of the constraints it follows. CAGP is applied to solve an instance of the symbolic regression problem, in which a function of one variable needs to be discovered. The results of the experiments show an overall improvement on the average performance of CAGP over GP alone and a significant reduction of the complexity of the produced solution. Moreover, the execution time required by CAGP is comparable with the time required by GP alone.     

一种线性表示的遗传程序设计方法研究

遗传程序设计领域中的一个重要研究内容是如何有效地表示进化的个体（计算机程序），对采用树的线性后缀形式的个体进行位置信息编码以实现多种形式的遗传操作，并给出形式化定义，设计并实现了一个基于栈的遗传程序设计算法，通过模拟实验比较了各操作的性能，这种编码方式可以扩展到程序的线性结构中，以实现特定的遗传操作，显示出线性表示具有适于解决不同问题的可行性和灵活性，还给出了基于串的一点交叉的线性遗传程序设计的模式理论，它可以把标准遗传算法的模式生成机制统一到该理论框架中。     

Evolving Recursive Programs by Using Adaptive Grammar Based Genetic Programming

Genetic programming (GP) extends traditional genetic algorithms to automatically induce computer programs. GP has been applied in a wide range of applications such as software re-engineering, electrical circuits synthesis, knowledge engineering, and data mining. One of the most important and challenging research areas in GP is the investigation of ways to successfully evolve recursive programs. A recursive program is one that calls itself either directly or indirectly through other programs. Because recursions lead to compact and general programs and provide a mechanism for reusing program code, they facilitate GP to solve larger and more complicated problems. Nevertheless, it is commonly agreed that the recursive program learning problem is very difficult for GP. In this paper, we propose techniques to tackle the difficulties in learning recursive programs. The techniques are incorporated into an adaptive Grammar Based Genetic Programming system (adaptive GBGP). A number of experiments have been performed to demonstrate that the system improves the effectiveness and efficiency in evolving recursive programs. Communicated by: William B. Langdon An erratum to this article is available at .     

Evolving Programs and Solutions Using Genetic Programming with Application to Learning and Adaptive Control

This paper discusses two feasibility studies of Genetic Programming (GP) to the field of control theory, GP being a method inspired from nature where the goal is to create a computer program automatically from high-level statements of problems' requirements. The first feasibility study derives from stability theory and deals with evolving a program that can solve discrete-time Lyapunov equations. The second application of GP tackles the problem of producing a self-evolved Model Reference Adaptive System (MRAS). Basic structure of the programs used in the experiments are only marginally different, yet applied to seemingly quite different problems. In the first feasibility study, it was observed that GP, beside correct usage of global variables, could also purposely arrange mathematical functions and operations in an iterative manner without being explicitly programmed for the task. In the second feasibility study, a controller was evolved for a second-order process based on a pre-defined reference model.     

Evolution of human-competitive lossless compression algorithms with GP-zip2

We propose GP-zip2, a new approach to lossless data compression based on Genetic Programming (GP). GP is used to optimally combine well-known lossless compression algorithms to maximise data compression. GP-zip2 evolves programs with multiple components. One component analyses statistical features extracted by sequentially scanning the data to be compressed and divides the data into blocks. These blocks are projected onto a two-dimensional Euclidean space via two further (evolved) program components. K-means clustering is then applied to group similar data blocks. Each cluster is labelled with the optimal compression algorithm for its member blocks. After evolution, evolved programs can be used to compress unseen data. The compression algorithms available to GP-zip2 are: Arithmetic coding, Lempel-Ziv-Welch, Unbounded Prediction by Partial Matching, Run Length Encoding, and Bzip2. Experimentation shows that the results produced by GP-zip2 are human-competitive, being typically superior to well-established human-designed compression algorithms in terms of the compression ratios achieved in heterogeneous archive files.     

XML-based genetic programming framework: design philosophy, implementation, and applications

We present the design philosophy, implementation, and various applications of an XML-based genetic programming (GP) framework (XGP). The key feature of XGP is the distinct representation of genetic programs as DOM parsing trees featuring corresponding flat XML text. XGP contributes to the achievements of: (i) fast prototyping of GP by using the standard built-in API of DOM parsers for manipulating the genetic programs, (ii) human readability and modifiability of the genetic representations, (iii) generic support for the representation of the grammar of a strongly typed GP using W3C-standardized XML schema; (iv) inherent inter-machine migratability of the text-based genetic representation (i.e., the XML text) in the distributed implementations of GP.     

GP算法中适应度函数的光滑拟合与调整参数方法研究

研究了遗传程序设计(GP)算法中适应度函数的光滑拟合问题,结合LAMs(Linear association memorys)方法和HJ(Hook和Jeevs)方法两种方法,估计GP树数值权值,以减少GP树适应度值评价的计算代价.光滑拟合的好坏关键取决于调整参数的选择.提出了一种选择调整参数的新方法,同时,给出了两个数学例子,并与广义交叉实验B-样条函数仿真比较验证.     

PSO-BP神经网络在多元有害气体检测中的应用

针对目前常见的多元有害气体检测问题,搭建了一种基于传感器阵列和GP神经网络相结合的多元有害气体检测系统。该检测系统中采用了GP神经网络算法对传感器阵列的4种混合有害气体的响应信号进行回归分析。为了提高GP神经网络的预测准确性,又利用了粒子群优化（ PSO）算法对GP神经网络的权值与阈值进行了优化。结果显示：通过PSO 优化的GP（ PSO-GP）神经网络预测的平均相对误差小于2%,能够有效解决气体传感器交叉敏感问题。     

遗传规划在符号回归中的应用

遗传规划(GP)是一种基于达尔文进化理论的数学规划方法。讨论了GP在符号回归中的应用。与传统的数据拟合方法相比,GP不必给出拟合函数的形式,同时,在初始群体足够大而且交叉和变异概率设置合理的情况下,不会陷入局部优化,具有更广泛的适用性。对于不给定函数形式的曲线拟合,GP可以自动得到曲线的函数形式及其参数大小,避免了传统方法的缺陷。通过具体的应用实例,说明了GP在测量数据处理中的应用。     

Predicting high-strength concrete parameters using weighted genetic programming

Genetic programming (GP) is an evolutionary algorithm-based methodology that employs a binary tree topology with optimized functional operators. This study introduced weight coefficients to each GP linkage in a tree in order to create a new weighted genetic programming (WGP) approach. Two distinct advantages of the proposed WGP include (1) balancing the influences of the two front input branches and (2) incorporating weights throughout generated formulas. Resulting formulas contain a certain quantity of optimized functions and weights. Genetic algorithms are employed to accomplish WGP optimization of function selection and proper weighting tasks. Case studies presented herein highlight a high-strength concrete reference study. Results showed that the proposed WGP not only improves GP in terms of introduced weight coefficients, but also provides both accurate results and formula outputs.     

DepthLimited crossover in GP for classifier evolution

Genetic Programming (GP) provides a novel way of classification with key features like transparency, flexibility and versatility. Presence of these properties makes GP a powerful tool for classifier evolution. However, GP suffers from code bloat, which is highly undesirable in case of classifier evolution. In this paper, we have proposed an operator named “DepthLimited crossover”. The proposed crossover does not let trees increase in complexity while maintaining diversity and efficient search during evolution. We have compared performance of traditional GP with DepthLimited crossover GP, on data classification problems and found that DepthLimited crossover technique provides compatible results without expanding the search space beyond initial limits. The proposed technique is found efficient in terms of classification accuracy, reduced complexity of population and simplicity of evolved classifiers.     

A survey and taxonomy of performance improvement of canonical genetic programming

The genetic programming (GP) paradigm, which applies the Darwinian principle of evolution to hierarchical computer programs, has been applied with breakthrough success in various scientific and engineering applications. However, one of the main drawbacks of GP has been the often large amount of computational effort required to solve complex problems. Much disparate research has been conducted over the past 25 years to devise innovative methods to improve the efficiency and performance of GP. This paper attempts to provide a comprehensive overview of this work related to Canonical Genetic Programming based on parse trees and originally championed by Koza (Genetic programming: on the programming of computers by means of natural selection. MIT, Cambridge, 1992). Existing approaches that address various techniques for performance improvement are identified and discussed with the aim to classify them into logical categories that may assist with advancing further research in this area. Finally, possible future trends in this discipline and some of the open areas of research are also addressed.     

遗传程序设计算法中选择调整参数的光滑拟合方法

对遗传程序设计(GP)算法中的适应度评价函数光滑拟合问题进行了研究,结合LAM(Linear Association Memory)和HJ(Hook和Jeevs)两种方法,估计GP树数值权值,以减少GP树适应度值评价的计算代价。提出了一种选择调整参数的新方法,同时,给出了一个数学例子,并与广义交叉实验B一样条函数仿真比较验证。