Multi expression programming

<h2 id="representation">Representation</h2>
<p>MEP chromosomes are arrays of instructions represented in <a href="/facts/Three-address_code/q8Loz34Y">Three-address code</a> format.
</p><p>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.
</p>
<h3>Example of MEP program</h3>
<p>Here is a simple MEP chromosome (labels on the left side are not a part of the chromosome):
</p>
1: a
2: b
3: + 1, 2
4: c
5: d
6: + 4, 5
7: * 3, 5

<h2 id="fitness-computation">Fitness computation</h2>
<p>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).
</p><p>For the above chromosome, here is the list of possible programs obtained during decoding:
</p>
E1 = a,
E2 = b,
E4 = c,
E5 = d,
E3 = a + b.
E6 = c + d.
E7 = (a + b) * d.

<p>Each instruction is evaluated as a possible output of the program.
</p><p>The fitness (or error) is computed in a standard manner. For instance, in the case of <a href="/facts/Symbolic_regression/kUFNHUfB">symbolic regression</a>, the fitness is the sum of differences (in absolute value) between the expected output (called target) and the actual output.
</p>
<h2 id="fitness-assignment-process">Fitness assignment process</h2>
<p>Which expression will represent the chromosome? Which one will give the fitness of the chromosome?
</p><p>In MEP, the best of them (which has the lowest error) will represent the chromosome. This is different from other GP techniques: In <a href="/facts/Linear_genetic_programming/tTo1ueAN">Linear genetic programming</a> the last instruction will give the output. In <a href="/facts/Cartesian_Genetic_Programming/TxomAlQw">Cartesian Genetic Programming</a> the gene providing the output is evolved like all other genes.
</p><p>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.
</p>
<h2 id="software">Software</h2>
<h3>MEPX</h3>
<p>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 <a href="/facts/Symbolic_regression/kUFNHUfB">symbolic regression</a>, <a href="/facts/Statistical_classification/jXXHRkXR">statistical classification</a> and <a href="/facts/Time-series/fSXPR817">time-series</a> problems.
</p>
<h3>libmep</h3>
<p><a href="https://www.github.com/mepx">Libmep</a> is a free and open source library implementing Multi Expression Programming technique. It is written in C++.
</p>
<h3>hmep</h3>
<p><a href="http://hackage.haskell.org/package/hmep">hmep</a> is a new open source library implementing Multi Expression Programming technique in Haskell programming language.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Genetic_programming/kGa2jr0w">Genetic programming</a></li>
<li><a href="/facts/Cartesian_genetic_programming/TxomAlQw">Cartesian genetic programming</a></li>
<li><a href="/facts/Gene_expression_programming/jPvNjy6N">Gene expression programming</a></li>
<li><a href="/facts/Grammatical_evolution/g2aLEkmb">Grammatical evolution</a></li>
<li><a href="/facts/Linear_genetic_programming/tTo1ueAN">Linear genetic programming</a></li></ul>
<h2 id="notes">Notes</h2>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.mepx.org">Multi Expression Programming website</a></li>
<li><a href="https://www.github.com/mepx">Multi Expression Programming source code</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Oltean M.; Dumitrescu D.: "Multi Expression Programming", Technical report, Univ. Babes-Bolyai, Cluj-Napoca, 2002 <a href="https://mepx.github.io/oltean_mep.pdf" target="_blank">https://mepx.github.io/oltean_mep.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>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 <a href="https://mepx.github.io/oltean_ecal2003.pdf" target="_blank">https://mepx.github.io/oltean_ecal2003.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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 <a href="https://mepx.github.io/oltean_eh04.pdf" target="_blank">https://mepx.github.io/oltean_eh04.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Multi expression programming open-in-new

Multi expression programming