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.     

开放尾部的基因表达式程序设计

基因表达式程序设计（GEP）的染色体由具有特殊限制的头、尾组成,并要求尾部符号严格取自基本的终端集。这一做法作用明了、易于表述,基本为现有GEP所采纳,但不利于语义计算的重用。谋求突破尾部限制条件,探究一种开放尾部的新型GEP算法。该算法将运行过程产生的优良个体动态地引入种群个体的基因,从而实现运算精度的提升。符号回归实验表明,开放尾部的GEP算法在平均精度性能上要优于主流GEP方法。     

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.     

Representational issues in genetic optimization

Abstract

Functions are partially characterized as easy or hard for genetic algorithms to optimize. The failure modes of inappropriate embedding, crossover disruption, and deceptiveness are introduced, analyzed, and resolved in part. Virtually all optimizable (by any method) real valued functions defined on a finite domain are shown to be theoretically easy for genetic algorithms given appropriately chosen representations. Unfortunately, problems that are easy in theory can be difficult in practice because of sampling error. Also, the transformations required to induce favorable representations are generally arbitrary permutations, and the space of permutations is so large that search for good ones is intractable. The space of inversions is amenable to search, but inversions are insufficiently powerful to overcome deceptiveness. On the other hand, affine transformations (over the diadic group) are shown to be sufficiently powerful to transform at least selected deceptive problems into easy ones. These new results should be useful in guiding empirical studies and are expected to provide a foundation for further theoretical analysis.     

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.     

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: I

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

遗传规划中遗传算子对种群多样性的影响

为了能有效地避免过早收敛并跳出局部最优,提出了一种改进的遗传规划算法来研究遗传算子（选择、交叉和变异）对种群多样性（主要是基因型和表现型）的影响。首先在基准问题（奇偶校验和符号回归中的四次多项式函数）中比较不同的遗传算子在离散和连续的适应度空间中的搜索寻优,然后使用斯皮尔曼相关系数来度量种群多样性与适应度的相关性。结果表明选择和交叉算子极大地减少了种群多样性,变异算子则能维持甚至提高种群多样性,这说明通过控制遗传算子来改变种群多样性从而找到最优个体是可行的。     

新的线性遗传程序设计方法

受其他多种线性编码的遗传程序设计算法的启发,提出一种新的编码方式的遗传程序设计——符号遗传程序设计。该编码方式具有简单、无语法限制并且能够在不增加计算量的情况下将染色体翻译成多个表达式等特点。分析与实验表明该算法具有较高的效率和较强的稳定性。