📂最適化理論

多重表現プログラミング MEP

定義 ¹

遺伝的アルゴリズムの変形として、回帰問題を染色体の線形結合として表現して解く手法を 多重表現プログラミング^{MEP, Multiple Expression Programming}という。

MEPの構成要素は関数の集合 $F$ と変数の役割を果たすターミナル^terminalの集合 $T$、そしてこれらの組合せとして現れる染色体の集合 $C$ で構成される。染色体の長さ、すなわち遺伝子^geneの数を $n$ とすると、1つの染色体 $\mathbf{c}$ は $E_{1} , \cdots , E_{n}$ のように $n$ 個の表現式^expressionを持つ。遺伝子はターミナルか関数のいずれかに属し、

説明

MEPはかなり複雑なアイデアが多く絡んでいるため、例で見るのが理解しやすい。

染色体と表現式

$$ f(x,y,z) = x^{2} - 2 \sqrt{ y z } $$ 例えば、我々が求める関数が上のような $f : \mathbb{R}^{3} \to \mathbb{R}$ だとし、関数は不明だが $x,y,z$ に従う $f$ の値がデータとして与えられているとする。このとき $F$ と $T$ は次のようにとる。 $$ F = \left\{ + , - , \cdot , /, \sqrt{ \cdot } \right\} , \quad T = \left\{ x , y , z \right\} $$ $f$ を近似する関数を $\hat{f}$ とすると、$f$ を完全に説明する $\hat{f}$ の染色体 $\mathbf{c} = \left( c_{1} , \cdots , c_{n} \right)$ は次のように表せる。 $$ \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*} $$ 定義で述べたように、遺伝子は関数か変数のどちらかであり、$c_{i}$ が関数である場合は演算の種類に応じて $j < i$ に相当する遺伝子 $c_{j}$ たちを引数^argumentとして取る形で決定される。

• $c_{6}$: 引数の数は関数が何であるかに応じて自由に変わり得る。
• $c_{8}$: 繰り返し演算は自然に係数を推定する役割につながる。

目的関数

データセットが $\left\{ \mathbf{x}_{k} , y_{k} \right\}_{k=1}^{N}$ のように与えられているとする。表現式 $E$ はそれ自体で関数近似 $\hat{f}$ となり、表現式 $E = \hat{f}$ の目的関数 $L$ は次のように定義できる。 $$ L ( E ) = \sum_{k=1}^{N} \left| \hat{f} ( \mathbf{x}_{k} ) - y_{k} \right| $$

染色体の $L$ は当然ながら、その染色体が持つ表現式の中で最小値となる。 $$ L ( \mathbf{c} ) = \min_{ i } L \left( E_{i} \right) $$

問題はこの目的関数を最小化するために勾配降下法のようなものを使うのは難しいということで、いくつかの定義がすでに示唆するように、遺伝的アルゴリズムで実装するのはさほど難しくない。