📂Optimization

Multiple Expression Programming MEP

Definition ¹

As a variation of the genetic algorithm, a technique for solving the regression problem by representing it as a linear combination of chromosomes is called Multiple Expression Programming.

The components of MEP are the set of functions $F$, the set of terminals $T$ that act as variables, and the set of chromosomes $C$ that arise from combinations of these two. Let the chromosome length, i.e., the number of genes, be $n$; then a single chromosome $\mathbf{c}$ has $n$ expressions as shown in $E_{1} , \cdots , E_{n}$. A gene belongs to either a terminal or a function, and

Explanation

Because MEP involves many rather complex ideas, it is easier to understand by example.

Chromosomes and expressions

$$ f(x,y,z) = x^{2} - 2 \sqrt{ y z } $$ Suppose the function we seek is $f : \mathbb{R}^{3} \to \mathbb{R}$ as above, and although the function is unknown, values $f$ corresponding to $x,y,z$ are given as data. In this case, $F$ and $T$ are chosen as follows. $$ F = \left\{ + , - , \cdot , /, \sqrt{ \cdot } \right\} , \quad T = \left\{ x , y , z \right\} $$ Let the function approximating $f$ be $\hat{f}$; then a chromosome $\mathbf{c} = \left( c_{1} , \cdots , c_{n} \right)$ that perfectly describes $\hat{f}$ can be represented as follows. $$ \begin{align*} c_{1} = x & \implies E_{1} = x \\ c_{2} = (\cdot , 1 , 1) & \implies E_{2} = c_{1} \cdot c_{1} = x^{2} \\ c_{3} = y & \implies E_{3} = y \\ c_{4} = z & \implies E_{4} = z \\ c_{5} = (\cdot , 3 , 4) & \implies E_{5} = c_{3} \cdot c_{4} = y z \\ c_{6} = (\sqrt{ \cdot } , 5) & \implies E_{6} = \sqrt{ c_{5} } = \sqrt{ y z } \\ c_{7} = (- , 2 , 6) & \implies E_{7} = c_{2} - c_{6} = x^{2} - \sqrt{ y z } \\ c_{8} = ( - , 7 , 6 ) & \implies E_{8} = c_{7} - c_{6} = x^{2} - 2 \sqrt{ y z } \end{align*} $$ As mentioned in the definition, a gene is either a function or a variable, and if $c_{i}$ is a function, it is determined by taking as arguments the genes $c_{j}$ corresponding to $j < i$, depending on the type of operation.

• $c_{6}$: The number of arguments may freely vary depending on which function it is.
• $c_{8}$: Repeated operations naturally serve the role of estimating coefficients.

Objective function

Suppose the dataset is given as $\left\{ \mathbf{x}_{k} , y_{k} \right\}_{k=1}^{N}$. An expression $E$ itself becomes the function approximation $\hat{f}$, and the objective function $L$ of expression $E = \hat{f}$ can be defined as follows. $$ L ( E ) = \sum_{k=1}^{N} \left| \hat{f} ( \mathbf{x}_{k} ) - y_{k} \right| $$

The $L$ of a chromosome is, of course, the minimum among the expressions contained in that chromosome. $$ L ( \mathbf{c} ) = \min_{ i } L \left( E_{i} \right) $$

The problem is that it is difficult to use methods like gradient descent to minimize this objective function; however, as several definitions have already hinted, implementing it with a genetic algorithm is not particularly difficult.