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.     

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.     

基于GEP和GA技术的非线性系统辨识研究

给出了利用基因表达式编程（GEP）进行非线性系统辨识的方法,弥补了传统辨识方法需要过多预知信息的不足,有着比遗传编程（GP）更简洁有效的系统模型结构表达方式.利用改进的遗传算法（GA）并行地进行模型参数进化,可以在有限的给定数据内得到合适的模型.关于模型适应度的定义,综合考虑了精确性和复杂性因素,能够获取一种比较折中的辨识结果.仿真结果表明,这种方式可以快速、准确地获取非线性模型.     

Comparing extended classifier system and genetic programming for financial forecasting: an empirical study

As a broad subfield of artificial intelligence, machine learning is concerned with the development of algorithms and techniques that allow computers to learn. These methods such as fuzzy logic, neural networks, support vector machines, decision trees and Bayesian learning have been applied to learn meaningful rules; however, the only drawback of these methods is that it often gets trapped into a local optimal. In contrast with machine learning methods, a genetic algorithm (GA) is guaranteeing for acquiring better results based on its natural evolution and global searching. GA has given rise to two new fields of research where global optimization is of crucial importance: genetic based machine learning (GBML) and genetic programming (GP). This article adopts the GBML technique to provide a three-phase knowledge extraction methodology, which makes continues and instant learning while integrates multiple rule sets into a centralized knowledge base. Moreover, the proposed system and GP are both applied to the theoretical and empirical experiments. Results for both approaches are presented and compared. This paper makes two important contributions: (1) it uses three criteria (accuracy, coverage, and fitness) to apply the knowledge extraction process which is very effective in selecting an optimal set of rules from a large population; (2) the experiments prove that the rule sets derived by the proposed approach are more accurate than GP.     

Emergence in simulated evolution

Wolfgang Banzhaf’s essay elegantly shows how emergence can be observed within the genetic programming (GP) framework. His work provides inspiration to employ GP for investigating emerging phenomena in biological evolution. This commentary attempts to further stimulate such development towards a more realistic GP framework by incorporating features observed in natural evolution. The examples discussed are multiscalarity, lower-level stochasticity, and co-evolution of repair or protection mechanisms.     

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.     

经费分配中基于多目标优化的遗传规划模型

在传统遗传规划中引入多目标优化原理,探索新的经费分配方法和管理模式,建立了一种多目标优化的非线性遗传规划模型,提出了一种先进的基于正交试验的新型混合遗传算法来求解该问题.对求解过程中的选择算子、交叉算子和变异算子等进行正交试验,得到的种群个体明显优于基本遗传算法的个体.这种基于多目标优化的遗传规划模型能产生精度更高的最优解,通过对经费分配问题的实验验证,得到了较好的结果.     

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.     

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.     

A comparison of grammatical genetic programming grammars for controlling femtocell network coverage

We study grammars used in grammatical genetic programming (GP) which create algorithms that control the base station pilot power in a femtocell network. The overall goal of evolving algorithms for femtocells is to create a continuous online evolution of the femtocell pilot power control algorithm in order to optimize their coverage. We compare the performance of different grammars and analyse the femtocell simulation model using the grammatical genetic programming method called grammatical evolution. The grammars consist of conditional statements or mathematical functions as are used in symbolic regression applications of GP, as well as a hybrid containing both kinds of statements. To benchmark and gain further information about our femtocell network simulation model we also perform random sampling and limited enumeration of femtocell pilot power settings. The symbolic regression based grammars require the most configuration of the evolutionary algorithm and more fitness evaluations, whereas the conditional statement grammar requires more domain knowledge to set the parameters. The content of the resulting femtocell algorithms shows that the evolutionary computation (EC) methods are exploiting the assumptions in the model. The ability of EC to exploit bias in both the fitness function and the underlying model is vital for identifying the current system and improves the model and the EC method. Finally, the results show that the best fitness and engineering performances for the grammars are similar over both test and training scenarios. In addition, the evolved solutions’ performance is superior to those designed by humans.     

Local and global optimization for Takagi–Sugeno fuzzy system by memetic genetic programming

This work presents a method to incorporate standard neuro-fuzzy learning for Takagi–Sugeno fuzzy systems that evolve under a grammar driven genetic programming (GP) framework. This is made possible by introducing heteroglossia in the functional GP nodes, enabling them to switch behavior according to the selected learning stage. A context-free grammar supports the expression of arbitrarily sized and composed fuzzy systems and guides the evolution. Recursive least squares and backpropagation gradient descent algorithms are used as local search methods. A second generation memetic approach combines the genetic programming with the local search procedures. Based on our experimental results, a discussion is included regarding the competitiveness of the proposed methodology and its properties. The contributions of the paper are: (i) introduction of an approach which enables the application of local search learning for intelligent systems evolved by genetic programming, (ii) presentation of a model for memetic learning of Takagi–Sugeno fuzzy systems, (iii) experimental results evaluating model variants and comparison with state-of-the-art models in benchmarking and real-world problems, (iv) application of the proposed model in control.     

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

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

Evolution of superFeatures through genetic programming

