Problem Difficulty and Code Growth in Genetic Programming

This paper investigates the relationship between code growth and problem difficulty in genetic programming. The symbolic regression problem domain is used to investigate this relationship using two different types of increased instance difficulty. Results are supported by a simplified model of genetic programming and show that increased difficulty induces higher selection pressure and less genetic diversity, which both contribute toward an increased rate of code growth.     

Selection Based on the Pareto Nondomination Criterion for Controlling Code Growth in Genetic Programming

The rapid growth of program code is an important problem in genetic programming systems. In the present paper we investigate a selection scheme based on multiobjective optimization. Since we want to obtain accurate and small solutions, we reformulate this problem as multiobjective optimization. We show that selection based on the Pareto nondomination criterion reduces code growth and processing time without significant loss of solution accuracy.     

遗传归纳逻辑程序设计的个体编码生长现象

遗传归纳逻辑程序设计(GILP)的个体编码生长现象严重影响了算法的性能和规则的可读性．通过对变长编码的模式分析，解释了GILP的个体编码生长现象．并发现，若从初始种群开始添加长度惩罚项来解决个体编码生长问题，种群会出现退化现象．而采取在演化的初期不添加惩罚项，在种群的性状有了明显改善后再添加惩罚的策略，既可避免种群退化，又可有效解决个体编码生长问题．     

Genetic Programming Experiments with Standard and Homologous Crossover Methods

While successful applications have been reported using standard GP crossover, limitations of this approach have been identified by several investigators. Among the most compelling alternatives to standard GP crossover are those that use some form of homologous crossover, where code segments that are exchanged are structurally or syntactically aligned in order to preserve context and worth. This paper reports the results of an empirical comparison of GP using standard crossover methods with GP using homologous crossover methods. Ten problems are tested, five each of pattern recognition and regression.Results suggest that in terms of generalization accuracy, homologous crossover does generate consistently better performance. In addition, there is a consistently lower fraction of introns that are generated in the solution code.     

Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

A few schema theorems for genetic programming (GP) have been proposed in the literature in the last few years. Since they consider schema survival and disruption only, they can only provide a lower bound for the expected value of the number of instances of a given schema at the next generation rather than an exact value. This paper presents theoretical results for GP with one-point crossover which overcome this problem. First, we give an exact formulation for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Due to this formulation we are then able to provide an improved version of an earlier GP schema theorem in which some (but not all) schema creation events are accounted for. Then, we extend this result to obtain an exact formulation in terms of macroscopic quantities which makes all the mechanisms of schema creation explicit. This theorem allows the exact formulation of the notion of effective fitness in GP and opens the way to future work on GP convergence, population sizing, operator biases, and bloat, to mention only some of the possibilities.     

Size Fair and Homologous Tree Crossovers for Tree Genetic Programming

Size fair and homologous crossover genetic operators for tree based genetic programming are described and tested. Both produce considerably reduced increases in program size (i.e., less bloat) and no detrimental effect on GP performance.GP search spaces are partitioned by the ridge in the number of program v. their size and depth. While search efficiency is little effected by initial conditions, these do strongly influence which half of the search space is searched. However a ramped uniform random initialization is described which straddles the ridge.With subtree crossover trees increase about one level per generation leading to subquadratic bloat in program length.     

一种改进的遗传规划算法

遗传规划的实质是用广义的层次化计算机程序描述问题．比较适合于求解一类由于各种不确定因素导致的复杂非线性问题。该文采用了一种改进的遗传规划算法,建立了相应的预测模型,将其与Weka里的GP算法在标准数据集上进行对比测试,结果表明该改进的遗传规划算法是有效的、可行的。     

遗传程序设计的精确模式理论进展

1.引言从传统意义上来讲,模式定理是用来解释遗传算法是怎样进化的。模式定理可被看成是遗传算法的宏观模型,这就意味着它可以根据当前代测得的宏观量(模式适应度、种群适应度、模式中个体数量等)来确定下一代种群的属性。这些与微观模型形成鲜明对比的宏观量隐含了大量遗传算法自由度信息,由它们可以推导出易于理解和研究的等式。对传统GP模式定理的争论焦点是它们仅提供了在下一代模式H实例数量期望值的下界E[m(H,t 1)],而不是一     

