GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <s> The question of efficient translation between an "orthodox" mathematical notation of the kind ordinarily used in writing algebraic formulae (and copied as closely as is practicable in FORTRAN and ALGOL) and "Polish" notation has come to prominence as a result of the use of what is in effect Polish notation as the basic instruction language of two recent computers.* Polish notation is so-called because of its extensive use in Polish logical writings since its invention by -Lukasiewicz (1921, 1929). -Lukasiewicz demonstrated that if operators are written always in front of their operands, instead of (as in the case of the diadic operators of arithmetic, " + ", "—", " x " and so on) between them, there is never any need for brackets to indicate association of terms. Thus if in place of "a -fb" we write " + a b", and so on, the brackets in an expression such as "(a + b) X c" may be dispensed with in translation, since " X + a b c" indicates unambiguously the result of operating with " x " on "-\-ab" and "c": for "a + (b X c)" we should instead write " + a X b c." The resulting notation, in the case of long formulae, is a little harder to read, since brackets aid the eye, but it has some other advantages. In particular Reverse Polish—the notation which results if operators are placed after operands, as in "a b +"—has the property that the operators appear in the order in which they are required in computation. Reverse Polish is hence in some sense a natural notation for an instruction language, each symbol being interpretable as an instruction. (Number variables are "fetch" instructions.) The absence of brackets further makes Polish notation (— either Forward or Reverse, but probably preferably Forward—) useful in mechanized algebra, since it eliminates a continual source of complication in algebraic manipulations. <s> BIB001 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <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> BIB002 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <s> We describe a Genetic Algorithm that can evolve complete programs. Using a variable length linear genome to govern how a Backus Naur Form grammar definition is mapped to a program, expressions and programs of arbitrary complexity may be evolved. Other automatic programming methods are described, before our system, Grammatical Evolution, is applied to a symbolic regression problem. <s> BIB003 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <s> We describe a Genetic Algorithm that can evolve complete programs. Using a variable length linear genome to govern the mapping of a Backus Naur Form grammar definition to a program, expressions and programs of arbitrary complexity may be evolved. Our system, Grammatical Evolution, has been applied to problems such as a Symbolic Regression problem, and finding Trigonometric Identities. In this paper we describe how we applied GE to a Symbolic Integration problem, that being finding a function which is an integral of . We also show how a Steady State selection mechanism was found to improve the performance of Grammatical Evolution. <s> BIB004 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <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> BIB005 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <s> Linear Genetic Programming presents a variant of Genetic Programming that evolves imperative computer programs as linear sequences of instructions, in contrast to the more traditional functional expressions or syntax trees. Typical GP phenomena, such as non-effective code, neutral variations, and code growth are investigated from the perspective of linear GP. This book serves as a reference for researchers; it includes sufficient introductory material for students and newcomers to the field. <s> BIB006 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Representation <s> This paper describes three developments to improve object detection performance using genetic programming. The first investigates three feature sets, the second investigates a new fitness function,... <s> BIB007
An LGP individual is represented by a variable-length sequence of simple C language instructions. Instructions operate on one or two indexed variables v (also called registers) or on constants c from predefined sets. The result is assigned to a destination register. Single operations may be skipped by preceding conditional branches, e.g., if (r j > r k ). Some examples of LGP instructions are given below: operating on one register and one constant Example. An example of the LGP program is the following: The initial values for the variables v[0] ... v  are set to the value of inputs or to some numerical constants. After executing the program encoded into an LGP chromosome the output will be stored into a destination register. This register is usually chosen at the beginning of the search process and is kept unchanged until the end. It can be seen that not all the variables (registers) are effective (contribute to the final result). The usefulness of each register depends on the register chosen to provide the output of the program. Suppose that in the previously described chromosome the output is provided by the register v BIB002 . The last effective instruction (that modifies this register) is v BIB002 BIB007 . Now we have to search for the previous instructions that have changed the value of registers v[0] and v BIB003 . v [0] has not been changed, so we look for v BIB003 . This instruction is v BIB003 = v  * v BIB007 . The process continues until we have found the effective code for this program: The size of the effective code varies between 0 and the number of instructions in the LGP chromosome. A chromosome is a string of instructions. Each instruction is encoded as where op index is an integer that represent an index from the set of functions, while out register, in register 1 and in register 2 represent indexes from the set of registers (in our example a number between 0 an 10). The corresponding chromosome for our example program is: BIB007  BIB006 BIB005 , BIB005 BIB007 BIB006 , (2, BIB003  BIB007 , (0, 9, 0, 7)) ( * , v BIB003 , v  , v BIB007 ), (+, v[9] , v[0], v BIB003 )) If we consider that the first three registers contain the values a, b and c, then the chromosome C encodes the expression a + b c−a * sin(b).  Each GE individual is a variable length binary string that contains in its codons (groups of 8 bits) the necessary information for selecting a production rule from a BNF grammar. A BNF grammar consists of a terminal and a non-terminal set of symbols, a set of production rules and a start symbol. Grammar symbols may be re-written, using allgp Genetic Programming with linear representation: a survey 17 production rules, in other terminal and non-terminal symbols. An example from a BNF grammar is given by the following production rules BIB003 BIB004 : These production rules state that the start symbol S can be replaced (re-written) by either one of the non-terminals: expr, if -stmt, or by loop. The grammar is used in a generative process in order to construct a program by applying the production rules given by the genome, beginning with the starting symbol of the grammar. In order to select a GE production rule, the next codon value on the genome is generated and used in the following formula: Rule Index = Codon V alue mod N um Rules. If the next Codon Value is 4, knowing that we have 3 rules to select from, as in the example above, we get 4 mod 3 = 1. Therefore, S will be replaced with the non-terminal if-stmt, corresponding to the second production rule. Beginning from the left side of the genome codon, integer values are generated and used for selecting rules from the BNF grammar, until one of the following situations arises: (i) A complete program is generated. This occurs when all the non-terminals in the expression being mapped are turned into elements from the terminal set of the BNF grammar. Some genes might remain unexpressed in some cases. (ii) The end of the genome is reached, in which case the wrapping operator is invoked. This means that the following evaluated codon will be the first one and the evaluation process is restarted from this position. The restarted process continues until a higher threshold that represents the maximum number of wrapping events has occurred during the individual mapping process. In the case that a threshold on the number of wrapping events is exceeded and that the individual is still incompletely mapped, the mapping process is halted and the individual is assigned the worst possible fitness value. Example. Consider the grammar: G = {N, T, S, P }, where the terminal set is: T = {+, −, * , /, sin, (, )} and the nonterminal symbols are: N = {expr, op 2 , op 1 }. The start symbol is S = expr . The production rules P are: An example of a GE chromosome is the following: C GE = (00001001 00001100 00001100 00000011 00001111 00000111 00001011 00000100 00000010 00000101 00000000 00000110 00001011 00000000 00000001 00000111 00001100) . Translated into integer GE codons, the chromosome is: C * GE = (9 12 12 3 15 7 11 4 2 5 0 6 11 0 1 7 12). We can now start to translate this chromosome into a computer program. The start symbol is S = <expr >. We have six possibilities (productions) to choose from. In order to make a choice we read the first gene of the chromosome, which is number 9. This number modulo the number of possibilities will give us the production to choose. In this case the choice is the fourth production (because the productions are indexed starting with 0): 9 mod 6 = 3 . We obtain a new string: expr op 2 expr . We start again with the first nonterminal symbol, <expr >, and we extract the second gene of the chromosome in order to see which production to choose. We have again 6 possibilities and the second gene has value 12. We choose production 12 mod 6 = 0 which is actually the first production. We obtain the string: a op 2 expr . The first nonterminal symbol in this string is op 2 . We have 4 productions for this symbol and the next gene has value 12. Thus we choose rule 12 mod 4 = 0, which indicates the first production for the nonterminal symbol op 2 . The newly obtained string is: a + expr . The next nonterminal is <expr > and we have 6 productions to choose from. According to the next gene we choose production 3 mod 6 = 3 which is the fourth production for the current nonterminal. We obtain the string: a+ expr op 2 expr . Next nonterminal to expand is <expr >. We have 6 possibilities and the next gene which will decide the production has value 15. Thus, we choose the fourth production, 15 mod 6 = 3, and we obtain the string: a+ expr op 2 expr op 2 expr . Now the next nonterminal symbol is <expr > and next value of gene is 1. We choose production 1 mod 6 = 1 which is the second one and we obtain: a + b op 2 expr op 2 expr . By applying the same reasoning we succesivelly obtain the following intermediate expressions: The last nonterminal symbol is expr and the next gene of the GE chromosome has value 1. In this case we have to choose the second production, for this nonterminal, which leads to the expression: Note that in some cases not all the GE genes are used. For instance, in our example we have two genes which were not used, because the translation process was ended after using the first 15 genes (no more nonterminals were available for expanding). The obtained computer program depends on the BNF grammar used for translation. Different grammars (but with similar purposes) lead to different computer programs even if the GE chromosome employed is the same. CGP is Cartesian in the sense that the graph nodes are represented in a Cartesian coordinate system. This representation was chosen due to the node connection mechanism, which is similar to the GP mechanism. A CGP node contains a function symbol and pointers toward nodes representing function parameters. Each CGP node has an output that may be used as an input for another node. A sketch of a CGP node is depicted in Figure 3 . A CGP program is a set of interconnected nodes. Example. An example of a CGP program is depicted in Figure 4 . This program is interpreted as follows: inputs labeled from 0 to 2 are depicted in the left side of the picture. The output of the program is provided by the output of node 13 (as shown in the right side of picture). In order to obtain the set of nodes, which are useful in this architecture, we have to start with node 13, which provides the result of this program. The input 0 and node 11 provide the arguments for the function encoded in this node. We move to node 11 whose inputs are provided by nodes 6 and 8. Inputs of node 6 are provided by nodes 1 and 4 while node 8 is connected to inputs 1 and 0. Node 4 is connected to inputs 2 and 0. In this way, we have obtained the set of nodes, which are used by the program encoded in the chromosome depicted in Figure 4 . Not all the other nodes are used for computing the output of this program. Each CGP program (graph) is defined by several parameters: • number of rows -n r , • number of columns -n c , The nodes interconnectivity is defined as being the number of the previous columns of cells that may have their outputs connected to a node in the current column (the primary inputs are treated as node outputs). This parameter is very important and defines how far two connected nodes can be in the matrix. If nodes' interconnectivity is equal to 1, each node can be connected only with nodes in the previous column. If nodes interconnectivity is equal to the number of rows, we can have a node connected to any other node in the previous columns. The CGP chromosomes are represented, within the computer memory, as arrays of integer values. In order to achieve this we first need to label each function with an integer value (+ = 0, − = 1, * = 2, / = 3, sin = 4) because we want to work with integer strings only. The CGP chromosomes are encoded as strings by reading the graph columns top-down and printing the input nodes and the function symbol for each node. The index of the node (which is given in the bottom-right side of a node) is not printed because this information does not help the search process. Thus, for each node, we print the following information: Genetic operators will modify these genes (providing the output) as all other genes. The programs from a stack-GP system are LISP S-expressions that contain terminals and functions. Unlike the standard GP 11 , in stack-based GP the functions receive arguments from a numerical stack and return their result by pushing it on the stack. Function calls are not nested: programs consist of flat linear sequences of functions and terminals. Terminals are simply a class of functions which push preset variables onto the stack when they are executed. In stack-GP one additional type of closure constraint must be imposed on the functions. If the stack does not contain sufficient elements for applying one of function (with other words, if the stack deep is less than the function arity), then it will do nothing. In the previous example, the operator + from the third position of the chromosome will not be executed because the stack contains only one argument. For instance, the following is an example of a program which encodes the math-  The stack is protected from underflow by this constraint; and stack overflow has not been a problem, and has been limited in practice so far by specifying a maximum allowable program length BIB002 . Numerical calculations are performed in Reverse Polish Notation (RPN) BIB001  . The advantage of RPN in this context is that the parse tree for the calculation is expressed simply by the order of the functions and terminals in the sequence and not by a constrained syntax demanding balanced parentheses.