CGP는 본래 논리 회로에 대해서 많이 사용되기 때문에, 별 관심이 없다가 최근에 몇가지 가능성을 보고 찾게된 이론이다. Linear GP 나 CGP 등 사실 Tree 기반의 GP 보다 구현이 쉽기 때문에 찾아보게 된 이유도 있다. 우선 기법에 대해 살펴보면 아래와 같다.
기존의 Tree 기반의 Genetic Programming과는 약간 다른 Integer String 으로 개체를 구성한다. 하나의 개체는 아래의 그림과 같이 구성할 수 있는데,
(1) (2) 는 입력을 의미하고, (3) 은 해당 노드의 연산자를 의미한다. 즉, 1, 2 로 부터의 입력을 3 의 처리를 거쳐 output 1 을 만들어내는 식인데, 이때 CGP 에서 출력은 사용자가 지정하는 것이 아니라 자동으로 지정되는 형태를 갖는다. 이는 CGP 가 Feedforward 형태의 흐름을 갖기 때문이며, Feedback 에 의한 루프 구성을 막기 위함이기도 하다. 만약 루프가 구성될 경우, 조건의 역할을 하는 함수가 아닐 경우, 이를 빠져나갈 방법이 묘연하여 무한 루프에 빠지게될 수 있고, 일정 횟수를 반복시킨다고 할 경우에 발생하는 효과는 오히려 루프를 이용하지 않는 것 보다 못할 수 있다.
그리고 이러한 형태의 블록이 여러개가 다중으로 연결될 수 있으며, 아래와 같이 구성될 수 있다.
이와 같이 여러개의 블럭을 사용하여 프로그램을 구성할 수 있으며, 점선으로 표시한 부분과 같이 연결이 이어지지 않는 부분도 발생할 수 있다. 이는 자동으로 할당된 출력이 다음 블럭의 어떠한 부분에도 연결되지 않는 경우 발생한다. 그리고 CGP 는 기존 트리기반의 GP 와 달리 항상 고정된 행과 열의 크기 만큼의 프로그램을 가지고 있는데, 초기에는 거의 모든 노드들이 연결된다. 그러나 시간이 지나면 지날 수록 이와 같은 연결되지 않는 부분이 발생하고, 이러한 작용에 의해 일종의 잉여 혹은 중복 공간(Redundancy)의 제거 효과가 나타날 수 있다.
CGP 는 위와 같은 다중의 형태로 인해 기존 GP와는 달리 단일 표현의 개체를 통해 다중의 출력을 얻어낼 수 있는데, 내가 이를 활용하게 된 이유는 바로 이것 때문이다. 기존의 로봇 게이트 진화에 사용했던 다중트리(Multi-tree) 기법은 서로 각각의 트리가 어떠한 관계도 없이 진화한다. 그러나 CGP 에서는 은연중에 서로간의 연결이 공유될 수 있기 때문에 완벽하게 독립된 형태가 아닌 어느정도 의존성을 갖는 형태로 진화하게 된다. 그러므로 각각의 관절의 움직임에 대해 기존의 GP 보다 효율적이며 유기적인 움직임을 보여줄 수 있을 거라고 기대할 수 있다.
물론 멀티트리를 사용할 경우에도 이에 추가적으로 ADF(Automatic Defined Functions)를 적용할 경우, 비슷한 효과를 낼 수 있지만, ADF의 개수나 크기에 대한 정의를 어떻게 할 지가 큰 문제가 될 수 있다. 이 경우 크기와 개수가 커질 경우, 해공간의 크기가 매우 크게 확장될 수 있고, Koza 외의 다른 사람들이 ADF 를 잘 적용하지 않는 데에는 그만한 이유가 있다고 생각해볼 수 있다.
그러나 CGP에도 단점은 있는데, 일반적인 GP에서는 ERC(Ephemeral Random Constants)라 하여 임의의 상수값이 트리의 어느 부분에나 적용될 수 있지만, CGP 에서는 그럴 수 없다. 제한된 입력값을 사용하기 때문에 발생할 수 있으며, 이 부분이 극복되지 않는 한 아래의 논문[1]에서도 언급한 것과 같이 Symbolic Regression 문제에 대해 완벽하게 적용되긴 어려울 것이다.
그럼에도 CGP 는 하나의 표현으로 다중의 출력을 낼 수 있다는 면에서 충분히 매력적이다. 시뮬레이션 로봇 모델을 통해 실험을 하고 있으며, 기존의 GP 보다 더 빠르며 안정적인 보행 자세를 몇가지 얻어낼 수 있었다.
기존의 Tree 기반의 Genetic Programming과는 약간 다른 Integer String 으로 개체를 구성한다. 하나의 개체는 아래의 그림과 같이 구성할 수 있는데,
(1) (2) 는 입력을 의미하고, (3) 은 해당 노드의 연산자를 의미한다. 즉, 1, 2 로 부터의 입력을 3 의 처리를 거쳐 output 1 을 만들어내는 식인데, 이때 CGP 에서 출력은 사용자가 지정하는 것이 아니라 자동으로 지정되는 형태를 갖는다. 이는 CGP 가 Feedforward 형태의 흐름을 갖기 때문이며, Feedback 에 의한 루프 구성을 막기 위함이기도 하다. 만약 루프가 구성될 경우, 조건의 역할을 하는 함수가 아닐 경우, 이를 빠져나갈 방법이 묘연하여 무한 루프에 빠지게될 수 있고, 일정 횟수를 반복시킨다고 할 경우에 발생하는 효과는 오히려 루프를 이용하지 않는 것 보다 못할 수 있다.
그리고 이러한 형태의 블록이 여러개가 다중으로 연결될 수 있으며, 아래와 같이 구성될 수 있다.
이와 같이 여러개의 블럭을 사용하여 프로그램을 구성할 수 있으며, 점선으로 표시한 부분과 같이 연결이 이어지지 않는 부분도 발생할 수 있다. 이는 자동으로 할당된 출력이 다음 블럭의 어떠한 부분에도 연결되지 않는 경우 발생한다. 그리고 CGP 는 기존 트리기반의 GP 와 달리 항상 고정된 행과 열의 크기 만큼의 프로그램을 가지고 있는데, 초기에는 거의 모든 노드들이 연결된다. 그러나 시간이 지나면 지날 수록 이와 같은 연결되지 않는 부분이 발생하고, 이러한 작용에 의해 일종의 잉여 혹은 중복 공간(Redundancy)의 제거 효과가 나타날 수 있다.
CGP 는 위와 같은 다중의 형태로 인해 기존 GP와는 달리 단일 표현의 개체를 통해 다중의 출력을 얻어낼 수 있는데, 내가 이를 활용하게 된 이유는 바로 이것 때문이다. 기존의 로봇 게이트 진화에 사용했던 다중트리(Multi-tree) 기법은 서로 각각의 트리가 어떠한 관계도 없이 진화한다. 그러나 CGP 에서는 은연중에 서로간의 연결이 공유될 수 있기 때문에 완벽하게 독립된 형태가 아닌 어느정도 의존성을 갖는 형태로 진화하게 된다. 그러므로 각각의 관절의 움직임에 대해 기존의 GP 보다 효율적이며 유기적인 움직임을 보여줄 수 있을 거라고 기대할 수 있다.
물론 멀티트리를 사용할 경우에도 이에 추가적으로 ADF(Automatic Defined Functions)를 적용할 경우, 비슷한 효과를 낼 수 있지만, ADF의 개수나 크기에 대한 정의를 어떻게 할 지가 큰 문제가 될 수 있다. 이 경우 크기와 개수가 커질 경우, 해공간의 크기가 매우 크게 확장될 수 있고, Koza 외의 다른 사람들이 ADF 를 잘 적용하지 않는 데에는 그만한 이유가 있다고 생각해볼 수 있다.
그러나 CGP에도 단점은 있는데, 일반적인 GP에서는 ERC(Ephemeral Random Constants)라 하여 임의의 상수값이 트리의 어느 부분에나 적용될 수 있지만, CGP 에서는 그럴 수 없다. 제한된 입력값을 사용하기 때문에 발생할 수 있으며, 이 부분이 극복되지 않는 한 아래의 논문[1]에서도 언급한 것과 같이 Symbolic Regression 문제에 대해 완벽하게 적용되긴 어려울 것이다.
그럼에도 CGP 는 하나의 표현으로 다중의 출력을 낼 수 있다는 면에서 충분히 매력적이다. 시뮬레이션 로봇 모델을 통해 실험을 하고 있으며, 기존의 GP 보다 더 빠르며 안정적인 보행 자세를 몇가지 얻어낼 수 있었다.
[1] Miller J. F, Thomson P., Cartesian Genetic Programming, In Proceedings of the 3rd European Conference on Genetic Programming, Springer, LNCS 1802, 2000, 121-132.
(*) 위의 그림들은 논문에 사용될 그림이기 때문에, 만약 사용하신다면 반드시 코멘트를 남겨 주셔야합니다.