An Evaluation of EvolutionaryGeneralisation in Genetic Programming

Generalisation is one of the most important performance evaluationcriteria for artificial learning systems. An increasing amount ofresearch has recently concentrated on the robustness or generalisationability of the programs evolved using Genetic Programming (GP). Whilesome of these researchers report on the brittleness of the solutionsevolved, some others propose methods of promotingrobustness/generalisation. In this paper, a review of research ongeneralisation in GP and problems with brittleness of solutions producedby GP is presented. Also, a brief overview of several new methodspromoting robustness/generalisation of the solutions produced by GP arepresented.     

Classification of electroencephalogram signal for the detection of epilepsy using Innovative Genetic Programming

Epilepsy, sometimes called seizure disorder, is a neurological condition that justifies itself as a susceptibility to seizures. A seizure is a sudden burst of rhythmic discharges of electrical activity in the brain that causes an alteration in behaviour, sensation, or consciousness. It is essential to have a method for automatic detection of seizures, as these seizures are arbitrary and unpredictable. A profound study of the electroencephalogram (EEG) recordings is required for the accurate detection of these epileptic seizures. In this study, an Innovative Genetic Programming framework is proposed for classification of EEG signals into seizure and nonseizure. An empirical mode decomposition technique is used for the feature extraction followed by genetic programming for the classification. Moreover, a method for intron deletion, hybrid crossover, and mutation operation is proposed, which are responsible for the increase in classification accuracy and a decrease in time complexity. This suggests that the Innovative Genetic Programming classifier has a potential for accurately predicting the seizures in an EEG signal and hints on the possibility of building a real‐time seizure detection system.     

遗传编程运行期个体多样性分析方法及应用

文中根据遗传算法理论分析了遗传编程中种群多样性对算法收敛特性的影响,提出了一种可行的种群多样性跟踪评测方法,同时提出了优选父代个体的改进方法。以求解旅行商问题为例,通过统计性实验数据验证了改进后的算法较采用同样局部优化的常规遗传算法具有更好的收敛速度和优化解,同时也对改进后算法的相关控制参数选择进行了实验分析,结论为改进算法能获得更好的收敛性能。     

An Empirical Study of Multipopulation Genetic Programming

This paper presents an experimental study of distributed multipopulation genetic programming. Using three well-known benchmark problems and one real-life problem, we discuss the role of the parameters that characterize the evolutionary process of standard panmictic and parallel genetic programming. We find that distributing individuals between subpopulations offers in all cases studied here an advantage both in terms of the quality of solutions and of the computational effort spent, when compared to single populations. We also study the influence of communication patterns such as the communication topology, the number of individuals exchanged and the frequency of exchange on the evolutionary process. We empirically show that the topology does not have a marked influence on the results for the test cases studied here, while the frequency and number of individuals exchanged are related and there exists a suitable range for those parameters which is consistently similar for all the problems studied.     

The Darwinian Genetic Code: An Adaptation for Adapting?

The genetic code is a ubiquitous interface between inert genetic information and living organisms, as such it plays a fundamental role in defining the process of evolution. There have been many attempts to identify features of the code that are themselves adaptations. So far, the strongest evidence for an adaptive code is that the assignments of amino acids (encoded objects) to codons (coding units) appear to be organized so as to minimize the change in amino acid hydrophobicity that results from random mutations. One possibility not previously discussed is that this feature of the code may in fact represent an adaptation to maximize the efficiency of adaptive evolution, particularly given the maximized connectedness of protein fitness landscapes afforded by the redundancy of the code.     

Genetic Programming and Autoconstructive Evolution with the Push Programming Language

Push is a programming language designed for the expression of evolving programs within an evolutionary computation system. This article describes Push and illustrates some of the opportunities that it presents for evolutionary computation. Two evolutionary computation systems, PushGP and Pushpop, are described in detail. PushGP is a genetic programming system that evolves Push programs to solve computational problems. Pushpop, an autoconstructive evolution system, also evolves Push programs but does so while simultaneously evolving its own evolutionary mechanisms.     

