GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Genetic operators <s> Some recent work in the field of genetic programming (GP) has been concerned with finding optimum representations for evolvable and efficient computer programs. This paper describes a new GP system in which target programs run on a stack-based virtual machine. The system is shown to have certain advantages in terms of efficiency and simplicity of implementation, and for certain problems, its effectiveness is shown to be comparable or superior to current methods. > <s> BIB001 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Genetic operators <s> HiGP is a new high-performance genetic programming system. This system combines techniques from string-based genetic algorithms, S-expression-based genetic programming systems, and high-performance parallel computing. The result is a fast, flexible, and easily portable genetic programming engine with a clear and efficient parallel implementation. HiGP manipulates and produces linear programs for a stack-based virtual machine, rather than the tree-structured S-expressions used in traditional genetic programming. In this paper we describe the HiGP virtual machine and genetic programming algorithms. We demonstrate the system's performance on a symbolic regression problem and show that HiGP can solve this problem with substantially less computational effort than can a traditional genetic programming system. We also show that HiGP's time performance is significantly better than that of a well-written S-expression-based system, also written in C. We further show that our parallel version of HiGP achieves a speedup that is nearly linear in the number of processors, without mandating the use of localized breeding strategies. <s> BIB002 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Genetic operators <s> Grammatical Evolution (GE) is a grammar based GA to generate computer programs which has been shown to be comparable with GP when applied to a diverse array of problems. GE has the distinction that its input is a BNF, which permits it to generate programs in any language, of arbitrary complexity, including loops, multiple line functions etc. Part of the power of GE is that it is closer to natural DNA than GP, and thus can benefit from natural phenomena such as a separation of search and solution spaces through a genotype to phenotype mapping, and a genetic code degeneracy which can give rise to silent mutations(Mutations that have no effect on the phenotype). ::: ::: We have previously shown how runs of GE are competitive with GP, and in this paper we analyse characteristics such as genotypic diversity, and individual genotypic length, in an attempt to shed light on the power of the system. Results indicate that GE can use certain features of the system to its benefit if and when necessary. <s> BIB003 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Genetic operators <s> We introduce a new form of linear genetic programming (GP). Two methods of acceleration of our GP approach are discussed: 1) an efficient algorithm that eliminates intron code and 2) a demetic approach to virtually parallelize the system on a single processor. Acceleration of runtime is especially important when operating with complex data sets, because they are occurring in real-world applications. We compare GP performance on medical classification problems from a benchmark database with results obtained by neural networks. Our results show that GP performs comparably in classification and generalization. <s> BIB004
Variation operators used in conjunction with LGP are crossover and mutation. Both crossover and mutation must handle variable length chromosomes. Crossover. By crossover, continuous sequences of instructions are selected and exchanged between parents. LGP uses two-point string crossover BIB004 . A segment of random starting position and random length is selected in both parents and exchanged between them. If one of the resulting children exceeds the maximum length, crossover is abandoned and restarted by exchanging equally sized segments. Mutation. Two types of mutation are used: micro mutation and macro mutation. By micro mutation, an operand or an operator of an instruction is changed. Macro mutation inserts or deletes a random instruction. As an effect of macro mutation, the size of the LGP chromosome is modified. The GEP technique uses several operators such as crossover, mutation and transposition in order to obtain new individuals. Crossover. In GEP there are three kinds of recombination: one-point, two-point and gene recombination. In all the cases, two parent chromosomes are randomly chosen and paired to exchange some material between them. The one-point and two-point recombination operators in the GEP representation are analogous to the corresponding binary representation operator. Two parents and one, respectively two, cutting-point(s) are chosen. Two offsprings are obtained from the parents, by exchanging genetic material according to the cutting-point(s). In gene recombination, an entire gene is exchanged during crossover. The exchanged genes are randomly chosen and they need to have occupied the same position in the parent chromosomes. The newly created individuals contain genes from both parents. Note that with this kind of recombination, similar genes can be exchanged but, most of the time, the exchanged genes are very different and new material is introduced in the population. Mutation. Mutations can occur anywhere in the chromosome. However, the structural organization of chromosomes must remain intact. In the head, any symbol can change into another (function or terminal); in the tail, terminals can only change into terminals. In this way, the structural organization of the chromosomes is maintained, and all the new individuals produced by mutation are structurally correct programs. Other GEP operators. Some GEP variants use transposition as one of the genetic operators in order to introduce variety in the population. The transposable elements of the GEP chromosome are fragments of the genome that can be activated and jump to another place in the chromosome  . In GEP there are three kinds of transposable elements: (1) short fragments with a function or terminal in the first position that transpose to the head of genes except for the root, (2) short fragments with a function in the first position that transpose to the root of genes, (3) entire genes that transpose to the beginning of the chromosome. The search operators used within the MEP algorithm are crossover and mutation. These search operators preserve the chromosome structure. All the offspring are syntactically correct expressions. Crossover. By crossover, two parents are selected and recombined. Several variants of recombination have been considered for MEP: one-point recombination, two-point recombination and uniform recombination. Mutation. Each symbol (terminal, function of function pointer) in the chromosome may be the target of the mutation operator. Some symbols in the chromosome are changed by mutation. In order to preserve the consistency of the chromosome, its first gene must encode a terminal symbol. If the current gene encodes a terminal symbol, it may be changed into another terminal symbol or into a function symbol. In the latter case, the position(s) indicating the function argument(s) is(are) randomly generated. If the current gene encodes a function, the gene may be mutated into a terminal symbol or into another function (function symbol and pointers towards arguments). We may say that the crossover operator occurs between genes and the mutation operator occurs inside genes. Genetic operators employed by GE are similar to those used in conjunction with binary encoding BIB003 . Other two operators: duplicate and prune have been tested within the GE system 7 . Crossover. Standard GE crossover is similar to the one cutting point crossover employed by the binary encoding. This operator implies the selection of two individuals (the parents). Then two cutting points (one in each individual) are randomly chosen. The segments on the right side of the cutting points are swapped BIB003 . Mutation. Mutation is performed as in the case of binary encoding  . This operator randomly flips some of the bits in a chromosome. Mutation can occur in any position in a chromosome with a small mutation probability. Remark. Some algorithms also used as genetic operators duplicate and prune. By duplication, a randomly chosen sequence of genes is copied into the position of the last gene of the chromosome. The prune operator is usually applied for reducing the number of introns (unused genes 11 ) and thus increasing the likelihood of beneficial crossover. Genes not used in the genotype-phenotype mapping process are discarded by the prune operator 7 . String genetic operators can be used within the CGP system. Nodes supplying the outputs of the entire program (see the right side of Figure 4) are not fixed as they may also be subject to genetic operators. Mutation. The mutation operator requires some special conditions (see the initialization restrictions) to be met. By mutation, some symbols in the current CGP chromosome are modified. Mutation consists of randomly changing one of the integer values in the CGP string of the genotype. Only one value is changed per mutation. A mutation can modify the node function, the node input or the connections in a gene. Since only a part of the genotype is decoded into the phenotype, mutations often do not affect the behavior of a cell. Remark. Although the crossover operator was not used by the CGP technique, it may be applied without any restrictions. Since there are no syntactical constraints on the critter sequences, the genetic operators applied on the stack-GP chromosome could be any of those used in a traditional GA. These string-based genetic operators are applied directly on the linear programs. The safety of the resulting programs was guaranteed by specifying that all the functions take their arguments from the stack. The function calls that occur with too few items on the stack are ignored, doing nothing BIB002 . Therefore, a two-cutting point crossover can be utilized: two points are randomly picked in each of the parents, and one child sequence is created by inserting the sequence enclosed by the points in the father into the space defined by the cuttingpoints in the mother chromosome BIB001 . In addition to crossover, one point mutation, which consists of changing some one function call in the sequence to some other function in the current function set, can be applied because the stack-GP chromosomes can be treated as strings.