📂최적화이론

다중 표현 계획법 MEP

정의 ¹

유전 알고리즘의 변형으로써, 회귀문제를 염색체의 선형결합으로써 표현하고 푸는 기법을 다중 표현 계획법^{MEP, Multiple Expression Programming}이라 한다.

MEP의 구성요소는 함수의 집합 $F$ 와 변수의 역할을 할 터미널^terminal의 집합 $T$, 그리고 이 둘의 조합으로써 나타나는 염색체의 집합 $C$ 로 이루어진다. 염색체의 길이, 즉 유전자^gene의 수를 $n$ 이라고 할 때, 하나의 염색체 $\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) $$

문제는 이 목적 함수를 최소화하기 위해서 경사하강법 같은 걸 쓰기는 곤란하다는 건데, 여러 정의가 이미 암시하듯이 유전 알고리즘으로 구현하는 것은 별로 어렵지 않다.