遗传规划中近似函数的求解问题

文中给出了两个测试例子以及它们的结果,提出了一种在给定区间以及给定运算符集合和终止符集合下求解近似函数的遗传规划方法,它在传统遗传算法的基础上克服了传统遗传算法中染色体必须是0,1二进制位串的缺点。通过这种方法,可以把遗传算法应用于更广泛的领域。     

遗传编程实现的研究

本文指出了遗传编程中的几个关键步骤，针对遗传编程的特点，提出实现的不同方法。并提出了一个通用的模型，以虚拟机来提高遗传编程的效率。     

Biomimetic Representation with Genetic Programming Enzyme

The standard parse tree representation of genetic programming, while a good choice from a generative viewpoint, does not capture the variational demands of evolution. This paper addresses the issue of whether representations in genetic programming might be improved by mimicry of biological behaviors, particularly those thought to be important in the evolution of metabolic pathways, the ‘computational’ structures of the cell. This issue is broached through a presentation of enzyme genetic programming, a form of genetic programming which uses a biomimetic representation. Evaluation upon problems in combinational logic design does not show any significant performance advantage over other approaches, though does demonstrate a number of interesting behaviors including the preclusion of bloat. An erratum to this article can be found at     

遗传算法程序的模块化设计

随着优化问题的复杂化和优化对象的多样化，对优化方法的主要实现形式－计算机程序设计提出了更高的要求，这里分析了一种进化算法－遗传算法特点，给出一种通用性与计算效率并重的模块化程序设计方法，在不同类型的优化问题中均能取得性能良好的解，在工程计算领域有很强的应用价值，目前已应用于网络图优化，生产作业排序等方面。     

编程现场上下文深度感知的代码行推荐

在软件开发的编程现场,有大量与当前开发任务相关的信息,比如代码上下文信息、用户开发意图等.如果能够根据已有的编程现场上下文给开发人员推荐当前代码行,不仅能够帮助开发人员更好地完成开发任务,还能提高软件开发的效率.而已有的一些方法通常是进行代码修复或者补全,又或者只是基于关键词匹配的搜索方法,很难达到推荐完整代码行的要求.针对上述问题,一种可行的解决方案是基于已有的海量源码数据,利用深度学习析取代码行的相关上下文因子,挖掘隐含的上下文信息,为精准推荐提供基础.因此,提出了一种基于深度学习的编程现场上下文深度感知的代码行推荐方法,能够在已有的大规模代码数据集中学习上下文之间潜在的关联关系,利用编程现场已有的源码数据和任务数据得到当前可能的代码行,并推荐Top-N给编程人员.代码行深度感知使用RNN Encoder-Decoder,该框架能够将编程现场已有的若干行上文代码行进行编码,得到一个包含已有代码行上下文信息的向量,然后根据该向量进行解码,得到预测的Top-N代码行输出.利用在开源平台上收集的大规模代码行数据集,对方法进行实验并测试,结果显示,该方法能够根据已有的上下文推荐相关的代码行给开发人员,Top-10的推荐准确率有60%左右,并且MRR值在0.3左右,表示用户满意的推荐项排在N个推荐结果中比较靠前的位置.     

Reinforced Genetic Programming

This paper introduces the Reinforced Genetic Programming (RGP) system, which enhances standard tree-based genetic programming (GP) with reinforcement learning (RL). RGP adds a new element to the GP function set: monitored action-selection points that provide hooks to a reinforcement-learning system. Using strong typing, RGP can restrict these choice points to leaf nodes, thereby turning GP trees into classify-and-act procedures. Then, environmental reinforcements channeled back through the choice points provide the basis for both lifetime learning and general GP fitness assessment. This paves the way for evolutionary acceleration via both Baldwinian and Lamarckian mechanisms. In addition, the hybrid hints of potential improvements to RL by exploiting evolution to design proper abstraction spaces, via the problem-state classifications of the internal tree nodes. This paper details the basic mechanisms of RGP and demonstrates its application on a series of static and dynamic maze-search problems.