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 보다 더 빠르며 안정적인 보행 자세를 몇가지 얻어낼 수 있었다.

[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.

(*) 위의 그림들은 논문에 사용될 그림이기 때문에, 만약 사용하신다면 반드시 코멘트를 남겨 주셔야합니다.

Posted by SHHyun

Automatically Defined Functions(ADFs)?


J. R. Koza 의 94년에 발간된 Genetic Programming II 에 보면 나오는 용어입니다. 말 그대로 풀이하면 자동적으로 정의된 함수들 쯤 될꺼 같습니다. 그 책의 내용에 따르면 이 기법을 사용하게 되면 트리 안에서 어떤 강제적인 흐름을 가지는 구조물을 위치시키게 되고, 이 구조물은 트리 안에서 반복적으로 사용될 수 있게 된다고 하고 있습니다.


GP 는 터미널 노드와 함수 노드를 사용하여 일정한 흐름의 프로그램을 만들어내죠. 이 ADFs 라는 녀석은 그 일정한 흐름의 프로그램들의 한 부분을 ADFs 라는 하나의 구조물안에 가두어서 반복적으로 사용할 수 있는 효과를 가지게 됩니다. 한마디로 어떤 구조가 반복적으로 사용되어 해결하기 좋은 문제일 경우에는 이를 사용할 경우에 톡톡한 효과를 볼 수 있다는 뭐 그런 말입니다.


GP 를 처음 접할 때 ADFs 라는 용어를 듣고, 그 녀석을 접하는 순간, 어떤 문제든 다 갖다 붙이고 싶은 욕구가 마구마구 싹텄었던 기억이 나는군요. 근데 사실 이녀석은 생각보다 널리 쓰기가 어려운 녀석입니다. 특정 몇몇 문제가 아니라면, 사용하는 자체가 오히려 전체적인 구조를 변화하지 못하게 만드는 주요 요인중에 하나가 됩니다.


예를들면, 어떤 회귀문제(어떤 특정 주어진 몇개의 점을 모두 지나가는 함수를 만드는 그런종류의 문제들)에 ADFs 를 사용한다고 생각해 봅시다. 우리가 일반적으로 생각하는 수식들에서 특정 구조가 지속적으로 반복되는 수식이 과연 얼마나 있을까요? ADFs 는 이런 문제의 경우에는 해당 문제를 오히려 특정 구조가 반복되게 만들 수도 있기 때문에 가급적 피하는것이 좋을 수 있습니다.


그러나 회로를 설계하는 문제를 생각해보면 달라집니다. 만약에 어떤 회로에 특정 필터를 사용하는 부분이 반복적으로 나타나야 한다면? ADFs 가 이 필터의 구조를 가지고 있다면, 지속적으로 특정 필터를 사용하는 그런 효과를 낼 수 있겠지요? 하지만 역시 이것도 현실적으로 잘 생각해보시면, 사람이 ADFs 가 아닌 DFs 로 정의해 놓지 않는한 과연 이것을 필터로 인식하고 지속적으로 사용할 것인가는 쉽게 결론이 나오지 않는 문제가 됩니다. 그러나 엄청난 컴퓨팅파워를 갖추고 있다면, 말도 안되는 군집크기와 진화 세대의 반복을 통해 아마도 좋은 결과를 얻어낼 수도 있지 않을지 생각해봅니다.


또한, 네트워크의 다중입출력 관계에 대한 어떤 구조설계를 한다고 할 경우에도 ADFs 를 사용할 수 있습니다. 기본적으로 GP 는 하나의 출력을 가집니다. 루트노드가 곧 출력이 되는 것이지요. 그리고 노드에 대한 다중상속구조를 지원하지 않습니다. 이런 것을 토대로 볼 때, 이를 해결하는 가장 쉬운 방법은 다중의 트리를 사용하고 모든 트리들은 같은 ADFs 를 공유하는 것 입니다. 이렇게 하면 만약 루트 노드 바로 아래에 ADFs 가 위치한다면 서로 특정 같은 구조의 노드들을 가지게 되는 것이므로 다중상속구조를 살짝이나마 가질 수 있는 것이지요.


ADFs 라는 것은 이렇듯 GP 에서 해결해야할 문제에 특화된 어떤 하나의 기술요소입니다. 문제에 따라서 문제 자체를 좀 더 용이하게 해결해 줄 수 있는 방법입니다. 그러나 역시 모든 기술요소가 그렇듯 장점만을 가지고 있는 것은 아니기에 조심스럽게 지금의 문제가 이 기술을 적용하기가 적합한지 아닌지에 대해 잘 고려해봐야할 필요가 있습니다.

Posted by SHHyun

Homologous CX 연산자는 기본적으로 동일 구조를 가진 서브트리들 간의 교환만 허용하는 연산자 입니다. 즉, 위의 그림에 Tree1 과 Tree 2 에서, 1-1, 2-2, 3-3, 6-4, 7-7 간의 교환만을 허용한다는 이야기 입니다.

이 연산자의 출발점은 생물체의 교배에 있어서 동일 형질의 유전자 만을 교환한다는 것으로 기억하고 있습니다. 예로서 팔의 유전자와 다리의 유전자를 교환해서는 이상형질이 나타날 수 있다는 것을 들 수 있겠습니다.

실제로 몇가지 테스트 문제에 대해 실험해 보면 매우 빠른 속도로 연산이 이루어지고, 코드의 증가 또한 기본 연산자에 비해서 매우 적게 증가하는 것을 확인할 수 있었습니다.

본 소스코드에 어떤 오류가 있을지는 모르겠습니다만, 혹시 참고하실 분은 첨부된 소스를 받으셔서 돌려보시면 되겠습니다.


homologous.c





Posted by SHHyun
유사 - [명사]{주로 일부 명사 앞에 쓰여} 서로 비슷함.

그렇습니다. 유사하다는 말을 서로 비슷하다는 말입니다.
비슷하다? 그럼 비슷하다는 말은?

비슷하다
[형용사]
『(…과)』 {‘…과’가 나타나지 않을 때는 여럿임을 뜻하는 말이 주어로 온다} 두 개의 대상이 크기, 모양, 상태, 성질 따위가 똑같지는 아니하지만 전체적 또는 부분적으로 일치하는 점이 많은 상태에 있다. {명사의 단독형 뒤에 쓰여}
1 정체가 확인되지 아니한 어떤 대상에 대하여 누구 또는 무엇이라고 짐작되는 상태에 있다.
2 비교가 되는 대상과 어느 정도 일치되지만 다소 미흡한 면이 있다.

네 그렇습니다. 크기, 모양, 상태, 성질 따위가 똑같지는 않지만, 전체적 또는 부분 적으로 일치하는 점이 많은 상태에 있다 라고 하고 있습니다.

일반적으로 진화 연산에서 각 개체군의 유사함을 평가하는데에 이용되는 방식은 크게 두가지 방식이라고 할 수 있겠습니다.

그것은 Genotype 과 Phenotype 의 형태에서 유사함을 평가하는 것 입니다.

여기서 Genotype 은 순수한 그 개체 자신을 나타내는 것이고,
Phenotype 은 개체가 어떤 적합도 함수를 거쳐서 결과물로서 나타나는 것을 말합니다.

Phenotype 을 통한 개체의 유사성 분류는 크게 문제될 것이 없습니다. 일반적인 적합도 함수를 이용한다면, 두개 이상의 값이 나타나지 않습니다. (물론 동시진화기법 (Co-evolution) 을 이용할 경우에는 달라질 수 있습니다만, 이것은 특이한 경우로 분류하겠습니다.) 그러므로, 적합도의 값의 차이, 즉, 유클리디안 거리를 통한 유사도 분류가 가능합니다.

Phenotype 을 통한 유사성 분류방식은 초기 진화연산 기법에서 많이 이용된 방식 이었습니다. 하지만 금방 단점이 나타나게 되었죠.

가장큰 단점은 아마도 이것이겠지요.

" 완전 다른 개체일 경우에도 비슷한 개체로 분류될 수 있다. "

그렇습니다. 여러분 께서 만약에 GA의 대표적 벤치마크 문제인 f3deceptive 문제를 접해 보셨다면, 무슨 의미인지 확실하게 이해하실 수 있을 것입니다.
000011000 는 1.8 의 적합도를 가집니다.
111000001 또한 1.8 의 적합도를 가집니다.

과연 위의 두 개체를 비슷한 개체라고 부를 수 있을까요?

이렇듯, 개체의 특성 자체가 반영되지 않은 상태에서 단지 적합도 만을 가지고 유사성을 논하는 것은 매우 큰 오류를 범하는 것을 확인할 수 있습니다.

그래서 많은 학자들이 Genotype 상태에서의 유사성 분류에 대한 기준을 마련하기 시작했습니다.

수많은 유전연산 기법들은 그들만의 표현양식(Representation)에 따라 그 유사성 분류 방식이 다를 수 밖에 없습니다. Bit String 표현 기법을 갖는 GA 의 경우에는 해밍거리 를 통한 측정방식이 있습니다. 각각의 위치한 비트를 비교하여 몇개의 비트가 서로 다른 비트 값을 갖는지를 이용하여 측정하는 방식입니다. Real Number 로 표현되는 GA 나 ES 의 경우에는 각각의 개체에 대해 유클리디언 거리측정을 통하면 그 차이를 측정할 수 있죠.

하지만 GP 의 트리는 아직까지도 확실한 유사성 분류 기준이 없습니다. 트리구조의 유사성을 분류하는 수학적인 기준도 아직까지 없는 것으로 알고 있습니다.

여기서 짚고 넘어가야 할 게 있는데, 왜 유사성을 분류하는 것이 중요한지에 대한 것입니다. 예전에 GA 나 GP 등의 진화연산에서 중요하게 생각하는 문제중의 하나가 조기수렴 문제라고 언급한 적이 있었습니다. 이는 거의 모든 개체가 한 점으로 수렴해 나가는 현상을 말한다고 말씀 드린 적이 있습니다. 이것은 일반적으로 Phenotype 의 관점에서 봤을 때, 한 점으로 수렴하는 현상을 말 합니다. 하지만, Phenotype 의 관점에서는 한점에 수렴 했다 하더라도, Genotype 의 관점에서는 수 많은 곳으로 분포해 있을 수 있는 것입니다. 이 가능성은 개체들을 여러곳으로 분산시킬 수 있는 다른 효과를 기대해 볼 수 있습니다.

즉, 유사성 분류기준, 혹은 유사성 측정에 대한 것은 조기수렴을 현상을 돌파할 수 있는 또다른 가능성을 제시해 줄 수 있다고 생각합니다.

다시 본론으로 돌아가서 트리구조의 유사성 측정에 대해 생각해 보도록 하겠습니다.

과연 우리가 어떨 때 이 트리가 유사하다고 생각할 수 있을까요?

제 생각은 이렇습니다.

1. 트리의 깊이가 비슷하다.
2. 트리의 퍼진 형태가 비슷하다.
3. 트리에 분포되어 있는 함수의 형태가 비슷하다.
4. 마지막으로 트리가 가진 적합도도 비슷하다.

한마디로 이렇습니다. 우리가 트리가 유사하다라고 하는 것은 트리의 겉 모양을 보고 "아 이것은 생긴게 비슷하다." 라고 할 수 있고, "트리를 거쳐 처리된 결과물이 비슷하다" 라고도 할 수 있습니다.

하지만, 이것에는 어느정도 괴리가 있습니다.
저 말들 중에 비슷하다 라는 것을 어떻게 표현할 것인가?

그래서 이런 방식을 제안해 보고자 합니다.
트리의 깊이, 터미널 노드의 개수(트리의 퍼진정도), 트리에 분포되어 있는 함수들
이 세가지 기준에 트리가 가진 적합도까지 추가하여

퍼지를 통한 분류 기법을 이용해보고자 합니다.
아직은 추상적이기 때문에, 조금 더 많이 구체화 시켜야 합니다만,
인간의 주관으로서 비슷하다라고 느끼는 것을 표현할 수 있다면,
그것을 통한 조기 수렴의 극복 및 새로운 연산기법의 적용이 가능 할 것 같습니다.
Posted by SHHyun

 오늘은 간단하게 Genetic Programming(GP) 에 대해서 정리해볼까 합니다.

 GP 라는건 GA 에서 파생되었다고도 할 수 있는 또다른 Evolutionary Computation 의 한 종류 입니다.
 Genetic Algorithm 에서는 유전자 형태를 Binary 또는 Real Type 의 조합을 이용했습니다.
 하지만 Genetic Programming 에서는 유전자 형태를 Tree 구조를 이용합니다.

 그림으로 표현해보면 다음과 같습니다.

사용자 삽입 이미지사용자 삽입 이미지

그림1. GA 와 GP 의 표현의 차이점


 GA 와 GP 는 보시는 것과 같이 표현에 차이를 두고 있습니다. CX나 MUT 역시 존재하지만 표현상의 차이로 인해 조금 다른 방식으로 이루어 집니다. CX 방식의 차이에 대해서 그림으로 표현해보면 다음과 같습니다.

사용자 삽입 이미지사용자 삽입 이미지

그림2. GA 와 GP 의 CX 의 차이점


 GA 와 GP 는 위와같이 표현상의 차이로 인해, 서로 해결하기 좋은 분야도 틀리고, 구현하는 방식도 틀립니다. GP는 쉽게 접하기 어려운 이유가 바로 저 Tree 구조를 이용하기 때문인데, GP 에서 Tree 각각의 노드(Tree의 구성요소 하나하나를 노드라고 합니다.)가 함수 그 자체의 역할을 하기 때문에 구현상 매우 어려움이 따릅니다. 그리고 도식화 시키기도 힘들뿐더러 Tree 를 해석하기 위해서는 Lisp 언어와 같은 표현방식에 익숙해 져야 하는 어려움이 따릅니다.
 
 하지만 GP 는 Genetic Programming 이라는 말과 같이 프로그램이 프로그램을 파생시키고 만들어내는 방식이기때문에 어떤 구조를 최적화 시키는데에 적합합니다. GA 는 각각의 유전자가 수치정보를 가지고 있기때문에 수치최적화에 적합하지만, GP 는 각각의 유전자가 함수형태의 정보도 취할 수 있기때문에 구조최적화에 적합한 것입니다.

 GP로 해결되는 대표적인 예는 다음과 같습니다.
어떤 말도 안되는 형태의 그래프가 주어지고, 이 형태와 가장 유사한 구조를 가지는 함수를 찾아내는 것이지요. Symbolic Regression 이라고 불리는 이 문제는 GP로 해결되는 대표적인 예중에 하나입니다. 그리고 Ant Problem 이라고 하는 문제가 있는데, 개미가 주어진 먹이를 정해진 시간동안 가장 정확하게, 가장 많이 찾아내는 것이 문제인 목표입니다. 그리고 Multiplexer Problem 같은 논리회로의 구조를 찾아내는 문제나, Filter Problem 과 같이 전자회로에서 주어진 입력값과 출력값을 올바르게 표현할 수 있는 아날로그 회로를 찾아내는 문제에도 이용되었습니다.

 GP는 GA 에 비해서 다루기가 많이 힘듭니다. 우선, 기본적으로 프로그래밍에 매우 능숙해야 그 구조나 형태를 파악할 수 있고, GA 나 ES 와 같이 오래된 역사를 갖고 있는 것도 아니기 때문에 GP에 대한 서적도 매우 적은 편입니다. 그래서 GP 에 대한 자료를 한번 이것저것 모아보려고 합니다. GA 와 마찬가지로 제 공부도 하면서 이제까지 아는 것도 정리하는 겸 하나씩 글을 써볼까 합니다.

 P.S. GA 를 0.001 버전을 완성하기는 했습니다만, SGA에 비해서 큰 차이를 보이지 못하기에 아직 웹상에 공개하기는 조금 그렇네요 ^^ HFC 알고리즘에 대한 구현을 마치게 되면 Rosenbrock 이나 Griewangk 같은 벤치마크 문제와 함께 제 블로그에서 공개할 예정입니다.
Posted by SHHyun