Multi expression programming
Multi Expression Programming is an evolutionary algorithm for generating mathematical functions describing a given set of data. MEP is a Genetic Programming variant encoding multiple solutions in the same chromosome. MEP representation is not specific. In the simplest variant, MEP chromosomes are linear strings of instructions. This representation was inspired by Three-address code. MEP strength consists in the ability to encode multiple solutions, of a problem, in the same chromosome. In this way, one can explore larger zones of the search space. For most of the problems this advantage comes with no running-time penalty compared with genetic programming variants encoding a single solution in a chromosome.
Representation
MEP chromosomes are arrays of instructions represented in Three-address code format.Each instruction contains a variable, a constant, or a function. If the instruction is a function, then the arguments are also present.
Example of MEP program
Here is a simple MEP chromosome :
1: a
2: b
3: + 1, 2
4: c
5: d
6: + 4, 5
7: * 3, 5
Fitness computation
When the chromosome is evaluated it is unclear which instruction will provide the output of the program. In many cases, a set of programs is obtained, some of them being completely unrelated.For the above chromosome, here is the list of possible programs obtained during decoding:
E1 = a,
E2 = b,
E4 = c,
E5 = d,
E3 = a + b.
E6 = c + d.
E7 = * d.
Each instruction is evaluated as a possible output of the program.
The fitness is computed in a standard manner. For instance, in the case of symbolic regression, the fitness is the sum of differences between the expected output and the actual output.
Fitness assignment process
Which expression will represent the chromosome? Which one will give the fitness of the chromosome?In MEP, the best of them will represent the chromosome. This is different from other GP techniques: In Linear genetic programming the last instruction will give the output. In Cartesian Genetic Programming the gene providing the output is evolved like all other genes.
Note that, for many problems, this evaluation has the same complexity as in the case of encoding a single solution in each chromosome. Thus, there is no penalty in running time compared to other techniques.