Multi expression programming
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
Multi Expression Programming (MEP) is an evolutionary algorithm for generating mathematical functions describing a given set of data. MEP is a
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 (given as instruction's addresses) are also present.
Example of MEP program
Here is a simple MEP chromosome (labels on the left side are not a part of the 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 (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 of symbolic regression, the fitness is the sum of differences (in absolute value) between the expected output (called target) 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 (which has the lowest error) will represent the chromosome. This is different from other GP techniques: In
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.
Software
MEPX
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 solving
libmep
Libmep is a free and open source library implementing Multi Expression Programming technique. It is written in C++.
hmep
hmep is a new open source library implementing Multi Expression Programming technique in Haskell programming language.
See also
- Genetic programming
- Cartesian genetic programming
- Gene expression programming
- Grammatical evolution
- Linear genetic programming
Notes
- ^ Oltean M.; Dumitrescu D.: "Multi Expression Programming", Technical report, Univ. Babes-Bolyai, Cluj-Napoca, 2002
- ^ Oltean M.; Grosan C.: "Evolving Evolutionary Algorithms using Multi Expression Programming", The 7th European Conference on Artificial Life, September 14–17, 2003, Dortmund, Edited by W. Banzhaf (et al), LNAI 2801, pp. 651-658, Springer-Verlag, Berlin, 2003
- ^ Oltean M.; Grosan C.: "Evolving Digital Circuits using Multi Expression Programming", NASA/DoD Conference on Evolvable Hardware, 24–26 June, Seattle, Edited by R. Zebulum (et al.), pages 87-90, IEEE Press, NJ, 2004