computer science

Multi expression programming

Multi expression programming is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Multi expression programming rather than just read about it. In short: Multi Expression Programming (MEP) 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.

Key takeaways

Multi expression programming belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Multi expression programming to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Multi expression programming from memory before moving on to harder problems.

Reference excerpt

Multi Expression Programming (MEP) 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 (multiple representations have been tested). 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 (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 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.

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 symbolic regression, statistical classification and time-series problems. User interface is created with wxWidgets.

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 Symbolic Regression Artificial intelligence Genetic programming Cartesian genetic programming Gene expression programming Grammatical evolution Linear genetic programming

Notes

External links Multi Expression Programming website Multi Expression Programming source code

Illustrations

Worked examples

Example 1 — a first encounter with Multi expression programming

Start with the simplest possible case. Write down what Multi expression programming claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Multi expression programming before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Multi expression programming ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Multi expression programming

In research: Multi expression programming appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Multi expression programming in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Multi expression programming is common in secondary-school and first-year university syllabi. It links to neighbouring topics Genetic programming, Machine learning algorithms, Regression and curve fitting software, so understanding it makes those chapters shorter.
In everyday life: Look for Multi expression programming outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Multi expression programming in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Multi expression programming means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Multi expression programming out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Multi expression programming in simple terms?

Why does Multi expression programming matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Multi expression programming?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Multi expression programming.