Emergence in genetic programming

Banzhaf explores the concept of emergence and how and where it happens in genetic programming [1]. Here we consider the question: what shall we do with it? We argue that given our ultimate goal to produce genetic programming systems that solve new and difficult problems, we should take advantage of emergence to get closer to this goal.     

Population variation in genetic programming

A new population variation approach is proposed, whereby the size of the population is systematically varied during the execution of the genetic programming process with the aim of reducing the computational effort compared with standard genetic programming (SGP). Various schemes for altering population size under this proposal are investigated using a comprehensive range of standard problems to determine whether the nature of the “population variation”, i.e. the way the population is varied during the search, has any significant impact on GP performance. The initial population size is varied in relation to the initial population size of the SGP such that the worst case computational effort is never greater than that of the SGP. It is subsequently shown that the proposed population variation schemes do have the capacity to provide solutions at a lower computational cost compared with the SGP.     

Repeated patterns in genetic programming

Evolved genetic programming trees contain many repeated code fragments. Size fair crossover limits bloat in automatic programming, preventing the evolution of recurring motifs. We examine these complex properties in detail using depth vs. size Catalan binary tree shape plots, subgraph and subtree matching, information entropy, sensitivity analysis, syntactic and semantic fitness correlations. Programs evolve in a self-similar fashion, akin to fractal random trees, with diffuse introns. Data mining frequent patterns reveals that as software is progressively improved a large proportion of it is exactly repeated subtrees as well as exactly repeated subgraphs. We relate this emergent phenomenon to building blocks in GP and suggest GP works by jumbling subtrees which already have high fitness on the whole problem to give incremental improvements and create complete solutions with multiple identical components of different importance.     

Granularity issues in a knowledge-based programming environment

Marvel is a knowledge-based programming environment that assists software development teams in performing and coordinating their activities. While designing Marvel, several granularity issues were discovered that have a strong impact on the degree of intelligence that can be exhibited, as well as on the friendliness and performance of the environment. The most significant granularity issues include the refinement of software entities in the software database and decomposition of the software tools that process the entities and report their results to the human users. This paper describes the many alternative granularities and explains the choices made for Marvel.     

Hoare logic-based genetic programming

Almost all existing genetic programming systems deal with fitness evaluation solely by testing. In this paper, by contrast, we present an original approach that combines genetic programming with Hoare logic with the aid of model checking and finite state automata, henceby proposing a brand new verification-focused formal genetic programming system that makes it possible to evolve reliable programs with mathematically-verified properties.     

Dynamic population variation in genetic programming

Three innovations are proposed for dynamically varying the population size during the run of the genetic programming (GP) system. These are related to what is called Dynamic Population Variation (DPV), where the size of the population is dynamically varied using a heuristic feedback mechanism during the execution of the GP with the aim of reducing the computational effort compared with Standard Genetic Programming (SGP). Firstly, previously developed population variation pivot functions are controlled by four newly proposed characteristic measures. Secondly, a new gradient based pivot function is added to this dynamic population variation method in conjunction with the four proposed measures. Thirdly, a formula for population variations that is independent of special constants is introduced and evaluated. The efficacy of these innovations is examined using a comprehensive range of standard representative problems. It is shown that the new ideas do have the capacity to provide solutions at a lower computational cost compared with standard genetic programming and previously reported algorithms such as the plague operator and the static population variation schemes previously introduced by the authors.     

Current issues in programming language standardisation: IV

This paper looks at issues of standardisation in the general field of programming languages as current at September 1983.     

Current issues in programming language standardisation: II

This paper looks at issues of standardisation in the general field of programming languages as current at September 1983.     

Neutral offspring controlling operators in genetic programming

Code bloat, one of the main issues of genetic programming (GP), slows down the search process, destroys program structures, and exhausts computer resources. To deal with these issues, two kinds of neutral offspring controlling operators are proposed—non-neutral offspring (NNO) operators and non-larger neutral offspring (NLNO) operators. Two GP benchmark problems—symbolic regression and 11-multiplexer—are used to test the new operators. Experimental results indicate that NLNO is able to confine code bloat significantly and improve performance simultaneously, which NNO cannot do.     

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

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

Representation and structural difficulty in genetic programming

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.     

Applying genetic programming technique in classification trees

Classification problems are often encountered in many applications. In the past, classification trees were often generated by decision-tree methods and commonly used to solve classification problems. In this paper, we have proposed an algorithm based on genetic programming to search for an appropriate classification tree according to some criteria. The classification tree obtained can be transferred into a rule set, which can then be fed into a knowledge base to support decision making and facilitate daily operations. Two new genetic operators, elimination and merge, are designed in the proposed approach to remove redundancy and subsumption, thus producing more accurate and concise decision rules than that without using them. Experimental results from the credit card data also show the feasibility of the proposed algorithm.     

Functional search in economics using genetic programming

This paper discusses economic applications of a recently developed artificial intelligence technique-Koza's genetic programming (GP). GP is an evolutionary search method related to genetic algorithms. In GP, populations of potential solutions consist of executable computer algorithms, rather than coded strings. The paper provides an overview of how GP works, and illustrates with two applications: solving for the policy function in a simple optimal growth model, and estimating an unusual regression function. Results suggest that the GP search method can be an interesting and effective tool for economists.