GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Weaknesses <s> Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems that straddle the breakeven point for computational effort Boolean parity functions determining the architecture of the program the lawnmower problem the bumblebee problem the increasing benefits of ADFs as problems are scaled up finding an impulse response function artificial ant on the San Mateo trail obstacle-avoiding robot the minesweeper problem automatic discovery of detectors for letter recognition flushes and four-of-a-kinds in a pinochle deck introduction to biochemistry and molecular biology prediction of transmembrane domains in proteins prediction of omega loops in proteins lookahead version of the transmembrane problem evolutionary selection of the architecture of the program evolution of primitives and sufficiency evolutionary selection of terminals evolution of closure simultaneous evolution of architecture, primitive functions, terminals, sufficiency, and closure the role of representation and the lens effect. Appendices: list of special symbols list of special functions list of type fonts default parameters computer implementation annotated bibliography of genetic programming electronic mailing list and public repository. <s> BIB001 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Weaknesses <s> Grammatical Evolution (GE) is an evolutionary system that employs variable length linear chromosomes to represent computer programs. GE uses the individuals to produce derivation trees that adhere to a Backus Naur Form grammar, which are then mapped onto a program. One unusual characteristic of the system is the manner in which chromosomes can be "wrapped", that is, if an individual has used up all of its genes before a program is completely mapped, the chromosome is reread. While this doesn't guarantee that an individual will map, prior work suggested that wrapping is beneficial for the system, both in terms of increased success rates and a reduced number of invalid individuals. However, there has been no research into the number of times an individual should be wrapped before the system gives up, and an arbitrary upper limit is usually chosen. ::: ::: This paper discusses the different types of grammars that could be used with this system, and indicates the circumstances under which individuals will fail. It then presents a heuristic to minimize the number of wraps that have to be made before the system can determine that an individual will fail. It is shown that this can drastically reduce the amount of wrapping on a pathologically difficult problem, as well as on two classes of grammar often used by the system. <s> BIB002
An important LGP parameter is the number of registers (or variables) used by a chromosome. This number is usually equal to the number of attributes of the problem. If the problem has only one attribute, it is impossible to obtain a complex expression such as the quartic polynomial BIB001 . In that case, we have to use several supplementary registers (variables). The number of supplementary registers (variables) depends on the complexity of the expression being discovered. An inappropriate choice of the number of registers(variables) may lead to poor results. GEP, as it was described in the original paper, uses a multigenic representation. There are some problems regarding multigenic chromosomes. Generally, it is not a good idea to assume that the genes may be linked either by addition or by multiplication. Providing a particular linking operator means providing partial information to the expression that is being discovered. However, if other additional operators (such as −, /) are used as linking operators, then the complexity of the problem substantially grows (since the problem of determining how to mix these operators with the genes is as difficult as the initial problem). Furthermore, the number of genes in the GEP multigenic chromosome raises a problem. As it can be seen in 5 , the success rate of GEP increases with the number of genes in the chromosome. However, after a certain value, the success rate decreases if the number of genes in the chromosome is increased. This happens because we cannot force a complex chromosome to encode a less complex expression. A large part of the chromosome is unused if the target expression is short and the head length is large. Note that this problem usually arises in systems that employ chromosomes with a fixed length.  There are problems where the complexity of the MEP decoding process is higher than the complexity of the GE, GEP, and LGP decoding processes. This situation usually arises when the set of training data is not a priori known (e.g., when game strategies are evolved). The GE mapping process also has some disadvantages. Wrapping may never end in some situations. For instance, consider the G GE grammar defined earlier in the first example. In this case the chromosome C GE = 0, 0, 0, 0, 0 cannot be translated into a valid expression because it does not contain operands. In order to prevent infinite cycling, a fixed number of wrapping occurrences is allowed. If this threshold is exceeded the expression obtained is incorrect and the corresponding individual is considered to be invalid. Several strategies for avoiding the generation of invalid computer programs due to infinite wrapping have been investigated in BIB002 . The inappropriate choice for the number of columns required by the CGP chromosome might lead to poor results. For instance if the number of columns is set to 1 we can have only simple solutions (made up of a single function with its arguments). This is why the number of columns should be big enough. In the stack-GP system there is no mechanism for allowing branching program execution. There are many problems for which branching execution is not necessary. But in many problems of planning and strategy the side effects of functions are of primary importance, and the actual sequence of the program execution is of interest rather than the final calculated result 42 . 