| Part ofa series on the |
| Evolutionary algorithm |
|---|
 |
| Genetic algorithm (GA) |
| Genetic programming (GP) |
| Differential evolution |
| Evolution strategy |
| Evolutionary programming |
| Related topics |
 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Multi Expression Programming (MEP) is an evolutionary algorithm for generating mathematical functions describing a given set of data. MEP is aGenetic Programming variant encoding multiple solutions in the same chromosome. MEP representation is not specific (multiple representations have been tested). In the simplest variant, MEP chromosomes are linear strings of instructions. This representation was inspired byThree-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 withgenetic programming variants encoding a single solution in a chromosome.[1][2][3]
MEP chromosomes are arrays of instructions represented inThree-address code format.
Each instruction contains a variable, a constant, or a function. If the instruction is a function, then the arguments (given as instruction's addresses) are also present.
Here is a simple MEP chromosome (labels on the left side are not a part of the chromosome):
1: a2: b3: + 1, 24: c5: d6: + 4, 57: * 3, 5
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 (they do not have common instructions).
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 = (a + b) * d.
Each instruction is evaluated as a possible output of the program.
The fitness (or error) is computed in a standard manner. For instance, in the case ofsymbolic regression, the fitness is the sum of differences (in absolute value) between the expected output (called target) and the actual output.
Which expression will represent the chromosome? Which one will give the fitness of the chromosome?
In MEP, the best of them (which has the lowest error) will represent the chromosome. This is different from other GP techniques: InLinear genetic programming the last instruction will give the output. InCartesian 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.
MEPX is a cross-platform (Windows, macOS, and Linux Ubuntu) free software for the automatic generation of computer programs. It can be used for data analysis, particularly for solvingsymbolic regression,statistical classification andtime-series problems.
Libmep is a free and open source library implementing Multi Expression Programming technique. It is written in C++.
hmep is a new open source library implementing Multi Expression Programming technique in Haskell programming language.