Abstract: The success of automatic classification is intricately linked with an effective feature selection. Previous studies on the use of genetic programming (GP) to solve classification problems have highlighted its benefits, principally its inherent feature selection (a process that is often performed independent of a learning method). In this paper, the problem of classification is recast as a feature generation problem, where GP is used to evolve programs that allow non‐linear combination of features to create superFeatures, from which classification tasks can be achieved fairly easily. In order to generate superFeatures robustly, the binary string fitness characterization along with the comparative partner selection strategy is introduced with the aim of promoting optimal convergence. The techniques introduced are applied to two illustrative problems first and then to the real‐world problem of audio source classification, with competitive results.     

DOM/XML-based portable genetic representation of the morphology,behavior and communication abilities of evolvable agents

This article presents the results of our work on the role of genetic representation in facilitating the quick design of efficiently running offline learning via genetic programming (GP). An approach using the widely adopted document object model/extensible mark-up language (DOM/XML) standard for the representation of genetic programs, and off-the-shelf DOM-parsers with built-in application programming interface (API) for manipulating them is proposed. This approach means a significant reduction in time in the usually slow software engineering of GP, and offers a generic way to facilitate the reduction of computational effort by limiting the search space of genetic programming by handling only semantically correct genetic programs. The concept is accomplished through strongly typed genetic programming (STGP), in which the use of W3C-recommended standard XML schema is proposed as a generic way to represent and impose the grammar rules in STGP. The ideas laid in the foundation of the proposed approach are verified by the implementation of GP in the evolving social behavior of agents in predator–prey pursuit problems.This work was presented in part at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24–26, 2003     

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.     

An Analysis of the Causes of Code Growth in Genetic Programming

This research examines the cause of code growth (bloat) in genetic programming (GP). Currently there are three hypothesized causes of code growth in GP: protection, drift, and removal bias. We show that single node mutations increase code growth in evolving programs. This is strong evidence that the protective hypothesis is correct. We also show a negative correlation between the size of the branch removed during crossover and the resulting change in fitness, but a much weaker correlation for added branches. These results support the removal bias hypothesis, but seem to refute the drift hypothesis. Our results also suggest that there are serious disadvantages to the tree structured programs commonly evolved with GP, because the nodes near the root are effectively fixed in the very early generations.     

Applying Dynamic Training‐Subset Selection Methods Using Genetic Programming for Forecasting Implied Volatility

Volatility is a key variable in option pricing, trading, and hedging strategies. The purpose of this article is to improve the accuracy of forecasting implied volatility using an extension of genetic programming (GP) by means of dynamic training‐subset selection methods. These methods manipulate the training data in order to improve the out‐of‐sample patterns fitting. When applied with the static subset selection method using a single training data sample, GP could generate forecasting models, which are not adapted to some out‐of‐sample fitness cases. In order to improve the predictive accuracy of generated GP patterns, dynamic subset selection methods are introduced to the GP algorithm allowing a regular change of the training sample during evolution. Four dynamic training‐subset selection methods are proposed based on random, sequential, or adaptive subset selection. The latest approach uses an adaptive subset weight measuring the sample difficulty according to the fitness cases' errors. Using real data from S&P500 index options, these techniques are compared with the static subset selection method. Based on mean squared error total and percentage of non‐fitted observations, results show that the dynamic approach improves the forecasting performance of the generated GP models, especially those obtained from the adaptive‐random training‐subset selection method applied to the whole set of training samples.     

Scaling of program functionality

The distribution of fitness values (landscapes) of programs tends to a limit as the programs get bigger. We use Markov chain convergence theorems to give general upper bounds on the length of programs needed for convergence. How big programs need to be to approach the limit depends on the type of the computer they run on. We give bounds (exponential in N, N log N and smaller) for five computer models: any, average or amorphous or random, cyclic, bit flip and four functions (AND, NAND, OR and NOR). Programs can be treated as lookup tables which map between their inputs and their outputs. Using this we prove similar convergence results for the distribution of functions implemented by linear computer programs. We show most functions are constants and the remainder are mostly parsimonious. The effect of ad-hoc rules on genetic programming (GP) are described and new heuristics are proposed. We give bounds on how long programs need to be before the distribution of their functionality is close to its limiting distribution, both in general and for average computers. The computational importance of destroying information is discussed with respect to reversible and quantum computers. Mutation randomizes a genetic algorithm population in generations. Results for average computers and a model like genetic programming are confirmed experimentally.     

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

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

Application of genetic programming for multicategory patternclassification

Explores the feasibility of applying genetic programming (GP) to multicategory pattern classification problem. GP can discover relationships and express them mathematically. GP-based techniques have an advantage over statistical methods because they are distribution-free, i.e., no prior knowledge is needed about the statistical distribution of the data. GP also automatically discovers the discriminant features for a class. GP has been applied for two-category classification. A methodology for GP-based n-class classification is developed. The problem is modeled as n two-class problems, and a genetic programming classifier expression (GPCE) is evolved as a discriminant function for each class. The GPCE is trained to recognize samples belonging to its own class and reject others. A strength of association (SA) measure is computed for each GPCE to indicate the degree to which it can recognize samples of its own class. SA is used for uniquely assigning a class to an input feature vector. Heuristic rules are used to prevent a GPCE with a higher SA from swamping one with a lower SA. Experimental results are presented to demonstrate the applicability of GP for multicategory classification, and they are found to be satisfactory. We also discuss the various issues that arise in our approach to GP-based classification, such as the creation of training sets, the role of incremental learning, and the choice of function set in the evolution of GPCE, as well as conflict resolution for uniquely assigning a class