GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Multi Expression Programming <s> A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori "head-to-head" minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems' enforcing of a type of uniformity over all algorithms. <s> BIB001 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Multi Expression Programming <s> Finding the optimal parameter setting (i.e. the optimal population size, the optimal mutation probability, the optimal evolutionary model etc) for an Evolutionary Algorithm (EA) is a difficult task. Instead of evolving only the parameters of the algorithm we will evolve an entire EA capable of solving a particular problem. For this purpose the Multi Expression Programming (MEP) technique is used. Each MEP chromosome will encode multiple EAs. An nongenerational EA for function optimization is evolved in this paper. Numerical experiments show the effectiveness of this approach. <s> BIB002 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Multi Expression Programming <s> Multi expression programming (MEP) is a genetic programming (GP) variant that uses linear chromosomes for solution encoding. A unique MEP feature is its ability of encoding multiple solutions of a problem in a single chromosome. These solutions are handled in the same time complexity as other techniques that encode a single solution in a chromosome. In this paper MEP is used for evolving digital circuits. <s> BIB003
Multi Expression Programming (MEP)  BIB002  BIB003 is a GP variant that uses a linear representation of chromosomes. MEP individuals are strings of genes encoding complex computer programs. When MEP individuals encode expressions, their representation is similar to the way in which compilers translate C or Pascal expressions into machine code  . A unique MEP feature is the ability of selecting the best gene to provide the output for the chromosome. This is different from other GP techniques which employ a fixed gene for output. A similar situation is provided by Cartesian GP (see Section 7) where the outputs are evolved in the same manner as all the other symbols in the chromosome. A single parsing of the chromosome can perform evaluation of the expressions encoded into a MEP individual. The offspring obtained by crossover and mutation are always syntactically correct MEP individuals (computer programs). Thus, no extra processing for repairing newly obtained individuals is needed. The MEP representation ensures that no cycle arises while the chromosome is decoded (phenotypically transcripted). According to the MEP representation scheme, the first symbol of the chromosome must be a terminal symbol. In this way, only syntactically correct programs (MEP individuals) are obtained. Example. Consider a representation where the numbers on the left stand for gene labels. Labels do not belong to the chromosome, as they are provided only for explanation purposes. For this example, we use the set of functions: F = {+, −, * , /, sin}, and the set of terminals T = {a, b, c}. An example of a chromosome C using the sets F and T is given below (it encodes the expression a + The maximum number of symbols in the MEP chromosome is given by the formula: where n is the number of arguments of the function with the greatest number of arguments. The maximum number of effective symbols is achieved when each gene (excepting the first one) encodes a function symbol with the highest number of arguments. The minimum number of effective symbols is equal to the number of genes and it is achieved when all the genes encode terminal symbols only. Translation of the MEP chromosome into a valid computer program is done topdown. A terminal symbol specifies a simple expression. A function symbol specifies a complex expression obtained by connecting the operands specified by the argument positions with the current function symbol. For instance, genes 1, 2 and 5 in the previous example encode simple expressions formed by a single terminal symbol. These expressions are: Gene 3 indicates the operation + on the operands located at positions 1 and 2 of the chromosome. Therefore, gene 3 encodes the expression: Gene 4 indicates the operation sin on the operand located at position 2 . Therefore, gene 4 encodes the expression: Gene 6 indicates the operation − on the operands located at positions 5 and 1 . Therefore, gene 6 encodes the expression: Gene 7 indicates the operation / on the operands located at position 2 and 3. Therefore, this gene encodes the expression: Gene 8 indicates the operation / on the operands located at position 2 and 6. Therefore, this gene encodes the expression: Gene 9 indicates the operation * on the operands located at positions 8 and 4 of the chromosome. Therefore, gene 9 encodes the expression: Gene 10 indicates the operation − on the operands located at positions 7 and 8 of the chromosome. Therefore, gene 10 encodes the expression: Gene 11 indicates the operation + on the operands located at positions 1 and 9 of the chromosome. Therefore, this gene encodes the expression: There is neither practical nor theoretical evidence that one of these genes is better than the others. Moreover, Wolpert and McReady  BIB001 proved that we cannot use the behavior of the search algorithm up to a certain moment for a particular test function in order to predict its future behavior on that function. This is why each MEP chromosome allows any gene to provide the output of the chromosome. The value of these expressions may be computed by reading the chromosome top-down. Partial results are computed by Dynamic Programming  and are stored in a conventional manner. The chromosome fitness is usually defined as the fitness of the best expression encoded by that chromosome. For instance, if we want to solve symbolic regression problems, the fitness of each sub-expression E i may be computed using the formula: where o k i is the result obtained by the expression E i for the fitness case k and f k is the targeted result for the fitness case k. In this case the fitness needs to be minimized. The fitness of an individual is set to be equal to the lowest fitness of the expressions encoded in the chromosome: